Project activities can be shortened by paying for them, at a known cost per day each, down to a floor. Minimising the bill subject to finishing by a deadline is a linear programme whose deadline is a single right-hand side, so the exact time-cost curve is the ranging function of “Duality and Sensitivity Analysis” applied to that row. The curve bends where the set of critical paths changes, and the first day is not always bought on the activity a reader expects.
Core ideas
Three ideas: what the variables are, why the curve is convex, and why the programme's answer is checked by something that is not a programme.
Write y_i for the number of days taken off activity i, between zero and its crash room normal − crash. Its duration is then normal − y_i and its cost is normal cost + rate × y_i. The objective is only sum rate × y, because the normal cost is paid whatever happens — 290 on the lab's project — and a constant in the objective shifts the curve without bending it.
Each day taken off the finish costs at least as much as the day before. On the lab's project, reading from the loosest deadline inwards, the days cost 15, 20, 30 and 35. The reason is on the screen at the moment it happens: once a second path becomes critical, a day off the finish has to be bought on both paths at once, and the bill per day is the sum of two rates rather than one.
A linear programme reports an optimal bill and a set of y values. Whether those durations actually finish the project on time is a separate question with a separate method: a forward and a backward pass over the crashed durations, sharing no arithmetic with the simplex. The lab runs it on every plan it prints, and re-solves each piece of the curve from scratch at its own endpoint as well.
The material
The model, the rates, the programme, and the exact curve on a four-activity project where the first day is not bought where you would expect.
An activity has a normal duration and a normal cost, and a crash duration and a crash cost. Its crash room is normal − crash days and its rate is (crash cost − normal cost) / (normal − crash), the cost of one day, assumed constant across the range.
The decision variable y_i is the number of days bought on activity i, with 0 ≤ y_i ≤ crash room. The duration becomes normal − y_i and the bill is sum rate × y.
Two refusals are worth naming because both are modelling errors rather than typing errors, and the lab rejects them by name. An activity that crashes to a longer duration is not a crashable activity; and one that is cheaper crashed than normal makes the normal plan the wrong baseline, so the whole curve is measured from the wrong place.
Minimise sum rate_i y_i subject to: 0 ≤ y_i ≤ crash room_i for every activity; a timing row for every precedence, saying that an activity starts no earlier than its predecessors finish with their crashed durations; and one deadline row saying the project finish is at most d.
The deadline appears in exactly one row, as its right-hand side. That is what makes the exact time-cost curve a right-hand-side ranging problem rather than a family of separate solves.
The rates are the data to read first. C is the cheapest activity to shorten at 15 a day, A and B cost 20, and D costs 30. But cheapness is not the whole story: A and D lie on both paths, so a day bought on either shortens the project by a day whatever else is happening, while B and C each lie on one path and a day bought there only helps while that path is the long one.
A is the obvious candidate: it is critical, it lies on both paths, and shortening it always shortens the project. It is also 20 a day, and it is not what the programme buys first. The first day costs 15 and is bought on C.
The reason is the day of slack on B. At normal durations A C D is 14 and A B D is 13, so one day can be taken off the longer path alone, and C is the cheapest way to do it. After that day both paths are 13 and both are critical, and from then on a day off the finish needs a day off both — which is when A, at 20 a day on both paths at once, becomes the cheapest thing to buy. Nothing is bought on A until the two middle paths are critical together.
That ordering is read off the programme rather than reasoned towards: the lab re-solves at every integer deadline, and A first appears at d = 12. An argument starting from “shorten the critical activity on both paths” buys A first and pays 20 for a day that was on sale at 15.
The slopes go 15, 20, 30, 35 as the deadline tightens, and each increase has a cause. 15 buys the slack on B. 20 buys A, which shortens both paths at once, for two days until A runs out of room. 30 buys D, the other shared activity, at its higher rate. 35 is the last day and it is bought on two activities at once — B at 20 and a second day of C at 15 — because by then every path must be shortened separately.
The trap is counting pieces as rates. The lab's straight-chain preset reports three pieces with slopes 15, 20 and 20: a piece is an interval on which one basis stays optimal, and the basis can change without the price per day changing.
The first is critical-path method run on the crashed durations. At d = 11 the plan buys A by two and C by one, giving durations A 4, B 4, C 4, D 3; a forward and a backward pass over those finish the project on day 11 with all four activities critical. That is a different calculation from the simplex, done on the answer the simplex produced, and the lab runs it on every plan it prints.
The second is a fresh solve at each breakpoint. Ranging one right-hand side through a sequence of bases is exactly the sort of machinery that can drift, so every piece is re-solved from scratch at its own left endpoint and the two values compared. The panel reports the count, and on all three presets it is every piece.
What the model leaves out is the usual gap between a project plan and a project. The rates are constant and real overtime is not; the activities are independent, so two crashed at once never compete for the same people; and the durations are point estimates with no uncertainty on them. The programme prices the plan it was given exactly, which is a different thing from pricing the project.
Interactive
The crash bill is a linear programme; its curve bends where the critical path changes
Method
Five steps, and the last is the one that catches a plan that does not work.
Room is normal − crash; rate is the cost difference divided by the room, exactly. An activity with no room has no rate and is not a decision. Refuse an activity that is cheaper crashed than normal rather than modelling it: the normal plan is then not the baseline and the curve measures from the wrong place.
The first gives the project length you are paying to reduce, and the slack on each activity; the second gives the floor below which no amount of money helps. On the lab's project that is 14 and 9, and every deadline outside that range is either free or impossible.
Days bought as the variables, rate times days as the objective, crash room as upper bounds, one timing row per precedence and one deadline row. The normal cost is not in the objective; add it back at the end.
This is right-hand-side ranging on a single row, and it produces exact breakpoints rather than a scan over sampled deadlines. Read the cost per day off each piece, and expect the slopes to rise as the deadline tightens.
Forward and backward over normal − y, and confirm the project really finishes by the deadline. This is not a formality: it is the only check in the procedure that does not share arithmetic with the thing being checked, and it is what turns an optimal tableau into a plan you can hand to somebody.
The lab's opening preset, priced at every integer deadline. Every figure is what the panel reports as the deadline slider is moved.
The first purchase is the one to remember. A is critical, lies on both paths and costs 20; C is on one path and costs 15. The programme buys C, because at normal durations B has a day of slack and only the longer path needs shortening. Buy A first and you have paid 20 for a day that was on sale at 15.
After that day both paths are 13 and every later day has to be bought on both. That is where the 20 comes from — A shortens both at once — and it is why the slopes only ever rise. Convexity here is not an assumption about the cost data; it is a consequence of paths becoming critical and never becoming uncritical again.
For a rehearsal, switch to the preset where the cheapest activities are not the ones that matter: A 4:2:40:48, B 7:4:60:120 | A, C 2:1:20:24, D 5:3:40:70 | C. The supplied first move is that there are two chains, A B at 11 days and C D at 7, so only the first decides the finish and C and D have four days of slack each. A and C both cost 4 a day, the cheapest on the project. Predict which one the programme buys and what the first two days cost, before the panel says.
You should be able to compute crash rooms and rates as exact fractions, run the critical-path method at normal and at crash durations to bracket the deadlines that mean anything, write the programme with the deadline as one right-hand side and the normal cost outside the objective, read the exact curve off a ranging of that row, say why the slopes rise, and confirm any chosen plan with a forward and a backward pass over the durations it bought.
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.