Linear programming sensitivity within a fixed optimal basis ($v(b+ϵ)=y^T(b+ϵ)$)

For a linear program with unchanged cost and constraint matrix, an optimal simplex basis remains optimal while its basic solution remains feasible. Its reduced costs and dual certificate do not change. The new basic variables are $A_B^{-1}(b+ϵ)$, and the objective is the displayed affine function, with $y$ the basis's dual solution. This gives an exact piecewise-affine sensitivity region, determined by nonnegativity of the basic variables, rather than merely a formal first derivative.

For a square invertible constraint matrix $A$ in $\max \{c^{T}x:Ax\le b,x\ge 0\}$, suppose $y>0$ and $A^{T}y=c$. This fixed dual vector stays optimal under a changed right-hand side $b^{\prime }$ exactly when $A^{-1}{b}^{\prime }\ge 0$. 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}^{\prime }$. The inequalities define the whole validity cone, including degenerate boundary optima.