The transportation problem is the minimum-cost flow programme laid out as a table: sources down the side, destinations across the top, a cost in every cell. Before anything can be solved the two margins have to agree, and a dummy row or column priced at zero is how that is arranged. Then a starting solution has to occupy exactly the right number of cells — and one of the two standard rules sometimes cannot.
Core ideas
Two of the three ideas here are about arithmetic that happens before any optimisation, and they are where the instances go wrong.
If supply exceeds demand, add one destination that absorbs the difference at a cost of zero per unit; if demand exceeds supply, add one source. Every real cost in the table is left exactly as it was — the lab checks this on all three of its worked examples and reports that not one real unit cost moved. A dummy is a bookkeeping device for making the two margins agree, and it must not be allowed to express an opinion.
There are m + n constraints and only m + n − 1 independent ones, because the rows of the incidence matrix sum to zero. So a basic solution occupies m + n − 1 cells, and those cells must form a spanning tree of the bipartite graph of rows and columns: connected, so every potential is determined, and acyclic, so none is over-determined.
The count can be met with some occupied cells carrying zero — those zeros are real basic cells and the lab names them rather than dropping them. Or the count can be missed altogether, which is worse: the occupied cells then fall into two disconnected pieces and the potentials cannot be solved for at all. The repair is to place a zero in a cell that joins two pieces without closing a cycle.
The material
The table and what it is, then balancing, then the two starting rules and the count each one has to satisfy.
Given m sources with supplies sᵢ, n destinations with demands dⱼ, and a unit cost cᵢⱼ for each pair, the transportation problem is to choose xᵢⱼ ≥ 0 minimising Σ cᵢⱼ xᵢⱼ subject to each row summing to its supply and each column to its demand.
It is balanced when Σ sᵢ = Σ dⱼ. Only a balanced problem has a feasible solution, because the row equations and the column equations both add up to the total shipped.
This is the minimum-cost flow programme with the drawing removed. The sources and destinations are the nodes, the cells are the arcs, no arc has a capacity — and the node equations, written as a table, become “each row sums to its supply, each column to its demand”. A tableau is worth having anyway, because the structure it exposes is what the method in the “Potentials and the Stepping-Stone Cycle” exploits.
Two cases, one fix each. More supply than demand: add a dummy destination whose demand is the difference, with a cost of zero in every cell of its column. More demand than supply: add a dummy source with that supply and a zero row. Either way the problem becomes balanced, every real cost is untouched, and units sent to the dummy are units that never move.
Three mills supplying 20, 30, 25 and three yards demanding 20, 25, 20: 75 available and 65 wanted. The lab adds a dummy destination carrying 10, both totals become 75, and the three costs in the new column are 0, 0, 0.
The optimum for this instance costs 605, and whichever plan is chosen, exactly 10 units go to the dummy — they have nowhere else to go. That is what makes a uniform dummy price harmless and a non-uniform one dangerous.
Two sources supplying 4 and 6 against demands of 5, 5, 5: 10 available and 15 wanted. A dummy source of 5 is added, with the row 0, 0, 0, and both sides become 15.
The dummy row now says which destinations go short, and by how much. That is genuinely useful output and it is the reason the dummy is part of the model rather than an apology for it.
The north-west corner rule fills the top-left cell with as much as its row and column allow, crosses off whichever is exhausted, and repeats. It never looks at a single cost. The least-cost rule picks the cheapest remaining cell instead, so it reads the costs and is greedy. Both produce a basic feasible solution; neither produces an optimum, and neither claims to.
On the three-plant table above, the north-west rule occupies six cells and ships at a cost of 520. The least-cost rule occupies six cells too and ships at 475, one of which carries zero — the cell joining the second plant to the second depot.
The optimum is 435, so neither start is close and the cheaper start is not automatically the better one to start from. What matters is that both are bases: six cells, spanning, acyclic.
On the lab's third table — three depots and three shops where the north-west rule ties — the least-cost rule occupies only four cells where five are needed, and those four fall into two disconnected pieces. The potentials of the lesson that follows then cannot be solved for: three of the six never get a value.
The lab repairs it by placing a zero allocation in the cell joining the first depot to the first shop, which is the cheapest cell that joins two pieces of the forest without closing a cycle. The count is restored to five, the basis becomes a spanning tree, and the method can start. The north-west rule on the same data occupies five cells, two of them carrying zero.
Those zeros are not decoration and they are not absences. A basic cell carrying zero is in the basis, it has a potential equation, and it can be the cell that leaves at the next pivot. A reader who quietly drops them will find the count wrong two steps later and will not know when it went wrong.
Interactive
the dummy carries what never moves, at a cost of nothing
Method
Balance, then start, then count. The count is not a formality: everything in “Potentials and the Stepping-Stone Cycle” assumes it.
Σ sᵢ against Σ dⱼ. Equal, and you have a balanced problem. Otherwise note the difference and which side is short, because that decides whether you are adding a column or a row.
A dummy destination absorbs surplus supply; a dummy source covers unmet demand. Every cell in it costs zero. Resist the urge to charge for the dummy, and if you think the situation really does have a penalty for unmet demand, put that penalty in the model deliberately and say so.
North-west if you want the count to be the only thing you are thinking about, least-cost if you want to open nearer the optimum. Cross off a row or a column each time, never both, unless the problem is over.
Too many is impossible if you crossed off one line at a time. Exactly right, including any zeros, and you have a basis. Too few means the start is degenerate in the serious sense and needs repair before anything else happens.
Find a cell whose row belongs to one component of the occupied cells and whose column belongs to another, put a zero in it, and treat it as basic. Placing the zero inside a component instead closes a cycle and leaves you no better off.
The counts are the thing to follow. Every figure below is what the lab reports as the start is built, and two of the three starts are degenerate in one of the two senses.
Table 3's least-cost start is the instructive one, and notice what it is not: it is not wrong, and it is not infeasible. It ships 40 units at a cost of 150, which happens to be the optimum. It simply is not a basis, so the machinery that proves optimality has nothing to stand on — and a reader who does not count will conclude the method is broken.
For a rehearsal, take table 2 and change the demands to 20, 25, 30. Supply and demand now both come to 75, the dummy disappears, and the tableau goes back to three by three with a basis of five. Watch the count control as you type: it is the fastest way to internalise where m + n − 1 comes from.
The harder rehearsal: on table 1, build the north-west start and then deliberately drop the smallest allocation, leaving five cells. Ask the lab for the potentials. You will get a disconnected forest and a refusal, which is exactly what happens to a reader who treats a zero allocation as an empty cell.
You should be able to decide whether a dummy row or a dummy column is needed and price it at zero, build a start by either rule, count the occupied cells against m + n − 1 including zeros, and repair a short count by placing a zero in a cell that joins two components of the occupied forest.
Something to change about this lesson? Write it down, tick it off when it is handled, and export the list when you want to act on it. Kept in this browser only: nothing is sent anywhere, and nobody is notified.
No recommendations yet for this lesson.