 Support-preserving right-hand-side changes in linear programming

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 }$.