= Solution
{c}
Let $x^*=(0,3,4,0,5)^T$. By <strong duality>, an optimal dual vector $y^*$ exists. <Complementary slackness> at $x^*$ makes the dual constraints equalities at indices $2,3,5$, where $x_j^*>0$. The vector $\widehat x=(0,1,2,0,3)^T$ has exactly that same support. It is nonnegative and satisfies $A\widehat x=\widehat b$, while $y^*$ remains dual feasible because dual feasibility depends on $A,c$, not on the right-hand side. Hence
$$
c^T\widehat x=(A^Ty^*)^T\widehat x=\widehat b^Ty^*.
$$
The objective gap is zero, so \b[$\widehat x$ is optimal for the modified programme]. This is <support-preserving right-hand-side changes in linear programming>.
Back to article page
