= Solution
{c}
The <complementary slackness> conditions are
$$
\boxed{y_i\bigl(b_i-(A\mathbf x)_i\bigr)=0\quad(1\le i\le m),\qquad
x_j\bigl((A^T\mathbf y)_j-c_j\bigr)=0\quad(1\le j\le n).}
$$
To see their role, decompose the <duality gap> as
$$
\mathbf b^T\mathbf y-\mathbf c^T\mathbf x
=\sum_i y_i\bigl(b_i-(A\mathbf x)_i\bigr)
+\sum_j x_j\bigl((A^T\mathbf y)_j-c_j\bigr).
$$
Every summand is nonnegative for <feasible solutions>, so the gap is zero exactly when every displayed product vanishes. Zero gap implies optimality by <weak duality>. Conversely, <strong duality> states that primal and dual optima, when both are attained, have equal values, and hence satisfy these conditions.
Back to article page
