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 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

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.

For this tableau sign convention, a negative coefficient in the objective row means the corresponding nonbasic variable can increase profit. Initially $x_3$ has the most negative coefficient. The simplex ratio test gives $33/5$ in row one and $18/3=6$ in row two, so row two leaves to preserve feasibility. Next $x_1$ is the only column with a negative objective coefficient. The ratios are $3/(1/3)=9$ and $6/(1/3)=18$, so row one leaves. All resulting basic variables remain nonnegative.

In the usual linear programming sensitivity within a fixed optimal basis, retain the optimal basis $\{x_1,x_3\}$ while allowing its values to adjust. If the second resource amount is $b$, thenThe dual prices remain $(1,1)$, so optimality persists exactly while both basic variables are nonnegative:The optimal profit on that range is $33+b$. At the endpoints the basis is degenerate but remains optimal. If the wording is instead read as requiring the exact numerical production vector $(9,0,3)$ to remain unchanged and optimal, only $b=18$ does so; the standard allowable range concerns the basis and its adjusted solution.

At the current dual prices $(1,1)$, the new product has reduced cost $5-(1+2)=2>0$, so it can increase profit. Its transformed resource column isIncreasing $x_4$ by $t$ changes the old basic variables to $x_1=9+7t$ and $x_3=3-3t$. Thus $x_3$ leaves at $t=1$, givingFor a certificate, take dual prices $(1/3,7/3)$. They price the four products at $3,17/3,26/3,5$, respectively, each at least its profit. Their resource total is $33/3+18(7/3)=53$, equal to the achieved profit. Weak duality proves optimality, and the profit has increased by two.

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.

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.