__2014_DvojstvennSM+Gomory_ukr_rus_new

s1 12 14 x3 14 x4 .

і підставимо у друге рівняння-відсікання:

23 x4 23 ( 12 14 x3 14 x4 ) s2 23 ;

16 x3 56 x4 s2 1.

Востанню рівність підставимо вираз для залишкових змінних x3 і x4 (отримані з

рівнянь (26а) и (27а) ), після зведення подібних отримаємо:

Введення цих точок двох обмежень у початкову систему дозволяє отримати нову екстремальну з координатами (1,1), в якій досягається оптимальний розв’язок для початкової цілочислової задачі (див. рис. 10).

двохетапного або М-методу. Оптимальна таблиця послабленої задачі (31)-(34) буде такою:

Таблиця 16

Розв’язок послабленої задачі не є цілочисловим.

Правило 1. Отсечение ( i ) более эффективно, чем отсечение ( k ), если

fi fk ,

fij fkj , j,

31

причем, по крайней мере, в одном случае выполняется строгое неравенство.

За правилом 1, відсікання, побудоване за x2 -рядком більш ефективне, ніж відсікання, побудоване за z -рядком. За цим правилом не можна зробити висновок

щодо ефективності відсікань за рядками змінних x2 та x1 :

247 x3 1124 x4 34 (відсікання за z -рядком),

Отже, зупинимось на x2 -рядку, який має вигляд

x2 18 x3 18 x4 34

і призводить до відсікання

18 x3 18 x4 s1 34 ,

яке додамо до табл. 16 (розв’язання відповідної розширеної ЗЛП двоїстим симплекс-методом показано в табл. 17).

32

x1 - рядок породжує відсікання: 121 x4 23 s1 s2 34 . Додамо його до останньої

симплекс-таблиці. (табл. 18).

Виконавши ітерацію двоїстого симплекс-методу, отримаємо :

Розв’ язок ще не є допустимим, тому виконаємо ще одну ітерацію двоїстого симплекс-методу (результат ітерації – у табл. 20):

Таблиця 20

33

Бачимо, що нульовий та другий рядки містять всі невід’ємні коефіцієнти при від’ємному розв’язку. Це означає, що задача не має цілочислового розв’язку.

Покажемо це графічно (рис. 11).

Перше і друге відсікання мають вигляд:

18 x3 18 x4 s1 43 ;

121 x4 23 s1 s2 34 .

Узмінних x1 і x2 ці обмеження відповідно такі:

34

x1 -рядком та x2 -рядком співпадають. За правилом 1 відповідне відсікання ефективніше за відсікання за z -рядком. Побудуємо відсікання за рядком x2 , що має наступний вигляд:

x2 73 x3 72 x4 76 .

Це призводить до відсікання (табл. 22):

Розв’ язок розширеної задачі не є цілочисловим. x2 -рядок (як і x4 -рядок)

породжує відсікання:

53 x3 53 s1 s2 15 .

Додамо його до останньої симплекс-таблиці :

36

За x3 -рядком побудуємо нове обмеження-відсікання:

13 s2 s3 13 .

Виконавши ітерацію двоїстого симплекс-методу, отримаємо оптимальний розв’ язок вхідної задачі :

Розв’ язок цього прикладу проілюстровано на рис. 12:

38

Рис. 12. Графічна ілюстрація розв’язку прикладу 7

2.6. Вправи

За наступними породжуючими рівняннями побудувати відсікаючі площини за допомогою методу Гоморі.