If you have written any optimization code, you have met linear programming even if nobody called it that. "Maximize output without blowing the resource budget" is an LP problem, and the classic algorithm that solves it is the simplex method. It is worth understanding not because you will hand-code it (you'll usually call a solver), but because knowing how it moves makes you far better at modeling problems for it.
Here is the algorithm stripped down to its logic.
The problem shape
Every LP problem has three parts:
an objective function to maximize or minimize, e.g. Z = 5x1 + 4x2
a set of linear constraints, e.g. 6x1 + 4x2 <= 24, x1 + 2x2 <= 6
non-negativity: all variables >= 0
Geometrically, the constraints carve out a feasible region (a polytope). The optimum always sits at a corner of that region. The simplex method is just a smart way of hopping from corner to corner, uphill, until there is no higher corner to move to.
The algorithm as pseudocode
build initial tableau (add a slack variable per <= constraint)
loop:
compute Cj - Zj for each column
if all (Cj - Zj) <= 0: break # optimal reached
pivot_col = column with most positive Cj - Zj # entering variable
ratios = RHS / pivot_col entries (only positive entries)
pivot_row = row with smallest non-negative ratio # leaving variable
pivot(pivot_row, pivot_col) # elementary row operations
return solution from final tableau
That's it. Four moves per iteration: score the columns, pick the entering variable, run the ratio test for the leaving variable, pivot. Repeat until the optimality condition holds.
A quick worked run
Take Maximize Z = 5x1 + 4x2 subject to 6x1 + 4x2 <= 24 and x1 + 2x2 <= 6. Add slack variables s1, s2, build the tableau, and iterate. The optimum lands at x1 = 3, x2 = 1.5, Z = 21. Two pivots and you're done.
Simple on paper until the numbers get ugly.
Where humans (and debugging) actually break
The algorithm is clean. The arithmetic is not. A single wrong entry in one pivot silently corrupts every tableau after it, exactly like an off-by-one that only surfaces three functions later. When your hand-computed answer disagrees with the "official" one, the useful question is never what the answer is it's which iteration diverged.
That is the one job a good tool should do: show every intermediate tableau, not just the final vector. When I want to verify a run, I use this free simplex method calculator because it prints each tableau, the Zj and Cj - Zj rows, and every pivot so I can line it up against my own work and find the exact step that broke. It also does the variants you hit the moment problems get realistic: the 2-phase and Big M methods for >= constraints (artificial variables), the dual and revised simplex, and transportation problems, for 2, 3, and 4 variables.
Why bother understanding it if a library solves it?
Because modeling is the hard part, not solving. If you know that >= constraints force artificial variables, that equality constraints tighten the feasible region, and that an unbounded direction means a missing constraint, you write better models and you read solver output like it's your native language. The simplex method is the mental model that makes scipy.optimize.linprog or an OR-Tools call stop feeling like magic.
TL;DR
LP optimum is always at a corner of the feasible region.
Simplex = hop corner-to-corner, uphill, via pivots.
Each iteration: score columns (Cj - Zj) → entering variable → ratio test → leaving variable → pivot.
Stop when no Cj - Zj is positive.
Verify by hand and against a step-by-step tool so you catch arithmetic slips.
If you want to see the whole tableau process on a real problem with every pivot shown, free and no signup run one through Nestixex and watch the iterations happen.
Top comments (1)
Nice algorithmic explanation. One small nuance: an LP does not always have a unique optimum at a single corner. If an optimum exists, at least one optimal extreme point can be found, but an entire edge may also be optimal. It may also be worth mentioning degeneracy, cycling, and unbounded cases, since those are usually where the clean pseudocode meets real-world solver behavior.