4 P74086A   3. The table below shows the stock held at each supply point and the stock required at each demand point in a standard transportation problem. The table also shows the cost, in pounds, of transporting the stock from each supply point to each demand point. Q A B C D Demand R S Supply 23 18 12 45 8 10 14 27 11 14 21 34 19 15 11 50 75 37 44 The problem is partially described by the linear programming formulation below. Let xij be the number of units transported from i to j where i A B C D , , , j Q R S , , and xij 0 Minimise P x x x x x x x x x x 23 18 12 1 8 0 14 11 14 21 19 AQ AR AS BQ BR BS CQ CR CS DQ DR DS 15 11 x x (a) Write down, as inequalities, the constraints of the linear program. (2) (b) Use the north-west corner method to obtain an initial solution to this transportation problem. (1) (c) Taking AS as the entering cell, use the stepping-stone method to find an improved solution. Make your route clear. (2) (d) Perform one further iteration of the stepping-stone method to obtain an improved solution. You must make your method clear by showing the route and the • shadow costs • improvement indices • entering cell and exiting cell (4) (Total for Question 3 is 9 marks)   5 Turn over P74086A 4. Four students, A, B, C and D, are to be allocated to four rounds, 1, 2, 3 and 4, in a competition. Each student is to take part in exactly one round and no two students may play in the same round. Each student has been given an estimated score for each round. The estimated scores for each student are shown in the table below. 1 A B C D 2 3 4 34 20 18 15 49 31 12 34 48 27 23 26 52 45 42 42 (a) Reducing rows first, use the Hungarian algorithm to obtain an allocation that maximises the total estimated score. You must make your method clear and show the table after each stage. (7) (b) Find this total estimated score. (1) (Total for Question 4 is 8 marks)