3 P61186A Turn over 2. Four workers, Ted (T), Harold (H), James (J) and Margaret (M), are to be assigned to four tasks, 1, 2, 3 and 4. Each worker must be assigned to just one task and each task must be done by just one worker. The profit, in pounds, resulting from allocating each worker to each task, is shown in the table below. The profit is to be maximised. 1 2 3 4 T 103 97 74 80 H 201 155 145 155 J 111 80 77 92 M 203 188 137 184 (a) Reducing rows first, use the Hungarian algorithm to obtain an allocation that maximises the total profit. You must make your method clear and show the table after each stage. (6) (b) Determine the resulting total profit. (1) (Total for Question 2 is 7 marks) 4 P61186A 3. B 24 24 14 –24 –24 –30 –17 –25 29 20 19 27 32 17 D C E F 19 G A H S I T J 13 28 13 x 18 Figure 1 In Figure 1 the weight of arc SB is denoted by x where x . 0 (a) Explain why Dijkstra’s algorithm cannot be used on the directed network in Figure 1. (1) It is given that the minimum weight route from S to T passes through B. (b) Use dynamic programming to find (i) the range of possible values of x (ii) the minimum weight route from S to T. (12) (Total for Question 3 is 13 marks) 5 P61186A Turn over 4. Player B Option X Option Y Option Z Option P 3 –2 0 Player A Option Q –4 4 –2 Option R 1 2 –1 A two person zero-sum game is represented by the pay-off matrix for player A shown above. (a) Verify that there is no stable solution to this game. (2) Player A intends to make a random choice between options P, Q and R, choosing option P with probability p1, option Q with probability p2 and option R with probability p3 Player A wants to find the optimal values of p1 , p2 and p3 using the Simplex algorithm. Player A formulates the following linear programming problem for the game, writing the constraints as inequalities. Maximise P = V subject to V . 3p1 – 4p2 + p3 V . –2p1 + 4p2 + 2p3 V . –2p2 – p3 p1 + p2 + p3 - 1 p1 . 0, p2 . 0, p3 . 0, V . 0 (b) Correct the errors made by player A in the linear programming formulation of the game, giving reasons for your answer. (3) (c) Write down an initial Simplex tableau for the corrected linear programming problem. (3) The Simplex algorithm is used to solve the corrected linear programming problem. The optimal values are p1 = 0.6, p2 = 0 and p3= 0.4 (d) Calculate the value of the game to player A. (2) (e) Determine the optimal strategy for player B, making your reasoning clear. (4) (Total for Question 4 is 14 marks)