Отже, послідовні переходи від одного сполученого базису до іншого виробляють до тих пір, поки не отримають рішення задачі або не встановили її нерозв'язність. Кожен перехід від одного псевдоплан до іншого складає одну ітерацію (один крок) двоїстого симплекс-методу.

Кожна ітерація містить два етапи. На першому етапі з'ясовують, чи не є псевдоплан оптимальним планом прямої задачі, і якщо немає, то можна вирішити чи завдання. Для цього необхідно обчислити і встановити їх знаки. Другий етап полягає в здійсненні елементарного перетворення - (однієї ітерації) методу повного виключення Жордана-Гауса, що приводить до нового псевдоплану з меншим значенням цільової функції.

Опис алгоритму. Завдання ЛП повинна бути задана в канонічній формі (1.1), (1.2) або зведена до неї. Відшукують пов'язаний базис двоїстої задачі і позначають його . Розкладемо А0 по векторах базису Аі1,., Аіm відповідно до (1.9) і знайдемо псевдоплан прямої задачі.

Досліджуємо знаки {хi0}. Якщо має місце випадок , То початковий псевдоплан є оптимальним планом прямої задачі. При наявності негативних компонент {хi0} обчислюємо коефіцієнти розкладання векторів Aj по векторами сполученого базису {хij} відповідно до (1.8).

Якщо для деякого r такого, що хr0 <0, все то завдання не можна вирішити (другий випадок), і на цьому процес обчислень закінчується.

Якщо має місце третій випадок (тобто для кожного r такого, що хr0 <0, принаймні одна з компонент хrj <0), то переходимо до другого етапу. З цією метою складають таблицю k -й ітерації (аналогічну симплекс-таблиці), яка складається (m + 2) рядків і (n + 1) -го стовпця ( табл. 6.1 ).

Стовпець Вx таблиці, як зазвичай, містить вектори {Ai} базису псевдоплан Xk, а стовпець А0 - базисні компоненти псевдоплан {хi0 (k)}. Рядок (m + 1) -індексная, її заповнюють параметрами , Які є оцінками векторів Аj:

величина - значення цільової функції при псевдоплане

Ітерацію k завершують заповненням головної частини таблиці (від першої до (m + 1) -й рядків).

На першому етапі (k + 1) -й ітерації з'ясовують, чи має місце перший, другий чи третій випадок.

У третьому випадку переходимо до другого етапу. Спочатку визначають вектор Аr, який необхідно вивести з базису. Його індекс r визначають з умови

тобто за максимальною за модулем від'ємною компоненті базисного рішення.

Потім заповнюють елементи (m + 2) -й рядка, які обчислюють за формулою

В рядку заповнюють лише ті позиції, для яких xrj <0. Вектор Аl, який повинен бути введений в базис, знаходять з умови

Визначивши направляючу рядок r і стовпець l, обчислюють елементи головної частини таблиці (k + 1) -й ітерації по рекурентним співвідношенням

де xri - направляючий елемент перетворення.

Обчислювальна схема алгоритму двоїстого симплекс-методу схожа на обчислювальну схему симплекс-методу. Аналогічні і форми таблиць.

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

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

Відзначимо деякі важливі властивості подвійного симплекс-методу.

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

Розглянемо, наприклад, типову задачу мінімізації

за умов

Для завдання такого виду знайти відразу початковий опорний план не можна, і тому необхідно застосувати метод штучних змінних і виконати значний обсяг обчислень. У той же час псевдоплан знаходиться майже автоматично. Дійсно, перейдемо від (1.17) - (1.19) до еквівалентної задачі в розширеній формі, ввівши вільні змінні xn + 1, xn + 2,., Xn + m ...

за умов

Запишемо обмеження двоїстої задачі

З нерівностей (1.23) - (1.24) бачимо, що оскільки рішення yi при i = 1, m задовольняє всім обмеженням (1.23), то пов'язаний базис утворюють вектори An + 1, An + 2, ..., An + m при вільних змінних. При цьому початковий псевдоплан такий:

Отже, для завдання виду (1.17) - (1.18) пpи умови (1.20) застосування двоїстого сімплес-методу виявляється переважно в порівнянні з прямим.

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