Transportation problem

At a Glance

• Frequency: 5 sub-parts across 5 of 13 years (2014, 2017, 2020, 2022, 2025)
• Priority tier: T2
• Marks (count): 15 (1), 20 (4)
• Average solve time: ~22 min
• Difficulty mix: hard 4, medium 1
• Section: A | Dominant type: computation

Why This Chapter Matters

Transportation questions appear in 5 of the last 13 years and are consistently 20 marks — the single highest-mark question in Paper 2’s linear-programming cluster. Every question follows the same two-phase algorithm: find an initial basic feasible solution (IBFS) by Vogel’s Approximation Method (VAM), then test and achieve optimality by the MODI ($u,v$) method. The algorithm is long but entirely procedural; the challenge is accuracy across many small arithmetic steps. A student who internalises the VAM and MODI templates can reliably score all 20 marks here.

Minimum Theory

Balanced transportation problem. $m$ sources with supplies $a_i$, $n$ destinations with demands $b_j$, cost $c_{ij}$ per unit shipped on route $(i,j)$. Balanced means $\sum a_i=\sum b_j$; if unbalanced, add a dummy row or column with zero costs.

Basic feasible solution (BFS). A solution with exactly $m+n-1$ allocated cells (non-degenerate). Fewer allocations = degenerate; handle by adding a tiny allocation $\varepsilon$ in an unoccupied cell.

Vogel’s Approximation Method (VAM) — IBFS.

1. For each row/column, compute the penalty = (2nd smallest cost) $-$ (smallest cost).
2. Identify the row or column with the maximum penalty.
3. In that row/column, allocate as much as possible to the cheapest cell: allocate $\min(\text{remaining supply},\text{remaining demand})$.
4. Cross out the exhausted row or column. Recompute penalties (ignoring crossed-out rows/columns).
5. Repeat until all supply and demand are fulfilled.

MODI / $u$-$v$ optimality test.

1. For each allocated cell $(i,j)$, set $u_i+v_j=c_{ij}$. Fix $u_1=0$ and solve for all $u_i,v_j$.
2. For each unallocated cell, compute the opportunity cost $\Delta_{ij}=c_{ij}-u_i-v_j$.
3. If all $\Delta_{ij}\ge0$: the current BFS is optimal.
4. If any $\Delta_{ij}<0$: bring the cell with the most negative $\Delta$ into the basis via a closed loop reallocation; repeat.

Question Archetypes

One pattern covers every transportation question in the corpus.

transportation-problem (5 question(s); 2014, 2017, 2020, 2022, 2025)

Recognition Cues

• A table of costs with row supply and column demand totals; “find IBFS by Vogel’s method.”
• “Hence find the optimal solution and the minimum transportation cost.”
• Sometimes: “Only find the IBFS by VAM” (no MODI step).

Solution Template

Phase 1: VAM

1. Write the cost table with supply and demand.
2. Compute row and column penalties. Record them next to each row/column.
3. Mark the maximum penalty; allocate to the cheapest cell in that row/column; update supply/demand; cross out the exhausted row/column.
4. Repeat. If a tie in penalties, break it arbitrarily (or choose the allocation that gives a smaller cost).
5. Stop when all supply and demand are met. Count allocations: must be $m+n-1$.

Phase 2: MODI

1. Label allocated cells. Set $u_1=0$; solve $u_i+v_j=c_{ij}$ for all allocated cells.
2. Compute $\Delta_{ij}=c_{ij}-u_i-v_j$ for all unallocated cells.
3. If all $\Delta_{ij}\ge0$: current solution is optimal; compute and state total cost.
4. If any $\Delta_{ij}<0$: enter the most-negative cell via a loop (trace a path of alternating horizontal and vertical moves through allocated cells); redistribute along the loop by adding/subtracting $\theta=$ minimum allocation on the minus-sign cells.

Worked Example(s)

2014 Paper 2, 2014-P2-Q2c (20 marks)

Transportation problem (3 sources × 4 destinations); find IBFS by VAM; test and achieve optimality by MODI.

VAM iterations (penalties in parentheses):

Iter 1: Row penalties $O_1$:3, $O_2$:5, $O_3$:1; Col penalties $D_1$:2, $D_2$:1, $D_3$:1, $D_4$:3. Max penalty 5 at $O_2$. Cheapest cell in $O_2$: $(O_2,D_3)$ cost 2. Allocate $\min(16,15)=15$. Eliminate $D_3$.

Iter 2: Max penalty 3 at $D_4$. Cheapest in $D_4$: $(O_3,D_4)$ cost 2. Allocate 4. Eliminate $D_4$.

Iter 3: Max penalty 2 at $O_1$. Cheapest in $O_1$: $(O_1,D_2)$ cost 4. Allocate 10. Eliminate $D_2$.

Iter 4: Only $D_1$ remains (demand 6). Fill: $x_{11}=4$, $x_{21}=1$, $x_{31}=1$.

IBFS allocations and cost: $4(6)+10(4)+1(8)+15(2)+1(4)+4(2)=24+40+8+30+4+8=\mathbf{114}$.

MODI check: Set $u_1=0$. From allocated cells: $v_1=6,v_2=4,v_3=0$ ($u_2+v_3=2\Rightarrow u_2=2$), $v_4=4$ ($u_3+v_4=2\Rightarrow u_3=-2$).

Opportunity costs for unallocated cells: $(1,3)$:$1-0-0=1$; $(1,4)$:$5-0-4=1$; $(2,2)$:$9-2-4=3$; $(2,4)$:$7-2-4=1$; $(3,2)$:$3-(-2)-4=1$; $(3,3)$:$6-(-2)-0=8$. All $\ge0$.

$\boxed{\text{Optimal cost}=114.}$

2020 Paper 2, 2020-P2-Q4c (20 marks)

Costs $S_1[10,0,20,11]/15$, $S_2[12,7,9,20]/25$, $S_3[0,14,16,18]/5$; demands $[5,15,15,10]$.

Note: cost 0 entries are legitimate (no cost on that route). Run VAM and MODI following the same template; the zero entries are the cheapest cells and will be allocated first in the penalty step.

Common Traps

• $m+n-1$ allocations: a $3\times4$ table requires $3+4-1=6$ allocations for a non-degenerate BFS. If VAM gives only 5, add a small $\varepsilon$ to one unoccupied cell adjacent to an already-used row and column before applying MODI.
• Penalty recomputation: after eliminating a row or column, recompute penalties from the surviving rows/columns only. Using stale penalties is the most common error.
• MODI system: set $u_1=0$ (not $u_i=0$ for the row with the most allocations — any starting point works, but $u_1=0$ is simplest). Solve by propagating from allocated cells.
• Loop direction: in the MODI loop reallocation, alternate $+$ and $-$ around the closed path. The quantity shifted is the minimum of all current allocations on the $-$ corners; one of those cells will drop to zero (leaves the basis).

Practice Set

• 2017-P2-Q4b (15 m) — — IBFS only by VAM for a 3×5 table; straightforward penalty application.
• 2022-P2-Q4c (20 m) — — balanced 3×4; VAM+MODI; a good full-algorithm practice.