 Complementary slackness

For the primal maximization $Ax\le b$, $x\ge 0$ and dual minimization $A^{T}y\ge c$, $y\ge 0$, a feasible pair has the nonnegative objective-gap decompositionThus equal objective values are equivalent toThese are complementary slackness. Combined with primal and dual feasibility they certify optimality by weak duality. Conversely, primal and dual optima satisfy them by strong duality.

A positive dual multiplier forces its primal constraint to be tight, and a positive primal variable forces its dual constraint to be tight. A tight constraint need not have a positive multiplier: both factors in a complementary product may be zero. This distinguishes ordinary complementary slackness from a stronger strict-complementarity assertion. In the example under linear programming, the third primal inequality is slack and its multiplier is zero.^[ref]