Transportation problems

Transportation problems Test

Spec 1.1–3 · Edexcel A-Level Further Maths: Subtopic test

Studying this course? Keep your progress in one place.

Two ways to do this test

Question by question

One question at a time. Each answer is marked the moment you hand it in, so you learn as you go. Drago helps if you get stuck. All 10 questions, or just 5.

Exam mode

The whole paper in one go, timed like the real exam. Nothing is marked until you hand it in, then you get every mark explained.

10 questions, 27 marks

Edexcel A-Level Further Maths

Transportation problems

Total 27 marks

Name

Class

Date

  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]
    • A2020
    • B1515
    • C55
    • D3535
    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 ×\times unit cost for the occupied cells, 15(4)+5(6)+30(3)+25(2)15(4)+5(6)+30(3)+25(2)
    A1: £230

    Accept: 230 without units

    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 RiR_i (sources) and KjK_j (destinations) are found from Ri+Kj=CijR_i+K_j=C_{ij} for occupied cells with R1=0R_1=0, and the improvement index of an unoccupied cell is Iij=Cij−Ri−KjI_{ij}=C_{ij}-R_i-K_j.
    (a)
    What is the shadow cost R2R_2?
    [1 mark]
    • A22
    • B88
    • C55
    • D−2-2
    Show the mark scheme

    Mark scheme

    Answer: A
    (b)
    What is the improvement index of the unoccupied cell S2D1?
    [1 mark]
    • A11
    • B33
    • C55
    • D−1-1
    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: K3=4K_3=4, R3=0R_3=0, giving I13=8−0−4=4I_{13}=8-0-4=4, I31=9−0−4=5I_{31}=9-0-4=5 and I32=8−0−3=5I_{32}=8-0-3=5
    B1: S2D1 (index
    −1-1) is the only negative index, so the solution is not optimal and S2D1 should enter
    Accept: shadow costs
    R=(0,2,0)R=(0,2,0), K=(4,3,4)K=(4,3,4)

    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 RA=0R_A=0, find the shadow costs RBR_B, RCR_C, KXK_X, KYK_Y and KZK_Z, and hence find the improvement index of the unoccupied cell CX.
    [3 marks]
    Show the mark scheme

    Mark scheme

    M1: uses Ri+Kj=CijR_i+K_j=C_{ij} for the occupied cells, starting from RA=0R_A=0 (e.g. KX=3K_X=3, KY=4K_Y=4)
    A1:
    RB=2R_B=2, RC=1R_C=1, KX=3K_X=3, KY=4K_Y=4, KZ=5K_Z=5
    A1:
    ICX=2−1−3=−2I_{CX}=2-1-3=-2
    Accept:
    ICXI_{CX} found by the stepping-stone loop, with cost change −2-2 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:
    θ=min⁡(30,35,20)=20\theta=\min(30,35,20)=20, so AX exits
    A1: new solution CX 20, CZ 10, BZ 30, BY 15, AY 25

    A1: new cost £500 (a saving of
    20×2=£4020\times2=£40)
    Accept: loop traced in the opposite direction

    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]
    Show the mark scheme

    Mark scheme

    B1: (i) total supply 7070 is less than total demand 8080
    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)
    20(3)+10(5)+15(2)+25(7)+10(0)=£31520(3)+10(5)+15(2)+25(7)+10(0)=£315
    Accept: the dummy placed as a row or a column
    (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]
    Show the mark scheme

    Mark scheme

    B1: (i) variables xij≥0x_{ij}\ge0, the number of pallets from depot ii to shop jj (including the dummy D)
    B1: (i) minimise
    3xPX+5xPY+4xPZ+6xQX+2xQY+7xQZ3x_{PX}+5x_{PY}+4x_{PZ}+6x_{QX}+2x_{QY}+7x_{QZ} (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)
    m+n−1=3+3−1=5m+n-1=3+3-1=5; the solution has 5 occupied cells, so it is not degenerate
    B1: (iii)
    xDZ=10x_{DZ}=10 means shop Z receives 10 pallets fewer than it needs
    Accept: the dummy terms written with coefficient 0

    Total for question 4: 12 marks

End of questions

Subtopic tests