Salam Academy
Sign inCreate account
Contents · 0% complete
  1. Learning objectives
  2. Core idea
  3. Key formulae
  4. Worked examples
  5. Explore the graph
  6. Common mistakes
  7. Exam tip
  8. Guided practice
  9. Practice questions
  10. Challenge
  11. Summary
  12. Quick quiz
  13. Same topic, different board
  14. Past paper questions
Learn9FM0Option · Decision Mathematics 2Transportation problemsThe stepping-stone method
Transportation problems · Subtopic 1 of 1

Transportation Problems

Goods move from supply points to demand points at given unit costs. Balance supply and demand (dummy if needed), start with the north-west corner, then compute shadow costs Ri+Kj=CijR_i+K_j=C_{ij} on occupied cells and improvement indices Iij=Cij−Ri−KjI_{ij}=C_{ij}-R_i-K_j on empty ones. A negative index means a cheaper plan: move stock round a stepping-stone loop.

Edexcel 9FM0 Option≈ 50 minRevision 1 · updated 2026-10-27
Section 1 of 14

Learning objectives

  • Balance a transportation problem and find a north-west corner solution.
  • Calculate shadow costs and improvement indices.
  • Use the stepping-stone method to reach the optimum.
Pause and think

Two warehouses supply three shops. Why might sending everything to the nearest shop not be cheapest overall?

Section 2 of 14

Core idea

Start hereWarehouses and shops

Two warehouses must supply three shops, and every route has its own cost per item. Start with any sensible plan, then ask: would shifting a few items along some loop save money? Shadow costs answer that question for every empty route at once.

The big idea

Find an initial solution (north-west corner), compute shadow costs from occupied cells, and improvement indices for empty cells. Bring in the most negative index via a stepping-stone loop; stop when no index is negative.

1. Initial solution

Supplies A30A30, B20B20; demands X10X10, Y25Y25, Z15Z15; costs AA: 4,6,84,6,8; BB: 5,3,75,3,7.

Worked exampleNorth-west corner

Find the NW corner solution and its cost.

Goal
Allocation and cost.
Strategy
Fill from top-left, moving right or down.
  1. AX=10AX=10
    XX satisfied; move right.
  2. AY=20AY=20
    AA exhausted; move down.
  3. BY=5, BZ=15BY=5,\ BZ=15
    Finish YY, then ZZ.
AnswerCost 40+120+15+105=28040+120+15+105=280.
✓ Check4=m+n−14=m+n-1 cells ✓.

2. Improving

Shadow costs and indices
  1. RA=0; KX=4, KY=6R_A=0;\ K_X=4,\ K_Y=6
    From AXAX, AYAY.
  2. RB=3−6=−3; KZ=7+3=10R_B=3-6=-3;\ K_Z=7+3=10
    From BYBY, BZBZ.
  3. IAZ=8−0−10=−2, IBX=5+3−4=4I_{AZ}=8-0-10=-2,\ I_{BX}=5+3-4=4
    Empty cells.
AZAZ has a negative index: each unit moved there saves 22.
Worked exampleStepping stone

Enter AZAZ.

Goal
New cost.
Strategy
Loop AZ(+)AZ(+), BZ(−)BZ(-), BY(+)BY(+), AY(−)AY(-).
  1. θ=min⁡(BZ,AY)=min⁡(15,20)=15\theta=\min(BZ,AY)=\min(15,20)=15
    Smallest in a minus cell.
  2. AX10, AY5, AZ15, BY20AX10,\ AY5,\ AZ15,\ BY20
    BZBZ empties.
  3. 280−2×15=250280-2\times15=250
    Saving.
Answer250250; new indices are all ≥0\ge0, so optimal.
✓ Check40+30+120+60=25040+30+120+60=250 ✓.
Stepping-stone method

Iterate until no saving remains.

Common misconceptionDegeneracy If fewer than m+n−1m+n-1 cells are occupied, place a 00 in an empty cell so shadow costs can be found.
Key takeawayDummies If supply exceeds demand, add a dummy demand point with zero costs.
Pause and think

What does a zero improvement index at the optimum mean?

Summary

  • m+n−1m+n-1 cells.
  • Ri+Kj=CijR_i+K_j=C_{ij}.
  • I=C−R−KI=C-R-K; enter most negative.
Key words
Shadow cost
Notional cost per unit at a source or destination.
Improvement index
Change in cost per unit moved into an empty cell.
HistoryHitchcock and Kantorovich. Frank Hitchcock (1941) and Leonid Kantorovich (1939) formulated the transportation problem; Kantorovich later won a Nobel Prize in economics.
Fun factWartime origins. Koopmans used transportation methods in WWII to cut empty voyages of Allied cargo ships.
Section 3 of 14

Key formulae

