Схема двоїстого симплекс-методу для задачі максимізації цільової функції
Розглянемо теоретичне обґрунтування методу [12].
Крок 1. Вибір змінної, що виводиться з множини базисних (умови допустимості)
За змінну, що виводиться з базису, треба вибрати найбільшу за абсолютною величиною від’ємну базисну змінну, тобто вибрати ведучий рядок q, такий, що
.
Якщо всі базисні змінні ³ 0 (тобто такого q не існує), то СТОП, одержали допустимий і оптимальний розв’язок. У протилежному випадку стовпчик, що відповідає змінній 
, повинен бути виведений з базису.
Крок 2. Вибір змінної, що вводиться в множину базисних (умова оптимальності)
Якщо j-й небазисний стовпчик замінює q-й базисний, тоді після застосування перетворень Гаусса відносна оцінка q-го стовпчика в новому ДБР буде дорівнювати 
. Для того, щоб компоненти вектора dN, як і раніше, були невід’ємні (виконувалась умова оптимальності), знаменник повинен бути від’ємним.
Визначимо коефіцієнт q за формулою
(6.7)
і нехай мінімум досягається при j = p.
Якщо у q-му рядку немає жодного 
для j, які відповідають небазисним змінним (ознака відсутності допустимих розв’язків), то СТОП, пряма задача не має допустимих розв’язків.
Отже, у множину базисних будемо вводити змінну 
:
;
.
Якщо взяти більше значення параметра q , ніж те, яке дає (6.7), наприклад значення, яке відповідає j = r , і якщо змінну 
ввести в базис, то в новому розв’язку одержимо
, тому що 
і умови оптимальності ДБР прямої задачі не будуть виконуватися.
Крок 3. Перехід до нового ДБР
За допомогою елементарних перетворень Гауcса виконується операція заміщення на 
. Перехід до кроку 1.
Схема двоїстого симплекс-методу для задачі мінімізації ЦФ відрізняється від схеми розв’язання задачі на максимум у правилі вибору змінної, що виводиться (критерії оптимальності).
Коефіцієнт q визначають за формулою
(6.7а)
(як і раніше розглядаються тільки відношення з від’ємним знаменником).
Ознака відсутності допустимих розв’язків така сама: у рядку, що відповідає вивідній змінній, немає жодного 
для j, які відповідають небазисним змінним.
З урахуванням (6.7) і (6.7а) можна записати єдине (для задач максимізації та мінімізації) правило вибору ведучого стовпчика:
.
Таким чином, двоїстий симплекс-метод на кожному кроці забезпечує умову оптимальності розв’язку і систематичне наближення його до області допустимих розв’язків. Коли отриманий розв’язок виявляється допустимим, ітераційний процес обчислень закінчується, оскільки цей розв’язок є і оптимальним.
У табл. 6.1 наведено порівняльну характеристику прямого і двоїстого симплекс-методів.
Таблиця 6.1
| Прямий симплекс-метод | Двоїстий симплекс-метод | |
| Проміжний розв’язок | Задача на мінімізацію " хj ³ 0 і $ j dj > 0. Проміжні розв’язки є допустимими, але неоптимальними за критерієм оптимальності | Задача на максимізацію " dj ³ 0, але $ j xj < 0. Проміжні розв’язки є оптимальними за критерієм оптимальності, але не є допустимими |
| Проміжний розв’язок | Задача на максимізацію " хj ³ 0 і $ j dj < 0. Проміжні розв’язки є допустимими, але не є оптимальними. | Задача на мінімізацію " dj £ 0, але $ j xj < 0. Розв’язки є оптимальними за критерієм оптимальності, але не є допустимими. |
| Опти-мальний розв’язок | Задача на мінімізацію | |
| " xj ³ 0 " dj £ 0 | " xj ³ 0 " dj £ 0 |
Продовження таблиці 6.1