A shadow price is the change in the optimum per unit of a right-hand side, and it is valid only while the current basis stays feasible. The interval over which that holds comes from a ratio test of the plan against one column of the basis inverse, and outside it a different basis and a different price take over. So the optimum is a piecewise-linear function of each right-hand side, with a corner at every breakpoint, and a price is a rate with a stated interval rather than a derivative.
Core ideas
The price is the easy half and it is already in the tableau. The hard idea is that the number is attached to an interval, and outside that interval it is not approximately right.
Change bᵢ and the plan changes to B⁻¹b with the same basis, so z* changes by c_BᵀB⁻¹ times the change — that is, by yᵢ per unit. The relationship is exactly linear for as long as that basis remains the right one, which makes z* a straight line in bᵢ over an interval and not a curve at all.
The basis stays feasible while every entry of B⁻¹(b + Δeᵢ) stays non-negative. Each basic variable gives one bound on Δ, from its own entry divided by its entry in column i of B⁻¹, and the binding ones give the two ends. At each end some basic variable is exactly zero and a different basis takes over.
Past a breakpoint the slope changes, so extending the old price gives an answer that is wrong by an amount that grows with the distance. On the workshop, four units past the end of assembly's range the naive prediction is out by 2 and the true slope is zero: more assembly capacity has stopped being worth anything at all.
The material
Where the range comes from, what the optimum looks like as a function of one right-hand side, and the two different ways a row can be worth nothing.
The shadow price of constraint i is the rate of change of the optimal objective value with respect to bᵢ, holding everything else fixed, over the interval in which the current optimal basis remains feasible. It is the i-th entry of y = c_BᵀB⁻¹.
The interval is part of the answer. This course never prints a price without it, because a price quoted outside its interval is not approximately right — it is a different number.
Why the price is the slope at all is one line, now that the tableau has been read. With basis B fixed, the plan is B⁻¹b and the value is c_BᵀB⁻¹b = yᵀb. Add Δ to bᵢ and the value becomes yᵀb + yᵢΔ. So the value is linear in bᵢ with slope yᵢ, for exactly as long as B is still the optimal basis — and the only thing that can go wrong is feasibility, because the objective row does not involve b at all.
Let d = B⁻¹eᵢ be column i of the basis inverse and x_B = B⁻¹b the current basic plan. The current basis stays optimal for bᵢ + Δ exactly while x_B + Δd ≥ 0, which gives
Δ ≥ max over rows with dᵣ > 0 of (−x_Bᵣ / dᵣ) and Δ ≤ min over rows with dᵣ < 0 of (−x_Bᵣ / dᵣ),
with an infinite bound on either side when no row constrains it. Inside that interval z* changes by yᵢ per unit; at each end some basic variable reaches exactly zero, and past it a different basis is optimal.
Cutting is worth 0 over 2 ≤ b1, with no upper limit. Glazing is worth 3/2 over 6 ≤ b2 ≤ 18. Assembly is worth 1 over 12 ≤ b3 ≤ 24.
Read the first one carefully: the cutting row is worth nothing, and its range still has an end. Below b1 = 2 the row starts to bite and the price stops being zero, which is a thing a reader who has been told that slack rows are worth nothing does not expect.
The three slopes are the whole lesson in one row of numbers. Assembly capacity is worth 5/2 an hour while it is the only thing in short supply, worth 1 an hour once cutting has begun to bind as well, and worth nothing at all past 24, where the plan has run out of cutting capacity and more assembly hours cannot be used. Three prices, one row, and each true on its own interval.
At b3 = 26 the naive extension predicts 44 and the answer is 42. That is not a small error in a linear approximation: the function is exactly linear and the slope used was the wrong one, because the basis that slope belonged to stopped being feasible at 24. The lab checks this the hard way, by solving again at every endpoint and at a point a hundredth outside it, and requiring the prediction to break there.
The workshop's cutting row has 2 units spare at the optimum, so complementary slackness forces its price to zero: more of a resource you are not using cannot help. That is the easy case and it is the one most readers expect.
The other case is max x + y subject to x ≤ 2, y ≤ 2, x + y ≤ 4. At (2, 2) all three rows are tight, and the firing row is priced at 0 over 4 ≤ b3 — tight, fully used, and worth nothing. Its range is also one-sided at the current value, which is the second way degeneracy shows up here: the kiln and wheel rows are priced at 1 over 0 ≤ b ≤ 2, and 2 is where they already are, so there is no room above at all.
That last observation is worth stating plainly. A range whose end is the current right-hand side means the price is valid for decreases and for nothing else. Quoting it as the value of one more unit is then simply wrong, and a degenerate optimum is where it happens.
This is also the lesson that replaces calculus on this path, and it is worth saying why the replacement is an improvement rather than a workaround. At a breakpoint z* has a corner: the slope arriving from the left and the slope leaving to the right are both correct and they are different — 5/2 and 1 at b3 = 12, 1 and 0 at b3 = 24. A derivative would have to choose one of them or fail to exist. A rate with a stated interval reports both, and it is the honest object.
Interactive
z drawn as an exact piecewise-linear function, and the price as one segment's slope
Method
The price and the range are one answer in two parts, and the second part is the one that gets dropped.
Under the initial identity column for that row, as in the previous lesson. For a row with slack the answer is zero before you compute anything, by complementary slackness.
Divide each basic variable's current value by its entry in column i of B⁻¹. The positive entries bound the decrease and the negative entries bound the increase. Where no entry constrains a side, that side is unbounded — a one-sided interval is a real answer.
A price with no interval attached is a number with no claim attached. Write y = 1 over 12 ≤ b3 ≤ 24, and notice at once when one end of the interval is the current value: then the price is valid in one direction only.
Inside the range the prediction z* + yᵢΔ is exact. Make one prediction inside and one outside, and check both. The one outside is the one that teaches: it fails by an amount that grows, and the basis named on the other segment is the reason.
One row, one price, one interval, and two predictions. The second prediction is wrong on purpose, and the size of the error is what the interval was protecting you from.
The s1 = 0 line is the mechanism. The range ends where a basic variable reaches zero, and that is what the ratio test computes; one unit further and that variable would be negative, so a different basis — and a different price — has taken over.
For a faded rehearsal, do the glazing row on the same programme. The supplied move is that column 2 of the basis inverse is (−1/3, 1/3, 1/2), so the signs of the three ratios are the other way round from the ones above. Compute the interval, predict z* at b2 = 15 and at b2 = 21, and check both. One of them is inside the range and one is not; say which before you solve.
Then do the three-activity preset, whose three prices and ranges are all whole numbers: 3 over 8 ≤ b1 ≤ 12, 2 over 6 ≤ b2 ≤ 10, and 0 over 2 ≤ b3. Predict the effect of one more unit of each and check all three at once.
You should be able to read a price out of the objective row, compute its interval by a ratio test against one column of the basis inverse, predict the optimum for a change inside the interval and confirm it, and say why the same prediction fails outside — naming the basic variable that reached zero at the end.
Something to change about this lesson? Write it down, tick it off when it is handled, and export the list when you want to act on it. Kept in this browser only: nothing is sent anywhere, and nobody is notified.
No recommendations yet for this lesson.