The simplex method

A factory scheduling problem

A factory makes two products. Each product uses machine time and labor, but in different amounts. The factory has limited resources. How do you maximize profit?

You could try every combination of products A and B, but the constraints carve out a region of feasible options. That region is a polygon. The optimal answer always sits at a corner.

The feasible region

graph TD
  A["Constraint 1: 3A + 1B <= 12 (machine hours)"]
  B["Constraint 2: 2A + 4B <= 16 (labor hours)"]
  C["Constraint 3: A >= 0, B >= 0"]
  A --> D["Feasible region: a polygon (intersection of half-planes)"]
  B --> D
  C --> D
  D --> E["Optimal solution is at a corner (vertex) of this polygon"]

The simplex method walks along the edges of this polygon, checking one corner at a time, always moving to a better corner until no better neighbor exists. It never needs to search the interior.

Now let’s see the math behind this.

Prerequisites

You should understand Lagrangian duality and the basics of linear algebra, especially matrix operations. Knowing what a convex set is will help you see why the feasible region of an LP has a nice structure.

Linear programs

A linear program (LP) minimizes a linear objective subject to linear constraints. Every LP can be written in standard form:

where $A$ is an $m \times n$ matrix with $m < n$ (more variables than constraints), $b \ge 0$, and $c \in \mathbb{R}^n$.

Any LP with inequality constraints can be converted to this form by adding slack variables. For example:

Converting to standard form

graph TD
  A["Original LP with inequalities"] --> B["Add slack variable for each <= constraint"]
  B --> C["All constraints become equalities"]
  C --> D["Standard form: min c^T x, Ax = b, x >= 0"]

Why standard form matters

The constraints $Ax = b$ define a flat surface (affine subspace) and $x \ge 0$ intersects it with the non-negative orthant. The result is a polytope: a bounded region with flat faces, edges, and vertices. The simplex method exploits the fact that the optimal solution to an LP always occurs at a vertex of this polytope (assuming the optimum exists and is finite).

Basic feasible solutions

A basic feasible solution (BFS) is a vertex of the feasible polytope. Here is the formal definition.

Given $Ax = b$ with $A$ being $m \times n$, choose $m$ columns of $A$ that form a nonsingular $m \times m$ submatrix $B$. Call these the basic columns, and the remaining $n - m$ columns are nonbasic. Set the nonbasic variables to zero and solve $Bx_B = b$ for the basic variables $x_B$. If $x_B \ge 0$, then this is a basic feasible solution.

The simplex method moves from one BFS to an adjacent one (they share $m - 1$ basic variables) by swapping one variable in and one variable out of the basis.

The simplex tableau

The simplex method is most easily tracked with a tableau. Given a current basis $B$, the tableau organizes:

• The basic variables and their values
• The reduced costs $\bar{c}_j = c_j - c_B^T B^{-1} A_j$ for each nonbasic variable
• The constraint coefficients after elimination

The algorithm:

1. Optimality check: If all reduced costs $\bar{c}_j \ge 0$ for nonbasic variables, the current BFS is optimal. Stop.
2. Pivot selection (entering variable): Choose a nonbasic variable $j$ with $\bar{c}_j < 0$. This variable will enter the basis.
3. Ratio test (leaving variable): Among basic variables, find which one hits zero first as $x_j$ increases. This is the minimum ratio test.
4. Pivot: Swap the entering and leaving variables. Update the tableau.
5. Go to step 1.

Simplex iteration at a glance

graph TD
  A["Current vertex (BFS)"] --> B["Check: all reduced costs >= 0?"]
  B -- Yes --> C["Optimal! Stop."]
  B -- No --> D["Pick entering variable (negative reduced cost)"]
  D --> E["Ratio test: find leaving variable"]
  E --> F["Pivot: move to adjacent vertex"]
  F --> A

Example 1: Solving a 2-variable LP by simplex

Problem:

subject to:

(We maximize here. To fit the “minimize” convention, negate the objective: $\min \; -5x_1 - 4x_2$.)

Step 1: Add slack variables.

Variables: $x_1, x_2, s_1, s_2$. All $\ge 0$.

Step 2: Initial BFS.

Set $x_1 = 0, x_2 = 0$. Then $s_1 = 24, s_2 = 6$. Basis = $\{s_1, s_2\}$.

Objective value: $5(0) + 4(0) = 0$.

Step 3: Compute reduced costs.

For maximization, we want to increase a variable with a positive coefficient in the objective (equivalently, negative reduced cost in the min formulation). $x_1$ has coefficient $5$ and $x_2$ has coefficient $4$. Choose $x_1$ (largest coefficient, Dantzig’s rule).

Step 4: Ratio test.

Increase $x_1$. From constraint 1: $6x_1 \le 24 \Rightarrow x_1 \le 4$. From constraint 2: $x_1 \le 6$. Minimum ratio: $\min(24/6, 6/1) = \min(4, 6) = 4$.

