Complementary slackness

At a primal-dual optimum, each positive variable corresponds to a tight dual constraint and conversely for positive dual variables.

For the linear program maximizing $c^{T}x$ subject to $Ax=b$, $x\ge 0$, let $x^{\ast }$ be optimal and let $y^{\ast }$ be an optimal dual linear program solution. Complementary slackness makes $A_j^T{y}^{\ast }=c_j$ on every positive coordinate of $x^{\ast }$. Any nonnegative $\hat{x}$ supported on those coordinates therefore hasThe same $y^{\ast }$ is dual feasible when the right-hand side is changed to $\hat{b}=A\hat{x}$. Equality of feasible objectives and weak duality prove optimality of $\hat{x}$ for that modified problem.

There is also a direct primal proof. If $z\ge 0$ had $Az=A\hat{x}$ and $c^{T}z>c^T\hat{x}$, then $x^{\ast }+\epsilon (z-\hat{x})$ would remain feasible and nonnegative for sufficiently small $\epsilon >0$. On zero coordinates of $x^{\ast }$, support inclusion makes its perturbation nonnegative; on positive coordinates, smallness preserves positivity. Its objective would improve, contradicting optimality of $x^{\ast }$.

For the primal linear program maximising $c^{T}x$ with $Ax\le b$, $x\ge 0$, and its dual linear program minimising $b^{T}y$ with $A^{T}y\ge c$, $y\ge 0$, let $x,y$ be optimal. The complementary slackness identity gives $x_j((A^{T}y{)}_j-c_j)=0$. Thus a strict inequality in the $j$th dual constraint forces $x_j=0$. One optimal dual feasible solution can therefore force zero components in every primal optimum. The same argument with roles reversed says that $y_i>0$ forces the $i$th primal constraint to be an equality.