The optimal linear-programming solution is never interior: simplex climbs only along boundary vertices
The optimum of a linear program always sits on some boundary vertex, so the simplex algorithm never searches the interior: starting from the origin, it picks a direction from the most negative column, sets the step size by the minimum ratio, and keeps moving to a more profitable adjacent vertex.
The argument · tap a timestamp to hear it
Climbing between adjacent vertices
A linear program seeks the extreme value of an objective function inside a feasible region bounded by straight-line constraints. The simplex algorithm does not search the interior of that region; it starts at the origin and moves along an edge to an adjacent vertex that raises revenue, then from the new vertex looks at the next adjacent vertex, until no move increases revenue any further. Because the algorithm "cannot see" the picture, all the seemingly complicated matrix operations that follow are essentially answering two questions with numbers: which direction, and how far.
— Josh StarmerFirst normalize every constraint to less-than-or-equal
Before the iterations proper, standardization is required: a constraint with a greater-than-or-equal sign must be flipped into less-than-or-equal by multiplying both sides by -1; a constraint with an equals sign is split into a less-than-or-equal and a greater-than-or-equal inequality, and the greater-than-or-equal one is then multiplied by -1 and flipped, so the two inequalities form a kind of "inequality sandwich" equivalent to the original equality. The episode explains the purpose: the algorithm then only has to handle one kind of sign at every step, with no branching checks for different constraint forms during iteration.
— Josh StarmerSlack variables pad inequalities into equalities
Even after an expression becomes less-than-or-equal, the left and right sides may still not be equal. The fix is to append a non-negative slack variable to each equation, filling in exactly the shortfall. The episode's example: when producing 10 kg of cookie mix and 8 kg of doughnut mix, only 8 kg of flour is actually used while 10 kg is available, so the slack variable for flour is set to 2 kg; the slack variables of the other constraints vanish from the calculation because their coefficients are 0. Only after the slack variables are added do all equations share one format and can be put into a matrix uniformly.
— Josh StarmerLoad the matrix, then negate the first row
The last formatting step is to fill all coefficients and totals into the matrix and multiply the first row by -1. The negation is only to match the usual definition of the simplex method, so that "where to go next" can be read directly as the most negative coefficient in the first row; at this point the initial revenue is 0, because the search starts at the origin. Once the matrix is in order, every iteration revolves around the same action: first choose a direction, then fix a distance, and finally use row operations to read the new vertex's coordinates explicitly.
— Josh StarmerOnly the minimum ratio lands on the boundary
The algorithm itself cannot see the feasible region, so it uses the ratio test to set the step size: take the total on the right-hand side of each constraint row and divide it by the corresponding positive coefficient in the current column; the quotient is the coordinate reachable along that axis. The episode uses three candidate points on the cookie mix axis to illustrate: the ratios 25 and 16.7 correspond to where the yellow and blue lines meet the axis, both outside the feasible region; the lowest, 10, lands on the brown line's intersection, i.e. on the boundary. So the minimum ratio is always chosen; a point with a larger ratio necessarily overshoots. If the minimum ratio is tied, the convention is to pick the row with the smallest row number.
— Josh StarmerGaussian elimination makes the coordinates surface on their own
Once the pivot column and pivot row are chosen, Gaussian elimination turns the pivot position into 1, then clears every other position in that column to 0 by adding multiples of rows. After elimination the reading rule is simple: if a column has a single 1 and zeros everywhere else, read the total on that column's row as the current vertex's coordinate on that axis; when several variable columns satisfy this at once, the coordinates appear together, and the value in the top-right corner directly gives that vertex's revenue. The episode reads off the second vertex (10,10) and revenue 50 this way.
— Josh StarmerStop when the first row has no negatives
When to stop matters as much as how to move. As long as the first row still holds a most negative coefficient that can serve as a candidate, the algorithm keeps testing whether revenue can be raised; once the first row has no negatives left, the simplex method declares the current vertex optimal. The second stop of the first example, (10,10), satisfies this condition, and revenue 50 is the best value attainable under the three constraints of flour, sugar and chocolate. This stopping condition is exactly the matrix-language equivalent of the geometric intuition that "no adjacent vertex can raise revenue any further."
— Josh StarmerThe three-dimensional example adds no new machinery
Extending the example from two products to three, the simplex method still holds. The episode labels doughnut, cookie and brownie mix as x, y and z, gives each of the five constraints its own slack variable, and after starting from the origin every step is still the same procedure: use the most negative coefficient in the first row to pick a column, use the minimum ratio to pick the pivot row, then do Gaussian elimination. When several most negative coefficients tie, take the leftmost column first. After a few moves the first row has no negatives left, and the algorithm stops at (9,9,4), corresponding to a maximum revenue of 22.
— Josh StarmerIn their own words · checked verbatim
The simplex algorithm starts at the origin and then moves to neighboring vertices that increase revenue until moving to the next vertex does not increase the revenue. Bam.
Josh Starmer1:06
Now the two inequalities give us a sort of inequality sandwich that is the equivalent of the original equality.
Josh Starmer4:06
The idea is that when the total amount of something like flour used by the cookie and doughnut mixes on the left is less than the amount available on the right, the slack variables make up the difference.
Josh Starmer5:08
In this example, the largest negative number in the first row, -3, is in the first column, the column for cookie mix. So, we could decide to go along the cookie mix axis.
Josh Starmer8:10
Again, in general, the simplex algorithm selects the lowest value because larger values are always outside of the feasible region.
Josh Starmer15:16
In other words, the point 10, 10, which represents a revenue of 50, is the best we can do given the constraints on the amount of flour, sugar, and chocolate that we can use.
Josh Starmer18:19
Figures
| Endpoint of the first move in the first example | cookie mix = 10, doughnut mix = 0 | 13:16 |
| Revenue at that vertex | 30 | 13:16 |
| Endpoint of the second move in the first example | cookie mix = 10, doughnut mix = 10 | 17:17 |
| Revenue gain at that vertex | from 30 to 50 | 18:19 |
| Optimal vertex of the three-dimensional example | x = 9, y = 9, z = 4 | 25:33 |
| Maximum revenue of the three-dimensional example | 22 | 25:33 |
Glossary
- simplex algorithm
- An algorithm that starts at the origin and moves step by step along adjacent boundary vertices to find the optimal solution of a linear program.
- feasible region
- The region containing all feasible solutions, bounded by all the constraints together.
- objective function
- The linear equation to be maximized or minimized; in the example, the revenue equation.
- slack variable
- A non-negative variable added to pad an inequality into an equality.
- Gaussian elimination
- Using row operations to reduce a matrix to echelon form so the intersection coordinates can be read off.
- ratio test
- Dividing each constraint total by the positive coefficient in the current column and taking the smallest ratio to set the step size.
How to listen
Engineers who call optimization libraries but have never derived the simplex method by hand, operations-research students, and teachers preparing to lecture on linear programming.
The Gurobi ad at the top, the linear-programming recap at the start, and the book-and-merch pitch at the end are skippable; everything else is hand-calculation detail.