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

Достаточный признак оптимальности взаимно двойственных задач ЛП: пусть x ≥ 0, Ax ≤ b (primal feasible) и y ≥ 0, A^T y ≥ c (dual feasible). Если c^T x = b^T y, то x и y являются оптимальными решениями primal и dual соответственно (по слабой двойственности).

Эквивалентно: пары x, y удовлетворяют условиям комплементарной слепоты:

• y_i (b_i − (A x)_i) = 0 для всех i,
• x_j ((A^T y)_j − c_j) = 0 для всех j.