Simplex method

The simplex method moves between adjacent basic feasible solutions along improving edges of a feasible polytope until no improving pivot remains.

In a feasible minimization simplex dictionary, the nonbasic variables are nonnegative. If every reduced cost ${\bar{c}}_j\ge 0$, the displayed objective identity proves $z\ge z_0$ for every feasible point. Thus the current basic feasible solution is globally optimal. If all reduced costs are strictly positive, equality forces every nonbasic variable to vanish and gives a unique basic solution, provided the dictionary determines all basic variables.

For a feasible simplex dictionary, let $r_j>0$ be a nonbasic variable's improving reduced cost and let ${\theta }_j$ be its largest feasible increase from the simplex ratio test. The greatest improvement pivot rule chooses an entering variable maximizing $r_j{\theta }_j$. It measures the improvement over the entire edge, whereas the Dantzig pivot rule maximizes only $r_j$.

// Target: mathematical-optimization.bigb

In maximization, select the entering nonbasic variable with greatest positive reduced cost, meaning objective increase per unit of that variable. Unlike geometric steepest-edge pricing, this rate depends on variable and constraint scaling. A rescaled Klee-Minty cube can give the same $2^n-1$-pivot path as smallest-index improving-facet pivoting.

For $0<\epsilon <1/2$, these inequalities define a deformed cube with $2^n$ vertices of a polytope. Choose either the lower or upper bound recursively at each coordinate to obtain a vertex of a polytope; changing one choice gives an adjacent vertex of a polytope. When maximizing $x_n$, smallest-index improving-facet pivoting visits all $2^n$ vertices of a polytope: first traverse the lower last-coordinate face, then move to the upper face and traverse the preceding path in reverse. Thus this geometric version of the Bland pivoting rule can require $2^n-1$ pivots. Rescaling the coordinate $x_i$ to $y_i={\epsilon }^{2(n-i)}{x}_i$ makes the positive rate per unit freed coordinate equal to ${\epsilon }^{-(n-i)}$; Dantzig pivot rule then selects the same exponential path. Euclidean edge-length pricing is a different rule.

A simplex tableau records the canonical constraint equations for a simplex basis and the canonical objective equation. For maximization use $z+{\sum }_j{\rho }_j{x}_j=z_0$, so a negative nonbasic objective-row coefficient is an improving direction. Constraint rows have an identity matrix in the basic columns. A simplex method pivot divides the leaving row by the pivot coefficient and eliminates the entering column from the other rows, including the objective row. The simplex ratio test chooses the largest feasible step. When all basic values and all ${\rho }_j$ are nonnegative, the objective equation directly proves $z\le z_0$ for every nonnegative feasible vector.

For a maximization problem with unpriced unit slack variables, their columns in a final simplex tableau give $B^{-1}$, where $B$ consists of the original basic columns. The constraint right side is $\bar{b}=B^{-1}b$, so $b=B\bar{b}$. If the objective row uses reduced costs $r_j=c_j-c_B^T{B}^{-1}{A}_j$, its slack entries are $-y^T$ with $y^T=c_B^T{B}^{-1}$. Therefore $c_B^T=y^{T}B$. In a homogeneous linear objective with no constant offset, the displayed basic objective value must equal $c_B^T\bar{b}=y^{T}b$. This identity detects inconsistent tableau constants; an affine offset affects the value but not the reduced costs.

If a variable $x_k$ gains an objective coefficient $p$, the new objective is $z=z_{\mathrm{old}}+p{x}_k$. Substitute this in the old canonical objective equation and eliminate any remaining basic-column coefficients using the constraint rows. If $x_k$ is nonbasic, this simply subtracts $p$ from its objective-row coefficient. When a slack variable is sold, rename the old slack as the sales quantity; its equation already gives the correct equality and no new slack is added. Reoptimization can then start directly from the altered simplex tableau.

For a maximization simplex dictionary, choose the smallest-index nonbasic variable with positive reduced cost to enter. Among basic variables attaining the minimum feasible ratio, choose the smallest-index one to leave. This fixed index rule prevents cycling, including in degenerate pivots whose step length is zero. It need not minimize the number of pivots on a particular instance.

Phase I introduces nonnegative artificial variables to create a feasible basis and minimizes their sum, or maximizes its negative. A positive minimum proves infeasibility. At a zero minimum, remove artificial variables and use the resulting feasible original basis in Phase II with the original objective. If an artificial variable remains basic at zero, pivot it out when possible; otherwise its row is redundant. Each phase uses the simplex ratio test to preserve nonnegative basic values.

In a feasible simplex basis, increasing a nonbasic variable by $\theta$ changes basic coordinates to $x-\theta d$. Nonnegativity limits $\theta$ by the smallest ratio $x_i/d_i$ with $d_i>0$; a minimizing coordinate leaves the basis. Ties can leave zero-valued basic variables. This pivot test is distinct from the analytic ratio test for series convergence.

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.

For $0\le x_i\le 1$, $x_1+x_2+x_3\le 5/2$, and objective $x_1+2x_2+4x_3$, the oriented edge graph has eight improving paths from the origin to the unique optimum $(1/2,1,1)$. Their lengths range from three to five pivots.