Questions on transportation problems and the north-west corner method

Question 1

A transportation problem has supplies of 40, 30 and 50, and demands of 35, 45 and 25. State what must be done before any method is applied, giving the figure involved.

Accepted Answer

Total supply is 120 and total demand is 105, so the problem is unbalanced. Add a dummy destination of demand 15, reachable from every source at a cost of zero. B1 for the two totals, B1 for the dummy destination, B1 for a demand of 15. Whichever source ends up supplying the dummy is the one whose goods are not sent anywhere.

Question 2

State how many cells a solution to a 4 by 5 transportation problem should use, and what it means if it uses fewer.

Accepted Answer

4 + 5 − 1 = 8 cells. Using fewer means the solution is degenerate, which happens when a supply and a demand run out together. M1 for 4 + 5 − 1, A1 for the cell count, B1 for degeneracy. A zero allocation is recorded in a suitable cell to restore the count, without moving any goods.

Question 3

A transportation problem has supplies A 45 and B 30 and demands X 25 and Y 50. State the first cell the north-west corner method fills and the amount it puts there.

Accepted Answer

Supply totals 75 and demand totals 75, so the problem is balanced and the method starts at once. The north-west corner is the cell in the first row and the first column, AX. B1. It takes as much as the supply and the demand allow, min(45, 25) = 25, which uses up column X and leaves A with 20 still to send. B1. The costs play no part in either answer.

Question 4

Explain why the north-west corner method never looks at a cost, and state what follows about the solution it produces.

Accepted Answer

Each step fills the top-left cell of what is left with the largest amount the remaining supply and demand allow, and then crosses off whichever of the two has run out. Every one of those decisions is settled by the supplies and demands alone, so no cost is consulted. B1.
What follows is that the plan is feasible but not generally cheap: it meets every supply and every demand and uses the right number of cells, and that is all it is for. It is a starting point for the improvement stage, which is where the costs are used. B1.

Question 5

Supplies are A 40, B 30, C 50 and demands are X 35, Y 45, Z 40. Costs per unit are AX 8, AY 5, AZ 6, BX 4, BY 9, BZ 7, CX 3, CY 6, CZ 5. Find the north-west corner solution and its cost.

Accepted Answer

AX takes min(40, 35) = 35, using up X. AY then takes A's remaining 5, using up A. BY takes 30, using up B. CY takes the last 10 that Y needs, and CZ takes 40.
Allocations: AX 35, AY 5, BY 30, CY 10, CZ 40.
Cost = 35(8) + 5(5) + 30(9) + 10(6) + 40(5) = 280 + 25 + 270 + 60 + 200 = 835. M1 for starting at the north-west corner, A1 A1 for the allocations, M1 for the cost sum, A1 for 835.

Question 6

For that solution, confirm the cell count is right and comment on the quality of the answer.

Accepted Answer

It uses five cells and 3 + 3 − 1 = 5, so the count is right and no zero allocation is needed. The cost is poor. The method never looks at a cost at all, and it has put 30 units on BY at 9 per unit, the dearest route in the table. B1 for the cell count, B1 for the comment on the cost.

Question 7

A source in a different problem cannot supply one particular destination at all. Explain how this is handled, and why a cost of zero would be wrong.

Accepted Answer

Give that cell a cost large enough that no improvement method would ever choose it, and say in your working that you have done so. A cost of zero would make the route look like the cheapest in the table, so the method would fill it first: the forbidden route needs to be made unattractive, not free. B1 for a prohibitively large cost, B1 for saying so in the working, B1 for why zero is wrong. A dummy destination is the opposite case, where zero is right because nothing is actually moved.

Question 8

A problem has two sources with supplies 25 and 35, and three destinations with demands 30, 20 and 25. State what must be done before the north-west corner method is applied, and how many cells the resulting solution should use.

Accepted Answer

Supply totals 60 and demand totals 75, so demand exceeds supply by 15 and this time the shortfall is on the supply side. Add a dummy source with supply 15, at a cost of zero to every destination. Any demand met from the dummy is demand that goes unmet in reality, which tells the planner which destination goes short. The table is then 3 by 3, so a solution should use 3 + 3 − 1 = 5 cells. B1 for the two totals, B1 for a dummy source rather than a destination, B1 for a supply of 15 at zero cost, B1 for the five cells.

Question 9

Supplies are A 20, B 30, C 25 and demands are X 25, Y 30, Z 20. A colleague proposes the allocation AY 20, BX 25, BZ 5, CY 10, CZ 15. Verify that it is a feasible solution using the right number of cells, and explain how you can tell, without carrying the method out, that it did not come from the north-west corner method.

Accepted Answer

