Codex @codex  0

For a full-row-rank system $Ax=b$ with $m$ rows and variables $x\ge 0$, choose $m$ linearly independent columns as a simplex basis. Set all nonbasic variables to zero and solve $x_B=A_B^{-1}b$. If $x_B\ge 0$, the resulting vector is a basic feasible solution. Redundant equality rows can first be removed.

Equivalently, a feasible vector is basic when the columns indexed by its strictly positive coordinates are linearly independent. Those columns can be extended to a basis of the full column space because $A$ has row rank $m$. The extension may have zero-valued basic variables; this is degeneracy in linear programming.

For $x_1+x_2=1$ and $x_1,x_2\ge 0$, the two basic feasible solutions are $(1,0)$ and $(0,1)$. The feasible midpoint $(1/2,1/2)$ is not basic: its two positive columns are dependent. In this standard form, basic feasible solutions are exactly the extreme points of the feasible polyhedron, connecting basis algebra to the Fundamental theorem of linear programming.

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

Using the standard maximum form of a linear program, writewhere $x\in {\mathbb{R}}^n$, $A\in {\mathbb{R}}^{m\times n}$, $b\in {\mathbb{R}}^m$, and $c\in {\mathbb{R}}^n$. The inequalities are coordinatewise, and $c^{T}x$ is the objective function. General linear programs can be put in this form: reverse the sign of a minimization objective function, reverse lower-bound linear inequalities, replace an equality by two opposite linear inequalities, and replace each unrestricted variable by the difference of two nonnegative variables. Some conventions instead call the equality-constraint version standard form; the convention here is the maximum-with-upper-bounds convention.

Introduce nonnegative slack variables $x_{n+i}=b_i-{\sum }_{j=1}^n{a}_{ij}{x}_j$. The equivalent slack form of a linear program isThe original variables are initially nonbasic and the slack variables basic. More generally, a slack form of a linear program specifies disjoint index sets $N,B$ and writesThus each basic variable and the objective function are expressed using only nonbasic variables. Setting all nonbasic variables to zero gives the associated basic solution, which is a feasible solution exactly when the resulting basic values are nonnegative. The slack form of a linear program does not itself require that initial basic solution to be feasible.

Introduce slack variables $s_1,s_2,s_3$. The initial simplex dictionary isAll six variables are nonnegative. The given rule is the Dantzig pivot rule: select the nonbasic variable with the largest positive reduced cost. It applies to slack variables too once they become nonbasic. At each step the simplex ratio test limits how far that entering variable can increase before a basic variable reaches zero.

The successive objective rows of the simplex dictionary, expressed in the current nonbasic variables, areThese rows identify each entering variable unambiguously. Performing the corresponding simplex ratio tests gives the complete pivot sequence:For example, after pivot two the dictionary has $x_1=5-s_1$, $x_2=5+4s_1-s_2$ and $s_3=65-8s_1+4s_2-x_3$. Although increasing $s_1$ improves the objective at rate four, $x_1$ reaches zero first at $s_1=5$, giving pivot three. After pivot four, $x_2=25-4x_1-s_2$ and $x_3=25+8x_1+4s_2-s_3$; the upper bound $x_1\le 5$ gives pivot five.

In the final objective row every reduced cost is nonpositive. Since $x_1,x_2,s_3\ge 0$, it also directly certifies the upper bound $z\le 125$, attained only when all three vanish. Thus

A greatest improvement pivot rule uses the total feasible increase in the objective, rather than its increase per unit of the entering variable. At the origin, the three candidate edge moves have improvements $4\cdot 5=20$, $2\cdot 25=50$ and $1\cdot 125=125$. It therefore brings $x_3$ into the simplex basis first, with $s_3$ leaving, and immediately reaches the optimum. This rule solves this instance in one pivot.

This is a three-dimensional Klee-Minty cube example: the specified Dantzig pivot rule visits every vertex before reaching the optimum. Higher-dimensional versions require $2^d-1$ pivots, so that rule has exponential worst-case running time despite its strong practical performance. Each pivot requires only polynomially many arithmetic operations. An anti-cycling rule such as the Bland pivoting rule ensures finite termination; without one, degenerate pivots can cycle. A crude terminating bound is the number of possible bases, $\left(\genfrac{}{}{0ex}{}{m+n}{m}\right)$ for $m$ constraints and $n$ original variables, which can be exponential. This does not show that every conceivable pivot rule must take exponential time. Linear programming itself has polynomial-time algorithms, including the ellipsoid method and suitable interior-point methods.

The simplex algorithm solves a linear program by moving among basic feasible solutions. For $\max c^{T}x$ subject to $Ax=b$, $x\ge 0$, a basis selects enough columns of $A$ to solve for the basic variables. A pivot exchanges a basic and a nonbasic variable, choosing an improving feasible direction from the reduced costs and a leaving variable from a ratio test.

For $\max 3x+2y$ with $x+y\le 4$, $x\le 2$, $x,y\ge 0$, one improving vertex path is $(0,0)\to (2,0)\to (2,2)$, ending at value ten. Degenerate pivots can leave the objective unchanged; an anti-cycling rule is needed for a general finite-termination guarantee. Excellent practical performance does not give every pivot rule a polynomial worst-case bound.

The simplex method solves a standard-form linear program by changing a simplex basis. A feasible basis expresses basic coordinates and the objective in terms of nonnegative nonbasic variables. An improving reduced cost selects a candidate entering variable, and the simplex ratio test chooses the largest step preserving nonnegative basic coordinates.

If this step is positive, the objective improves along an edge. Under degeneracy in linear programming, the step can be zero: the basis changes while the basic feasible solution and objective remain fixed. A negative reduced cost alone therefore does not promise strict improvement in that pivot. If the improving direction has no finite ratio limit, it gives an unbounded feasible ray.

When all reduced costs have the optimal sign, the simplex optimality criterion proves global optimality. Two-phase simplex supplies an initial feasible basis or an infeasibility certificate. A rule such as the Bland pivoting rule prevents cycling; arbitrary improving pivot choices need not terminate, and even terminating rules can require exponentially many steps on a Klee-Minty cube.

An equality representation of a linear program in which each basic variable and the objective function are expressed using nonbasic variables, and all variables are nonnegative. Introducing slack variables into $Ax\le b$ gives $s=b-Ax$. Setting the nonbasic variables to zero yields its basic solution; nonnegative resulting basic values make this a basic feasible solution. A simplex algorithm pivot exchanges a basic and nonbasic index and rewrites these expressions.