A corner walk you can do on paper
The solver running in this page implements the simplex method directly, and the whole of it fits on one screen. That is worth knowing for two reasons. It means nothing here has to be taken on faith, because the walk can be done by hand on a small problem and compared against the machine. And it means that when a model misbehaves, the internals are inspectable rather than mysterious, which matters a great deal in session 9, where this exact solver turns out to have been wrong twice while passing all of its tests.
★ What you walk out with tonight. A tableau you can read without flinching: which columns are variables, which are slacks, where the objective lives and why it is stored negated. Two pivots done by hand, on a problem small enough to check, ending at 36 at (2, 6). And the moment the shadow prices appear: they are not computed at the end, they have been sitting in the objective row under the slack columns the whole time.
LiveThe one-paragraph version4 min▶
Start at the corner where you make nothing at all, which is always feasible and always terrible. Look at the objective and ask which variable, if it were allowed to grow, would raise the margin fastest per unit. Grow it. Something will stop you, because some constraint runs out first, and the amount you can grow by is set by whichever row runs out soonest. At that moment you are at a new corner, one wall further in, earning more. Repeat. When no variable improves the objective any more, you are done, and you are done for a reason rather than because you ran out of patience.
Everything else is bookkeeping, and the tableau is the bookkeeping. It keeps the whole system of equations in a form where "which variable grows fastest" and "which row runs out first" are both readable off the grid rather than worked out from scratch each time.
Tonight's walk is on the solver's own first test problem, not on Ravensworth: maximise 3x + 5y subject to x at most 4, 2y at most 12, and 3x + 2y at most 18, whose optimum is 36 at (2, 6). Two variables and three rows is small enough to finish by hand in ten minutes and check against the machine, which is the only way to learn a mechanism. Ravensworth has the same shape and more columns.
Self-studyThe words tonight adds4 min▶
- Slack variable. The unused part of a constraint, given a name. It turns
x <= 4intox + s1 = 4withs1 >= 0. - Standard form. The problem written entirely as equations, with all variables non-negative. Simplex needs this.
- Tableau. That system as a grid: one row per constraint, one column per variable including slacks, one column for the right hand side, and one extra row for the objective.
- Basis. The variables currently allowed to be nonzero, one per row. It starts as the slacks, which is the corner where nothing is made.
- Entering column. The variable chosen to grow. Here, the most negative entry in the objective row.
- Leaving row. The row that runs out first, found by the ratio test: smallest right hand side divided by entry in the entering column, over positive entries only.
- Pivot. The row arithmetic that swaps those two, moving you to an adjacent corner.
- Optimality test. No negative entry in the objective row. It means no single variable can be grown to improve things, so no adjacent corner is better.
- Degeneracy. A pivot of length zero, where the corner does not actually move. Real, and a cause of cycling.
- Unbounded. An entering column with no positive entry anywhere: nothing stops the variable growing, so there is no best plan.
Name the unused part, and the inequalities become equations
18 min liveSimplex cannot work with inequalities, and the fix is almost insultingly simple. An inequality says a quantity is at most a ceiling. The difference between them is a real, meaningful, non-negative quantity, so give it a name and write an equation instead. Nothing is lost, one new variable is gained per row, and the entire problem becomes a system of linear equations, which is territory with a well understood method.
LiveWhy the objective row is stored negated4 min▶
The code writes obj[j] = -c[j] and it is worth being clear that this is a convention rather than a trick. Maximising 3x + 5y is the same as minimising -3x - 5y, and once the row holds the negated coefficients, "which variable would help most" becomes "which entry is most negative", which is one comparison rather than two.
It also makes the stopping rule a single test. When there is no negative entry left in the objective row, no variable can be increased to improve the objective, and the search is over. One sign convention buys you both the choice rule and the halt condition, which is why nearly every implementation does it, and why a tableau you find in the wild will usually look like this.
LiveThe first corner is free3 min▶
Notice what the starting tableau already is. The slack columns form an identity block, the basis is the three slacks, and the right hand side is the original ceilings. Read that as a plan and it says: make nothing, and all three capacities are entirely unused. That plan is feasible, it earns zero, and it required no work to find.
Having a feasible starting point for free is the reason this form is chosen, and it is also the reason this particular solver refuses any problem with a negative right hand side. A row like -x <= -5 would make the "make nothing" plan illegal, so the free starting corner disappears and a preliminary phase is needed to find any feasible point at all. The code returns "needs-phase-one" for that case rather than guessing, and the consequences of that refusal being silent elsewhere are the subject of session 9.
Two pivots, by hand, to 36 at (2, 6)
20 min liveThe starting tableau has -5 under y and -3 under x, so y is the column that pays best per unit and y goes first. How far can y grow? Row 2 allows 12 divided by 2, which is 6. Row 3 allows 18 divided by 2, which is 9. Row 1 has a zero in the y column, so it does not restrict y at all. The smallest is 6, so row 2 is the first wall y hits, and row 2 leaves the basis. That is the entire decision, and it repeats.
...
LiveWhat a pivot actually does to the numbers4 min▶
Three lines of arithmetic. Divide the leaving row through by the entry sitting at the intersection of the entering column and the leaving row, so that entry becomes 1. Then subtract a multiple of that row from every other row, including the objective row, so that the rest of the entering column becomes 0. Then record that the entering variable now occupies that row in the basis.
That is ordinary elimination, the same operation used to solve simultaneous equations by hand, applied to a grid. Nothing clever happens. What makes it a method rather than a manipulation is the pair of rules for choosing where to pivot, and the guarantee those rules carry: the new corner is feasible, and it is at least as good as the old one.
Watch the right hand column while you step the live box. It holds the current values of the basic variables, and the bottom right cell holds the objective. It goes 0, then 30, then 36, and those three numbers are the three corners of the walk. Nothing about them is retrieved at the end; the tableau has been carrying the answer the whole time.
LiveWhere the shadow prices come from5 min▶
Look at the final objective row of the walk: 0 and 0 under x and y, then 0, 1.5 and 1 under s1, s2 and s3, and 36 in the right hand corner. The three entries under the slack columns are the shadow prices of the three constraints, and the code returns them directly with no extra computation: for (i = 0; i < m; i++) dual.push(T[m][n + i]);
The reason is readable from what a slack variable means. The slack in a row is the unused capacity of that row. Its entry in the objective row is the rate at which the objective would change if that slack were forced to be one unit larger, which is to say if one unit of capacity were taken away. Turn the sign around and it is what one more unit would be worth. So the first row here, which ends with slack left over, is worth 0, and the two rows the plan has used up are worth 1.5 and 1.
This is the point where the machinery starts paying rent beyond the plan itself. The prices arrive free with the answer, they say what each ceiling is worth at the margin, and every one of them is a rate with a validity range that nobody quotes. Session 4 is that range, measured, and it turns out to be shorter than anyone expects: at Ravensworth the milling price of 33.7931 stops holding at about +0.46 hours.
var r = OPT.solveLP([3, 5], [[1, 0], [0, 2], [3, 2]], [4, 12, 18]); r.status; // "optimal" r.objective; // 36 r.x; // the corner the last pivot landed on r.slack; // what each row has left over at that corner r.shadow; // the final objective row, under the slack columns r.binding; // true where slack is zero OPT.CASES; // the three hand-checkable problems the solver ships OPT.selfTest().ok; // all three, run in this browser, right now
Self-studyDegeneracy, cycling and the guard in this code5 min▶
The ratio test can produce a tie, and a tie means more than two walls pass through the same corner. When that happens the next pivot can have a ratio of zero: the basis changes, the arithmetic all happens, and the corner does not move. The objective does not improve. That is degeneracy, and it is common in real models, especially ones with many similar rows.
A run of degenerate pivots can in principle return to a basis it has already visited, at which point the method cycles for ever. Anti-cycling rules exist and they work by changing the choice of entering column when ties appear. They also cost something: the rule that provably prevents cycling tends to choose poor columns and take many more steps.
What does this implementation do? It does not have an anti-cycling rule. It has if (++guard > 5000) return { status: "iteration-limit" };, which is a counter, not a proof. That is an honest engineering choice for a teaching solver and it is worth knowing about rather than discovering: a status of "iteration-limit" means the walk gave up, and the correct response is to look at the model rather than to raise the limit.
Self-studyWhere serious people disagree5 min▶
The rule used here for choosing the entering column, take the most negative objective entry, is the original one and it is not the only one. Whether it is the right default is a genuinely open argument.
One camp defends it on cost. The rule is a single scan of one row, it is almost free per step, and on the overwhelming majority of practical problems the number of steps stays modest. Spending more effort per step to choose a better column is paying a certain cost for an uncertain benefit, and a simple rule keeps the implementation small enough to audit, which has its own value.
The other camp points out that the rule measures the wrong thing. The most negative entry is the biggest improvement per unit of the entering variable, not the biggest improvement per step, and those come apart badly when columns are scaled differently. Rules that estimate the actual gain per step take far fewer steps on hard problems, and on large models the step count is what dominates. There are also problems constructed specifically to make the simple rule take an enormous number of steps.
Neither side claims a universal winner, because there is not one: the choice trades work per step against number of steps, and which dominates depends on the problem. What is not in dispute is that the choice is a choice. If a model is slow, the pivoting rule is one of the things to look at, and it is not a detail of the implementation so much as a lever on it.
Walk it on paper, then make the solver agree with you
18 min hands onSix steps on the small problem. The aim is to be able to pick up any tableau, say which column enters and which row leaves, and know when to stop, without looking up a rule.
Write the starting tableau from scratch
On paper, turn the three inequalities into equations with s1, s2 and s3, and lay out the grid with the objective row negated. Check it against the first diagram cell by cell before you go on. Everything after this is arithmetic, so an error here is an error everywhere.
Choose the first pivot yourself
Name the entering column and say why. Do the ratio test on all three rows out loud, including the row where the entry is zero, and say why that row is skipped rather than treated as infinite improvement. Then name the leaving row.
Do the row arithmetic by hand
Divide the leaving row by the pivot entry, then clear the rest of the entering column, objective row included. Compare your result with the first tableau in the second diagram. If a number is off, the fault is almost always in the objective row, because it is the row people forget to update.
Step the live box and check yourself
Pivot once in the live box and compare every cell with your paper. Then do the second pivot on paper first, predict the stopping condition, and only then step the box. Read the objective as it goes 0, then 30, then 36.
Read the prices off the final row
Take the three entries under s1, s2 and s3 in your final tableau. Then call OPT.solveLP([3, 5], [[1, 0], [0, 2], [3, 2]], [4, 12, 18]) and compare with r.shadow. Say which constraint is worth nothing, and say why that one, using r.slack as the evidence.
Walk the deliberate tie
Switch the live box to the second problem, max x + y subject to x + y at most 10, and step it. One pivot ends it at 10. Then look at the objective row entry under the structural column that is not in the basis: it is zero, which is the tableau telling you that bringing that variable in would change nothing, because an entire edge is optimal.
The habit to keep. When a model behaves strangely, the tableau is inspectable and the status field is informative. An "unbounded" status means some column had no positive entry to stop it, which is a missing constraint. An "iteration-limit" means the walk did not terminate, which is usually degeneracy rather than size. And a shadow price of zero always has slack sitting next to it, so the two fields check each other.
Three questions
In the starting tableau the objective row reads -3 under x and -5 under y. Which column enters, and what does the choice mean?
The row holds the negated objective coefficients, so a more negative entry is a better per-unit improvement. Choosing the most negative is the original pivoting rule. It is a rule about improvement per unit of the variable, which is not the same as improvement per step, and that difference is where other rules come from.
The entering column is y. Row 1 has a 0 in that column, row 2 has 2 with a right hand side of 12, row 3 has 2 with a right hand side of 18. Which row leaves?
The ratio test asks how far the entering variable can grow before some row runs out. A zero entry means that row does not restrict y, so it is skipped rather than counted. Twelve over two is six, eighteen over two is nine, and six comes first, so row 2 is the binding wall and it leaves the basis.
The final objective row reads 0, 0, 0, 1.5, 1 with 36 in the corner. What are the 1.5 and the 1?
Each slack column's objective entry is the rate at which the objective changes as that row's capacity changes, which is exactly a shadow price, and the solver returns it without further work. The slack values themselves live in the right hand column, not the objective row, and a row with slack left over always prices at zero.
Homework
Thirty minutes, paper first and the console second.
Walk the third shipped problem by hand
Maximise 2x + y subject to x + y at most 10 and x at most 20, whose optimum is 20 at (10, 0). Do the tableau on paper, predict how many pivots it takes, then check against the live box. Note which constraint ends with slack and confirm its price is zero.
Predict Ravensworth's binding set
Before session 4, write down which of the mill's three ceilings you expect the optimal plan to use up completely, and which you expect to have room left over. Then solve it and check. Session 4 puts a price on each one and measures how far that price survives being multiplied.