Skip to content
Tutorials Center
My learning

Topics

Lesson 25 of 38 ยท Linear and Quadratic Programs

The Simplex Method from Scratch

Build the simplex method step by step: slack variables, the tableau, choosing the entering and leaving variables, pivoting, and reading the dual prices from the result.

The simplex method, invented by George Dantzig in the 1940s, solves LPs by walking along the edges of the feasible polyhedron from one vertex to a better neighboring vertex until no neighbor improves. It is still a workhorse in practice, even though newer interior-point methods have better worst-case guarantees.

In this lesson you build a small, readable version using a tableau. It handles problems of the form maximize cแต€x subject to Ax โ‰ค b, x โ‰ฅ 0 with b โ‰ฅ 0 (so the origin is a feasible starting vertex).

Slack variables

An inequality x + y โ‰ค 4 becomes an equality by adding a slack variable s โ‰ฅ 0: x + y + s = 4. The slack measures unused capacity. After adding one slack per row, we have m equations in n + m unknowns.

A basic feasible solution picks m variables to be "basic" (allowed to be non-zero) and sets the other n to zero. These correspond exactly to the vertices of the polyhedron. We start with all slacks basic: that is the origin x = 0.

The tableau

Store everything in one matrix. Each row is an equation, plus a last row for the objective. For the workshop LP (max 3x + 2y):

Text
   x   y  s1  s2  s3 |  rhs
   1   1   1   0   0 |   4
   1   3   0   1   0 |   9
   1   0   0   0   1 |   3
  -3  -2   0   0   0 |   0

The bottom row holds -c. A negative entry means "increasing this variable improves the objective". Each iteration does three things:

  1. Entering variable. Choose the column with the most negative bottom entry (Dantzig's rule). If none is negative, stop: the current vertex is optimal.
  2. Leaving variable. In that column, look at rows with a positive entry and compute rhs / entry. The smallest ratio decides which constraint becomes tight first. If no entry is positive, the problem is unbounded.
  3. Pivot. Divide the pivot row by the pivot entry, then subtract multiples of it from every other row so the pivot column becomes a unit vector.
Python A tableau simplex solver

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The trace shows the path: from the origin to (3, 0) (the market cap becomes tight), then to (3, 1) (labor becomes tight). The final bottom row under the slack columns holds the dual prices (2, 0, 1), the same numbers you found with KKT conditions and linprog.

Why are duals in the bottom row? At the end, the bottom entry for a slack column equals the reduced cost of that slack, which is the improvement per unit of that constraint's right-hand side. That is exactly the shadow price.

Testing against a library

A from-scratch solver is only trustworthy after comparing it with a reference. The test below makes random problems with positive data (so they are bounded and the origin is feasible) and checks the optimal value against linprog.

Python Random test against linprog

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Limits and real-world solvers

  • Starting point. If some b_i < 0, the origin is not feasible. Real solvers add a "Phase 1" that finds a feasible vertex first.
  • Cycling. With degenerate vertices, Dantzig's rule can in theory loop forever. Bland's rule (always pick the lowest-index candidate) prevents cycling at some cost in speed.
  • Speed. Simplex can need exponentially many pivots on specially built examples, yet in practice it typically takes a number of pivots proportional to a small multiple of m. Interior-point methods have polynomial guarantees and shine on huge problems.
  • Numerics. Production solvers do not store the full tableau; they keep a factorized basis (the "revised simplex").

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What does a slack variable represent?

    Adding s โ‰ฅ 0 turns a โ‰ค inequality into an equality; s is how much capacity is left over.
  2. 2. In the simplex tableau, how is the leaving variable chosen?

    The minimum ratio test finds the constraint that becomes tight first, keeping the new vertex feasible.
  3. 3. What does it mean if every entry of the entering column is โ‰ค 0?

    No constraint stops the entering variable from growing, so the objective can improve forever.
  4. 4. Where does the finished tableau show the shadow prices (for a max problem with โ‰ค constraints)?

    The reduced costs of the slack variables are the per-unit values of the constraint resources.

Summary

  • Slack variables turn Ax โ‰ค b into equalities; the starting basis is the slacks (the origin).
  • Each pivot moves to a neighboring vertex with a better (or equal) objective: choose an entering column, find the leaving row by the minimum ratio, pivot.
  • Stop when the bottom row has no negative entries; the same row then carries the dual prices.
  • Always test a hand-built solver against a library on random problems.

Next: Quadratic Programs