Check the totals against the table. Row A sends 20, row B sends 25 + 5 = 30 and row C sends 10 + 15 = 25, matching the supplies. Column X receives 25, column Y receives 20 + 10 = 30 and column Z receives 5 + 15 = 20, matching the demands, so the plan is feasible. It uses five cells against 3 + 3 − 1 = 5, so the count is right and it is not degenerate. The north-west corner method begins by filling the top-left cell AX with min(20, 25) = 20, which is not zero, yet this plan leaves AX empty, so the method cannot have produced it. B1 for the row totals, B1 for the column totals, B1 for the cell count, B1 for the argument from the empty AX cell.

Question 10

Supplies are A 25, B 45 and C 20 and demands are X 35, Y 25 and Z 30. The route from A to X is unavailable, and has been given a prohibitively large cost in the table. Find the north-west corner solution, state the difficulty it creates, and say what removes that difficulty.

Accepted Answer

Supply and demand both total 90, so the table is balanced. AX takes min(25, 35) = 25, using up A. BX takes the 10 that X still needs, BY takes 25, then BZ takes B's remaining 10, and CZ takes 20. M1 for the method, A1 for AX 25, BX 10, BY 25, BZ 10, CZ 20, which is five cells against 3 + 3 − 1 = 5.
The difficulty is that the plan puts 25 units on AX, the route that cannot be used, so it is not a plan the firm could carry out. The method never looks at a cost, so a prohibitive entry does nothing to keep it out of that cell. B1 for the forbidden route being filled, with the reason.
Removing it is the improvement stage's work: the prohibitive cost gives AX a large positive contribution to the total, so the shadow costs and improvement indices drive the allocation off that cell and every later plan avoids it. B1.

Question 11

A haulier moves goods from two depots, A with 20 units and B with 30, to two shops, X needing 25 and Y needing 25. The charge is £0.05 per unit per kilometre, and the distances in kilometres are AX 120, AY 200, BX 160 and BY 80. Write down the cost table, find the north-west corner solution, and give its total cost with its units.

Accepted Answer

The cost of a route per unit is the charge times the distance, so AX costs 0.05 × 120 = 6, AY 0.05 × 200 = 10, BX 0.05 × 160 = 8 and BY 0.05 × 80 = 4, each in pounds per unit. M1 for rate times distance, A1 for 6, 10, 8 and 4.
Supply and demand both total 50, so the table is balanced. AX takes min(20, 25) = 20, using up A; BX takes the 5 that X still needs; BY takes the last 25. That is three cells against 2 + 2 − 1 = 3. M1 for the method, A1 for the allocation.
Total cost = 20(6) + 5(8) + 25(4) = 120 + 40 + 100 = £260. Pounds per unit per kilometre, multiplied by units and by kilometres, leaves pounds. B1 for 260 with its units.

Question 12

Supplies are A 30, B 40 and C 20; demands are X 30, Y 25 and Z 20. Costs per unit are AX 5, AY 8, AZ 6, BX 7, BY 4, BZ 9, CX 6, CY 5 and CZ 3. Prepare the problem for solution, find the north-west corner solution and its cost, and comment on the number of cells used.

Accepted Answer

Supply totals 90 and demand totals 75, so the problem is unbalanced. Add a dummy destination of demand 15, with a cost of zero from every source.
North-west corner on the 3 by 4 table: AX takes min(30, 30) = 30, which exhausts row A and column X together. Move on to BY, which takes min(40, 25) = 25, then BZ takes the remaining 15 of B's supply, then CZ takes the 5 that Z still needs, and CD takes 15.
Cost = 30(5) + 25(4) + 15(9) + 5(3) + 15(0) = 150 + 100 + 135 + 15 + 0 = 400.
Only five cells are in use against 3 + 4 − 1 = 6, so the solution is degenerate. It happened because row A and column X ran out at the same moment. Record a zero allocation in AY, next along the route, which restores the count without moving any goods and lets every shadow cost be found later.
B1 for the imbalance, B1 for the dummy demand of 15, M1 for the north-west corner method, A1 A1 for the allocations, M1 for the cost, A1 for 400, B1 for the degeneracy and the zero allocation.

Question 13

Supplies are A 20, B 30, C 25, D 25 and demands are X 45, Y 30, Z 25. Costs per unit are AX 6, AY 4, AZ 9, BX 5, BY 8, BZ 6, CX 7, CY 3, CZ 5, DX 8, DY 6, DZ 4. Find the north-west corner solution and its cost, and deal with any difficulty that arises.

Accepted Answer

The table balances at 100, so start at once. AX takes min(20, 45) = 20, using up A. BX takes the 25 that X still needs, then BY takes B's remaining 5. CY now takes min(25, 25) = 25, and row C and column Y run out together. DZ takes the last 25.
Allocations: AX 20, BX 25, BY 5, CY 25, DZ 25.
Cost = 20(6) + 25(5) + 5(8) + 25(3) + 25(4) = 120 + 125 + 40 + 75 + 100 = 460.
Only five cells are in use against 4 + 3 − 1 = 6, so the solution is degenerate, and this time the simultaneous exhaustion happened at CY, in the middle of the table rather than at the final corner. Record a zero allocation in CZ, the next cell along the route, which restores the count without moving any goods.
M1 for the north-west corner method, A1 A1 for the allocations, M1 for the cost sum, A1 for 460, B1 for spotting the degeneracy and where it arose, B1 for the zero allocation in a suitable cell.