So $s_1$ leaves the basis, $x_1$ enters. New basis = $\{x_1, s_2\}$.

Pivot: Divide row 1 by 6:

Update row 2: subtract row 1 from row 2:

New BFS: $x_1 = 4, x_2 = 0, s_1 = 0, s_2 = 2$.

Objective: $5(4) + 4(0) = 20$.

Step 5: Check optimality.

Reduced cost for $x_2$: $4 - 5 \cdot (2/3) = 4 - 10/3 = 2/3 > 0$ (still improvable in max sense).

Reduced cost for $s_1$: $0 - 5 \cdot (1/6) = -5/6$ (not improvable).

Actually let me redo this more carefully with the tableau approach for the max problem.

Update the objective row. Original objective: $z = 5x_1 + 4x_2$. After substituting $x_1 = 4 - (2/3)x_2 - (1/6)s_1$:

$x_2$ has a positive coefficient ($2/3$), so we can improve. Enter $x_2$.

Step 6: Ratio test for $x_2$.

Row 1: $x_1 + (2/3)x_2 = 4$, so $x_2 \le 4/(2/3) = 6$.

Row 2: $(4/3)x_2 = 2$, so $x_2 \le 2/(4/3) = 3/2$.

Minimum ratio: $3/2$. So $s_2$ leaves, $x_2$ enters. New basis = $\{x_1, x_2\}$.

Pivot: Multiply row 2 by $3/4$:

Update row 1: subtract $(2/3) \times$ new row 2:

New BFS: $x_1 = 3, x_2 = 3/2, s_1 = 0, s_2 = 0$.

Objective: $z = 20 + (2/3)(3/2) - (5/6)(0) = 20 + 1 = 21$.

Check optimality. Update the objective:

Substitute $x_2 = 3/2 + (1/8)s_1 - (3/4)s_2$:

Both nonbasic variables ($s_1, s_2$) have negative coefficients. No improvement possible. Optimal!

Solution: $x_1 = 3, x_2 = 3/2$. Optimal value: $z = 21$.

Verification: $6(3) + 4(3/2) = 18 + 6 = 24$ ✓. $3 + 2(3/2) = 3 + 3 = 6$ ✓. Both constraints tight.

Vertices of the feasible region

The feasible region of the LP above is a polygon in 2D. Its vertices are the points where pairs of constraint boundaries intersect while remaining feasible:

The simplex method visited: $(0,0) \to (4,0) \to (3, 1.5)$. It walked along two edges of the polygon to reach the optimum.

The simplex method moves along vertices of the feasible polytope. Starting from (0,0), it moves to (4,0) then to the optimal vertex (3,2) where the objective 3x + 2y = 13 is maximized.

Example 2: Starting with a full tableau

Problem:

subject to:

Add slacks $s_1, s_2, s_3$:

Initial tableau:

BFS: $(x_1, x_2) = (0, 0)$, $z = 0$.

Iteration 1: Most negative reduced cost: $x_2$ with $-2$. Enter $x_2$.

Ratios: $5/1 = 5$, no entry for $s_2$ (coefficient is 0), $3/1 = 3$. Minimum: 3. $s_3$ leaves.

Pivot on row 3, column $x_2$. Row 3 stays (already coefficient 1):

BFS: $(x_1, x_2) = (0, 3)$, $z = -(-6) = 6$ improvement.

Wait, in the min formulation: $z = -x_1 - 2x_2$. At $(0, 3)$: $z = 0 - 6 = -6$. The tableau shows $z = 6$ because we track $-z$ or we track the objective differently. Let me keep the convention consistent: the bottom row tracks $z - (-x_1 - 2x_2) = 0$, so $z = -x_1 - 2x_2 +$ (reduced cost terms).

After the pivot: $z = -6 - x_1 + 2s_3$. Current value: $-6$.

Iteration 2: $x_1$ has reduced cost $-1$. Enter $x_1$.

Ratios: $2/1 = 2$, $4/1 = 4$. Minimum: 2. $s_1$ leaves.

Pivot on row 1, column $x_1$:

Correcting the $z$ row: after entering $x_1$, the reduced costs become $z = -8 + s_1 + s_3$. All reduced costs non-negative. Optimal!

Solution: $x_1 = 2, x_2 = 3$. Objective: $-(2) - 2(3) = -8$.

Check: $2 + 3 = 5 \le 5$ ✓, $2 \le 4$ ✓, $3 \le 3$ ✓.

Example 3: Identifying degeneracy

Problem:

subject to:

The optimum is $(2, 2)$ with objective $-4$. But notice something: at $(2, 2)$, all three constraints are active ($x_1 + x_2 = 4$, $x_1 = 2$, $x_2 = 2$). We have three active constraints but only two variables. This means the vertex $(2, 2)$ is degenerate: more constraints are active than necessary.

Why degeneracy matters:

In a degenerate BFS, some basic variables equal zero. During a pivot, the ratio test might give a ratio of zero, meaning the objective does not improve. The simplex method can cycle: it pivots through a sequence of degenerate bases that all represent the same point, never making progress.

