 Simplex algorithm

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 algorithm is a widely used method for solving linear programming problems, which are mathematical optimization problems where the objective is to maximize or minimize a linear function subject to a set of linear constraints. Developed by George Dantzig in the 1940s, the Simplex algorithm efficiently finds the optimal solution by moving along the edges of the feasible region defined by the constraints.