Simplex Method¶

Definition¶

The simplex method solves an LP by moving between basic feasible solutions through basis exchanges. In the course's maximization tableau convention, start with a feasible basis, test the objective row (optimality test), select an improving entering variable, apply the minimum-ratio test to select a leaving variable, pivot, and repeat until optimality or unboundedness is established.

Interpretation¶

The simplex method finds an optimal corner of a linear program without listing all corners. It starts at one corner and repeatedly moves to a neighbouring corner with a better objective value, stopping when no neighbour is better. Algebraically, a corner is a basic feasible solution and a move is a pivot of the tableau.

The feasible pentagon with the simplex path from the origin along the edges through two corners to the optimal corner (20, 60), with the objective value at each corner.

On the Giapetto model, $\max(3x_s+2x_t)$ $2 x_{t})$ , the path starts at the origin, where the slacks are basic and $z=0$ $0$ . Each arrow runs along an edge of the feasible region to an adjacent corner: $(40,0)$ with $z=120$ $120$ , $(40,20)$ with $z=160$ $160$ , and $(20,60)$ with $z=180$ $180$ , where the optimality test is passed. The corner $(0,80)$ is never visited.

The entering variable rule picks a nonbasic variable whose increase improves $z$ ; the minimum-ratio test determines how far it can increase before a basic variable would turn negative, and that variable leaves. If no variable improves $z$ , the solution is optimal; if an improving variable can increase without limit, the LP is unbounded. Searching corners suffices because a finite optimum is always attained at some corner (corner-point optimality).

The method needs a feasible starting basis; when none is obvious, as with $\ge$ or $=$ constraints, the two-phase method finds one. A pivot never lowers $z$ in a maximization, but with step length zero it changes the basis without moving the point, a case called degeneracy.

Key Results¶

The elementary starting form uses equality constraints, nonnegative right-hand sides, and nonnegative variables.
A slack basis starts the method for $\le$ constraints with nonnegative right-hand sides.
The two-phase method supplies a feasible basis when one is not immediately available.
Degenerate pivots can change the basis without moving the decision vector.

Examples¶

For maximization, a feasible pivot does not decrease the objective. Degenerate pivots may leave it unchanged; an anti-cycling rule is needed to guarantee termination rather than relying only on the finite number of bases.

The two-variable example visits $(0,0)$ , $(5,0)$ , and $(3,4)$ , with values 0, 15, and 17.
The three-variable example ends at $(0,5,4)$ with value 33.

Prerequisites¶

Sources¶

OR Modelling · Week 2

Aliases: simplex algorithm, primal simplex method

Last updated: 20 October 2026 03:02