Transportation problemsEdexcel A-Level Further Maths: Subtopic test

1. 1
   A company has three warehouses W1, W2 and W3 holding 20, 30 and 25 units of stock, and three shops S1, S2 and S3 needing 15, 35 and 25 units. The cost (£ per unit) of sending stock is: from W1, S1 £4, S2 £6, S3 £8; from W2, S1 £5, S2 £3, S3 £7; from W3, S1 £9, S2 £6, S3 £2. The north-west corner method is used to find an initial solution.

   (a)

   Using the north-west corner method, how many units are sent from W1 to S2?

   [1 mark]

   • A$20$
   • B$15$
   • C$5$
   • D$35$

   (b)

   How many cells are occupied in the north-west corner solution, and is it degenerate?

   [1 mark]

   • A5 cells, not degenerate
   • B4 cells, degenerate
   • C4 cells, not degenerate
   • D5 cells, degenerate

   (c)

   Calculate the total cost of the north-west corner solution.

   [2 marks]

   Total for question 1: 4 marks

2. 2
   In a transportation problem the sources are S1, S2 and S3 and the destinations are D1, D2 and D3. The occupied cells have unit costs S1D1 £4, S1D2 £3, S2D2 £5, S2D3 £6 and S3D3 £4. The unoccupied cells have unit costs S1D3 £8, S2D1 £5, S3D1 £9 and S3D2 £8. Shadow costs $R_i$ (sources) and $K_j$ (destinations) are found from $R_i+K_j=C_{ij}$ for occupied cells with $R_1=0$, and the improvement index of an unoccupied cell is $I_{ij}=C_{ij}-R_i-K_j$.

   (a)

   What is the shadow cost $R_2$?

   [1 mark]

   • A$2$
   • B$8$
   • C$5$
   • D$-2$

   (b)

   What is the improvement index of the unoccupied cell S2D1?

   [1 mark]

   • A$1$
   • B$3$
   • C$5$
   • D$-1$

   (c)

   Find the improvement indices of the other three unoccupied cells. State whether the current solution is optimal and, if not, which cell should enter.

   [2 marks]

   Total for question 2: 4 marks

3. 3
   Three quarries A, B and C supply 25, 45 and 30 tonnes of gravel to three building sites X, Y and Z, which need 20, 40 and 40 tonnes. The cost (£ per tonne) is: from A, X £3, Y £4, Z £9; from B, X £6, Y £6, Z £7; from C, X £2, Y £6, Z £6. The current solution sends 20 tonnes from A to X, 5 from A to Y, 35 from B to Y, 10 from B to Z and 30 from C to Z, at a total cost of £540.

   (a)

   Using $R_A=0$, find the shadow costs $R_B$, $R_C$, $K_X$, $K_Y$ and $K_Z$, and hence find the improvement index of the unoccupied cell CX.

   [3 marks]

   (b)

   Cell CX has a negative improvement index. Use the stepping-stone method to find the entering and exiting cells, the new solution, and its total cost.

   [4 marks]

   Total for question 3: 7 marks

4. 4
   A distributor has two depots, P and Q, holding 30 and 40 pallets. Three shops X, Y and Z need 20, 25 and 35 pallets. The cost (£ per pallet) of delivery is: from P, X £3, Y £5, Z £4; from Q, X £6, Y £2, Z £7. The distributor wishes to minimise the total delivery cost.

   (a)

   (i) Show that the problem is not balanced and explain how to balance it.
   (ii) Use the north-west corner method to find an initial solution to the balanced problem.
   (iii) Find the cost of this solution.

   [6 marks]

   (b)

   (i) Formulate the balanced problem as a linear programming problem.
   (ii) State the number of occupied cells a non-degenerate solution needs, and whether the north-west corner solution is degenerate.
   (iii) Interpret the value in cell DZ in context.

   [6 marks]

   Total for question 4: 12 marks

End of questions