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 буде мінімальним.

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

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 30  Наверх ↑