Simplex basis

For standard-form linear programming constraints $Ax=b$ of full row rank, a simplex basis is a set of columns forming an invertible square matrix $B$. The remaining variables are nonbasic; setting them to zero gives the basic solution $x_B=B^{-1}b$. It is feasible if these basic variables are nonnegative. A pivot exchanges one basic and one nonbasic column while maintaining this representation.

A nonbasic variable corresponds to a column outside the current simplex basis. In standard nonnegative linear programming, it is set to zero at the basic solution. With explicit finite bounds, it is normally fixed at one of its bounds.

// Target: mathematical-optimization.bigb

A basic variable corresponds to a column of the current simplex basis. Given the nonbasic variables, the invertible basis matrix determines the basic variables from the equality constraints.

// Target: mathematical-optimization.bigb

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.