створюються штучно і використовуються для створення вихідного базису, їх значення у вирішенні сильно відрізняються:
В· додаткові змінні повідомляють, наскільки відповідне їм обмеження В«недовикористанихВ». Значення додаткової змінної, рівне нулю, відповідає рівності значень правих і лівих частин обмеження.
В· допоміжні змінні повідомляють, наскільки дана умова далеко від припустимого (щодо конкретного обмеження). Якщо значення допоміжної змінної більше нуля, то дане рішення не виконує певне обмеження, а значить не є допустимим.
Тобто ненульове значення додаткової змінної може (але не повинно) сигналізувати про неоптимальности рішення. Ненульове значення допоміжної змінної сигналізує про неприпустимість рішення. p align="justify"> Фази рішення
Після того, як було модифіковано умова, створюється допоміжна цільова функція . Якщо допоміжні змінні були позначені, як y i , i? {1., K}, то допоміжну функцію визначимо, як
.
Після цього проводиться звичайний симплекс-метод відносно допоміжної цільової функції. Оскільки всі допоміжні змінні збільшують значення, в ході алгоритму вони будуть по черзі виводиться з базису, при цьому після кожного переходу нове рішення буде все ближче до безлічі допустимих рішень. p align="justify"> Коли буде знайдено оптимальне значення допоміжної цільової функції, можуть виникнути дві ситуації:
В· оптимальне значення більше нуля. Це означає, що як мінімум одна з допоміжних змінних залишилася в базисі. У такому випадку можна зробити висновок, що допустимих рішень даної задачі лінійного програмування не існує.
В· оптимальне значення дорівнює нулю. Це означає, що всі допоміжні змінні були виведені з базису, і поточне рішення є допустимим.
У другому випадку ми маємо допустимий базис, або, інакше кажучи, вихідне допустиме рішення. Можна проводити подальшу оптимізацію з урахуванням вихідної цільової функції, при цьому вже не звертаючи уваги на допоміжні змінні. Це і є другою фазою рішення. br/>
4. Модифікований симплекс-метод
У модифікованому методі матриця
В
не перераховується, зберігається і перераховується тільки матриця. В іншому алгоритм схожий на вищеописаний. p align="justify">. Обчислюємо двоїсті змінні
. Перевірка оптимальності. перетвориться в.
Перевірка поляга...
