Back to the on-screen lesson ·
A shadow price is a gradient with a range attached, and past the range the value bends.
Paper packet. Every task here also exists on screen, where it is checked automatically; answers written on paper are not assessed by Nydus. When you are back at a device, enter your answers there.
By the end of this lesson you will be able to find the range of a right-hand side over which the optimal basis does not change, read the allowable decrease and increase of a sensitivity report, say what a zero shadow price, a zero allowable increase and a zero reduced cost each mean, and compute the optimum on both sides of the kink where the rate changes.
You can read a shadow price as the rate at which the optimum improves. This lesson attaches the missing half of that sentence: over what range of the capacity the rate is the rate.
The range of a right-hand side is the interval over which the optimal basis does not change. Its two halves are the allowable decrease and the allowable increase. At the end of a range the optimal value's graph has a kink, and past the kink a new shadow price applies.
A shadow price is the gradient of the optimal value in a capacity, and a gradient is only meaningful with a range attached. The range is the interval of the right-hand side over which the same basis stays optimal: inside it, each extra unit is worth the same shadow price and the optimal value is a straight line; at the ends, some other constraint becomes binding and the basis changes.
The function of capacity that results is piecewise linear and concave: a sequence of straight segments whose gradients decrease. Relaxing a constraint can only ever buy less once another has begun to bind, so a reported sequence of rising shadow prices would be a defect rather than a finding.
Objective coefficients have ranges too, and they work the other way round: the current corner stays optimal while the objective's slope stays between the slopes of the two constraints meeting there.
One at a time. Every range is computed with everything else held still. Two limits can each move inside their own range and together change the basis.
Another way: steps
Another way: picture
The optimal value drawn against one capacity: a rising line that bends downwards at each kink, never upwards. Each straight stretch is one basis, each gradient is that basis's shadow price, and each kink is where a new constraint starts to bind.
The shadow price is multiplied by a quantity far larger than the allowable increase, which values a block of capacity at its first unit's rate and overstates the gain. The second error is moving two right-hand sides at once and checking each against its own range: the ranges were each computed with the other held fixed, and both being satisfied does not mean the basis survives.
Wood has shadow price $\tfrac{90}{11}$ at a limit of $100$, and the labour row is the other binding one.
A rate at a point.
As wood rises, the plan makes more tables and fewer chairs, until chairs reach zero. That is where the basis changes.
The end of the range.
Past it, wood is no longer the scarce thing in the same way, and its price falls. The report gives the limit at which that happens.
A new segment, a shallower gradient.
The basis is already at the end of its range in that direction.
No room left.
One more unit of capacity changes which constraints bind, so the current shadow price applies to no further units at all.
Maximise $9x + 3y$ over $x \ge 0$, $y \ge 0$, $x \le 5$, $y \le 5$, $x + y \le s$. For which values of $s$ does the optimum stay at the crossing of $x + y = s$ with $x = 5$? Give the interval.
This task has no paper form; do it on a device.
A report says the wood limit is $22$ with an allowable decrease of $2$ and an allowable increase of $3$, and the labour limit is $21$ with an allowable decrease of $7$ and increase of $9$. Fill in the ends of each range.
| Lowest | Current | Highest | |
|---|---|---|---|
| Wood | 22 | ||
| Labour | 21 |
A sensitivity report on a program with a wood limit of $34$ carries these lines. Match each to what it tells you.
| The row has capacity to spare | One more unit would change the optimal basis | There is a second optimal plan | No rise in that cost can change the plan | |
|---|---|---|---|---|
| The wood row's shadow price is $0$ | ||||
| The wood row's allowable increase is $0$ | ||||
| A variable outside the basis has reduced cost $0$ | ||||
| A cost coefficient's allowable increase is unlimited |
A binding row has shadow price $9$ and an allowable increase of $6$. Its capacity rises by $8$, which is past the end of the range. What happens to the rate of improvement?
The optimum is $47$, a binding row has shadow price $5$, and a supplier offers $2$ extra units, which is inside the allowable increase. What is the most worth paying per unit?
Answer:
The optimum is $76$ and a binding row has shadow price $6$ over an allowable increase of $2$. Past that, the new shadow price is $2$. Fill in the optimum at the top of the range and one unit beyond it.
| The optimum | |
|---|---|
| At the top of the range | |
| One unit further |
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
Maximise $4x + 3y$ over $x \ge 0$, $y \ge 0$, $x \le 7$, $y \le 8$, $x + y \le s$. For which values of $s$ does the optimum stay at the crossing of $x + y = s$ with $x = 7$? Give the interval.
This task has no paper form; do it on a device.
You can find and read the range over which a shadow price holds, and work out the optimum past the end of it. Say in your own words why the shadow prices of one capacity come in a decreasing sequence.
7. Your turn: a row's allowable increase is $0$. What does that say?, step 2