Complementary slackness and sensitivity

For the primal maximization form $Ax\le b$, $x\ge0$ and dual $A^Ty\ge c$, $y\ge0$, expand the gap as $y^T(b-Ax)+x^T(A^Ty-c)$. Every summand is nonnegative at a feasible pair. Therefore a zero gap is equivalent to every product being zero. A positive dual price forces its resource constraint to be tight. A positive primal activity forces its corresponding dual inequality to be tight. These implications are one-way: a tight constraint need not carry a positive price, and an activity with zero reduced profit need not be used.

Complementary slackness is necessary and sufficient for optimality of a primal-dual feasible pair. Dropping the feasibility condition breaks the theorem because positive and negative terms could cancel or the proposed points could lie outside their domains. In practice one can guess the support of an optimizer, solve the resulting equalities for primal and dual variables, then verify all remaining signs and inequalities. This converts intuition about active resources into a rigorous certificate. If any sign check fails, the guessed support was not justified, even when the resulting objective looks attractive.

Let $v(b)$ be the optimal maximization value when only the resource vector changes and the other data remain fixed. Every dual feasible $y$ gives $v(b')\le b'^Ty$ whenever the perturbed primal is feasible. If $y^*$ is optimal at $b$, this becomes $v(b')\le v(b)+y^{*T}(b'-b)$. Thus an optimal price is a supergradient of the concave value function on its feasible domain. Equality for a finite perturbation requires that the same dual certificate remain optimal; the bound alone does not promise a constant marginal price forever.

A convenient sufficient check uses a fixed standard-form basis. Right-hand-side perturbations change its basic coordinates to $B^{-1}(b+\Delta b)$, while reduced costs remain unchanged because $A$ and $c$ do not change. If the old basis was dual feasible and the new basic vector stays nonnegative, it remains optimal. The new value is exactly affine over that basis's feasibility region. At its boundary a basic variable reaches zero; beyond it a different basis may take over, the model may become infeasible, or multiple prices may describe a kink.

Objective perturbations reverse the bookkeeping: a fixed basis keeps the same primal coordinates when $A$ and $b$ are unchanged, but its reduced costs change. For maximization, their required sign is nonpositive after eliminating the basic variables. Equivalently, solve $B^Ty=c_B$ for the basis price vector and check every inequality $A_N^Ty\ge c_N$. This gives inequalities in the perturbed cost coefficients. As long as they hold, the original feasible basis remains optimal. At equality, another activity may become competitive and alternate optima may appear.

Sensitivity reports should specify which parameters change jointly. Separate one-at-a-time allowable ranges cannot generally be combined into a rectangular region of simultaneous validity. Degeneracy can produce several optimal bases and several dual solutions; a solver's single reported price may describe only one supporting bound at a nondifferentiable value function. Units matter as well: a price is objective units per resource unit, so rescaling a constraint rescales its multiplier. These qualifications turn a solver printout into an interpretable model rather than a collection of apparently universal marginal values.