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

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

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

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

Таблиця 3.3.

Б Q
-1
-1
f -5 -3 -1

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

 

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

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

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

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

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

Таблиця 3.4.

Б Q
-2
-3 -1
f -1

 

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

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

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

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

 

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

 

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

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

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

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

 

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

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

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

Таблиця 3.5.

Б Q
2 -1
-2
F

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

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

Таблиця 3.6

Б Q
f -2

 

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

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

 

3.6. Табличний симплекс-алгоритм

 

Нехай є заповнена симплекс-таблиця. Підбиваючи підсумки викладеному, одержимо наступний алгоритм вирішення ЗЛП симплекс-методом.

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

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

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

4. Заповнюємо нову симплекс-таблицю, у якій:

1) з базису виведено змінну, що стоїть в генеральному рядку; в базис уведено змінну, що стоїть у генеральному стовпці;

2) генеральний рядок ділимо на генеральний елемент;

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

Приклад I. Вирішити симплекс-методом

Задача записана в канонічному вигляді, потрібно привести її до табличного вигляду. Система рівнянь записана в жордановій формі з невід’ємними правими частинами (базисні змінні й ). Необхідно привести до табличного вигляду цільову функцію. Для цього виразимо базисні змінні через вільні

x3=10 - 2x1 - x2

x4= 8 - x1 - 2x2

і підставимо в цільову функцію

Для одержання табличного вигляду функцію запишемо так:

Тепер маємо табличний вигляд ЗЛП:

Заповнимо першу симплекс-таблицю

 

Таблиця 3.7

Б Q
F

 

У таблиці 3.7 умови оптимальності й нерозв'язності не виконуються. Виберемо за генеральний стовпець , у якого в нижньому рядку стоїть додатне число. Потім, порівнюючи відносини 10:3 і 8:1, виберемо перший рядок як генеральний. У таблиці генеральний елемент 2 .

Діючи відповідно до пункту 4 табличного симплекс-алгоритму, перейдемо до таблиці 3.8.

Таблиця 3.8

Б Q
F -5 -22

 

Умови оптимальності й нерозв'язності не виконуються. Вибираємо в таблиці 3.8 генеральний елемент і переходимо до наступної таблиці

Таблиця 3.9

Б Q
F -24


Таблиця 3.9 задовольняє умові оптимальності.

Відповідь: оптимальний план

Мінімальне значення цільової функції fmin = - 24.

 

Приклад 2. Вирішити симплекс-методом:

 

Насамперед, ЗЛП потрібно привести до канонічного вигляду

Тепер приводимо ЗЛП до табличного вигляду. Бачимо, що система рівнянь записана в жордановій формі з невід’ємними правими частинами (і z - базисні змінні). Однак у цільову функцію входить базисна змінна. Маємо:

Отже, табличний вигляд ЗЛП такий:

Заповнюємо симплекс-таблицю (таблиця 3.10).

 

 

Таблиця 3.10

Б z Q
-1
z -2
g -1

 

Після вибору генерального елемента переходимо до таблиці 3.11

Таблиця 3.11

Б z Q
-1
z -2
g -2 -9

 

Звернемо увагу на стовпець. Він показує, що цільова функція g не обмежена знизу на ОПР. Згадуючи, що g =-f, одержуємо відповідь.

Відповідь: ЗЛП нерозв'язна через необмеженість зверху на ОПР цільової функції f.

 

Приклад 3. Вирішимо симплекс-методом задачу про використання обладнання, поставлену в параграфі 2.1. Саме там приводилася її математична модель

 

Приводимо ЗЛП до канонічного вигляду

 

Система рівнянь записана в жордановій формі з невід’ємними правими частинами, базисні змінні не входять у цільову функцію g. Тому табличний вигляд цільової функції такий:.

Заповнюємо симплекс-таблицю (таблиця 3.12).

 

Таблиця 3.12

Б Q
G

 

Умови оптимальності й нерозв'язності не виконуються. Стовпець (у нижньому рядку якого стоїть найбільше додатне число) виберемо генеральним. Порівнюючи відносини 30:3, 40:2, і 60:4, обираємо перший рядок як генеральний. Поділивши його на 3 і зробивши за допомогою жорданової процедури нулі у всіх інших рядках генерального стовпця, після заміни базисної змінної на змінну , одержимо таблицю 3.13.

Таблиця 3.13

Б Q
x2
z2
g -70

 

Знову вибираємо генеральний елемент і переходимо до таблиці 3.14

 

Таблиця 3.14

Б Q
g - 2 -80

 

У нижньому рядку таблиці 3.14 стоять недодатні числа. Тому опорний план, що відповідає цій таблиці, оптимальний. Випишемо його:

Оскільки змінні не фігурували у вихідній постановці задачі, крім того, функція f = - g у вихідній постановці максимізувалася, то можна записати наступне оптимальне рішення вихідної задачі

Повертаючись до змістовної постановки (параграф 2.1), доходимо наступного висновку: прибуток підприємства буде максимальним (80 грош.од.), якщо виробів А випустити 7,5 од., виробів В випустити 5 од.

Це ж завдання ми вирішили геометрично (див. параграф 2.5, приклад 5) і, природно, одержали саме такий результат.