AlgoVerse

The simplex method

Solve a linear program: start at a corner of the feasible region and move to a neighbouring corner while the objective improves; in exact fractions.

Linear programming: maximize a linear function c·x under linear constraints A·x ≤ b and x ≥ 0. The feasible region is a polytope, and if there is an optimum, one is at a corner.

Read the full explanation ↓
Input:
A 3×3 · b 3×1 · c 1×3PDF export

Maximize 3x1 + x2 + 2x3 under three constraints; the answer is 28 at x = (8, 4, 0).

  1. from fractions import Fraction
  4. def simplex(A, b, c):
  5. # Maximize c·x subject to A·x ≤ b and x ≥ 0 (with b ≥ 0, so x = 0 is a starting corner).
  6. m, n = len(A), len(c[0])
  7. # The tableau: [A | I | b] for the constraints, and [−c | 0 | 0] for the objective at the bottom.
  8. T = [[Fraction(v) for v in A[i]] + [Fraction(int(i == k)) for k in range(m)] + [Fraction(b[i][0])] for i in range(m)]
  9. T.append([Fraction(-v) for v in c[0]] + [Fraction(0)] * (m + 1))
  10. basis = [n + i for i in range(m)]
  11. while True:
  12. # Bland's rule: the first variable whose objective entry is negative enters.
  13. col = next((j for j in range(n + m) if T[m][j] < 0), None)
  14. if col is None:
  15. break
  16. rows = [i for i in range(m) if T[i][col] > 0]
  17. if not rows:
  18. return None
  19. row = min(rows, key=lambda i: (T[i][-1] / T[i][col], basis[i]))
  20. pivot = T[row][col]
  21. T[row] = [v / pivot for v in T[row]]
  22. for i in range(m + 1):
  23. if i != row and T[i][col] != 0:
  24. f = T[i][col]
  25. T[i] = [v - f * w for v, w in zip(T[i], T[row])]
  26. basis[row] = col
  27. x = [Fraction(0)] * n
  28. for i, var in enumerate(basis):
  29. if var < n:
  30. x[var] = T[i][-1]
  31. return str(T[m][-1]), [str(v) for v in x]

Invariant: The tableau always describes a feasible corner (the last column stays non-negative), and the objective never gets worse with a pivot.

Start

basis—

The table is still empty.

Local variables

Orange = changed in this step

A list

[1, 1, 3][2, 2, 5][4, 1, 2]

b list

[30][24][36]

c list

[3, 1, 2]

Call stack

  1. simplex()line 4
Step 1 of 68
Black = pivot · Orange = key stepstart: 0/1 · ratio_test: 0/2 · pivot: 0/2 · optimal: 0/1
    Explanation

    The idea

    Linear programming: maximize a linear function c·x under linear constraints A·x ≤ b and x ≥ 0. The feasible region is a polytope, and if there is an optimum, one is at a corner.

    Simplex

    1. Start at the corner x = 0 (feasible since b ≥ 0). The slack variables start out in the "basis".
    2. If the objective row has a negative entry, raising that variable pays: it enters the basis.
    3. The ratio test decides how far we can go and which variable leaves the basis.
    4. Pivoting (like Gaussian elimination) rewrites the tableau for the new corner.
    5. When no negative entry is left, the corner is optimal.

    Bland's rule (always the first negative column) prevents endless cycling.

    Cost

    Exponential in the worst case, but very fast in practice, and still the most widely used method.

    What to watch in the trace

    • Look at the T table after each pivot; the last column holds the basic variables' values and the bottom-right corner the objective's value.