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) містить оптимальний розв’язок задачі, що розглядалась. Разом з тим зауважимо, що інформація, яка може бути одержана за допомогою сиплекс-методу, не обмежується оптимальними значеннями змінних. Сиплекс-метод фактично дозволяє дати економічну інтерпретацію отриманого розв’язку та провести аналіз моделі на чутливість.
25 26 27 28 29 30 Наверх ↑