Edexcel A-Level Further Maths
Transportation problems
Total 27 marks
Name
Class
Date
- 1A 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
- B
- C
- D
Show the mark scheme
Mark scheme
Answer: C(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
Show the mark scheme
Mark scheme
Answer: B(c)Calculate the total cost of the north-west corner solution.[2 marks]Show the mark scheme
Mark scheme
M1: sum of quantity unit cost for the occupied cells,
A1: £230
Accept: 230 without unitsTotal for question 1: 4 marks
- 2In 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 (sources) and (destinations) are found from for occupied cells with , and the improvement index of an unoccupied cell is .(a)What is the shadow cost ?[1 mark]
- A
- B
- C
- D
Show the mark scheme
Mark scheme
Answer: A(b)What is the improvement index of the unoccupied cell S2D1?[1 mark]- A
- B
- C
- D
Show the mark scheme
Mark scheme
Answer: D(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]Show the mark scheme
Mark scheme
B1: , , giving , and
B1: S2D1 (index ) is the only negative index, so the solution is not optimal and S2D1 should enter
Accept: shadow costs ,Total for question 2: 4 marks
- 3Three 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 , find the shadow costs , , , and , and hence find the improvement index of the unoccupied cell CX.[3 marks]
Show the mark scheme
Mark scheme
M1: uses for the occupied cells, starting from (e.g. , )
A1: , , , ,
A1:
Accept: found by the stepping-stone loop, with cost change per tonne(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]Show the mark scheme
Mark scheme
M1: loop CX , CZ , BZ , BY , AY , AX
A1: , so AX exits
A1: new solution CX 20, CZ 10, BZ 30, BY 15, AY 25
A1: new cost £500 (a saving of )
Accept: loop traced in the opposite directionTotal for question 3: 7 marks
- 4A 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.[6 marks]
(ii) Use the north-west corner method to find an initial solution to the balanced problem.
(iii) Find the cost of this solution.Show the mark scheme
Mark scheme
B1: (i) total supply is less than total demand
B1: (i) add a dummy depot D with supply 10 and zero cost to every shop
M1: (ii) north-west corner starting at PX: PX 20, PY 10
A1: (ii) QY 15, QZ 25
A1: (ii) DZ 10
B1: (iii)
Accept: the dummy placed as a row or a column(b)(i) Formulate the balanced problem as a linear programming problem.[6 marks]
(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.Show the mark scheme
Mark scheme
B1: (i) variables , the number of pallets from depot to shop (including the dummy D)
B1: (i) minimise (dummy costs are 0)
B1: (i) supply constraints: row sums equal 30, 40 and 10
B1: (i) demand constraints: column sums equal 20, 25 and 35
B1: (ii) ; the solution has 5 occupied cells, so it is not degenerate
B1: (iii) means shop Z receives 10 pallets fewer than it needs
Accept: the dummy terms written with coefficient 0Total for question 4: 12 marks
End of questions