= Support-preserving right-hand-side changes in linear programming
{title2=$x^*\text{ optimal},\ \operatorname{supp}\widehat x\subseteq\operatorname{supp}x^*,\ \widehat x\geq0\implies\widehat x\text{ optimal for }A\widehat x$}
For the <linear program> maximizing $c^Tx$ subject to $Ax=b$, $x\geq0$, let $x^*$ be optimal and let $y^*$ be an optimal <dual linear program> solution. <Complementary slackness> makes $A_j^Ty^*=c_j$ on every positive coordinate of $x^*$. Any nonnegative $\widehat x$ supported on those coordinates therefore has
$$
c^T\widehat x=(y^*)^TA\widehat x.
$$
The same $y^*$ is dual feasible when the right-hand side is changed to $\widehat b=A\widehat x$. Equality of feasible objectives and <weak duality> prove optimality of $\widehat x$ for that modified problem.
There is also a direct primal proof. If $z\geq0$ had $Az=A\widehat x$ and $c^Tz>c^T\widehat x$, then $x^*+\varepsilon(z-\widehat x)$ would remain feasible and nonnegative for sufficiently small $\varepsilon>0$. On zero coordinates of $x^*$, support inclusion makes its perturbation nonnegative; on positive coordinates, smallness preserves positivity. Its objective would improve, contradicting optimality of $x^*$.
Back to article page
