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

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

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

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

 

 

 

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

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

 

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

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

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

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

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

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

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

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

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

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

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

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

 

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