В. 22 Идея двойственного симплексного метода (ДСМ)

P: c*х → min

A*x=b

x≥0,

D: b*u → max

А^Т*u≤c (естественное).

Надо решить А^Т*u≤c. Для этого вспомним симплексный метод.

, А^Т*u≤c - ограничение двойственной задачи.

.

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

Идея двойственного симплексного метода заключается в том, что мы начинаем решать прямую задачу с оптимального, но не допустимого решения, постепенно делаем его допустимым, но поскольку двойственная задача остаётся допустимой в прямой задаче решение до конца остаётся оптимальным.

Двойственный симплексный метод применяется для решения задачи линейной оптимизации вида:

c*х → min

A*x≥b

x≥0.

Чтобы привести к каноническому виду:

c*х → min

A*x-Е*у=b

x≥0, у≥0, где Е – единичная матрица.

Домножим на «-1».

c*х → min

-A*x+Е*у=-b

x≥0, у≥0, где Е*у – базис.

Вектор правой части (b) стал отрицательным, поэтому сначала решение будет недопустимым, но оптимальным. Если c_j≥0, то min достигается, если х=0. Задача двойственного симплексного метода сделать это решение допустимым.