= Strictly positive dual certificate and right-hand-side sensitivity
For a square invertible constraint matrix $A$ in $\max\{c^Tx:Ax\leq b,x\geq0\}$, suppose $y>0$ and $A^Ty=c$. This fixed dual vector stays optimal under a changed right-hand side $b'$ exactly when $A^{-1}b'\geq0$. Sufficiency follows from primal feasibility and equal primal/dual objectives. Necessity follows from <complementary slackness>: since every $y_i$ is positive, every optimal primal constraint must bind, forcing $x=A^{-1}b'$. The inequalities define the whole validity cone, including degenerate boundary optima.
Back to article page
