Двойственная задача линейного програмирования

Двойственная задача линейного програмирования может быть сформулирована следующим образом:

Найти переменные y_i (i=1,2,...m), при которых целевая функция была бы минимальной

,

не нарушая ограничений

Данная задача называется двойственной (симметричной) по отношению к прямой задаче, сформулированной во втором параграфе данной главы. Однако, правильным будет и обратное утверждение, т.к. обе задачи равноправны. Переменные двойственной задачи называются объективно обусловленными оценками.

Прямая и обратная задачи линейного програмирования связаны между собой теоремами двойственности.

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

F(x)=Z(y) или .

Если же хотя бы одна из задач не имеет допустимого решения, то ни одна из них не имеет оптимального решения.

Вторая теорема двойственности (теорема о дополняющей нежесткости). Для того чтобы векторы были оптимальными решениями соответственно прямой и двойственной задачи, необходимо и достаточно, чтобы выполнялись следующие условия:

Следствие1.Пусть оптимальное значение некоторой переменной двойственной задачи строго положительно

.

Тогда из условия (1) получим:

или

Экономический смысл данных выражений можно интерпретировать в следующей редакции. Если объективно обусловленная оценка некоторого ресурса больше нуля (строго положительна), то этот ресурс полностью (без остатка) расходуется в процессе выполнения оптимального плана.

Следствие2. Пусть для оптимального значения некоторой переменной x_i прямой задачи выполняется условие строгого неравенства

.

Тогда основываясь на том же первом условии (1) можно заключить, что y_i=0.

Экономически это означает, что если в оптимальном плане какой-то ресурс используется не полностью, то его объективно обусловленная оценка обязательно равна нулю.

Решение двойственной задачи линейного програмирования

Ранее мы рассматривали прямую задачу линейного програмирования:

В системе неравенств должны быть однотипные знаки «меньше или равно». Поэтому неравенство умножим на – 1 и поменяем знак неравенства на противоположный.

Ограничение на целочисленность переменных здесь не требуется.

Решение прямой задачи дало следующие результаты:

Х₁=80; Х₂=1400; F(x)=42400.

В результате решения двойственной задачи получим

Y₁=0; Y₂=33.3; Y₃=220; Z(y)=42400.

Объективно обусловленная оценка Y₁=0 указывает на то, что у нас избыток древесины. Y₂=33.3,т.е. больше нуля. Это говорит о том, что этот ресурс (труд) полностью используется в оптимальном плане. Значение целевой функции Z(y)= F(x)=42400.Это свидетельствует о том, что найденное решение оптимально.