Transportation problems

Transportation problems

Spec 1.1–3 · Edexcel A-Level Further Maths: Revision notes

Studying this course? Keep your progress in one place.

Key facts

  • A transportation problem sends a product from sources to destinations at least total cost.
  • It must be balanced: add a dummy with all costs 0 if supply and demand differ.
  • The north-west corner method gives a start; a basic solution has m+n−1m+n-1 occupied cells.
  • Find shadow costs from Ri+Kj=CijR_i+K_j=C_{ij}, then improvement indices Iij=Cij−Ri−KjI_{ij}=C_{ij}-R_i-K_j. Optimal when none is negative.
  • The stepping-stone method moves θ\theta, the smallest quantity in a −- cell, round a loop.

The transportation problem

Move a single product from mm sources to nn destinations at unit cost CijC_{ij} to minimise total cost. Balance it first.

A transportation problem moves one product from mm sources (supplies) to nn destinations (demands). A transportation tableau has one row per source, one column per destination, and each cell shows the cost and the quantity sent.

The problem is balanced when total supply equals total demand. Cells carrying a quantity are occupied; the others are unoccupied. A non-degenerate basic solution has exactly m+n−1m+n-1 occupied cells.

Check totals first and balance the problem before anything else.

  1. 1

    Balance

    add a dummy if supply and demand differ

  2. 2

    Initial solution

    north-west corner method

  3. 3

    Shadow costs

    solve R + K = C on occupied cells

  4. 4

    Improvement indices

    I = C - R - K on unoccupied cells

  5. 5

    Stepping-stone

    move θ round a loop through the entering cell

  6. 6

    Repeat

    stop when no index is negative

Solving a transportation problem

A problem has total supply 80 and total demand 75. What do you add to balance it?

The north-west corner method

Start at the top-left cell and send as much as possible. Cross out the used-up row or column and move on. Costs are ignored.

The north-west corner method gives an initial basic feasible solution without looking at costs.

Start at the top-left cell and send the smaller of the supply and the demand. Cross out the row or column that is used up and move to the next cell (right if the row has stock left, down if the column still needs stock). Repeat until everything is allocated.

Check each row and column total, and count the occupied cells.

  1. 1

    Start top-left

    cell W1S1

  2. 2

    Send the smaller

    of the row's supply and the column's demand

  3. 3

    Cross out

    the row or column that is used up

  4. 4

    Move on

    right if the row has stock, down if the column needs stock

  5. 5

    Repeat

    until all supply is allocated

North-west corner method.

S1

W1:
15
W2:
–
W3:
–

S2

W1:
5
W2:
30
W3:
–

S3

W1:
–
W2:
–
W3:
25

Worked example

Sources W1, W2, W3 have supplies 20, 30, 25 and destinations S1, S2, S3 have demands 15, 35, 25. The costs of the occupied cells are 4, 6, 3 and 2 in order of allocation. Find the cost.

In the north-west corner method, which cell do you fill first?

Degeneracy and dummies

Fewer than m+n−1m+n-1 occupied cells is degenerate. Unbalanced problems need a dummy source or destination with all costs 0.

Degeneracy: a solution with fewer than m+n−1m+n-1 occupied cells is degenerate, as when W2 and S2 ran out at the same time. Place a quantity 0 (sometimes ε\varepsilon) in an unoccupied cell, chosen so there is no closed loop of occupied cells, until there are m+n−1m+n-1.

Dummy locations: if supply exceeds demand add a dummy destination; if demand exceeds supply add a dummy source. All costs to or from a dummy are 0.

A quantity sent to or from a dummy is not real: it is unused stock or unmet demand.

  1. 1

    Balance

    add a dummy destination or source, all costs 0

  2. 2

    Count cells

    occupied cells must equal m+n−1m+n-1

  3. 3

    Add a zero

    put 0 in an unoccupied cell with no closed loop

  4. 4

    Continue

    as normal

Handling degeneracy and unbalanced problems.

Supply exceeds demand

Add:
dummy destination
All costs:
0
Quantity means:
unused stock

Demand exceeds supply

Add:
dummy source
All costs:
0
Quantity means:
unmet demand

A 3 by 4 problem has a basic solution with 5 occupied cells. Is it degenerate?

Shadow costs and indices

