Свойства двойственных задач

1. Если целевая функция исходной задачи формулируется на максимум, а целевая функция двойственной задачи – на минимум, при этом в задаче на максимум все неравенства в ограничениях приводят к виду “ ”, а в задаче на минимум – вид “ ”.

2. Матрица, составленная из коэффициентов при неизвестных в системе ограничений исходной задачи, и аналогичная матрица в двойственной задаче являются транспонированными по отношению друг к другу.

3. Число переменных в двойственной задаче равно числу ограничений исходной задачи, а число ограничений двойственной задачи – числу переменных в исходной задаче.

4. Коэффициентами при неизвестных в целевой функции двойственной задачи являются свободные члены в системе ограничений исходной задачи.

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

6. Предполагается, что переменные в обеих задачах являются неотрицательными.

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

Замечание.

Двойственная задача к двойственной будет исходной.

Замечание.

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

Между взаимно двойственными ЗЛП имеет место взаимосвязь, которая следует из теорем двойственности.