4.2. Двоетапний метод.

Названий метод включає наступну послідовність процедур:

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

Етап 2.  Оптимальний базисний розв’язок, отриманий на етапі 1, використовується в якості початкового розв’язку вихідної задачі.

Проілюструємо процедури двоетапного методу на тому ж прикладі (3.2), що й метод великих штрафів.

Етап 3.  Введемо штучні змінні до першого й другого рівнянь та сформулюємо допоміжну цільову функцію r:

 R =R1+R2 min

У рівнянні цільової функції мають фігурувати лише небазисні змінні. Тому необхідно змінні початкового базису R1 іr2  виразити через небазисні змінні x1, x2, x3 і отримані вирази підставити в цільову функцію. Виразивши з першого рівняння R1=3-3x1-x2, а з другого  R2=6-4x1-3x2+x3 і підставивши в рівняння допоміжної цільової функції, одержимо:

R=(3-3x1-x2)+( 6-4x1-3x2+x3)=-7 x1-4 x2+ x3+9.

У результаті перенесення всіх змінних до лівої частини рівняння цільової функції, це рівняння набуде вигляду:

R+7x1+4x2-x3=9,

Звідки очевидно, що початковому розв’язку задачі відповідає значення цільової функції r=9.

За допомогою сиплекс-методу знайдемо розв’язок, при якому значення функції r буде мінімальним.

 

Таблиця 3.9

         

         

           

 

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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 
25 26 27 28 29  Наверх ↑