Question 14

Two factories, A with 30 units and B with 25, supply three shops, X needing 20, Y needing 25 and Z needing 30. Costs per unit are AX 4, AY 9, AZ 7, BX 6, BY 3 and BZ 8. Prepare the problem for solution, find the north-west corner solution and its cost, and state which shop goes short and by how much.

Accepted Answer

Supply totals 30 + 25 = 55 and demand totals 20 + 25 + 30 = 75, so the problem is unbalanced and this time the shortfall is on the supply side. B1 for the two totals.
Add a dummy source with supply 20 and a cost of zero to every shop. Goods drawn from the dummy are goods that never arrive, so the dummy records demand that goes unmet. B1 for a dummy source of 20 at zero cost.
The table is now 3 by 3. AX takes min(30, 20) = 20, using up X; AY takes A's remaining 10; BY takes the 15 that Y still needs; BZ takes B's remaining 10; and the dummy supplies the last 20 that Z needs. M1 for the method, A1 for AX 20, AY 10, BY 15, BZ 10 and 20 from the dummy to Z, five cells against 3 + 3 − 1 = 5, so the solution is not degenerate.
Cost = 20(4) + 10(9) + 15(3) + 10(8) + 20(0) = 80 + 90 + 45 + 80 = 295. A1.
The dummy's 20 units all go to Z, so Z receives only 10 of the 30 it wants and is 20 short. B1.
The improvement stage may well move the shortfall elsewhere once the costs are consulted.

Question 15

A transportation problem with m sources and n destinations is balanced. Show that the north-west corner method always produces a feasible solution, and that it fills at most m + n − 1 cells, saying what it means when it fills fewer.

Accepted Answer

At each step the method puts min(remaining supply, remaining demand) into the top-left cell of what is left, which empties that row or that column, or both at once. So every step crosses off at least one row or column. M1 for each step removing a row or a column.
There are m rows and n columns, m + n in all, and the very last step must exhaust a row and a column together, since nothing is left afterwards. Every earlier step removes at least one and the last removes two, so the number of cells filled is at most m + n − 1. A1.
Nothing is ever put into a cell beyond what its row can send or its column needs, so no supply is exceeded and no demand overfilled; and because the two totals were equal to start with, the remaining supply and remaining demand stay equal throughout, so both run out together and every supply and demand is exactly met. M1 A1 for feasibility, with the equal totals doing the work.
Fewer than m + n − 1 cells means some earlier step also emptied a row and a column at the same moment, and the solution is degenerate. B1. A zero allocation in a suitable cell restores the count without moving any goods, which is what the improvement stage needs.

Question 16

The table gives the cost, in pounds, of sending one unit along each route from depots A, B and C to shops X, Y and Z, together with the supply held at each depot and the demand at each shop. State what must be done to the table before the north-west corner method can be applied, and do it. Then find the north-west corner solution and its cost, and state whether that solution uses the number of cells it should.

Accepted Answer

Total supply is 30 + 40 + 50 = 120 and total demand is 25 + 45 + 30 = 100, so the problem is unbalanced, with 20 units of supply that nothing calls for. M1 for the two totals.
Add a dummy destination of demand 20, reachable from every depot at a cost of 0, since the units sent there are not moved at all. A1 for the dummy and its demand.
Now work from the north-west corner of the balanced table. AX takes min(30, 25) = 25, which uses up X and leaves A with 5. AY takes A's remaining 5, using up A and leaving Y needing 40. BY takes min(40, 40) = 40. CZ takes 30, and the dummy column takes C's last 20. M1 for filling each north-west corner with the largest amount the remaining supply and demand allow.
The allocation is AX 25, AY 5, BY 40, CZ 30 and 20 to the dummy. A1 for the five allocations.
Its cost is 25 × 7 + 5 × 4 + 40 × 8 + 30 × 5 + 20 × 0 = 175 + 20 + 320 + 150 = £665. A1 for the cost.
A three-by-four table needs 3 + 4 − 1 = 6 occupied cells, but only five were filled. B1 for the comparison. This happened because B's supply of 40 and Y's remaining demand of 40 ran out together, so one step crossed off a row and a column at once. The solution is therefore degenerate, and a zero allocation is entered in a cell of the row or column just crossed off, CY for instance, to bring the count back to six so that shadow costs can be found. B1 for degeneracy and the zero allocation.
The cost is poor, as the method's costs are never consulted: it has put 40 units on BY at £8, the dearest of the routes it uses, while CX at £3 carries nothing.