Тема 4. Методи одержання штучного початкового розв’язку ЗЛП.

У розглянутій вище задачі для одержання початкового допустимого базисного розв’язку були використані залишкові змінні. Проте, в тих випадках, коли не всі вихідні обмеження задачі мають знак «», неможливо одразу ж одержати початковий базисний розв’язок. Звернемось до наступного прикладу.

Приклад 3.2. Необхідно знайти мінімум функції:

Z=4x1+x2

При додержанні обмежень:

 

Подамо задачу в стандартній формі:

Z =4x1+x2min

 

Маємо три рівняння з чотирма невідомими. На відміну від випадку, коли кожне рівняння містить залишкову змінну, в даній ситуації не має гарантії, що при нульовому значенні однієї із змінних інші три базисні змінні будуть невід’ємними. Звичайно, початковий базисний розв'язок можна знайти шляхом підбору допустимих значень змінних. Проте така процедура є неефективною. Більш раціональним є підхід, що передбачає введення так званих «штучних базисних змінних» до лівих частин обмежень, що не містять «очевидних» початкових базисних змінних. Ці змінні забезпечують початковий допустимий розв'язок. При цьому схема обчислень має забезпечити одержання такого оптимального розв’язку, в якому всі штучні змінні дорівнюють нулю. Розроблено два основні методи одержання початкового допустимого розв’язку на основі штучних змінних: метод великих штрафів (або М-метод) і двоетапний метод.

 

4.1. Метод великих штрафів (М-метод).

Розглянемо більш детально перший із двох названих методів: метод великих штрафів.

Введемо до другого й третього обмежень задачі прикладу 3.2. По одній невід’ємній штучній змінній: R1 і R2  відповідно:

3x1+x2 +R1 =3,

4x1+3 x2 –x3  +R2 =6.

За використання штучних змінних необхідно «накласти штраф»: у цільовій функції цим змінним слід приписати досить великі додатні коефіцієнти (в задачі на мінімум) або досить великі за модулем від’ємні коефіцієнти (в задачі на максимум). Математична модель задачі набуде вигляду:

Z=4x1+x2+МR1+МR2 min

Звернемо увагу на логіку використання штучних змінних. Система обмежень задачі в стандартній формі містить 3 рівняння і 6 невідомих. Отже, початковий базисний розв’язок повинен містити 6-3=3 нульові змінні. Якщо покласти x1=x2=x3=0, то відразу одержимо початковий допустимий розв’язок: R1=3, R2=6, x4=4.

Введення великих додатних коефіцієнтів при R1  іr2 до цільової функції забезпечить поступове (покрокове) виключення цих штучних змінних із базису. В оптимальному розв’язку всі штучні змінні мають стати рівними нулю.

Для подання процесу розв’язання задачі в зручній табличній формі необхідно “переформулювати” умову задачі так, щоб рівняння цільової функції містило лише вихідні змінні: x1,, x2, x3, а права його частина являла собою константу. З цією метою з обмежень виразимо штучні змінні R1 , R2 через x1, x2, x3: R1=3-3x1-x2, R2=6-4x1-3x2+x3  і підставимо в цільову функцію:

Z=4x1+x2+M(3-3x1-x2)+M(6-4x1-3x2+x3)=(4-7M)x1+(1—M)x2+Mx3+9M. Цільова функція з невід’ємною правою частиною набуде вигляду:

Z+(7M-4)x1+(4M-1)x2-Mx3=9M.

Занесемо перетворене рівняння цільової функції та обмеження, що містять штучні початкові базисні змінні, до таблиці й знайдемо оптимальний розв’язок задачі симплексним методом (див. Табл. 3.5.–3.8).

Після двох ітерацій симплексним методом отримаємо оптимальний розв’язок, представлений у табл. 3.8.

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

 

 

Зауважимо, що важливим недоліком М-методу є наступне: через великий розмір штрафів М внесок вихідних коефіцієнтів до цільової функції є незначним. Внаслідок похибок округлення, що властиві будь-якій ЕОМ, процес обчислень може стати нечутливим до значень вихідних коефіцієнтів (для аналізованого приклада це коефіцієнти при x1, x2). Виникає загроза, що ці змінні будуть інтепретуватись як такі, що мають нульові коефіцієнти в цільовій функції.

Від цього недоліку є вільним так званий двоетапний метод.