How many occupied cells does a non-degenerate basic solution have?

m+n-1 (for m sources and n destinations).

What does the north-west corner method do?

Allocates as much as possible starting from the top-left cell, moving right or down, ignoring costs.

A solution with fewer than m+n-1 occupied cells.

How do you fix a degenerate solution?

Place a 0 in an unoccupied cell (without making a closed loop of occupied cells).

How are shadow costs found?

Ri+Kj=C{ij} for every occupied cell, with R1=0.

When is a solution optimal?

When all improvement indices are \ge0.

The unoccupied cell with the most negative improvement index.

How is \theta chosen in the stepping-stone loop?

The smallest quantity in a - cell; that cell exits.

What are the LP constraints for a transportation problem?

Row sums equal the supplies and column sums equal the demands, with x{ij}\ge0.

Transportation problemsEdexcel A-Level Further Maths: Flashcards

Card 1 of 140 of 14 known

Question

What is a balanced transportation problem?

Tap or press Space to reveal

Tap card or press Space to flip

See all 14 cards

What is a balanced transportation problem?: Total supply equals total demand.
How many occupied cells does a non-degenerate basic solution have?: $m+n-1$ (for $m$ sources and $n$ destinations).
What does the north-west corner method do?: Allocates as much as possible starting from the top-left cell, moving right or down, ignoring costs.
What is degeneracy?: A solution with fewer than $m+n-1$ occupied cells.
How do you fix a degenerate solution?: Place a 0 in an unoccupied cell (without making a closed loop of occupied cells).
When do you add a dummy destination?: When supply exceeds demand.
When do you add a dummy source?: When demand exceeds supply.
What are the costs to and from a dummy?: Zero.
How are shadow costs found?: $R_i+K_j=C_{ij}$ for every occupied cell, with $R_1=0$ .
Formula for the improvement index?: $I_{ij}=C_{ij}-R_i-K_j$
When is a solution optimal?: When all improvement indices are $\ge0$ .
Which cell enters?: The unoccupied cell with the most negative improvement index.
How is $\theta$ chosen in the stepping-stone loop?: The smallest quantity in a $-$ cell; that cell exits.
What are the LP constraints for a transportation problem?: Row sums equal the supplies and column sums equal the demands, with $x_{ij}\ge0$ .

Exam questions on Transportation problems

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.
Calculate the total cost of the north-west corner solution.2 marks
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 $R_i$ (sources) and $K_j$ (destinations) are found from $R_i+K_j=C_{ij}$ for occupied cells with $R_1=0$ , and the improvement index of an unoccupied cell is $I_{ij}=C_{ij}-R_i-K_j$ .
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
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.
Using $R_A=0$ , find the shadow costs $R_B$ , $R_C$ , $K_X$ , $K_Y$ and $K_Z$ , and hence find the improvement index of the unoccupied cell CX.3 marks

See the full worksheet

Written by the Exaim team, led by Shaun Daswani (Head of Upper Secondary, Improve ME Institute; MSc Financial Mathematics, Imperial College London; BSc, UCL) and Jason Daswani (operational lead, Improve ME Institute; LSE).