5.3 Complementary slackness
Theorem 5.3.1 (Complementary slackness). Feasible \(x\) for (P) and \(y\) for (D) are both optimal if and only if \[ y_i\bigl (b_i - (Ax)_i\bigr ) = 0 \text { for every } i, \qquad x_j\bigl ((A^{\mathsf T}y)_j - c_j\bigr ) = 0 \text { for every } j . \]
Proof. In the proof of weak duality, \(b^{\mathsf T}y - c^{\mathsf T}x = y^{\mathsf T}(b - Ax) + x^{\mathsf T}(A^{\mathsf T}y - c)\), a sum of non-negative terms. It is zero, which by strong duality is optimality, if and only if every term is zero. □
In words: a resource that is not fully used has price zero, and a resource with a positive price is fully used; a product that is made just breaks even at the dual prices, and a product that would lose money at those prices is not made. In Example 5.1.1 the third constraint has slack \(3\) at the optimum, so \(y_3 = 0\), and both products are made, so both dual constraints are tight: \(2y_1 + 2y_2 = 10\) and \(y_1 + 4y_2 = 15\), which give \(y = (\frac 53, \frac {10}3, 0)\) without solving the dual. This is the usual way to recover dual solutions by hand, and to check that a proposed solution is optimal.
Questions on this section
Stuck on something here? Ask below and it stays attached to this topic.