Теоремы двойственности. Нахождение двойственных оценок

Теоремы двойственности позволяют установить взаимосвязь между оптимальными решениями пары двойственных задач.

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

Следствие 1. Если целевая функция одной из пары двойственных задач не ограничена на множестве допустимых планов (например, или ), то система ограничений другой задачи противоречива (т.е. задача не имеет решения).

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

Теорема 1.2 Для оптимальности допустимых решений и пары двойственных задач необходимо и достаточно, чтобы они удовлетворяли системе уравнений

Таким образом: Если при подстановке компонент оптимального плана в систему ограничений исходной задачи i -е ограничение обращается в неравенство, то i – я компонента оптимального плана двойственной задачи равна нулю.

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