With two variables, a linear programming problem is solved by drawing the feasible region and evaluating the objective at its vertices. With fifty variables and thirty constraints nothing can be drawn, and the vertices can be astronomically many. We need a method that visits only the useful vertices.
The simplex method, developed by George Dantzig in the late 1940s, does exactly that: it starts from a vertex of the feasible region and moves along the edges towards ever better adjacent vertices, until it finds one from which no move improves the objective. Since the region is convex, that vertex is the global optimum.
First step: standard form
The simplex method works with equalities. Each «less than or equal» constraint is transformed by adding a slack variable, which measures how much of the resource remains unused. Let us go back to the tables problem:
maximise 60x + 40y
2x + y + s1 = 100
x + y + s2 = 80
x, y, s1, s2 ≥ 0
s1 is the unused carpentry hours, s2 the unused painting hours. With x = y = 0 we get s1 = 100 and s2 = 80: this is the starting vertex, that is, «make nothing».
Basic and non-basic variables
At each vertex some variables are zero (the non-basic ones) and the others are obtained from the equations (the basic ones). The number of basic variables equals the number of constraints. At the start the basic variables are s1 and s2; x and y are zero.
Moving to an adjacent vertex means bringing a non-basic variable into the basis and taking a basic one out. This operation is called a pivot.
The tableau and the pivot rules
The data is arranged in a table, the tableau. The last row holds the objective coefficients with their sign changed, which show how much the profit would improve by increasing each variable.
| Basis | x | y | s1 | s2 | Value |
|---|---|---|---|---|---|
| s1 | 2 | 1 | 1 | 0 | 100 |
| s2 | 1 | 1 | 0 | 1 | 80 |
| Objective | −60 | −40 | 0 | 0 | 0 |
Who enters? Choose a variable with a negative coefficient in the objective row; the classic rule picks the most negative. Here x enters: each kitchen table is worth 60.
Who leaves? Increase x until a constraint stops it. For each row with a positive coefficient in x's column, compute the ratio value / coefficient: 100/2 = 50 and 80/1 = 80. The minimum is 50, in the row of s1: carpentry runs out first. s1 leaves. This minimum ratio test guarantees that we stay inside the feasible region.
After the pivot, using ordinary row operations, we get x = 50, y = 0, profit 3,000. In the objective row the coefficient of y is still negative (−10): it pays to bring y in. The ratio test makes s2 leave. The new vertex is x = 20, y = 60, with profit 3,600. Now all coefficients in the objective row are non-negative: no variable would improve the result, and the algorithm stops.
In the final objective row the coefficients of s1 and s2 are both 20: these are the shadow prices of the two resources, read directly from the tableau.
Finding a starting vertex
In the example the initial vertex was obvious. With «greater than or equal» constraints or equalities, the origin may not be feasible. The two-phase method is then used: in the first phase artificial variables are added and an auxiliary problem is solved that pushes them to zero. If this succeeds, you have a feasible vertex from which to start the real problem; if it fails, the original problem is infeasible.
Special cases
- Unbounded problem: the entering variable has no positive coefficients in its column, so no constraint stops it. The objective can grow without limit.
- Multiple solutions: at the optimum a non-basic variable has a zero coefficient in the objective row. Bringing it in leads to another vertex with the same value.
- Degeneracy: a basic variable is zero. A pivot may not improve the objective and, in rare cases, the algorithm can go round in circles among the same bases. Bland's rule, which always chooses the variable with the lowest index among the eligible ones, prevents these cycles.
How fast it is
There are examples built on purpose in which the simplex method visits a number of vertices that grows exponentially with the size of the problem. In practice, however, the number of pivots usually grows moderately with the number of constraints, and the simplex method remains one of the most widely used algorithms for LP. There are also interior-point methods, which cross the interior of the region instead of walking along the edges and have polynomial-time guarantees; modern solvers offer both approaches.
A practical reason why the simplex method remains central is the warm start: if a constraint is added or a coefficient changes, you can restart from the last basis instead of from scratch. This is essential in integer programming algorithms, which solve thousands of almost identical linear programs.
In short
- The simplex method walks between adjacent vertices of the feasible region, improving the objective at every step.
- Slack variables turn constraints into equalities and provide the initial vertex.
- At each pivot a variable that improves the objective enters and the one indicated by the minimum ratio test leaves.
- The two-phase method finds a starting point or proves infeasibility.
- Unboundedness, multiple solutions and degeneracy can be recognised directly from the tableau.
