3.2 Теоремы двойственности в линейном программировании

Основные утверждения о взаимно двойственных задачах содержатся в следующих теоремах.

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

.

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

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

1)

2)

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

Третья теорема двойственности (теорема об оценках). Значения переменныху_i в оптимальном решении двойственной задачи представляют собой оценки влияния свободных членов ограничений исходной задачи на экстремальное значение ее целевой функции Z_max, т.е.

.