Подвійний симплекс-метод

Вирішення прямої задачі оптимізації можна визначити за допомогою симплекс-метода. Його можна отримати такою заміною базису, при якій усі вільні члени у співвідношеннях прямої системи стануть невід'ємними, оскільки тільки при невід'ємних вільних членах для нульових значень небазових змінних базисні змінні будуть невід'ємними. Разом з тим, екстремальне значення функції мети досягається при такій заміні базисних змінних, при якій усі коефіцієнти при небазових змінних у виразі для L негативні.

Подвійний симплекс-метод називаютьметодом послідовного поліпшення оцінок. Сенс його полягає по суті в тому, що замість прямої задачі вирішують подвійну і потім за оптимальними значеннями змінних двоїстої задачі визначають оптимальні значення прямої задачі, причому оптимальне базисне рішення однієї задачі виходить прирівнюванням її нових базисних змінних коефіцієнтів при відповідних небазових змінних в лінійній формі двоїстого завдання, взятого зі знаком “–”.

Двійний симплекс-методдоцільно застосовувати, коли у вихідному завданні число обмежень значно більше від числа невідомих. Якщо в цьому випадку перейти до двоїстої задачі, то симплекс-процедура буде простіше, ніж для прямої задачі. Разом з тим, двоїстий симплекс-метод широко застосовується в різних методах вирішення задач цілісного програмування.

Часто рішення двоїстої задачі називають псевдопланом, щоб відрізняти його від рішення прямої задачі, званого просто планом.

Найпростіше проілюструвати двоїстий метод на прикладі.

Приклад. Розглянемо наступне завдання лінійного програмування:

---