P66795A 2 Write your answers in the answer book provided. 1. Five workers, A, B, C, D and E, are available to complete four tasks, P, Q, R and S. Each task must be assigned to exactly one worker and each worker can do at most one task. Worker B cannot be assigned to task R. The amount, in pounds, that each worker will earn if they are assigned to each task is shown in the table below. P Q R S A 55 56 58 57 B 60 61 – 64 C 59 60 62 63 D 64 66 71 69 E 65 68 72 66 The Hungarian algorithm is to be used to find the maximum total amount that can be earned by the five workers. (a) Explain how the table should be modified to allow the Hungarian algorithm to be used, giving reasons for your answer. (2) (b) Reducing rows first, use the Hungarian algorithm to obtain the maximum possible total earnings. You should explain how any initial row and column reductions were made and how you determined if the table was optimal at each stage. (7) (Total for Question 1 is 9 marks) P66795A 3 Turn over 2. A G C S D T F B E H 30 25 60 13 17 41 24 2 0 32 13 19 1 5 36 64 28 22 49 15 66 24 47 21 31 14 19 8 25 17 35 74 15 28 20 11 56 32 19 37 Figure 1 Figure 1 shows a capacitated, directed network. The number on each arc represents the capacity of that arc. The numbers in circles represent an initial flow. (a) State the value of the initial flow. (1) (b) Obtain the capacity of the cut that passes through the arcs AG, CG, GF, FT, FH and EH. (1) (c) Complete the initialisation of the labelling procedure on Diagram 1 in the answer book by entering values along SD, BD, BE and GF. (2) (d) Use the labelling procedure to find a maximum flow through the network. You must list each flow-augmenting route you use, together with its flow. (3) (e) Use the answer to part (d) to add a maximum flow pattern to Diagram 2 in the answer book. (1) (f) Prove that your answer to part (e) is optimal. (3) (Total for Question 2 is 11 marks) P66795A 4 3. In your answer to this question you must show detailed reasoning. A two-person zero-sum game is represented by the following pay-off matrix for player A. B plays X B plays Y A plays Q 4 −3 A plays R 2 −1 A plays S −3 5 A plays T −1 3 (a) Verify that there is no stable solution to this game. (2) Player B plays their option X with probability p. (b) Use a graphical method to find the optimal value of p and hence find the best strategy for player B. (6) (c) Find the value of the game to player A. (1) (d) Hence find the best strategy for player A. (2) (Total for Question 3 is 11 marks)