Further Maths Transportation problems Practice Questions

Free Further Maths Transportation problems practice questions with full step-by-step worked solutions. Covers transportation, tableau, degeneracy, balancing. Practise exam-style problems and check your method.

transportationtableaudegeneracybalancingcostnorth-west-corner
Further Maths70 questionsStep-by-step solutions
Question 1
2 markseasy
The table below shows the cost (in pounds) of transporting one unit from each supply point SiS_i to each demand point DjD_j, together with the supplies and demands. D1D2D3SupplyS143910S27597S37585Demand1417\begin{array}{c|ccc|c} & D_1 & D_2 & D_3 & \text{Supply} \\ \hline S_1 & 4 & 3 & 9 & 10 \\ S_2 & 7 & 5 & 9 & 7 \\ S_3 & 7 & 5 & 8 & 5 \\ \hline \text{Demand} & 14 & 1 & 7 & \end{array} Find the total supply available.
Show worked solution

Worked solution

  1. Read the supplies from the table

    s1=10, s2=7, s3=5s_1 = 10,\ s_2 = 7,\ s_3 = 5

    The supply of each source is the entry in the final column of its row.

  2. Add the supplies together

    10+7+5=2210 + 7 + 5 = 22

    The total supply is the sum of the individual supplies.

  3. State the total supply

    total supply=22\text{total supply} = 22

    This is how many units are available in total.

Answer
2222
Question 2
2 markseasy
The table below shows the cost (in pounds) of transporting one unit from each supply point SiS_i to each demand point DjD_j, together with the supplies and demands. D1D2D3D4SupplyS1857712S228944S326785S466275Demand11753\begin{array}{c|cccc|c} & D_1 & D_2 & D_3 & D_4 & \text{Supply} \\ \hline S_1 & 8 & 5 & 7 & 7 & 12 \\ S_2 & 2 & 8 & 9 & 4 & 4 \\ S_3 & 2 & 6 & 7 & 8 & 5 \\ S_4 & 6 & 6 & 2 & 7 & 5 \\ \hline \text{Demand} & 11 & 7 & 5 & 3 & \end{array} Using the north-west corner method, state the number of units allocated to the cell in row S1S_1, column D1D_1.
Show worked solution

Worked solution

  1. Apply the north-west corner rule

    allocate min⁡(si,dj) starting at the top-left cell\text{allocate } \min(s_i, d_j) \text{ starting at the top-left cell}

    Each step fills the current top-left cell and crosses out an exhausted supply or demand.

  2. Record the allocations in the order they are made

    (S1,D1)→11, (S1,D2)→1, (S2,D2)→4, (S3,D2)→2, (S3,D3)→3, (S4,D3)→2, (S4,D4)→3(S_1, D_1) \to 11,\ (S_1, D_2) \to 1,\ (S_2, D_2) \to 4,\ (S_3, D_2) \to 2,\ (S_3, D_3) \to 3,\ (S_4, D_3) \to 2,\ (S_4, D_4) \to 3

    Moving right when a demand remains and down when a supply remains gives the initial solution.

  3. Write out the initial allocation

    x11=11x_{11} = 11, x12=1x_{12} = 1, x22=4x_{22} = 4, x32=2x_{32} = 2, x33=3x_{33} = 3, x43=2x_{43} = 2, x44=3x_{44} = 3

    These are the occupied cells of the north-west corner basic feasible solution.

  4. State the allocation

    x11=11x_{11} = 11

    This is the north-west corner allocation for that cell.

Answer
x11=11x_{11} = 11
Question 3
4 marksintermediate
The table below shows the cost (in pounds) of transporting one unit from each supply point SiS_i to each demand point DjD_j, together with the supplies and demands. D1D2D3SupplyS14826S27344S356210Demand1253\begin{array}{c|ccc|c} & D_1 & D_2 & D_3 & \text{Supply} \\ \hline S_1 & 4 & 8 & 2 & 6 \\ S_2 & 7 & 3 & 4 & 4 \\ S_3 & 5 & 6 & 2 & 10 \\ \hline \text{Demand} & 12 & 5 & 3 & \end{array} The problem is formulated as a linear programme with xijx_{ij} the number of units sent from SiS_i to DjD_j. Which of the following is the supply constraint for S3S_3?
Show worked solution

Worked solution

  1. Recall that supply and demand must be met exactly

    ∑jxij=si,∑ixij=dj\sum_j x_{ij} = s_i, \quad \sum_i x_{ij} = d_j

    In a balanced problem every supply is used up and every demand is filled.

  2. Write the required constraint

    x31+x32+x33=10x_{31} + x_{32} + x_{33} = 10

    The relevant variables sum to the supply.

  3. Recall what a transportation problem asks

    min⁡∑i∑jcijxij\min \sum_i \sum_j c_{ij} x_{ij}

    The aim is to meet every demand from the available supplies at least total cost.

  4. Recall the balance condition

    ∑isi=∑jdj\sum_i s_i = \sum_j d_j

    A transportation problem can only be solved once total supply equals total demand.

  5. Recall how a dummy restores balance

    dummy supply or demand=∣∑isi−∑jdj∣\text{dummy supply or demand} = \left|\sum_i s_i - \sum_j d_j\right|

    A dummy row or column with zero costs absorbs the surplus, leaving a balanced problem.

  6. Recall the number of occupied cells needed

    occupied cells=m+n−1\text{occupied cells} = m + n - 1

    A non-degenerate basic feasible solution of an m×nm \times n problem fills exactly m+n−1m+n-1 cells.

  7. State the constraint

    x31+x32+x33=10x_{31} + x_{32} + x_{33} = 10

    This is one of the equality constraints of the transportation LP.

