The Transportation Problem
A network of factories must ship to a network of warehouses, and every route has a cost. Which factory should serve which warehouse, and how much, to move everything at the least total cost? This is the transportation problem — a special linear program with such clean structure that it deserves its own faster machinery. This chapter builds that machinery: the transportation tableau, three ways to get started, and the MODI test that tells you when the shipping plan cannot be bettered.
- The structure of the transportation problem and its LP formulation.
- How to read and fill a transportation tableau.
- Making a problem balanced with a dummy row or column.
- Three ways to build an initial basic feasible solution: Northwest Corner, Least Cost, and VAM.
- The MODI (u–v) method to test a solution for optimality.
- Improving a solution with a stepping-stone loop, and handling degeneracy.
The Transportation Problem
The transportation problem asks how to ship a commodity from several sources (each with a fixed supply) to several destinations (each with a fixed demand) so that the total shipping cost is minimized. Each source–destination route \((i, j)\) has a known unit cost \(c_{ij}\), and we choose the amount \(x_{ij}\) to send along it. Because supplies and demands are simple totals and every route is linear in \(x_{ij}\), it is a linear program — but a very structured one, which lets us solve it far faster than by general simplex.
Formulation and the Transportation Tableau
With \(m\) sources of supply \(a_i\) and \(n\) destinations of demand \(b_j\), the LP is:
Every plan is laid out in a transportation tableau: a grid with a row per source and a column per destination, the unit cost \(c_{ij}\) written small in each cell and the allocation \(x_{ij}\) written large. A supply column and a demand row border it. The optimal solution below (found later in the chapter) ships everything at a total cost of \(335\):
| D₁ | D₂ | D₃ | Supply | |
|---|---|---|---|---|
| S₁ | c=85 | c=65 | c=335 | 45 |
| S₂ | c=425 | c=9— | c=5— | 25 |
| S₃ | c=7— | c=230 | c=6— | 30 |
| Demand | 30 | 35 | 35 | 100 |
Balanced and Unbalanced Problems
The methods below require a balanced problem: total supply must equal total demand. Most real problems are unbalanced, and the fix is a fictitious placeholder.
If supply exceeds demand, add a dummy destination that absorbs the surplus at zero cost (goods that stay put). If demand exceeds supply, add a dummy source that supplies the shortfall at zero cost (unmet demand). The dummy's zero costs mean it never distorts the real routing — it merely soaks up the imbalance so the row and column totals match.
Finding an Initial Basic Feasible Solution
We start with any feasible shipping plan, then improve it. Three methods build that starting plan, differing in how much they look at cost. Using the tableau above (supplies \(45, 25, 30\); demands \(30, 35, 35\)):
| Method | Idea | Quality of start |
|---|---|---|
| Northwest Corner | Fill from top-left, ignoring cost | Fast but usually poor (cost \(715\) here) |
| Least Cost | Fill the cheapest available cell first | Much better (cost \(335\) here) |
| Vogel's Approximation (VAM) | Fill by largest "penalty" for not using the cheapest route | Usually near-optimal |
Northwest Corner allocates as much as possible to the top-left cell, then steps right or down as supplies/demands exhaust — ignoring cost entirely — giving \(x_{11}=30, x_{12}=15, x_{22}=20, x_{23}=5, x_{33}=30\) at cost \(715\). Least Cost instead fills the cheapest cell first (here \(c_{32}=2\)), producing the allocation shown in Section 12-2 at cost \(335\). VAM computes, for each row and column, the penalty (difference between its two cheapest cells) and serves the largest penalty first, which usually lands closest to optimal. Every method yields exactly \(m + n - 1\) occupied cells.
Optimality: the MODI Method
Given a feasible solution, the MODI (modified distribution, or u–v) method tests whether it can be improved. Assign a potential \(u_i\) to each row and \(v_j\) to each column so that \(u_i + v_j = c_{ij}\) for every occupied cell (set \(u_1 = 0\) to start). Then the opportunity cost of each empty cell measures the change in total cost from shipping one unit through it.
If every empty cell has \(d_{ij} \ge 0\), no reroute can lower the cost — the solution is optimal. If any \(d_{ij} < 0\), shipping through that cell would reduce cost, so the solution can be improved. For the Least-Cost solution above, computing potentials gives \(u = (0, -4, -4)\), \(v = (8, 6, 3)\), and every empty-cell \(d_{ij} \ge 0\) — so that \(335\) plan is already optimal.
Improving via Stepping Stones
When MODI flags an empty cell with negative opportunity cost, we bring it into the solution using a stepping-stone loop: a closed path that starts at the entering cell and turns only at occupied cells, alternating "\(+\)" and "\(-\)". Shipping \(\theta\) units around the loop keeps every supply and demand balanced; \(\theta\) is the smallest allocation on a "\(-\)" corner, and that cell leaves the solution.
For the Northwest-Corner start (cost \(715\)), MODI flags cell \((S_3, D_2)\) with the most negative opportunity cost, \(d = -8\). Its loop is \((S_3,D_2)^{+}, (S_2,D_2)^{-}, (S_2,D_3)^{+}, (S_3,D_3)^{-}\); the smallest "\(-\)" allocation is \(\theta = 20\). Rerouting drops the total cost by \(\theta \times |d| = 20 \times 8 = 160\), to \(555\) — one step toward the optimum of \(335\). Repeating MODI-and-reroute until all \(d_{ij} \ge 0\) reaches the optimal plan.
Degeneracy
A basic feasible solution of a transportation problem must have exactly \(m + n - 1\) occupied cells — the number of independent supply-and-demand equations. This is what makes the MODI potentials solvable. If a solution has fewer occupied cells (which happens when a supply and a demand exhaust simultaneously during allocation), it is degenerate and the potentials cannot all be found.
To repair degeneracy, place a vanishingly small allocation \(\varepsilon\) (treated as zero for cost but as "occupied" for counting) in a suitable empty cell, restoring the count to \(m + n - 1\). The \(\varepsilon\) lets MODI proceed; it is removed at the end. Choosing where to put \(\varepsilon\) — an independent cell that does not form a loop with existing occupied cells — is the only subtlety.
Worked Examples
Problem. Write the LP for 2 sources (supplies \(20, 30\)) and 2 destinations (demands \(25, 25\)) with costs \(c_{ij}\).
Solution. Variables \(x_{11}, x_{12}, x_{21}, x_{22} \ge 0\).
Supply \(50 =\) demand \(50\), so it is balanced. Note one of the four equations is redundant (totals match), giving \(m + n - 1 = 3\) independent constraints.
Problem. Supplies total \(120\); demands total \(100\). How do you balance it?
Solution. Supply exceeds demand by \(20\), so add a dummy destination with demand \(20\) and zero shipping costs from every source. The \(20\) units routed to the dummy represent goods that are simply not shipped, at no cost — the totals now match and the standard methods apply.
Problem. Apply the Northwest Corner method to supplies \(45, 25, 30\) and demands \(30, 35, 35\).
Solution. Fill top-left: \(x_{11} = \min(45,30) = 30\) (D₁ done); \(x_{12} = \min(15,35) = 15\) (S₁ done); \(x_{22} = \min(25,20) = 20\) (D₂ done); \(x_{23} = \min(5,35) = 5\) (S₂ done); \(x_{33} = 30\). Five occupied cells \(= m + n - 1\). With the given costs the total is \(715\) — feasible, but not yet optimal.
Problem. Apply the Least Cost method to the same data (cheapest cell \(c_{32} = 2\)).
Solution. Allocate to the cheapest cell first: \(x_{32} = \min(30, 35) = 30\); then next-cheapest \(c_{13} = 3\): \(x_{13} = 35\); then \(c_{21} = 4\): \(x_{21} = 25\); then fill the rest at \(c_{12}=6\) and \(c_{11}=8\): \(x_{12} = 5,\ x_{11} = 5\). Total cost \(= 5(8)+5(6)+35(3)+25(4)+30(2) = 335\) — dramatically better than Northwest Corner's \(715\).
Problem. Verify the Least-Cost solution (occupied cells \((1,1),(1,2),(1,3),(2,1),(3,2)\)) is optimal.
Solution. Set \(u_1 = 0\). From occupied cells: \(v_1 = 8,\ v_2 = 6,\ v_3 = 3\) (row 1); \(u_2 = 4 - 8 = -4\) (from \((2,1)\)); \(u_3 = 2 - 6 = -4\) (from \((3,2)\)). Opportunity costs of the empties: \(d_{22} = 9 - 2 = 7\), \(d_{23} = 5 - (-1) = 6\), \(d_{31} = 7 - 4 = 3\), \(d_{33} = 6 - (-1) = 7\) — all \(\ge 0\), so the solution is optimal.
Problem. The Northwest-Corner solution has entering cell \((S_3, D_2)\) with \(d = -8\). Improve it.
Solution. The loop is \((S_3,D_2)^{+}, (S_2,D_2)^{-}, (S_2,D_3)^{+}, (S_3,D_3)^{-}\). The "\(-\)" allocations are \(x_{22} = 20\) and \(x_{33} = 30\), so \(\theta = 20\) and \((S_2, D_2)\) leaves. The new cost falls by \(\theta \times |d| = 20 \times 8 = 160\), from \(715\) to \(555\). Re-running MODI would find the next improving cell, converging to \(335\).
Chapter Summary
Ship from sources to destinations at least total cost — a structured LP.
Grid of cost \(c_{ij}\) and allocation \(x_{ij}\) with supply/demand margins.
Equalise supply and demand with a zero-cost dummy row or column.
Northwest Corner (fast), Least Cost (better), VAM (near-optimal).
\(d_{ij} = c_{ij} - (u_i + v_j)\); optimal when all \(d_{ij} \ge 0\).
Stepping-stone loop reallocates \(\theta\); keep \(m + n - 1\) occupied cells (add \(\varepsilon\) if short).
Problems
Draw the tableau for each, apply the requested method, and check optimality with MODI. Difficulty rises down the list.
- Write the LP (objective and constraints) for 3 sources and 2 destinations.
- Supplies total \(90\), demands total \(110\). Balance the problem and state the dummy's costs.
- Apply the Northwest Corner method to supplies \(50, 60, 50\) and demands \(30, 70, 60\).
- Apply the Least Cost method to the same data with a cost matrix of your instructor's choosing, and compare with Problem 3.
- State the rule for the number of occupied cells and explain why it matters for MODI.
- Given occupied-cell costs, set up the \(u_i + v_j = c_{ij}\) equations and solve for the potentials with \(u_1 = 0\).
- Compute the opportunity cost of one empty cell given the potentials, and interpret its sign.
- Describe the stepping-stone loop for an entering cell and how \(\theta\) is chosen.
- Explain how a dummy destination's zero costs guarantee it never distorts the real routing.
- A solution has only \(m + n - 2\) occupied cells. What has gone wrong and how is it fixed?
- Outline Vogel's Approximation Method and why its penalty idea gives a good start.
- A company ships from 3 plants (supplies \(45, 25, 30\)) to 3 markets (demands \(30, 35, 35\)) with costs \(\begin{smallmatrix}8&6&3\\4&9&5\\7&2&6\end{smallmatrix}\). Find an initial solution by Least Cost, test it with MODI, and confirm the minimum total cost — reporting the full shipping plan.