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

Для решения задач линейного программирования кроме прямого симплексного метода, изложенного в п.3.2, используется двойственный симплекс метод. В этом случае решение задачи распадается на два этапа. На первом этапе определяется начальный опорный план, его называют псевдопланом, для этого исключаются отрицательные коэффициенты в f – строке (для задачи на минимум, когда все коэффициенты этой строки записываются со своими знаками). На втором этапе определяется оптимальный план, для чего избавляются от отрицательных элементов в столбце свободных членов.

Алгоритм двойственного симплекс – метода состоит в следующем.