Linear Programming - Complementary Slackness

Complementary Slackness

It is possible to obtain an optimal solution to the dual when only an optimal solution to the primal is known using the complementary slackness theorem. The theorem states:

Suppose that x = (x₁, x₂, ..., x_n) is primal feasible and that y = (y₁, y₂, ..., y_m) is dual feasible. Let (w₁, w₂, ..., w_m) denote the corresponding primal slack variables, and let (z₁, z₂, ..., z_n) denote the corresponding dual slack variables. Then x and y are optimal for their respective problems if and only if

• x_j z_j = 0, for j = 1, 2, ..., n, and
• w_i y_i = 0, for i = 1, 2, ..., m.

So if the i-th slack variable of the primal is not zero, then the i-th variable of the dual is equal to zero. Likewise, if the j-th slack variable of the dual is not zero, then the j-th variable of the primal is equal to zero.

This necessary condition for optimality conveys a fairly simple economic principle. In standard form (when maximizing), if there is slack in a constrained primal resource (i.e., there are "leftovers"), then additional quantities of that resource must have no value. Likewise, if there is slack in the dual (shadow) price non-negativity constraint requirement, i.e., the price is not zero, then there must be scarce supplies (no "leftovers").