= Simplex method
{wiki}
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>.
Back to article page