Answer
x31+x32+x33=10x_{31} + x_{32} + x_{33} = 10
Question 4
6 markshard
The table below shows the cost (in pounds) of transporting one unit from each supply point SiS_i to each demand point DjD_j, together with the supplies and demands. D1D2D3D4SupplyS133939S227877S365624Demand7436\begin{array}{c|cccc|c} & D_1 & D_2 & D_3 & D_4 & \text{Supply} \\ \hline S_1 & 3 & 3 & 9 & 3 & 9 \\ S_2 & 2 & 7 & 8 & 7 & 7 \\ S_3 & 6 & 5 & 6 & 2 & 4 \\ \hline \text{Demand} & 7 & 4 & 3 & 6 & \end{array} Find the north-west corner solution and, taking u1=0u_1 = 0, determine the shadow cost u2u_2.
Show worked solution

Worked solution

  1. Apply the north-west corner rule

    allocate min⁡(si,dj) starting at the top-left cell\text{allocate } \min(s_i, d_j) \text{ starting at the top-left cell}

    Each step fills the current top-left cell and crosses out an exhausted supply or demand.

  2. Record the allocations in the order they are made

    (S1,D1)→7, (S1,D2)→2, (S2,D2)→2, (S2,D3)→3, (S2,D4)→2, (S3,D4)→4(S_1, D_1) \to 7,\ (S_1, D_2) \to 2,\ (S_2, D_2) \to 2,\ (S_2, D_3) \to 3,\ (S_2, D_4) \to 2,\ (S_3, D_4) \to 4

    Moving right when a demand remains and down when a supply remains gives the initial solution.

  3. Write out the initial allocation

    x11=7x_{11} = 7, x12=2x_{12} = 2, x22=2x_{22} = 2, x23=3x_{23} = 3, x24=2x_{24} = 2, x34=4x_{34} = 4

    These are the occupied cells of the north-west corner basic feasible solution.

  4. Set up the shadow-cost equations on the occupied cells

    u1+v1=3,u1+v2=3,u2+v2=7,u2+v3=8,u2+v4=7,u3+v4=2u_1 + v_1 = 3,\quad u_1 + v_2 = 3,\quad u_2 + v_2 = 7,\quad u_2 + v_3 = 8,\quad u_2 + v_4 = 7,\quad u_3 + v_4 = 2

    Each occupied cell gives one equation ui+vj=ciju_i + v_j = c_{ij}.

  5. Solve the equations taking u1=0u_1 = 0

    u1=0,u2=4,u3=−1,v1=3,v2=3,v3=4,v4=3u_1 = 0,\quad u_2 = 4,\quad u_3 = -1,\quad v_1 = 3,\quad v_2 = 3,\quad v_3 = 4,\quad v_4 = 3

    With u1=0u_1 = 0 the remaining potentials follow one occupied cell at a time.

  6. Read the required potential

    required potential u2=4\text{required potential } u_2 = 4

    The potential is read from the solved shadow-cost equations.

  7. Recall what a transportation problem asks

    min⁡∑i∑jcijxij\min \sum_i \sum_j c_{ij} x_{ij}

    The aim is to meet every demand from the available supplies at least total cost.

  8. Recall the balance condition

    ∑isi=∑jdj\sum_i s_i = \sum_j d_j

    A transportation problem can only be solved once total supply equals total demand.

  9. Recall how a dummy restores balance

    dummy supply or demand=∣∑isi−∑jdj∣\text{dummy supply or demand} = \left|\sum_i s_i - \sum_j d_j\right|

    A dummy row or column with zero costs absorbs the surplus, leaving a balanced problem.

  10. Recall the number of occupied cells needed

    occupied cells=m+n−1\text{occupied cells} = m + n - 1

    A non-degenerate basic feasible solution of an m×nm \times n problem fills exactly m+n−1m+n-1 cells.

  11. State the shadow cost

    u2=4u_2 = 4

    This potential satisfies ui+vj=ciju_i + v_j = c_{ij} on the occupied cells.

Answer
u2=4u_2 = 4
Question 5
9 markschallenging
The table below shows the cost (in pounds) of transporting one unit from each supply point SiS_i to each demand point DjD_j, together with the supplies and demands. D1D2D3SupplyS13487S283510S33375Demand4711\begin{array}{c|ccc|c} & D_1 & D_2 & D_3 & \text{Supply} \\ \hline S_1 & 3 & 4 & 8 & 7 \\ S_2 & 8 & 3 & 5 & 10 \\ S_3 & 3 & 3 & 7 & 5 \\ \hline \text{Demand} & 4 & 7 & 11 & \end{array} Starting from the north-west corner solution, perform one stepping-stone iteration and find the resulting total cost.
Show worked solution

