Курсовая работа: Двойственность в линейном программировании

При этом плане maxf=-46/3

1.2.2 Симметричные двойственные задачи

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

Исходная задача. Найти матрицу-столбец Х=(x₁ , x₂ ,…, x_n ), которая удовлетворяет системе ограничений

(1.12). АХ>А₀ , Х>0 и минимизирует линейную функцию Z=СХ

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

Используя симметричность, можно выбрать задачу, более удобную для решения. Объем задачи, решаемой с помощью ЭВМ, ограничен числом включаемых строк, поэтому задача, довольно громоздкая в исходной постановке, может быть упрощена в двойственной формулировке. При вычислениях без помощи машин использование двойственности упрощает вычисления.

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

1.3 Виды математических моделей двойственных задач

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

· Симметричные задачи

(1) Исходная задача Двойственная задача

Z_min =CX; f_max =Y>A₀ ;

AX=A₀ ; YA=С

X>0 Y>0

(2) Исходная задача Двойственная задача

Z_max =CX; f_min =YA_0;

AX=A₀ ; YA=С

X>0Y>0

· Несимметричные задачи

(3) Исходная задача Двойственная задача

Z_min =CX; f_max =YA₀ ;

AX=A₀ ; YA=С

X>0

(4) Исходная задача Двойственная задача

Z_max =CX; f_min =YA₀ ;

AX=A₀ ; YA=С

X>0

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

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

Для получения решения исходной задачи можно перейти к двойственной. А используя оценки ее оптимального плана, можно определить оптимальное решение исходной задачи.