5 Turn over P72118A 5. A standard transportation problem is described in the linear programming formulation below. Let xij be the number of units transported from i to j where  i ∈ {A, B, C, D} j ∈ {R, S, T}  and  xij  0 Minimise  P = 23xAR + 17xAS + 24xAT + 15xBR + 29xBS + 32xBT + 25xCR + 25xCS + 27xCT + 19xDR + 20xDS + 25xDT subject to ∑xAj  34 ∑xBj  27 ∑xCj  41 ∑xDj  18 ∑xiR  44 ∑xiS  37 ∑xiT  k Given that the problem is balanced, (a) state the value of k. (1) (b) Explain precisely what the constraint ∑xiR  44  means in the transportation problem. (2) (c) Use the north‑west corner method to obtain the cost of an initial solution to this transportation problem. (2) (d) Perform one 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 5 is 9 marks)