Decision Mathematics 2: Dynamic programmingEdexcel A-Level Further Maths: Topic test

1. 1
   A courier firm plans a route from its depot S to a customer T. The roads and their lengths, in km, are: SA 4, SB 5, AC 5, AD 3, BD 2, BE 6, CT 7, DT 8 and ET 3. Dynamic programming is used to find the shortest route, working back from T.

   (a)

   What is the minimum distance from A to T?

   [1 mark]

   • A$12$ km
   • B$11$ km
   • C$8$ km
   • D$15$ km

   (b)

   Which expression gives the minimum distance from S to T?

   [1 mark]

   • A$\min(4+11,\ 5+9)$
   • B$\min(4+5,\ 5+6)$
   • C$\max(4+11,\ 5+9)$
   • D$4+5+11+9$

   (c)

   Find the minimum distance from S to T and state the route.

   [2 marks]

   Total for question 1: 4 marks

2. 2
   A haulage firm chooses a route from S to T for an abnormal load. The weight limit of each bridge, in tonnes, is: SA 12, SB 9, AC 7, AD 10, BC 11, BD 8, CT 9 and DT 6. The load must be as heavy as possible, so the route is chosen so that its lowest weight limit is as large as possible, using dynamic programming (a maximin problem).

   (a)

   What is the greatest weight that can be carried from A to T?

   [1 mark]

   • A$10$ tonnes
   • B$6$ tonnes
   • C$7$ tonnes
   • D$9$ tonnes

   (b)

   How is a route compared with other routes in this problem?

   [1 mark]

   • AAdd the limits along each route, then choose the route with the largest total
   • BTake the largest limit on each route, then choose the route for which this is smallest
   • CTake the smallest limit on each route, then choose the route for which this is smallest
   • DTake the smallest limit on each route, then choose the route for which this is largest

   (c)

   Find the best route from S to T and the greatest weight that can be carried.

   [2 marks]

   Total for question 2: 4 marks

3. 3
   A farmer has 4 tonnes of fertiliser to spread over three fields, F1, F2 and F3, in whole tonnes, and uses all of it. The extra wheat, in tonnes, for 0, 1, 2, 3 and 4 tonnes of fertiliser is: F1 0, 5, 8, 10, 11; F2 0, 4, 9, 11, 12; F3 0, 6, 7, 10, 13. The extra wheat is to be maximised using dynamic programming, with F3 as stage 1, F2 as stage 2 and F1 as stage 3. The state is the number of tonnes still to be spread.

   (a)

   Find the greatest extra wheat from fields F2 and F3 together when 2, 3 and 4 tonnes are available to be spread over these two fields, and how much F2 receives in each case.

   [3 marks]

   (b)

   Use your results from part (a) to find how the 4 tonnes should be shared between the three fields, and the greatest extra wheat.

   [4 marks]

   Total for question 3: 7 marks

4. 4
   A water company lays a pipeline from a reservoir S to a treatment works T along sections between junctions. The lengths of the possible sections, in km, are: SA 7, SB 8, SC 3, AD 4, AE 2, BD 8, BE 3, BF 4, CE 2, CF 7, DG 9, DH 8, EG 2, EH 8, FG 2, FH 7, GT 9 and HT 7. Every route from S to T passes through exactly one of A, B, C, then one of D, E, F, then one of G, H.

   (a)

   Use dynamic programming, working back from T, to find the shortest route from S to T and its length.

   [6 marks]

   (b)

   The company now wants the route whose longest single section is as short as possible (a minimax problem). Use dynamic programming to find this route and the length of its longest section. Find the total length of this route and compare it with your answer to part (a).

   [6 marks]

   Total for question 4: 12 marks

5. 5
   A tour operator plans a coach route from S to T and wants the greatest total scenic score. The scores for each road are: SA 6, SB 8, SC 5, AD 7, AE 4, BD 5, BE 9, CE 8, CF 6, DT 9, ET 6 and FT 10. Dynamic programming is used, working back from T.

   (a)

   What is the greatest total score from C to T?

   [1 mark]

   • A$16$
   • B$14$
   • C$10$
   • D$21$

   (b)

   Working back from T, what is done at each vertex to find its value?

   [1 mark]

   • ATake the minimum of the road score plus the value of the next vertex
   • BTake the maximum of the road scores only
   • CTake the maximum of the road score plus the value of the next vertex
   • DAdd all the road scores leaving the vertex

   (c)

   Find the route with the greatest total score and state its score.

   [2 marks]

   Total for question 5: 4 marks

6. 6
   A project has three stages. The firm chooses a method A, B or C at the first stage, then a method D or E at the second, and the project ends at T. The costs, in £ thousand, of moving between methods are: S to A 5, S to B 7, S to C 4; A to D 6, A to E 9; B to D 3, B to E 5; C to D 8, C to E 4; D to T 4 and E to T 3. Dynamic programming is used to minimise the total cost. The state is the method currently in use, and the stage is the number of steps left before T.

   (a)

   What is the minimum cost from state B to T?

   [1 mark]

   • A£8 thousand
   • B£7 thousand
   • C£10 thousand
   • D£12 thousand

   (b)

   What is the best action from state C, and what is its value?

   [1 mark]

   • AC to D, with value 12
   • BC to E, with value 4
   • CC to D, with value 8
   • DC to E, with value 7

   (c)

   Find the minimum total cost from S to T and the route that gives it.

   [2 marks]

   Total for question 6: 4 marks

7. 7
   A hiking club plans a route from S to T. The steepest gradient, as a percentage, on each section is: SA 4, SB 6, SC 7, AD 7, AE 3, BD 5, BE 8, CD 6, CE 4, DT 5 and ET 7. The club wants the steepest gradient on the route to be as small as possible (a minimax problem), and uses dynamic programming working back from T.

   (a)

   Find the minimax value from each of A, B and C to T.

   [3 marks]

   (b)

   Hence find the best route from S to T, and the steepest gradient on it. Show that no other route has a smaller steepest gradient.

   [4 marks]

   Total for question 7: 7 marks

8. 8
   A council has 5 gritters to share between three regions, N (north), E (east) and W (west). Each region must get at least 1 gritter and at most 3. The expected total delay to traffic, in hours, for 1, 2 and 3 gritters is: N 9, 5, 5; E 8, 5, 4; W 10, 8, 6. The total delay is to be minimised using dynamic programming, with W as stage 1, E as stage 2 and N as stage 3. The state is the number of gritters available to the current region and the regions after it.

   (a)

   Complete stages 1 and 2: find the minimum delay for W alone when it has 1, 2 or 3 gritters available, and the minimum combined delay for E and W when 2, 3, 4 and 5 gritters are available, with the number E should be given.

   [6 marks]

   (b)

   Use your tables to find how the 5 gritters should be shared and the minimum delay. The council then gets a sixth gritter. Use the same tables to find the new best sharing and delay, and explain why the stage 1 and 2 results can be used again.

   [6 marks]

   Total for question 8: 12 marks

End of questions