Worked solution

  1. Apply the north-west corner rule

    allocate min⁡(si,dj) starting at the top-left cell\text{allocate } \min(s_i, d_j) \text{ starting at the top-left cell}

    Each step fills the current top-left cell and crosses out an exhausted supply or demand.

  2. Record the allocations in the order they are made

    (S1,D1)→4, (S1,D2)→3, (S2,D2)→4, (S2,D3)→6, (S3,D3)→5(S_1, D_1) \to 4,\ (S_1, D_2) \to 3,\ (S_2, D_2) \to 4,\ (S_2, D_3) \to 6,\ (S_3, D_3) \to 5

    Moving right when a demand remains and down when a supply remains gives the initial solution.

  3. Write out the initial allocation

    x11=4x_{11} = 4, x12=3x_{12} = 3, x22=4x_{22} = 4, x23=6x_{23} = 6, x33=5x_{33} = 5

    These are the occupied cells of the north-west corner basic feasible solution.

  4. Set up the shadow-cost equations on the occupied cells

    u1+v1=3,u1+v2=4,u2+v2=3,u2+v3=5,u3+v3=7u_1 + v_1 = 3,\quad u_1 + v_2 = 4,\quad u_2 + v_2 = 3,\quad u_2 + v_3 = 5,\quad u_3 + v_3 = 7

    Each occupied cell gives one equation ui+vj=ciju_i + v_j = c_{ij}.

  5. Solve the equations taking u1=0u_1 = 0

    u1=0,u2=−1,u3=1,v1=3,v2=4,v3=6u_1 = 0,\quad u_2 = -1,\quad u_3 = 1,\quad v_1 = 3,\quad v_2 = 4,\quad v_3 = 6

    With u1=0u_1 = 0 the remaining potentials follow one occupied cell at a time.

  6. Compute the improvement index of every unoccupied cell

    I13=8−(0)−(6)=2,I21=8−(−1)−(3)=6,I31=3−(1)−(3)=−1,I32=3−(1)−(4)=−2I_{13} = 8 - (0) - (6) = 2,\quad I_{21} = 8 - (-1) - (3) = 6,\quad I_{31} = 3 - (1) - (3) = -1,\quad I_{32} = 3 - (1) - (4) = -2

    The improvement index is Iij=cij−ui−vjI_{ij} = c_{ij} - u_i - v_j.

  7. Shift θ\theta units around the stepping-stone loop

    θ=4 at entering cell (S3,D2)\theta = 4 \text{ at entering cell } (S_3, D_2)

    The entering cell gains θ\theta units and the minus cells lose them.

  8. Cost the new allocation

    new cost=101+(4)(−2)=93\text{new cost} = 101 + (4)(-2) = 93

    The cost changes by θ\theta times the entering improvement index.

  9. Recall what a transportation problem asks

    min⁡∑i∑jcijxij\min \sum_i \sum_j c_{ij} x_{ij}

    The aim is to meet every demand from the available supplies at least total cost.

  10. Recall the balance condition

    ∑isi=∑jdj\sum_i s_i = \sum_j d_j

    A transportation problem can only be solved once total supply equals total demand.

  11. Recall how a dummy restores balance

    dummy supply or demand=∣∑isi−∑jdj∣\text{dummy supply or demand} = \left|\sum_i s_i - \sum_j d_j\right|

    A dummy row or column with zero costs absorbs the surplus, leaving a balanced problem.

  12. Recall the number of occupied cells needed

    occupied cells=m+n−1\text{occupied cells} = m + n - 1

    A non-degenerate basic feasible solution of an m×nm \times n problem fills exactly m+n−1m+n-1 cells.

  13. Recall the north-west corner rule

    start at the top-left cell and allocate as much as possible\text{start at the top-left cell and allocate as much as possible}

    Each allocation exhausts a supply or a demand, and we move right or down accordingly.

  14. Recall the shadow-cost equations

    ui+vj=cij on every occupied cellu_i + v_j = c_{ij} \text{ on every occupied cell}

    Fixing u1=0u_1 = 0 makes the potentials uiu_i and vjv_j uniquely determined.

  15. Recall the improvement index

    Iij=cij−ui−vjI_{ij} = c_{ij} - u_i - v_j

    The improvement index measures the change in cost from sending one unit through an empty cell.

  16. State the new total cost

    new cost=93\text{new cost} = 93

    This is the cost after one stepping-stone iteration.

Answer
9393

Unlock 65 more Transportation problems questions

Create a free account to work through every Further Maths Transportation problems question with instant step-by-step worked solutions, progress tracking and interactive lessons.

  • Full worked solutions for every question
  • Interactive lessons and instant feedback
  • Track your mastery across every topic
Create a Free Account

No card required · Free forever

More Transportation problems practice

Hard QuestionsWorked Solutions

Related Decision Maths topics

AlgorithmsAllocation (assignment)Critical path analysisDecision analysisDynamic programmingFlows in networks