Двойственная задача линейного програмирования
Двойственная задача линейного програмирования может быть сформулирована следующим образом:
Найти переменные yi (i=1,2,...m), при которых целевая функция была бы минимальной
,
не нарушая ограничений
Данная задача называется двойственной (симметричной) по отношению к прямой задаче, сформулированной во втором параграфе данной главы. Однако, правильным будет и обратное утверждение, т.к. обе задачи равноправны. Переменные двойственной задачи называются объективно обусловленными оценками.
Прямая и обратная задачи линейного програмирования связаны между собой теоремами двойственности.
Первая теорема двойственности. Если обе задачи имеют допустимые решения, то они имеют и оптимальное решение, причем значение целевых функций у них будет одинаково:
F(x)=Z(y) или .
Если же хотя бы одна из задач не имеет допустимого решения, то ни одна из них не имеет оптимального решения.
Вторая теорема двойственности (теорема о дополняющей нежесткости). Для того чтобы векторы были оптимальными решениями соответственно прямой и двойственной задачи, необходимо и достаточно, чтобы выполнялись следующие условия:
Следствие1.Пусть оптимальное значение некоторой переменной двойственной задачи строго положительно
.
Тогда из условия (1) получим:
или
Экономический смысл данных выражений можно интерпретировать в следующей редакции. Если объективно обусловленная оценка некоторого ресурса больше нуля (строго положительна), то этот ресурс полностью (без остатка) расходуется в процессе выполнения оптимального плана.
Следствие2. Пусть для оптимального значения некоторой переменной xi прямой задачи выполняется условие строгого неравенства
.
Тогда основываясь на том же первом условии (1) можно заключить, что yi=0.
Экономически это означает, что если в оптимальном плане какой-то ресурс используется не полностью, то его объективно обусловленная оценка обязательно равна нулю.
Дата добавления: 2016-05-30; просмотров: 1739;