Двоїстий симплекс-метод

Двоїстий симплекс-метод.

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

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

Приклад 1. Застосовуючи двоїстий симплекс-метод, вирішити наступне завдання:

Наводимо нерівності завдання до знаку ≥, множачи перше, друге і четверте обмеження на (-1); тоді модель двоїстої задачі буде мати вигляд:

Рішення, відповідне табл. 2, є оптимальним. Запишемо відповідність між змінними прямої і двоїстої задач. Якщо обмеження прямої задачі приводити до виду рівності, то в якості додаткових з'являться змінні x3. x4. x5. x6.

У F-рядку розташовані коефіцієнти при небазисних змінних y1. y2. y5. y4. Знайдемо оптимальне рішення прямої задачі:

Мінлива x5. відповідна y3. і x2. відповідна y6. дорівнюють нулю.

min F (y) = max F (x) = 6.

Таким чином, вирішуючи симплексним методом одну з пари двоїстих задач, автоматично отримуємо рішення іншого.

Схожі статті