A number that arrives free, and a number nobody computes
Two things are true of a shadow price at the same time, and holding both is the whole skill. It is exact: 33.7931 is not an estimate, it is the derivative of the optimum with respect to that ceiling, and the solver hands it over with the answer. And it is local: it describes the next fraction of an hour and says nothing whatever about the tenth. The first property is why the figure travels. The second property is why it does damage, because a number that exact does not look like it needs a caveat.
★ What you walk out with tonight. The three Ravensworth prices read straight off the objective row, and the one-line reason a row with slack in it prices at exactly 0 rather than at a small amount. A measured range for each binding row: milling holds to about +0.46 hours, protein to +0.77 tonnes. And a procedure you can run on any model you are handed, in about fifteen lines, that turns "the hour is worth 33.7931" into "the hour is worth 33.7931 for the next 0.46 of an hour", which is a sentence a capacity decision can actually be built on.
LiveThe one-paragraph version4 min▶
Solve the mill. Take the objective row of the final tableau and look under the slack column of each constraint: that entry is the rate at which the best achievable margin moves when that constraint's ceiling moves. Now raise one ceiling by a hundredth of a unit and solve again. The gain matches the rate exactly. Raise it by a tenth and it still matches. Keep going and at some point the plan reorganises itself around a different set of walls, the rate quietly becomes too generous, and every unit you assumed after that point was imaginary. The step where the match breaks is the only honest boundary on the figure, and finding it costs one loop.
Ravensworth's milling hour prices at 33.7931. A request to buy ten more hours therefore looks like it is worth 337.93. Solve the mill with ten more hours in it and the actual gain is 206.44. The price was not wrong and the solver was not wrong. The multiplication was, and it overstated the case by 1.64 times, which is the difference between a purchase that pays and one that does not.
Self-studyThe words tonight adds4 min▶
- Dual value. The other name for a shadow price. Every constraint in the primal problem has one, and the solver produces the whole set at once.
- Reduced cost. The same idea applied to a variable rather than a constraint: what the objective row says about a product the plan currently makes none of.
- Binding. Slack is zero. The plan ran out of that row.
r.bindingis exactlyr.slacktested against zero. - Complementary slackness. The pairing rule. A row with slack left over has a price of zero, and a row with a positive price has no slack. Both halves hold in every solved problem.
- Validity range. The interval of ceiling changes over which the basis, and therefore the price, stays the same. Not returned by the solver.
- Basis change. What happens at the end of the range: a different set of constraints becomes the binding set, and the rate drops to whatever the new set supports.
- Degeneracy. More walls through a corner than the corner needs. It makes the price at that corner ambiguous rather than wrong, which is its own problem.
- Right and left derivative. What one more unit buys, and what one fewer unit costs. They are the same number in the easy case and not in the degenerate one.
Under the slack columns, and why that is a price
18 min liveThe mechanism is short and it is worth being able to state without hedging. A slack variable holds the unused part of its row. Its entry in the final objective row is the rate at which the objective would move if that slack were forced one unit larger, which is to say if one unit of the ceiling were taken away. Reverse the sign and you have what one more unit is worth. The code is one loop with no arithmetic in it at all: for (i = 0; i < m; i++) dual.push(T[m][n + i]);
LiveZero is not "small", it is the pairing rule4 min▶
People read a shadow price of 0 as a rounding artefact or as "worth very little". It is neither. Blending ends the week with 0.2414 hours nobody used. Add an hour to a pool that already has unused hours in it and the plan does not change, because the blending ceiling was not preventing anything the plan wanted to do. Same plan, same margin, difference exactly zero. The size of the leftover is irrelevant: 0.2414 hours and 24 hours give the same price.
Written as a rule the pairing runs both ways, and both directions are useful when debugging. Slack positive means price zero. Price positive means slack zero. In this implementation that consistency is free to check, because binding is computed from slack and shadow comes from a different part of the tableau entirely, so agreement between them is evidence rather than tautology.
LiveWhat the solver rounds, and why you should know3 min▶
Every number leaving this solver passes through clean, which snaps anything under 1e-9 to zero and rounds the rest to nine decimal places. That is why blending's price prints as a flat 0 rather than as a trailing wisp of floating point, and it is why binding can use a tolerance of 1e-7 without arguing with the printed values.
It also means a genuinely tiny price and an exactly zero price look identical on the way out. On this problem that is not in doubt, because the slack field says which case you are in. On a model you did not write, check the slack before you conclude a resource is free.
var c = [38, 54, 71];
var A = [[1.1, 1.5, 2.3], [0.6, 0.9, 1.7], [0.1, 0.4, 1.0]];
var b = [131, 77, 29];
var r = OPT.solveLP(c, A, b);
r.shadow; // one entry per constraint row, straight from the objective row
r.slack; // what each row has left at the optimum
r.binding; // slack tested against zero, row by row
// the pairing rule, as an assertion you can leave in
r.shadow.every(function (p, i) {
return Math.abs(p) < 1e-7 || Math.abs(r.slack[i]) < 1e-7;
});
Walk the ceiling up until prediction and reality part
20 min liveThere is no field in the output for the range, and there is no shortcut worth trusting instead of measuring it. The measurement is a loop: take the base optimum, add a small amount to one ceiling, solve again, and compare the actual gain against the amount multiplied by the price. While they agree to the last decimal, the basis has not changed and the rate is still exactly right. The first step where they disagree is the boundary, and the last step before it is the number you report.
...
LiveWhat actually happens at the boundary4 min▶
Nothing breaks at +0.46. The optimum is still the optimum, the solver is still correct, and the price at the new ceiling is still exactly whatever the new objective row says it is. What changed is which walls the corner sits on. Up to that point every extra hour of milling is absorbed by making more of what the plan already favours, and the rate of return on those hours is constant. Past it, another ceiling has been reached, the plan has to reorganise around it, and the extra milling hour now buys whatever is possible under a tighter set, which is less.
So the gain curve is piecewise linear, falling in steps, and the shadow price is the slope of the first piece only. Multiplying it by ten is assuming the first piece runs for ten units. Here it runs for less than half of one.
LiveWhy the step size in the walk matters4 min▶
The walk resolves the boundary only as finely as it steps. A sweep in hundredths finds the break somewhere in a hundredth-wide window, which is what "about +0.46 hours" means and why the word "about" is doing real work. A sweep in whole units would report that the rate breaks somewhere before +1, which is true and nearly useless. A sweep in thousandths costs ten times as many solves for a boundary you will round anyway.
Pick the step from the decision, not from the arithmetic. If the question is whether to buy an hour, step in fractions of an hour. If the question is whether to add a shift, step in shifts, and expect the answer to be that the price expired long before the first one.
The comparison tolerance matters just as much. Compare predicted against actual with an absolute tolerance near the solver's own, 1e-6 or so. Too tight and floating point noise reports a break that is not there; too loose and the first genuine step of the flattening curve looks like agreement, which pushes the reported range out past where it really ends.
function rangeOf(c, A, b, row, step, cap) {
var base = OPT.solveLP(c, A, b);
var price = base.shadow[row];
var lastAgreeing = 0;
for (var d = step; d <= cap + 1e-12; d += step) {
var b2 = b.slice();
b2[row] = b[row] + d;
var r = OPT.solveLP(c, A, b2);
if (r.status !== "optimal") break;
var actual = r.objective - base.objective;
if (Math.abs(actual - price * d) > 1e-6) break; // the rate has stopped holding
lastAgreeing = d;
}
return { price: price, holdsTo: lastAgreeing };
}
// never report the first field without the second
rangeOf(c, A, b, 0, 0.01, 5);
Self-studyWhere serious people disagree5 min▶
When a corner is degenerate, more constraints pass through it than the corner needs, and the shadow price stops being a single well defined number. What one more unit buys and what one fewer unit costs come apart, and the figure the solver returns is whichever one its final basis happens to encode. Two solvers, or the same solver with a different pivoting rule, can return different prices for the same constraint on the same problem, and both are correct as one-sided rates. What to do about that is a live argument.
One camp says report the number anyway. A decision maker asked to approve an hour of capacity needs one figure, and the right-hand rate is the one that answers the question actually being asked. Handing over an interval, or a caveat about bases, gets the whole analysis discarded in favour of somebody's instinct, and an instinct has no range either. On this view the measured walk is sufficient protection: whatever the ambiguity at the corner, the walk shows what the next units really return.
The other camp says a single number from a degenerate corner is a false precision that the four decimal places make worse. The price is an artefact of the basis and the basis is an artefact of the pivoting rule, so reporting it as a property of the business is a category error. On this view the honest output is the pair of one-sided rates, or nothing at all until the model is reformulated to remove the redundancy that caused the degeneracy in the first place.
Both camps contain people who have been burned by the other's practice. What they agree on is worth keeping: the number alone is not a deliverable. They differ on whether the fix is a range measured empirically or a model rebuilt so the question has one answer.
Never a price without its range
18 min hands onSix steps on the mill. The aim is that reporting a shadow price without measuring where it stops becomes physically uncomfortable, the way quoting an average without a spread does.
Read the three prices before you compute anything
Call OPT.solveLP(c, A, b) on the mill and print r.shadow, r.slack and r.binding side by side. Say out loud which row prices at zero and point at the field that explains why. Do not accept "because blending is not the bottleneck" as the answer; point at the 0.2414.
Predict the milling range before measuring it
Write down, on paper, how many extra milling hours you think the rate of 33.7931 survives. Most people write something between 5 and 50. Keep the number visible for the rest of the session, because the gap between it and the measurement is the lesson rather than the measurement itself.
Run the walk in hundredths
Use the live box or the fifteen-line function. Step milling up by 0.01 at a time and find the last step where predicted and actual still agree. Compare with what you wrote down. Then do the same for premium protein.
Multiply the price and get caught
Set the live box to milling and buy 10 hours. Note the predicted 337.93 and the actual 206.44 and work out the ratio yourself before the box tells you. Then find, by trial, the purchase size at which the overstatement crosses whatever error you would consider unacceptable in a business case.
Walk the row that prices at zero
Switch to blending and buy any amount at all. Predicted is zero, actual is zero, and they agree forever, which is the walk's way of saying there is no boundary to find. Say why that is a different kind of answer from milling's, and what would have to change about the mill for blending to acquire a range.
Write the sentence you would actually send
One sentence containing both halves, aimed at somebody deciding whether to buy milling capacity. It should be impossible to read it and come away thinking ten hours are worth 337.93. Keep it; session 6 is about the kinds of modelling error that make such a sentence confidently wrong rather than merely incomplete.
The habit to keep. When a model hands you a price per unit of anything, the next command you type is the walk. Two fields, always together: the rate, and the quantity it survives. If the range turns out to be longer than any purchase anyone is contemplating, you have lost ninety seconds and gained a defensible number. If it turns out to be 0.46 of an hour, you have just prevented the entire business case.
Three questions
Blending hours price at exactly 0 while the plan finishes the week with 0.2414 hours unused. What does the 0 mean?
The pairing rule is absolute. A row with slack left over has a price of zero, and the size of the leftover makes no difference at all: 0.2414 hours spare gives the same answer as 24 hours spare. The two output fields are computed from different parts of the tableau, so their agreement is a real check rather than a restatement.
A colleague values a purchase of 10 extra milling hours at 10 times 33.7931, which is 337.93. Re-solving gives an actual gain of 206.44. What went wrong?
Nothing was wrong with the price or with the solver. 33.7931 is exact at the margin and the walk confirms it to the last decimal at +0.01, +0.10 and +0.25. Past the end of the range the binding set changes, the gain curve bends down, and the straight-line extrapolation overstates by 1.64 times.
You are handed a model you did not build and asked how much a tight resource is worth. What do you do before answering?
The range is not in the solver output and there is no reliable shortcut to it, so it has to be measured. The loop costs one solve per step on a problem of this size. Reporting the rate without the quantity it survives is what turns an exact number into a wrong business case.
Homework
Thirty minutes, console first and paper second.
Write the walk yourself and check it against the page
Implement rangeOf from scratch without copying it, run it on all three Ravensworth rows, and confirm you get about +0.46 on milling and +0.77 on protein. Then deliberately loosen the comparison tolerance to 1e-2 and watch the reported range grow. Say why a sloppy tolerance always errs in the dangerous direction.
Predict what whole tonnes will do to all of this
The mill cannot bag 30.6897 tonnes of Standard. Before session 5, write down what you expect to happen to the optimum when the quantities are forced to whole numbers: how much margin you expect to lose, and whether you expect the plan to move up or down from 30.6897. Bring both answers.