2.5. Приклади застосування алгоритму Гоморі Приклад 5. Max ; (25)

^; (26)

^; (27)

^; (28)

^- цілі. (29)

Зведемо задачу до канонічної форми:

max ; (25а)

^; (26а)

^; (27а)

^; (28а)

^- цілі. (29а)

Розглянемо початкову симплекс-таблицю послабленної задачі (25а) - (28а) :

Таблиця 11

Базисні змінні					Розв’язок
Z	0	-1	0	0	0
	3	2	1	0	6
	-3	2	0	1	0

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

Таблиця 12

Базисні змінні					Розв’язок
Z	0	0
	1	0			1
	0	1

Через те, що отриманий розв’язок не є цілочисловим, слід поширити дану задачу шляхом введення відсікання. У даному випадку -рядкок співпадає з -рядком, значить, відсікання, побудуване за -рядком співпаде з відсіканням за -рядком і тому немає сенсу говорити про більш ефективне рівняння-відсікання.

Отже, породжуюче рівняння має такий вигляд:

.

Виділимо цілі і дробові частини коефіцієнтів:

.

Сформуємо за цим обмеженням рівняння-відсікання Гоморі:

(30)

І введемо його в оптимальну симплекс-таблицю послабленої задачі (табл. 13).

Таблиця 13

Базисні змінні						Розв’язок
Z	0	0			0
	1	0			0	1
	0	1			0
	0	0			1

Застосувавши двоїстий симплекс-метод, отримуємо оптимальне розв’язок задачі (25а) - (28а), (30) (табл. 14)

Таблиця 14

Базисні змінні						Розв’язок
Z	0	0	0	0	1	1
	1	0	0
	0	1	0	0	1	1
	0	0	1	1	-4	2

Розв’язок знову не задовольняє обмеження цілочисельності (29). Тому продовжимо процес побудови відсікань за допомогою алгоритму Гоморі. У поточному розв’язку тільки змінна не ціла. За таблицею 14 - рядок має вигляд:

.

Виділимо цілі і дробові частини коефіцієнтів:

.

Відсікання, побудоване за цим обмеженням, має вигляд:

.

Додамо його до останньої симплекс-таблиці та знову застосуємо двоїстий симплекс- метод (табл. 15).

Таблиця 15

Базисні змінні														Розв’язок
Z		0		0		0		0		1		0		1
		1		0		0						0
		0		1		0		0		1		0		1
		0		0		1		1		-4		0		2
		0		0		0						1
Z	0		0		0		0		1		0		1
	1		0		0		0		1				1
	0		1		0		0		1		0		1
	0		0		1		0		-5				1
	0		0		0		1		1				1

Отримали оптимальний розв’язок початкової задачі: z=1, x₁=1, x₂=1.

А тепер переконаємося в тому, що розглянуті вище відсікання виключають деякі області многокутника допустимих розв’язків послабленої задачі, але не виключають жодного допустимого цілочислового розв’язку.

1. Перше рівняння-відсікання має вигляд: .

З рівнянь (26а) и (27а) виразимо залишкові змінні x₃ і x₄ через x₁ та x₂ :

,

,

та підставимо їх у перше рівняння-відсікання_.

.

Після зведення подібних отримаємо:

або (рис. 10).

Р ис.10. Графічна ілюстрація процесу розв’язання ЗЦЛП з прикладу 5

2. Друге рівняння-відсікання має вигляд:

.

З першого рівняння-відсікання виразимо змінну s₁ через x₃ та x₄ :

.

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

;

.

В останню рівність підставимо вираз для залишкових змінних x₃ і x₄ (отримані з рівнянь (26а) и (27а) ), після зведення подібних отримаємо:

або .

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

Приклад 6. Розв’язати ЗЦЛП.

z = 2x1 + 3x2 ; (31)

12x1 – 4x2  3 ; (32)

12x1 + 4x2  9 ; (33)

x1 , x2  0 ; (34)

x1 , x2 - цілі. (35)

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

Таблиця 16

Базисні змінні					Розв’я-зок
Z	0	0
	1	0
	0	1

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

Правило 1. Отсечение ( ) более эффективно, чем отсечение ( ), если причем, по крайней мере, в одном случае выполняется строгое неравенство.

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

(відсікання за -рядком),

(відсікання за -рядком),

(відсікання за -рядком).

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

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

,

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

Таблиця 17

Базисні змінні							Розв’язок
Z	0		0			0
	1		0			0
	0		1			0
	0		0			1
Z	0	0		0
	1	0		0
	0	1		0	0	1	0
	0	0		1	1	-8	6

x₁ - рядок породжує відсікання: . Додамо його до останньої симплекс-таблиці. (табл. 18).

Таблиця 18

Базисні змінні							Розв’язок
Z	0	0	0			0
	1	0	0			0
	0	1	0	0	1	0	0
	0	0	1	1	-8	0	6
	0	0	0			1

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

Таблиця 19

Базисні змінні							Розв’язок
z	0	0	0	0	1	2	0
	1	0	0	0	-1	1	0
	0	1	0	0	1	0	0
	0	0	1	0	-16	12	-3
	0	0	0	1	8	-12	9

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

Таблиця 20

Базисні змінні							Розв’ язок
z	0	0		0	0
	1	0		0	0
	0	1		0	0
	0	0		0	1
	0	0		1	0	-6

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

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

;

.

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

і .

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

Приклад 7. Мax z=4x₁ + 7x₂ ; (36)

2x₁ + 5x₂  10 ; (37)

3x₁ + 4x₂  12 ; (38)

x₁ ,x₂  0 ; (39)

x₁ ,x₂ - цілі. (40)

Оптимальна симплекс-таблиця послабленої задачі (36) - (40) буде такою:

Таблиця 21

Базисні змінні					Розв’язок
z	0	0
	1	0
	0	1

Розв’ язок послабленної задачі не є цілочисловим. Відсікання, побудовані за -рядком та -рядком співпадають. За правилом 1 відповідне відсікання ефективніше за відсікання за -рядком. Побудуємо відсікання за рядком , що має наступний вигляд:

.

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

.

Таблиця 22

Базисні змінні						Розв’ язок
z	0	0			0
	1	0			0
	0	1			0
	0	0			1
Z	0	0		0
	1	0	-1	0	1	2
	0	1		0
	0	0		1

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

.

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

Таблиця 23

Базисні змінні							Розв’ язок
z	0	0		0		0
	1	0	-1	0	1	0	2
	0	1		0		0
	0	0		1		0
	0	0		0		1

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

Таблиця 24

Базисні змінні							Розв’ язок
z	0	0	0	0	1
	1	0	0	0	2
	0	1	0	0	-1	1	1
	0	0	0	1	-2	1	1
	0	0	1	0	1

У базис увійшла змінна , це означає, що обмеження, яке відповідає -рядку,

є надлишковим. Це означає, що рядок і стовпець, які відповідають цій змінній, можна не розглядати (табл. 25):

Таблиця 25

Базисні змінні						Розв’ язок
z	0	0	0	1
	1	0	0	2
	0	1	0	-1	1	1
	0	0	1	1

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

.

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

Таблиця 26

Базисні змінні							Розв’ язок
Z	0	0	0	1	0	1	16
	1	0	0	2	0	-5	4
	0	1	0	-1	0	3	0
	0	0	1	1	0	-5	2
	0	0	0	0	1	-3	1

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

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