= Simplex algorithm
{wiki}
The <simplex algorithm> solves a <linear program> by moving among <basic feasible solutions>. For $\max c^Tx$ subject to $Ax=b$, $x\geq0$, 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\leq4$, $x\leq2$, $x,y\geq0$, 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.
Back to article page