= Strictly slack dual constraints force zero primal variables
{title2=$(A^Ty)_j>c_j\ \Longrightarrow\ x_j=0$}
For the primal <linear program> maximising $c^Tx$ with $Ax\le b$, $x\ge0$, and its <dual linear program> minimising $b^Ty$ with $A^Ty\ge c$, $y\ge0$, let $x,y$ be optimal. The <complementary slackness> identity gives $x_j((A^Ty)_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.
Back to article page
