агального підходу до вирішення завдань лінійного програмування, включає в себе канонізацію умов завдання, розрахунок симплекс-різниць, перевірку умов оптимальності, прийняття рішень про коригування базису і виняток Жордана-Гаусса.
Особливості полягають у наявності двох таблиць - основний і допоміжної, порядку їх заповнення та деякої специфічності розрахункових формул.
Кожній задачі лінійного програмування можна певним чином зіставити деяку іншу задачу, звану двоїстої або сполученої по відношенню до вихідної або прямий завданню. Зіставляючи форми запису прямої та двоїстої завдань, можна встановити між ними наступні взаємозв'язки:
1. якщо пряма задача є задачею максимізації, то двоїста буде задачею мінімізації, і навпаки;
2. коефіцієнти цільової функції прямої задачі стають вільними членами обмежень двоїстої задачі;
3. вільні члени обмежень прямої задачі стають коефіцієнтами цільової функції двоїстої задачі;
4. матриця обмежень двоїстої задачі виходить шляхом транспортування матриці обмежень прямої задачі;
5. знаки нерівностей в обмеженнях змінюються на протилежні;
6. число обмежень прямої задачі дорівнює числу змінних двоїстої задачі, і навпаки.
Види математичних моделей двоїстих задач можуть бути представлені в таблиці (Табл. 1.1). br/>
Таблиця 1.1
Види математичних моделей двоїстих задач
Вихідна завдання
Двоїста задача
Несиметричні завдання
В В
Симетричні завдання
В В
Таким чином, перш ніж записати двоїсту завдання для даної вихідної, систему обмежень вихідної задачі необхідно привести до відповідного виду. [3, с.114-115]
Якщо з пари двоїстих задач одна має оптимальним планом, то й інша має рішення, причому для екстремальних значень лінійних функцій виконується певне співвідношення (формула 1.10). Якщо лінійна функція одним із завдань не обмежена, то інша не має рішення.
(1.10)
Якщо пряма (а значить, і двоїста) завдання можна вирішити, то в кожній парі двоїстих умов одне є вільним, а інше закріпленим. Будь-яке з умов називається вільним, якщо воно виконується як суворе нерівність хочаб для одного оптимального вектора. Умова називається закріпленим, якщо воно виконується як рівність для всіх оптимальних векторів.
Двоїсту задачу вигідніше вирішувати, ніж пряму, якщо в прямій задачі при малій кількості змінних є велика кількість обмежень. [2, c 70-71]
Симплексних метод дозволяє поряд з отриманням розв'язання прямої задачі отримувати і рішення двоїстої задачі. Цей результат і лежить в основі двоїстого симплексного методу розв'язання задачі. Суть методу полягає в такому послідовному переборі кутових точок допустимої множини Q 0 двоїстої задачі, при якому значення цільової функції зростає, тобто в застосуванн...