Find shadow costs with Ri+Kj=CijR_i+K_j=C_{ij} on occupied cells, then Iij=Cij−Ri−KjI_{ij}=C_{ij}-R_i-K_j on the rest. Any negative index can be improved.

Find shadow costs RiR_i (one per source) and KjK_j (one per destination) so that for every occupied cell Ri+Kj=CijR_i+K_j=C_{ij}, with R1=0R_1=0. Fill them in order along the occupied cells.

The improvement index of each unoccupied cell is Iij=Cij−Ri−KjI_{ij}=C_{ij}-R_i-K_j: the change in total cost per unit if that cell is brought in.

If every Iij≥0I_{ij}\ge0 the solution is optimal. Otherwise the most negative cell is the entering cell.

  1. 1

    Set R1=0R_1=0

    then use Ri+Kj=CijR_i+K_j=C_{ij} on occupied cells

  2. 2

    Find all RiR_i and KjK_j

    working along occupied cells

  3. 3

    Improvement indices

    Iij=Cij−Ri−KjI_{ij}=C_{ij}-R_i-K_j on unoccupied cells

  4. 4

    Any negative?

    most negative enters; if none, optimal

Testing for optimality.
  • Occupied cellsRi+Kj=CijR_i+K_j=C_{ij}
  • Unoccupied cellsIij=Cij−Ri−KjI_{ij}=C_{ij}-R_i-K_j

Worked example

Occupied costs are S1D1 4, S1D2 3, S2D2 5, S2D3 6 and S3D3 4. Find the shadow costs and the improvement index of S2D1 (cost 5).

An unoccupied cell has C=7C=7, R=3R=3 and K=5K=5. What should you do?

The stepping-stone method

Trace a closed loop through the entering cell with alternating signs, and move the smallest quantity in a −- cell round it.

Trace a closed loop that starts and ends at the entering cell and turns only at occupied cells, with alternating ++ and −- signs starting with ++ at the entering cell.

Let θ\theta be the smallest quantity in a −- cell. Add it to the ++ cells and subtract it from the −- cells. A −- cell that falls to 0 is the exiting cell.

Recalculate shadow costs and indices. Repeat until no index is negative. Each row and column total stays unchanged.

AX −AY +BY −BZ +CZ −CX +
The loop through the entering cell CX: signs alternate, starting with + at CX.

Worked example

The entering cell CX has I=−2I=-2. The loop is as drawn. The minus cells hold 30, 35 and 20. The cost is £540. Find the new cost.

The minus cells in a loop hold 12, 8 and 15. What is θ\theta?

As a linear program

Let xijx_{ij} be the amount sent from source ii to destination jj: minimise cost subject to row sums equal supply and column sums equal demand.

Let xij≥0x_{ij}\ge0 be the amount sent from source ii to destination jj. For a balanced problem:

  • Objective: minimise ∑Cijxij\sum C_{ij}x_{ij}.
  • Supply: for each source, ∑jxij=si\sum_j x_{ij}=s_i.
  • Demand: for each destination, ∑ixij=dj\sum_i x_{ij}=d_j.

Dummy cells carry zero cost, so they vanish from the objective but stay in the constraints.

There are mnmn variables and m+nm+n constraints, but only m+n−1m+n-1 are independent, which is why a basic solution has m+n−1m+n-1 occupied cells.

  1. 1

    Variables

    xij≥0x_{ij}\ge0, amount from source ii to destination jj

  2. 2

    Objective

    minimise ∑Cijxij\sum C_{ij}x_{ij}

  3. 3

    Supply constraints

    row sums equal sis_i

  4. 4

    Demand constraints

    column sums equal djd_j

Building the linear program.
  • Supply (rows)∑jxij=si\sum_j x_{ij}=s_i
  • Demand (columns)∑ixij=dj\sum_i x_{ij}=d_j
  • Objectiveminimise ∑Cijxij\sum C_{ij}x_{ij}

A balanced problem has 3 sources and 4 destinations. How many variables and constraints does its LP have?

Try an exam question

Two depots PP and QQ hold 40 and 35 units. Three shops XX, YY, ZZ need 20, 25 and 25 units. Balance the problem and use the north-west corner method to find an initial solution.

[4 marks]

That's the notes covered.

Carry on to the next subtopic.

Try a question

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

1 mark, marked against the mark scheme

Revision notes