D2 June 2010 Q4
4.
Figure 1 represents the maintenance choices a council can make and their costs, in £1000s, over the next four years.
The council wishes to minimise the greatest annual cost of maintenance.
(a) Use dynamic programming to find a minimax route from S to T. (9)
(b) State your route and the greatest annual cost incurred by the council. (2)
(c) Calculate the average annual cost to the council. (2)
| Scheme | Marks | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 1M1 A1 2M1 A1 A1 3M1 A1ft A1ft A1ft | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| (9) |
| Scheme | Marks |
|---|---|
| Route: SAEHT Greatest annual cost: £38 000 | M1 A1ft |
| (2) |
| Scheme | Marks |
|---|---|
| Average expenditure \(\dfrac{37 + 38 + 34 + 21}{4} = \dfrac{130}{4} =\) £32 500 | M1 A1 |
| (2) | |
| (13 marks) |