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

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

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

,

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

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

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

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

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

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

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

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

.

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

или

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

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

.

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

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