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

Як відомо, двоїстою до задачі (1) є ЗЛП

(2)

Нехай вектори умов у задачі (1)є лінійно незалежними, – базисна матриця. Спробуємо перейти від СЗЛП (1)до КЗЛП, для цього помножимо прямі обмеження зліва на . Одержимо , де , Е – одинична матриця розмірності m × m. Якщо при цьому , то одержана ЗЛП є канонічною, якщо ж деякі компоненти вектора β від'ємні, то, звичайно, ні.

Означення 1. Майже канонічною задачею лінійного програмування (МКЗЛП) називається стандартна задача лінійного програмування (1), якщо матриця умов A містить одиничну матрицю.

Означення 2. Вектор називається майже допустимим базисним розв'язком, якщо він задовольняє обмеження (але не обов'язково обмеженням ) i його ненульовим компонентам відповідають лінійно незалежні вектори умов.

Для одержаної задачі маємо , вектори умов – лінійно незалежні, – базисна матриця. Змінні будемо називати базисними, – небазисними. Надалі будемо розглядати лише ті майже допустимі базисні розв'язки (або ж ті МКЗЛП, що їх визначають), для яких відносні оцінки невід'ємні, тобто (3)

Для таких майже допустимих базисних розв'язківє очевидним критерій оптимальності: майже допустимий базисний розв'язок є оптимальним, якщо він є допустимим.

Зауважимо, що для майже допустимого базисного розв'язку, для якого виконується (3), вектор є допустимим розв'язком двоїстої ЗЛП (). Отже, розглянемо МКЗЛ

для якої . Виключивши з цільової функції базисні змінні , маємо

(4)

Двоїста до ЗЛП (4) має вигляд

або, виконуючи заміну

Останню задачу легко переводимо до канонічного вигляду, вводячи додаткові невід'ємні змінні , та враховуючи, що максимiзацiя цільової функції еквівалентна мінімізації цієї ж функції з оберненим знаком:

(5)

Отже, двоїстою до МКЗЛП (4) є КЗЛП (5). Зміст двоїстого симплекс-методу полягає у застосуванні звичайного симплекс-методу для розв'язування двоїстої ЗЛП (5). Оскільки метод, що розглядається, цікавить нас як метод розв'язування задачі (4), вияснимо, що означають для ЗЛП (4) перетворення кожної iтерацiї симплекс-методу, застосованого до задачі (5). Прямі обмеження КЗЛП (5) визначають базисний розв'язок цієї задачі – n -вимірний вектор , для якого вектор тієї ж вимірності є вектором симплекс-рiзниць. Якщо , то є оптимальним розв'язком задачі (5). Отже, є оптимальним розв'язком ЗЛП (4) (критерій оптимальності майже допустимого базисного розв’язку). Інакше згідно симплекс-методу визначаються числа l та k з умов:

l: (6)

k: (7)

тобто, визначається ведучий елемент симплексного перетворення. Стосовно задачі (4) вказані дії також визначають ведучий елемент симплексного перетворення, при цьому з числа базисних виводиться вектор , а вектор уводиться до числа базисних. Виконавши вказане перетворення, одержимо МКЗЛП, що визначає майже допустимий базисний розв’язок (аналогічно КЗЛП)

де . З цього ж перетворення випливає також, що відносні оцінки , для пов'язані з співвідношенням

(8)

Враховуючи, що , , робимо висновок, що при виконується . Якщо ж , то, записавши (7) у вигляді , маємо, що . Отже, для нового МДБР відносні оцінки також невід'ємні. Легко підрахувати також, що , тобто, при переході від точки до значення цільової функції збільшується, якщо є невиродженим базисним розв'язком двоїстої ЗЛП i залишається незмінним у виродженому випадку.

Зауважимо нарешті, що коли для деякого у задачі (5) , то ця задача розв'язку не має через необмеженість цільової функції на допустимій множині, а задача (4) згідно теореми двоїстості не має розв'язку через те, що є порожньою її допустима множина. Все це дає можливість сформулювати алгоритм двоїстого симплекс-методу.

Алгоритм двоїстого симплекс-методу (ДСМ)

1.Зводимо вихідну ЗЛП до МКЗЛП i знаходимо її МДБР , для якого відносні оцінки невід'ємні.

2.Нехай на s -ій iтерацiї маємо МКЗЛП, що визначає МДБР , якому відповідають невід'ємні відносні оцінки. Без обмеження загальності будемо вважати, що визначається системою прямих обмежень

(9)

тобто, та

3. Якщо , то здійснюється вихід із алгоритму: є оптимальним розв'язком вихідної ЗЛП.

4.Якщо існує принаймні одне , таке, що , то здійснюється вихід із алгоритму: вихідна ЗЛП розв'язку не має (її множина допустимих розв’язків є порожньою).

5. Знаходимо l з умови . Отже, вектор виводиться з числа базисних.

6. Знаходимо k з умови . Вектор уводиться до числа базисних. Виконуємо симплексне перетворення над елементами розширеної матриці системи (9) з ведучим елементом i повертаємось до пункту 2 алгоритму, заміняючи s на s+1.