= Solution
The dual constraints and objective coefficients on $x$ are unchanged, so $y^*$ remains dual feasible. Since every component of $y^*$ is positive, complementary slackness forces every constraint of any primal optimum paired with it to bind. Let $A$ be the original three-by-three constraint matrix and $b'=b+\epsilon$. It is invertible, and the only possible paired primal point is
$$
x'=A^{-1}b'=\begin{pmatrix}7+(2\epsilon_1+4\epsilon_2+5\epsilon_3)/33\\22-\epsilon_1/3+\epsilon_2+\epsilon_3/3\\1+(-4\epsilon_1+3\epsilon_2+\epsilon_3)/33\end{pmatrix}.
$$
If this point is nonnegative, it is primal feasible with zero slacks and $c^Tx'=y^{*T}b'$, proving $y^*$ optimal. Conversely, if $y^*$ is optimal, <linear programming duality> supplies a paired primal optimum, and complementary slackness forces it to be exactly this point. This proves the <strictly positive dual certificate and right-hand-side sensitivity> criterion:
$$
\boxed{\begin{aligned}2\epsilon_1+4\epsilon_2+5\epsilon_3&\geq-231,\\-\epsilon_1+3\epsilon_2+\epsilon_3&\geq-66,\\-4\epsilon_1+3\epsilon_2+\epsilon_3&\geq-33.\end{aligned}}
$$
Non-strict inequalities are essential: boundary cases can be degenerate but retain the same optimal dual vector. This is the complete range, not just a small-perturbation sufficient condition for <linear programming sensitivity within a fixed optimal basis>.
Back to article page
