Решение задач целочис­ленного линейного программирования на ЭВМ, страница 2

┌─────────────────────────────────────────────────────────────────┐

│   ТЕКУЩЕЕ РЕШЕНИЕ МЕТОДА ВЕТВ.и ГРАН.- итерац.: 6  Стр.: 1      │

╞═══════════╤════════╤══════════╦════════╤════════════╤═══════════╡

│ Ниж.гран. │Перемен.│Верх.гран ║Перемен.│  Решение   │Целев.ф-ия.│

╞═══════════╪════════╪══════════╬════════╪════════════╪═══════════╡

│  1       є│  X1    │є 10      ║  X1    │      1.000 │   530.000 │

│  0       є│  X2    │є 10      ║  X2    │      9.333 │   480.000 │

│  0       є│  X3    │є 0       ║  X3    │      0.000 │   360.000 │

│  0       є│  X4    │є 10      ║  X4    │      0.000 │   650.000 │

╞═══════════╧════════╧══════════╩════════╧════════════╧═══════════╡

│            Текущая Ц Ф (Max.) =  5010 є ZL = 5040               │

└─────────────────────────────────────────────────────────────────┘

┌─────────────────────────────────────────────────────────────────┐

│   ТЕКУЩЕЕ РЕШЕНИЕ МЕТОДА ВЕТВ.и ГРАН.- итерац.: 7  Стр.: 1      │

╞═══════════╤════════╤══════════╦════════╤════════════╤═══════════╡

│ Ниж.гран. │Перемен.│Верх.гран ║Перемен.│  Решение   │Целев.ф-ия.│

╞═══════════╪════════╪══════════╬════════╪════════════╪═══════════╡

│  0       є│  X1    │є 0       ║  X1    │      0.000 │   530.000 │

│  0       є│  X2    │є 10      ║  X2    │     10.000 │   480.000 │

│  0       є│  X3    │є 0       ║  X3    │      0.000 │   360.000 │

│  0       є│  X4    │є 10      ║  X4    │      0.333 │   650.000 │

╞═══════════╧════════╧══════════╩════════╧════════════╧═══════════╡

│          Текущая Ц Ф (Max.) =  5016.667 є ZL = 5040             │

└─────────────────────────────────────────────────────────────────┘

┌─────────────────────────────────────────────────────────────────┐

│                   ИТОГОВЫЙ РЕЗУЛЬТАТ для лаба3(16)    Стр. : 1  │

╞═════════╤══════════╤═══════════╦═════════╤══════════╤═══════════╡

│Переменн.│          │Целев.ф-ия.║Переменн.│          │Целев.ф-ия.│

│No. Имена│ Решение  │Коэффициент║No. Имена│ Решение  │Коэффициент│

╞═════════╪══════════╪═══════════╬═════════╪══════════╪═══════════╡

│1   X1   │     0.000│   530.000 ║3   X3   │     2.000│   360.000 │

│2   X2   │     9.000│   480.000 ║4   X4   │     0.000│   650.000 │

╞═════════╧══════════╧═══════════╩═════════╧══════════╧═══════════╡

│      MAX   величина цел.ф-и =  5040  Всего итераций   = 7       │

└─────────────────────────────────────────────────────────────────┘

Построим дерево решений:

Дерево решений

 = 56

Z= 5057,143

 


                                                   

 = 59 + 3 = 62

 

 = 59 + 0 = 59

 

 = 59 + 1 = 60

 

 = 59 + 0 = 59

 
                                                                                   

 


3. Решим исходную задачу методом Гомори, в основу которого положен метод построения дополнительного ограничения; для этого мы сперва введем первоначальные данные в ЗЛП и по полученной симплекс-таблице рассчитаем новое ограничение.

КОНЕЧНАЯ ТАБЛИЦА (Всего итерац.=  2 )

┌─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬──────┐

│     │     │X1   │X2   │X3   │X4   │S1   │     │ B(i) │

│     │     ├─────┼─────┼─────┼─────┼─────┤     │──────│

│Базис│C(j) │530.0│480.0│360.0│650.0│    0│B(i) │A(i,j)│

╞═════╪═════╪═════╪═════╪═════╪═════╪═════╪═════╪══════╡

│X2   │480.0│1.222│1.000│0.778│1.667│0.111│10.56│    0 │

╞═════╧═════╪═════╪═════╪═════╪═════╪═════╪═════╪══════╡

│ C(j)-Z(j) │-56.7│    0│-13.3│ -150│-53.3│ 5067│      │

│   * Big M │    0│    0│    0│    0│    0│    0│      │

└───────────┴─────┴─────┴─────┴─────┴─────┴─────┴──────┘

(Max.) Оптим.величина ЦФ =  5066.667

Т.к. у нас значения переменных имеют дробные части, рассчитаем, чему будет равно новое ограничение. Для этого запишем первоначальное уравнение:

х1 + 1х2 + х3 + 1х4 + х5 = 10

запишем отдельно дробные части:

х1 + х2 + х3 + х4 + х5

Преобразуем данное неравенство: 222 х1 + 778 х3 + 667х4 + 111 х5 560

                                                           2 х1 + 7х3 + 6х4 + х5 5

Теперь преобразуем переменные первоначального уравнения, для того чтобы нам удалось выразить  х5 через эти переменные.

11х1 + 9х2 + 7х3 + 15х4 + х5 = 95

Выразим х5:      х5 = 95 - 11х1 - 9х2 - 7х3 - 15х4 

Подставим полученное значение в неравенство записанное выше и преобразуем его; имеем:  х1 + х2 + х4   10

Полученное новое ограничение заносим в ПЭР  и в режиме «Корректировка» меняем исходные данные. Получаем следующую таблицу:

НАЧАЛЬН.ТАБЛИЦА

+------------------------------------------------------------+

¦     ¦     ¦X1   ¦X2   ¦X3   ¦X4   ¦S1   ¦S2   ¦     ¦ B(i) ¦

¦     ¦     +-----+-----+-----+-----+-----+-----¦     ¦------¦

¦Базис¦C(j) ¦530.0¦480.0¦360.0¦650.0¦    0¦    0¦B(i) ¦A(i,j)¦

¦-----+-----+-----+-----+-----+-----+-----+-----+-----+------¦

¦S1   ¦    0¦11.00¦9.000¦7.000¦15.00¦1.000¦    0¦95.00¦    0 ¦

¦     ¦     ¦     ¦     ¦     ¦     ¦     ¦     ¦     ¦      ¦

¦S2   ¦    0¦6.000¦5.000¦    0¦    0¦    0¦1.000¦41.00¦    0 ¦

¦-----------+-----+-----+-----+-----+-----+-----+-----+------¦

¦ C(j)-Z(j) ¦530.0¦480.0¦360.0¦650.0¦    0¦    0¦    0¦      ¦

¦   * Big M ¦    0¦    0¦    0¦    0¦    0¦    0¦    0¦      ¦

+------------------------------------------------------------+

КОНЕЧНАЯ ТАБЛИЦА (Всего итерац.=  3 )

+------------------------------------------------------------+

¦     ¦     ¦X1   ¦X2   ¦X3   ¦X4   ¦S1   ¦S2   ¦     ¦ B(i) ¦

¦     ¦     +-----+-----+-----+-----+-----+-----¦     ¦------¦

¦Базис¦C(j) ¦530.0¦480.0¦360.0¦650.0¦    0¦    0¦B(i) ¦A(i,j)¦

¦-----+-----+-----+-----+-----+-----+-----+-----+-----+------¦