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

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

Обе задачи обладают следующими свойствами:

1. В одной задаче ищут максимум линейной функции, в другой – минимум.

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

3. В задаче максимизации система ограничений имеет все неравенства вида “≤”, а в задаче минимизации – все неравенства вида “≥”.

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

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

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

Общий вид двойственной пары задач в табл.5.

Таблица 5.

Соответствие прямой и двойственной задач ЛП