Симплекс-метод розв’язку ЗЛП

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

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

Вибравши деякий базис перетворимо систему обмежень і цільову функцію в канонічну форму

Із цієї системи створюємо таблицю:

Базис			…			…	b
			…			…	b1
			…			…	b2
…	…	…	…	…	…	…
			…			…	bm+n
Z			…			…	b0

Базис відповідає кожному куту симплекса. Перша таблиця відповідає початку координат. Останній рядок таблиці (без b₀) відповідає значенню базисних змінних для відповідного кута симплекса. В комірці b₀ знаходиться значення цільової функції при базисному розв’язку.

Ідея розв’язку ЗЛП – перевести незалежні змінні в базис, користуючись наступними критеріями.

Критерій допустимості базиса:

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

Критерій оптимальності таблиці:

якщо в останньому рядку немає додатніх елементів, крім, можливо, останнього, то відповідний цій таблиці базис оптимальний ( ). При цьому .

Критерій відсутності розв’язку:

якщо в симплекс-таблиці маємо такий стовпець, останній елемент якого додатній, а всі інші недодатні, то відповідна ЗЛП не має оптимального розв’язку ( ) .

Критерій існування ведучого елемента:

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

Тепер сформулюємо алгоритм правил перетворення симплекс-таблиці;

1) всі елементи рядка, на якому розміщений ведучий елемент, ділимо на нього (на місці ведучого елемента з’являється 1);

2) всі інші елементи ведучого стовпця заміняємо нулями;

3) всі інші елементи симплекс-таблиці перетворюємо по правилу прямокутника:

Тепер метод послідовного покращення плану або симплекс-метод можна представити так:

1) знаходимо будь-яке базисне рішення і складаємо симплекс-таблицю, відповідну цьому базису;

2) переглядаємо останній рядок таблиці, якщо в ньому немає додатніх елементів (крім, можливо ) то оптимальне рішення знайдено – буде мінімальним значенням ;

3) якщо ж серед елементів останнього рядка є додатні елементи, але хоча б над одним із них є стовпець, що не вміщує інших додатніх елементів, то система немає розв’язку;

4) якщо обидва критерії (пункти 2, 3) не виконані, то вибирають ведучий елемент і перетворюють симплекс-таблицю.

Перейдемо до розрахунку попереднього прикладу.

Складемо першу симплекс-таблицю:

Базис

Знаходимо ведучий елемент в стовпці

Значить, ведучий елемент . По відношенню до нього перетворюємо таблицю:

Базис

Ця ж таблиця після виконання арифметичних дій:

Базис
		3,75		-0,25
		0,625		0,125
		2,875		-0,625
		8,75		-6,25		-2500

В новій таблиці в останньому рядку є додатній елемент .

Над ним знаходимо ведучий елемент таблиці .

Значить, ведучим елементом є .

Повторюємо перетворення таблиці:

Базис
				1,105	-1,304	34,78
				0,261	0,217	39,13
				-0,217	0,348	17,39
				-7,438	-3,043	-2640

Таблиця оптимальна. В ній відповідь: .