Occupied cellsm+n−1  (else degenerate)m+n-1\ \ (\text{else degenerate})
Shadow costsRi+Kj=Cij (occupied),R1=0R_i+K_j=C_{ij}\ \text{(occupied)},\quad R_1=0
Improvement indexIij=Cij−Ri−Kj (empty)I_{ij}=C_{ij}-R_i-K_j\ \text{(empty)}
TrickLoop signs. Around a stepping-stone loop, alternate +θ+\theta and −θ-\theta; θ\theta is the smallest amount in a −- cell. Cost changes by I×θI\times\theta.
Section 4 of 14

Worked examples

Example 1 · North-west corner0 / 2 steps
Supplies A30A30, B20B20; demands X10X10, Y25Y25, Z15Z15. Costs AA: 4,6,84,6,8; BB: 5,3,75,3,7. Find the NW corner cost.
    Example 2 · Improve0 / 3 steps
    Find the improvement indices and improve.
      Section 5 of 14

      Explore the graph

      Cost as stock moves round the loop
      Loading the interactive graph…
      Try this
      1. xx is θ\theta, the amount moved. Each unit saves ∣IAZ∣=2|I_{AZ}|=2.
      2. θ\theta stops at 1515, when BZBZ empties.

      Cost falls from 280280 to 250250.

      In the real worldSupermarket logistics. Retailers route thousands of lorries nightly from depots to stores; the same shadow-cost ideas sit inside their software.
      Section 6 of 14

      Common mistakes

      IncorrectToo few occupied cells
      CorrectAdd a zero to make m+n−1m+n-1
      Otherwise shadow costs can't all be found.
      IncorrectEntering the largest positive index
      CorrectEnter the most negative
      Negative means a saving.
      IncorrectForgetting a dummy
      CorrectBalance first
      Supply must equal demand.

      All improvement indices ≥ 0

      Optimal. Park the lorries.

      Section 7 of 14

      Exam tip

      Exam tipCheck the total. After each iteration, row and column totals must still match supplies and demands.
      Section 8 of 14

      Guided practice

      SA-DM-TP-G011 markL1 FoundationNon-calculatorNorth-west corner
      A problem has 2 supply points and 3 demand points. How many occupied cells must a non-degenerate solution have?

      Sign in or create a free account to check answers, get hints and track your progress.

      Salam Academy Original Practice · Proposed mark scheme
      Section 9 of 14

      Practice questions

      SA-DM-TP-0012 marksL2 StandardNon-calculatorNorth-west corner
      Supplies A30A30, B20B20; demands X10X10, Y25Y25, Z15Z15. Unit costs: AA: X4X4, Y6Y6, Z8Z8; BB: X5X5, Y3Y3, Z7Z7. Find the cost of the north-west corner solution.

      Sign in or create a free account to check answers, get hints and track your progress.

      Salam Academy Original Practice · Proposed mark scheme
      SA-DM-TP-0022 marksL2 StandardNon-calculatorImproving
      With RA=0R_A=0, find the shadow cost KZK_Z.

      Sign in or create a free account to check answers, get hints and track your progress.

      Salam Academy Original Practice · Proposed mark scheme
      SA-DM-TP-0031 markL2 StandardNon-calculatorImproving
      Find the improvement index for cell AZAZ.

      Sign in or create a free account to check answers, get hints and track your progress.

      Salam Academy Original Practice · Proposed mark scheme

      More questions on every skill in this subtopic are in the question bank under Practise.

      Section 10 of 14

      Challenge

      SA-DM-TP-0043 marksL3 ExamNon-calculatorImproving
      Carry out one stepping-stone iteration entering AZAZ. Find the new total cost.

      Sign in or create a free account to check answers, get hints and track your progress.

      Salam Academy Original Practice · Proposed mark scheme
      Section 11 of 14

      Summary

      • Balance; NW corner.
      • m+n−1m+n-1 occupied cells.
      • Shadow costs, indices.
      • Negative index: improve.
      Section 12 of 14

      Quick quiz

      Q1 · SA-DM-TP-Q011 markL1 FoundationNon-calculatorImproving
      A transportation solution is optimal when
      Choose one option

      Sign in or create a free account to check answers, get hints and track your progress.

      Salam Academy Original Practice · Proposed mark scheme
      Section 13 of 14

      Same topic, different board

      Specification
      A level Further Mathematics 9FM0
      Where
      Decision 2 · Transportation problems
      Expected
      Balancing with dummies; north-west corner initial solution; degeneracy; shadow costs and improvement indices; stepping-stone method; formulating as a linear programme.
      Calculator
      Permitted; show enough working to earn the method marks.
      Typical style
      Edexcel often opens with a routine part and builds to a "show that" or "prove" part.
      Open in
      9FM0 · Option
      Section 14 of 14

      Past paper questions

      No past paper questions are tagged to this subtopic yet. We add papers every week.

      Browse past papers

      Salam Academy original content · Content status: reviewed and published. Syllabus mapping: Pearson Edexcel 9FM0, First teaching 2017 (official specification).