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

⇐ Назад

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

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

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

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

Базис			…			…	b
			…			…	b₁
			…			…	b₂
…	…	…	…	…	…	…
			…			…	b_m+n
Z			…			…	b₀

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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