Transportation problemsEdexcel A-Level Further Maths: Revision notes

A transportation problem moves a single product from $m$ sources (supplies) to $n$ destinations (demands) at a unit cost $C_{ij}$ for each route, to minimise the total cost. Everything is shown in a transportation tableau: one row per source, one column per destination, with each cell showing the cost and the quantity sent. The problem is balanced when total supply equals total demand. A solution is a set of non-negative quantities satisfying every supply and demand. The cells that carry a quantity are occupied; the others are unoccupied. If the problem is not balanced add a dummy location (see below). A non-degenerate basic solution has exactly $m+n-1$ occupied cells.

This gives an initial basic feasible solution without looking at costs. Start at the top-left (north-west) cell and send as much as possible, the smaller of the supply and the demand. Cross out the row or column that is used up, and move to the next cell (right if the row has stock left over, down if the column still needs stock). Repeat until everything is allocated. Example: supplies 20, 30, 25 and demands 15, 35, 25. W1S1 $=\min(20,15)=15$, W1S2 $=5$, W2S2 $=30$, W3S3 $=25$. With costs 4, 6, 3 and 2 per unit, the cost is $60+30+90+50=£230$. Check each row and column total, and that the solution has $m+n-1$ occupied cells.

Degeneracy: if a solution has fewer than $m+n-1$ occupied cells, it is degenerate. In the example above only 4 cells are occupied, because W2 and S2 ran out at the same time. To continue, place a quantity of 0 (sometimes written $\varepsilon$) in an unoccupied cell, chosen so that shadow costs can still be found (no closed loop of occupied cells), until there are $m+n-1$ cells. Dummy locations: if supply exceeds demand, add a dummy destination taking the surplus; if demand exceeds supply, add a dummy source supplying the shortfall. All costs to or from a dummy are 0. A quantity sent to or from a dummy is not real: it is unused stock or an unmet demand.

To test whether a solution is optimal, find shadow costs $R_i$ (one per source) and $K_j$ (one per destination) so that for every occupied cell $R_i+K_j=C_{ij},\qquad R_1=0.$ The improvement index of each unoccupied cell is $I_{ij}=C_{ij}-R_i-K_j.$ It is the change in total cost per unit if that cell is brought in. If every $I_{ij}\ge0$ the solution is optimal. If some are negative, the most negative cell is the entering cell. Example: occupied costs S1D1 4, S1D2 3, S2D2 5, S2D3 6, S3D3 4 give $R=(0,2,0)$ and $K=(4,3,4)$. For S2D1 (cost 5): $I=5-2-4=-1<0$, so it should enter.

To bring a cell in, trace a closed loop that starts and ends at the entering cell and turns only at occupied cells, with alternating $+$ and $-$ signs starting with $+$ at the entering cell. Let $\theta$ be the smallest quantity in a $-$ cell: it is added to the $+$ cells and subtracted from the $-$ cells. A $-$ cell that falls to 0 is the exiting cell. Example: quarries A, B, C and sites X, Y, Z. Entering cell CX has $I=-2$. Loop: CX $(+)$, CZ $(-)$, BZ $(+)$, BY $(-)$, AY $(+)$, AX $(-)$. The minus cells hold 30, 35 and 20, so $\theta=20$ and AX exits. The cost falls by $20\times2=£40$ from £540 to £500. Then recalculate shadow costs and indices. Repeat until no index is negative.

Let $x_{ij}\ge0$ be the amount sent from source $i$ to destination $j$. For a balanced problem:

• Objective: minimise $\sum C_{ij}x_{ij}$.
• Supply constraints: for each source, $\sum_j x_{ij}=s_i$ (row sums).
• Demand constraints: for each destination, $\sum_i x_{ij}=d_j$ (column sums). For two depots P, Q and a dummy D supplying 30, 40, 10 to shops X, Y, Z needing 20, 25, 35: minimise $3x_{PX}+5x_{PY}+4x_{PZ}+6x_{QX}+2x_{QY}+7x_{QZ}$ with $x_{PX}+x_{PY}+x_{PZ}=30$ and so on. There are $mn$ variables and $m+n$ constraints, but only $m+n-1$ are independent, which is why a basic solution has $m+n-1$ occupied cells.