Двойственность в задачах линейного программирования.

Рассмотрим задачу линейного программирования со смешанными ограничениями (0.10) - (0.13) Будем называть задачу (0.10) - (0.13) прямой задачей линейного программирования.

Двойственной задачей к задаче (0.10) - (0.13) называется задача линейного программирования минимизации по переменным u R линейного функционала

при линейных ограничениях

A^T₁₁u₁ + A^T₂₂u₂ = c₂,═══════════

(0.15)

A^T₁₂u₁ + A^T₂₁u₂ ≥ c₁,═

(0.16)

u₁ ≥ 0,═══════════

(0.17)

Здесь через A^T обозначается матрица, полученная транспонированием матрицы A

Теорема 4.1 (двойственности). Для того, чтобы задача линейного программирования (0.10) - (0.13) имела решение необходимо и достаточно, чтобы имела решение двойственная задача (0.14) - (0.17). В случае существования решений оптимальные значения функционалов в этих задачах совпадают.

Теорема 4.2 (критерий оптимальности). Пусть (x₁, x₂) удовлетворяют ограничениям (0.11)-(0.13), (u₁, u₂) удовлетворяют ограничениям (0.15) - (0.17) . Для того, чтобы (x₁, x₂) являлись решением задачи (0.10) - (0.13) , а (u₁, u₂) являлись решениыми задачи (0.14) - (0.17), необходимо и достаточно, чтобы выполнялись следующие условия, называемые условиями дополняющей нежесткости :

u₁(A₁₁x₁ + A₁₂x₂ - b₁) = 0,

x₁(A^T₁₁ + A^T₂₁ u₂ - c₁) = 0.

Определение 4.1. Функцией Лагранжа задачи линейного программирования (0.10) - (0.13) называется функция