3.3. Умова оптимальності опорного плану

Нехай є заповнена симплекс-таблиця. Сформулюємо умову оптимальності опорного плану.

Якщо в нижньому рядку симплекс-таблиці всі числа, крім, мабуть, самого правого, недодатні, то опорний план, що відповідає цій таблиці, оптимальний.

Для простоти обґрунтуємо справедливість цього твердження на прикладі. Нехай заповнена симплекс-таблиця має вигляд:

Таблиця 3.3.

Б						Q
	1	0	2	-1	3	2
	0	1	2	0	-1	3
f	0	0	-5	-3	-1	6

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

3.4. Умова нерозв'язності злп через необмеженість знизу на опр цільової функції

Якщо для ЗЛП заповнена симплекс-таблиця, то ОПР задачі непорожня, так опорний план, що відповідає симплекс-таблиці, належить ОПР. Однак ЗЛП може бути нерозв'язною через необмеженість знизу на ОПР цільової функції.

Умова нерозв'язності формулюється так.

Якщо симплекс-таблиця містить хоча б один стовпець, відмінний від самого правого, у якого в нижньому рядку знаходиться додатне число, а у всіх інших рядках стовпця - недодатні числа, то ЗЛП нерозв'язна через необмеженість знизу на ОПР цільової функції.

Для обґрунтування знову скористаємося прикладом.

Таблиця 3.4.

Б						Q
	1	0	2	5	-2	2
	0	1	-3	0	-1	3
f	0	0	3	-1	2	4

Стовпець у нижньому рядку містить додатне число, а в інших рядках - недодатні числа. Доведемо нерозв'язність ЗЛП.

Випишемо жорданову форму, що відповідає симплекс-таблиці, і перенесемо члени, що містять , у праву частину. Одержимо

Нехай а - довільне додатне число. Очевидно, ЗЛП має наступне припустиме рішення:. Обчислимо значення цільової функції при цьому припустимому рішенні. З таблиці 3.4 маємо:

. При зазначеному припустимому рішенні f = 4 - 2а. Звідси бачимо, що значення цільової функції може стати як завгодно малим при досить великому значенні а. Інакше кажучи, цільова функція не обмежена знизу на ОПР. Отже, ЗЛП нерозв'язна.

3.5. Перехід до нового опорного плану.

Припустимо, що умови оптимальності й нерозв'язності не виконуються. Тоді симплекс-метод переходить до нового опорного плану. Цей перехід відбувається за рахунок виведення з базису однієї з базисних змінних і введення в базис однієї з вільних змінних. При цьому повинні виконуватися наступні дві умови:

1) новий базис повинен бути як і раніше припустимим, тобто праві частини відповідної жорданової форми повинні бути як і раніше невід’ємними;

2) при новому опорному плані значення цільової функції не повинно перевищувати її значення при попередньому опорному плані.

Стовпець симплекс-таблиці, в якому стоїть змінна, що вводиться в базис, називається генеральним стовпцем. Рядок, в якому стоїть змінна, виведена з базису, називається генеральним рядком. Елемент, що стоїть на перетинанні генерального рядка й генерального стовпця, називається генеральним елементом.

Правило вибору генерального елемента.

Як генеральний стовпець вибирається будь-який стовпець симплекс-таблиці, відмінний від самого правого, у якого в нижньому рядку стоїть додатне число. Потім розглядаються тільки ті рядки симплекс-таблиці, відмінні від самого нижнього, у яких на перетинанні з генеральним стовпцем стоять додатні числа. Для кожного з таких рядків обчислюється відношення вільного члена до елемента, що стоїть в генеральному стовпці. Рядок, для якого це відношення мінімальне, вибирається генеральним. Елемент, що стоїть на перетинанні генерального рядка й генерального стовпця, і буде генеральним елементом.

Проілюструємо це правило на прикладі.

Таблиця 3.5.

Б						Q
	1	0	0	2	-1	4
	0	1	0	3	4	8
	0	0	1	-2	6	3
F	0	0	0	7	5	12

Як генеральний стовпець можна вибрати або стовпець , або стовпець. Виберемо(найчастіше вибирають той стовпець, у якого внизу більше додатне число). Тепер перейдемо до вибору генерального рядка. Для цього розглянемо два рядки -і. Складаємо відносини 4:2 і 8:3. Менше значення має відношення 4:2, тому перший рядок вибираємо генеральним. Отже, генеральний елемент дорівнює 2 - він стоїть на перетинанні стовпцяй рядка.

Після вибору генерального елемента потрібно перейти до нового опорного плану, при якому змінна стає базисною, а змінна х₁- вільною. Коефіцієнт при в новій жордановій формі повинен дорівнювати 1. Тому перший рядок таблиці 3.5 ділиться на 2. Помноживши потім отриманий перший рядок на (-3) і додавши до другого рядка, виключимо із другого рівняння. Аналогічно, за допомогою жорданової процедури виключаємоіз третього рівняння й із цільової функції (останнє вимагає табличний вигляд ЗЛП). У результаті одержимо наступну таблицю.

Таблиця 3.6

Б						Q
		0	0	1		2
		1	0	0	3	2
	1	0	1	0	5	7
f		0	0	0		-2

Звернемо увагу, що в стовпці Q у перших трьох рядках стоять невід’ємні числа, тобто новий базис як і раніше, є припустимим. Це не випадковий факт: так буде завжди при точному дотриманні правила вибору генерального рядка. Далі, значення цільової функції при новому опорному плані дорівнює -2, при старому воно дорівнювало 12. "Поліпшення" опорного плану гарантує правило вибору генерального стовпця. Хоча ці факти ми суворо не доводимо, потрібно мати на увазі, що вони завжди мають місце.

Подивившись на таблицю З.6 , ми бачимо, що не виконуються ані умова оптимальності опорного плану, ані умова нерозв'язності ЗЛП. Виходить, треба знову вибирати генеральний елемент і переходити до нової симплекс-таблиці. Читач зможе проробити це самостійно.