How to handle it:

• Bland’s rule: Always choose the entering and leaving variables with the smallest index. This guarantees termination.
• Lexicographic rule: Break ties in the ratio test using a lexicographic comparison.
• Perturbation: Add tiny random perturbations to $b$ to make the problem non-degenerate.

In practice, cycling is extremely rare. Most solvers use Bland’s rule as a fallback.

Let us trace through. Starting from $(0, 0)$ with slacks $(4, 2, 2)$:

Iteration 1: Enter $x_1$ (reduced cost $-1$). Ratios: $4/1 = 4$, $2/1 = 2$. $s_2$ leaves. New BFS: $(2, 0)$.

Iteration 2: Enter $x_2$ (reduced cost $-1$). Ratios: $(4-2)/1 = 2$, $2/1 = 2$. Tie! Both $s_1$ and $s_3$ give ratio 2. Pick $s_1$ by Bland’s rule (smaller index).

New BFS: $(2, 2)$. All slacks are zero. This is a degenerate vertex (three active constraints, but basis has only two non-slack variables plus one slack at zero).

Iteration 3: Check reduced costs. Both $s_1$ and $s_2$ have non-negative reduced costs. Optimal.

Solution: $(2, 2)$, objective $-4$.

Complexity

Worst case: The simplex method can take exponentially many steps. The classic Klee-Minty cube example constructs a polytope in $n$ dimensions where the simplex method (with Dantzig’s rule) visits all $2^n$ vertices.

Average case: Smoothed analysis by Spielman and Teng showed that the simplex method runs in polynomial expected time when the input is slightly perturbed. In practice, for an LP with $m$ constraints and $n$ variables, the simplex method typically takes $O(m)$ to $O(3m)$ iterations.

Each iteration costs $O(mn)$ for a dense tableau update, but sparse implementations can be much faster.

This is why the simplex method remains competitive with interior point methods despite its exponential worst case: the bad cases are pathological and never show up in real problems.

Duality in the simplex method

The simplex method implicitly maintains dual variables. At a BFS with basis $B$, the dual variables are:

The reduced cost of a nonbasic variable $j$ is:

When all reduced costs are non-negative, $y$ is dual feasible and complementary slackness holds. The primal and dual objectives are equal, confirming optimality. This is a direct application of Lagrangian duality.

Big-M and two-phase method

Sometimes finding an initial BFS is not obvious (when the original constraints are equalities or $\ge$ inequalities). Two approaches:

Big-M method: Add artificial variables $a_i$ with huge cost $M$ to the objective. If the optimal solution has all $a_i = 0$, the original problem is feasible.

Two-phase method:

• Phase I: Minimize the sum of artificial variables. If the minimum is zero, you have a BFS for the original problem.
• Phase II: Use that BFS to start the simplex method on the original problem.

The two-phase method is numerically more stable because it avoids the large coefficient $M$.

When to use simplex vs interior point

Simplex excels at warm-starting: if you change one constraint or one cost coefficient, the previous basis is often still nearly optimal, and a few pivots suffice. Interior point methods essentially start from scratch each time.

Python implementation sketch

import numpy as np

def simplex_tableau(c, A, b):
    """Solve min c^T x s.t. Ax <= b, x >= 0 using the simplex method."""
    m, n = A.shape
    # Add slack variables
    tableau = np.zeros((m + 1, n + m + 1))
    tableau[:m, :n] = A
    tableau[:m, n:n+m] = np.eye(m)
    tableau[:m, -1] = b
    tableau[-1, :n] = c  # objective row (for min)
    
    basis = list(range(n, n + m))  # slack variables
    
    while True:
        # Find entering variable (most negative reduced cost)
        reduced_costs = tableau[-1, :-1]
        j = np.argmin(reduced_costs)
        if reduced_costs[j] >= -1e-10:
            break  # optimal
        
        # Ratio test
        col = tableau[:m, j]
        rhs = tableau[:m, -1]
        ratios = np.full(m, np.inf)
        for i in range(m):
            if col[i] > 1e-10:
                ratios[i] = rhs[i] / col[i]
        i = np.argmin(ratios)
        if ratios[i] == np.inf:
            raise ValueError("Unbounded")
        
        # Pivot
        pivot = tableau[i, j]
        tableau[i] /= pivot
        for k in range(m + 1):
            if k != i:
                tableau[k] -= tableau[k, j] * tableau[i]
        basis[i] = j
    
    x = np.zeros(n)
    for i, var in enumerate(basis):
        if var < n:
            x[var] = tableau[i, -1]
    
    return x, tableau[-1, -1]

What comes next

The simplex method walks along edges of the feasible polytope. The Frank-Wolfe method borrows a similar idea for nonlinear objectives: at each step, it solves a linear subproblem over the constraint set and takes a step toward that solution. This yields sparse iterates and works well for large structured problems.