The Transportation Problem

A company runs three warehouses and must supply five shops. Each warehouse holds a fixed stock, each shop needs a fixed amount, and shipping a crate along each warehouse→shop route costs a known sum. In how many crates, along which routes, should the goods move so that every shop is served, no warehouse over-ships, and the total freight bill is as small as possible? That is the transportation problem — one of the oldest and most useful models in operations research, born in the 1940s from the very literal question of moving supplies to where they are needed.

The ingredients

A transportation problem has m supply sources (factories, warehouses, mines) each with an available amount s_i, and n demand sinks (shops, cities, customers) each needing an amount d_j. Shipping one unit from source i to sink j costs c_{ij}. The decisions are the shipment quantities x_{ij} \ge 0, and the model is a linear program:

\min \sum_{i=1}^{m}\sum_{j=1}^{n} c_{ij}\,x_{ij} \quad\text{s.t.}\quad \sum_j x_{ij} = s_i,\;\; \sum_i x_{ij} = d_j,\;\; x_{ij}\ge 0.

The first family of constraints says each source ships out exactly its supply; the second says each sink receives exactly its demand. Nothing else. This spare structure is what makes the problem so beautifully solvable.

Every source connects to every sink, and the number on each arc is its unit cost. A solution chooses how much flows along each arc so the columns balance the demands and the rows balance the supplies.

The transportation tableau

Rather than draw the network, practitioners lay the data out as a grid — the transportation tableau — with supplies down the right margin, demands along the bottom, and unit costs tucked into each cell. Here are two sources and three sinks, all in balance (20+30 = 10+25+15 = 50):

	Shop D₁	Shop D₂	Shop D₃	Supply
Warehouse S₁	8	6	10	20
Warehouse S₂	9	4	7	30
Demand	10	25	15	50

Each cell will eventually hold a shipment x_{ij}. Fill the grid so every row sums to its supply and every column to its demand, at least freight cost, and you have solved the problem.

Getting a starting solution

Two quick rules give a feasible starting shipment plan to improve from:

Northwest-corner rule — begin at the top-left cell, ship as much as the row and column allow, cross out whichever is exhausted, and step right or down. Fast, but it ignores costs entirely, so it usually starts expensive.
Least-cost rule — repeatedly pick the cheapest remaining cell and ship as much as possible there. It pays attention to the c_{ij}, so it typically starts much closer to optimal.

On the tableau above, the least-cost rule grabs cell S₂D₂ first (cost 4), shipping 25; then S₂D₃ (cost 7) for the remaining 5 of S₂; then fills S₁ into D₁ and D₃. A non-degenerate basic solution always uses exactly m + n - 1 routes — here 2 + 3 - 1 = 4.

Improving to the optimum

A starting plan is rarely optimal, so we test it. For every unused route we ask: if I forced one crate down it, would the total cost fall? Rerouting one crate ripples through the tableau along a closed loop of occupied cells (add here, subtract there, add, subtract), and adding up the costs around that loop gives the net saving. This bookkeeping is the stepping-stone method; the algebraic shortcut that computes all those loop costs at once, using row and column "potentials" u_i + v_j = c_{ij} on the used cells, is MODI (the modified distribution method). When no unused route offers a saving, the plan is optimal.

The transportation problem is a linear program — yet its optimal solution is automatically a whole number whenever the supplies and demands are whole numbers, with no need to demand integrality. The reason is the special shape of its constraint matrix: it is totally unimodular (every square sub-determinant is 0, +1 or -1), which forces every vertex of the feasible region onto integer coordinates. So the easy simplex solution is the integer solution — a rare and precious coincidence that also blesses assignment and min-cost-flow problems.

The tidy equalities \sum_i x_{ij}=d_j and \sum_j x_{ij}=s_i can only both hold if total supply equals total demand. If your warehouses hold 50 crates but the shops want only 45, the equalities are contradictory and the problem is infeasible as written. The fix is a dummy: add a phantom sink that "demands" the surplus 5 at zero cost (goods that stay put), or a phantom source that "supplies" any shortfall. Balance first, then solve — never feed an unbalanced tableau to the method.