Решение задач целочис­ленного линейного программирования на ЭВМ, страница 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х₄ + х₅ = 10

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

х₁ + х₂ + х₃ + х₄ + х₅

Преобразуем данное неравенство: 222 х₁ + 778 х₃ + 667х₄ + 111 х₅ 560

                                                           2 х₁ + 7х₃ + 6х₄ + х₅ 5

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

11х₁ + 9х₂ + 7х₃ + 15х₄ + х₅ = 95

Выразим х₅:      х₅ = 95 - 11х₁ - 9х₂ - 7х₃ - 15х₄ 

Подставим полученное значение в неравенство записанное выше и преобразуем его; имеем:  х₁ + х₂ + х₄   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)¦

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