Взаимосвязь между исходной и двойственной задачами

1) Если исходная задача является задачей максимизации, то двойственная будет задачей минимизации, и наоборот.

2) Каждому i – му ограничению системы ограничений исходной задачи ставят в соответствие переменную y_i двойственной задачи и наоборот: каждому j – му ограничению двойственной задачи ставят в соответствие x_j переменную исходной задачи.

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

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

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

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

Различают симметричные, несимметричные и смешанные двойственные задачи.

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