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

Смысл двойственного симплекс-метода заключается в том, что вместо прямой задачи решают двойственную при помощи обычного симплекс-метода. Затем по решению двойственной задачи находят оптимальное решение прямой. Для этого устанавливается взаимнооднозначное соответствие между переменными прямой и двойственной задач. Исходным переменным прямой задачи ставятся в соответствие дополнительные переменные двойственной, а дополнительным переменным исходной задачи ставятся в соответствие исходные переменные задачи прямой.

Пусть решена двойственная задача и получена оптимальная симплекс-таблица. Оптимальное решение прямой задачи определяется коэффициентами F-строки. Переменные прямой задачи приравниваются к коэффициентам при соответствующих им небазисных переменных в F-строке оптимальной симплекс-таблицы двойственной задачи. Остальные переменные равны нулю. Наиболее целесообразно применять двойственный симплекс-метод в случае, когда число ограничений прямой задачи намного больше, чем число неизвестных, а также в задачах целочисленного программирования.

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

F(x)=6x₁+12x₂ (min)

-2x₁+3x₂≤6;

4x₁-3x₂≤12;

3x₁+x₂≥3;

x₁≤2;

x_1,2≥0;

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

F(x)=-6y₁-12y₂+3y₃-2y₄ (max)

2y₁-4y₂+3y₃-y₄≤6

-3y₁+3y₂+y₃≤12

y₁≥0, y₂≥0, y₃≥0, y₄≥0.

Решение двойственной задачи осуществляем обычным симплекс-методом (табл. 1 и 2).

Таблица 1

Таблица 2

Решение, соответствующее табл. 2, является оптимальным. Запишем соответствие между переменными прямой и двойственной задач. Если ограничения прямой задачи приводить к виду равенств, то в качестве дополнительных появятся переменные x₃, x₄ , x₅, x₆.

Тогда

В F-строке расположены коэффициенты при небазисных переменных y₁, y₂, y₅, y₄. Найдем оптимальное решение прямой задачи:

x₃ = 8; x₄ = 8; x₁ =1; x₆ =1.

Переменная x₅ , соответствующая y₃, и x₂, соответствующая y₆ , равны нулю.

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

Таким образом, решая симплексным методом одну из пары двойственных задач, автоматически получаем решение другой.