Chapter 12 · Linear Programming

12.2 Transportation and Assignment Problems

Two linear programmes with so much structure that the simplex method runs on a table: the transportation problem — bases as spanning trees, the north-west corner, least-cost and Vogel starts, the MODI test, loops and degeneracy, unbalanced problems — and the assignment problem, solved by Kőnig's theorem and the Hungarian method.

A cement company has three plants and four construction sites; each plant can supply so many tonnes a week, each site needs so many, and shipping a tonne from plant $i$ to site $j$ costs $c_{ij}$. How much should go along each route? A hospital has four surgeons and four operating slots, and the expected duration of each surgeon's list in each slot is known; who should take which slot? The first is a transportation problem, the second an assignment problem, and both are linear programmes (§12.1). But their constraint matrices are so special — every column has exactly two $1$'s, one in a supply row and one in a demand row — that bases become spanning trees of a bipartite graph, every basic solution with integer data is integral, the dual variables can be found by inspection, and a simplex pivot becomes "push $\theta$ units around a loop". This is why these problems are solved by hand on a table.

GATE MA asks for the initial cost given by the north-west corner, least-cost or Vogel rule, for the number of basic cells and the meaning of degeneracy, for the minimum cost after the MODI test, and for the optimal value of an assignment problem (often a maximisation, sometimes unbalanced); MSQs test statements such as "Vogel's method always gives an optimal solution" or "a basic feasible solution has $m+n$ positive allocations". This section develops the theory in full — the results here are not proved in the CSIR course — and every algorithm is justified by a theorem. The LP background (bases, net evaluations, duality and complementary slackness) is §12.1.

The Transportation Problem and the Structure of Its Bases

📘 Definition 12.8 — Transportation problem; balanced and unbalanced; the transportation table

There are $m$ sources with supplies $a_1,\dots,a_m\gt0$ and $n$ destinations with demands $b_1,\dots,b_n\gt0$; shipping one unit from source $i$ to destination $j$ costs $c_{ij}$. The problem is balanced if $\sum_ia_i=\sum_jb_j$, and the (balanced) transportation problem (TP) is

$$\min\ \sum_{i=1}^m\sum_{j=1}^nc_{ij}x_{ij}$$ $$\text{s.t.}\ \ \sum_{j}x_{ij}=a_i\ \ (i\le m),$$ $$\sum_{i}x_{ij}=b_j\ \ (j\le n),\qquad x_{ij}\ge0.$$

The data are written in a transportation table with a cell $(i,j)$ for each route (cost in the corner, shipment $x_{ij}$ inside), the supplies on the right and the demands at the bottom. If $\sum a_i\gt\sum b_j$ (excess supply) the problem asks to ship at most $a_i$ from each source; if $\sum a_i\lt\sum b_j$ (shortage) it asks to deliver at most $b_j$ to each destination — such problems are unbalanced.

📐 Theorem 12.12 — Feasibility, existence and balancing
  1. A balanced TP is feasible — $x_{ij}=a_ib_j/T$ with $T=\sum_ia_i$ is a feasible solution — its feasible region is a polytope, and it has an optimal solution.
  2. If $\sum_ia_i\gt\sum_jb_j$, add a dummy destination $n+1$ with demand $b_{n+1}=\sum a_i-\sum b_j$ and costs $c_{i,n+1}=0$ (or the cost of storing a unit at source $i$). If $\sum a_i\lt\sum b_j$, add a dummy source $m+1$ with supply $\sum b_j-\sum a_i$ and costs $c_{m+1,j}=0$ (or the penalty for a unit of unmet demand at $j$). In either case the feasible solutions of the unbalanced problem correspond one-to-one to those of the balanced one, with equal costs.

Proof. (1) $\sum_ja_ib_j/T=a_i$ and $\sum_ia_ib_j/T=b_j\cdot\frac{T}{T}$, using $\sum_ia_i=\sum_jb_j=T$. Every feasible $x$ has $0\le x_{ij}\le\min(a_i,b_j)$, so the region is a bounded polyhedron, i.e. compact; a continuous (linear) function attains its minimum on a nonempty compact set. (2) Excess supply: given a feasible $x$ of the unbalanced problem ($\sum_jx_{ij}\le a_i$, $\sum_ix_{ij}=b_j$), put $x_{i,n+1}=a_i-\sum_{j\le n}x_{ij}\ge0$, the amount left at source $i$. Then every row sums to $a_i$, the dummy column sums to $\sum a_i-\sum b_j=b_{n+1}$, and the cost is unchanged because the dummy costs are $0$ (or it now includes the storage cost, as intended). Conversely, deleting the dummy column of a balanced solution gives a feasible solution of the unbalanced one. The shortage case is the same with rows and columns exchanged. ∎

A route that may not be used (a closed road, a forbidden pairing) gets a cost $M$, "larger than any number it is compared with", exactly as in the Big-M method of §12.1; it will carry nothing at the optimum unless the problem is infeasible without it.

Now the structure. Order the variables $x_{11},\dots,x_{1n},x_{21},\dots,x_{mn}$; the column of $x_{ij}$ in the constraint matrix is $e_i+e_{m+j}\in\mathbb{R}^{m+n}$ (a $1$ in supply row $i$ and a $1$ in demand row $j$).

📐 Theorem 12.13 — The rank is $m+n-1$
The $(m+n)\times mn$ constraint matrix of a TP has rank exactly $m+n-1$. Any one equation is implied by the others (in a balanced problem), and after deleting it the remaining $m+n-1$ rows are independent. Hence every basis consists of $m+n-1$ cells.

Proof. Let $R_i$ and $D_j$ denote the supply and demand rows. Each column $e_i+e_{m+j}$ has entry $1$ in $R_i$ and in $D_j$, so $\sum_iR_i=\sum_jD_j$ (both equal the all-ones row): the rows are dependent and the rank is at most $m+n-1$; balance makes the corresponding right-hand sides agree, so the deleted equation is implied. Suppose $\sum_i\alpha_iR_i+\sum_{j\lt n}\beta_jD_j=0$. The entry in the column of cell $(i,n)$ is $\alpha_i$ (row $D_n$ is not in the sum), so every $\alpha_i=0$; then the entry in the column of cell $(1,j)$ is $\beta_j$, so every $\beta_j=0$. Thus the $m+n-1$ rows other than $D_n$ are independent. ∎

📘 Definition 12.9 — Loops; the graph of a set of cells
A loop (cycle) is a sequence of distinct cells $(i_1,j_1),(i_1,j_2),(i_2,j_2),$ $(i_2,j_3),\dots,(i_k,j_k),(i_k,j_1)$, $k\ge2$, in which consecutive cells lie alternately in the same row and in the same column, returning to the start; it has an even number $2k\ge4$ of cells, the corners of a closed path made of horizontal and vertical segments (the path may cross other cells without turning there). To a set $S$ of cells associate the bipartite graph $G(S)$ whose vertices are the $m$ rows and $n$ columns and whose edges are the cells of $S$ (cell $(i,j)$ joins row $i$ to column $j$). Loops of cells are exactly cycles of $G(S)$.
📐 Theorem 12.14 — Bases are loop-free sets of $m+n-1$ cells (spanning trees)
For a set $S$ of cells, the columns $e_i+e_{m+j}$, $(i,j)\in S$, are linearly independent if and only if $S$ contains no loop. Consequently a set of cells is a basis of the TP if and only if it has $m+n-1$ cells and contains no loop, i.e. $G(S)$ is a spanning tree of the $m+n$ rows and columns.

Proof. If $S$ contains a loop, give its corners the signs $+,-,+,-,\dots$ in order. Each row and each column met by the loop contains exactly two of its corners, one of each sign, so $\sum\pm(e_i+e_{m+j})=0$: the columns are dependent. Conversely, let $S$ contain no loop, and suppose $\sum_{(i,j)\in S}\lambda_{ij}(e_i+e_{m+j})=0$ with not all $\lambda_{ij}=0$; let $S'\subseteq S$ be the cells with $\lambda_{ij}\ne0$. $G(S')$ has no cycle, so it is a forest with at least one edge, and a forest with an edge has a vertex of degree $1$ — a row or column containing exactly one cell of $S'$. The coordinate of that row (or column) in the sum is that cell's $\lambda$, which must therefore be $0$: a contradiction. So the columns are independent. For the last statement: by Theorem 12.13 a basis has $m+n-1$ independent columns; and a forest on $m+n$ vertices with $m+n-1$ edges is connected, i.e. a spanning tree. ∎

📐 Theorem 12.15 — Basic solutions by peeling leaves; integrality
Given a basis $S$, its basic solution is computed by repeatedly choosing a row or column that contains a single remaining basic cell, setting that cell equal to the remaining supply or demand of the line, subtracting it from the other line through the cell, and deleting the cell. Consequently, if all $a_i,b_j$ are integers, every basic solution is integral, and a balanced TP with integer data has an integral optimal solution.

Proof. $G(S)$ is a tree, so it has a leaf: a line with exactly one basic cell. In that line's equation all other variables are nonbasic ($=0$), so the basic cell equals the line's total. Removing the leaf and updating the total of the other line through the cell leaves a tree on one vertex fewer, and we repeat. Each value is a difference of integers, hence an integer. An optimal solution exists (Theorem 12.12), so by the fundamental theorem of linear programming (§12.1) an optimal basic solution exists; it is integral. ∎

✏️ Example 1 — Relief supplies: balancing, a closed road, and a basis by leaf peeling
Three depots $D_1,D_2,D_3$ hold $40,35,25$ tonnes of rice; four relief camps $C_1,\dots,C_4$ need $30,30,25,35$ tonnes. Transport costs (thousand rupees per tonne) are $D_1:(5,8,6,9)$, $D_2:(7,4,\text{—},6)$, $D_3:(6,7,5,8)$, where the road $D_2\to C_3$ is closed. Every tonne of unmet need at camp $j$ is valued at a penalty of $9,6,8,7$ respectively. (a) Set up the balanced table. (b) Is $S=\{(1,1),(1,3),(2,2),(2,4),$ $(3,3),(4,2),(4,4)\}$ a basis? (c) Show that $S'=\{(1,1),(1,2),(1,3),(2,2),$ $(2,4),(3,3),(4,4)\}$ is a basis, find its basic solution, and decide whether it is feasible and degenerate. What is its cost, and what does it mean?
(a) Balance Supply $100$, demand $120$: shortage $20$. Add a dummy depot $D_4$ with supply $20$ whose costs are the penalties $(9,6,8,7)$ — a tonne "shipped" from $D_4$ to $C_j$ is a tonne of $C_j$'s need left unmet. The closed road gets cost $M$.
$C_1$$C_2$$C_3$$C_4$supply
$D_1$$5$$8$$6$$9$$40$
$D_2$$7$$4$$M$$6$$35$
$D_3$$6$$7$$5$$8$$25$
$D_4$ (dummy)$9$$6$$8$$7$$20$
demand$30$$30$$25$$35$$120$
Now $m=n=4$, so every basis has $m+n-1=7$ cells.
(b) A loop $S$ has $7$ cells, but $(2,2),(2,4),(4,4),(4,2)$ is a loop (rows $2,4$, columns $2,4$). By Theorem 12.14, $S$ is not a basis: seven cells are necessary, not sufficient.
(c) A tree In $G(S')$: row 1 joins columns 1, 2, 3; row 2 joins columns 2, 4; row 3 joins column 3; row 4 joins column 4. All $8$ vertices are connected by $7$ edges: a spanning tree, so $S'$ is a basis. Peel leaves (Theorem 12.15): column 1 has only $(1,1)$, so $x_{11}=30$; row 3 has only $(3,3)$: $x_{33}=25$; row 4 has only $(4,4)$: $x_{44}=20$. Then column 3 needs $25-25=0$ more: $x_{13}=0$; column 4 needs $35-20=15$: $x_{24}=15$; row 2 has $35-15=20$ left: $x_{22}=20$; row 1 has $40-30-0=10$ left: $x_{12}=10$, and column 2 checks: $10+20=30$. ✓
Answer All values are $\ge0$, so this is a BFS; it is degenerate, since only $6$ of its $7$ basic cells are positive ($x_{13}=0$). Its cost is $5\cdot30+8\cdot10+4\cdot20$ $+6\cdot15+5\cdot25+7\cdot20=665$: shipping costs $525$ plus a penalty of $140$ for leaving $20$ tonnes of camp $C_4$'s need unmet. The closed road carries nothing.

Initial Basic Feasible Solutions: North-West Corner, Least Cost, Vogel

📘 Definition 12.10 — The three starting rules

All three rules repeat one step on a balanced table: choose a cell $(i,j)$ in a row and a column not yet crossed out; allocate $x_{ij}=\min(\text{remaining }a_i,\text{remaining }b_j)$; reduce both remainders; cross out the row or the column that has reached $0$. If both reach $0$ at once (and other lines remain), cross out only one of them — the row, say — and leave the column with remainder $0$; it will later receive a basic allocation of $0$. When one row and one column remain, the last allocation crosses out both. The rules differ only in the choice of cell:

  • North-west corner (NW) rule: the top-left cell of the remaining table. Costs are ignored.
  • Least-cost (matrix minimum) method: a cell of least cost in the remaining table (ties: the one allowing the largest allocation).
  • Vogel's approximation method (VAM): for each remaining row and column compute its penalty — the difference between its two smallest remaining costs (the cost itself if one cell remains). Take the line with the largest penalty (ties: the line containing the smaller least cost) and, in it, the cell of least cost. When a single row or column remains, its allocations are forced.
📐 Theorem 12.16 — The starting rules give basic feasible solutions
For a balanced TP each rule makes exactly $m+n-1$ allocations (some possibly $0$), and the allocated cells form a basis whose basic solution is the allocation. In particular the result is a BFS, which is degenerate exactly when some allocation is $0$.

Proof. Feasibility and termination. Throughout, the remaining supplies of uncrossed rows add up to the remaining demands of uncrossed columns (both drop by $x_{ij}$ at each step), and all remainders stay $\ge0$. Every allocation crosses out exactly one line, except the last, which crosses out the final row and column together (by balance their remainders are equal). As there are $m+n$ lines, there are exactly $m+n-1$ allocations, and at the end every row has shipped $a_i$ and every column received $b_j$. No loop. Suppose the allocated cells contained a loop, and let $(i,j)$ be the loop cell allocated first. When it was allocated, row $i$ or column $j$ was crossed out, say row $i$; no later allocation lies in row $i$. But the loop contains another cell of row $i$, allocated later — a contradiction (similarly for column $j$; the very last allocation crosses both lines but is not the first loop cell). By Theorem 12.14 the $m+n-1$ cells form a basis, and the allocation, which vanishes off them and satisfies all constraints, is its basic solution. ∎

🧭 Problem-solving strategy — Vogel's method by hand
  1. Balance the table first (dummy row or column with zero or penalty costs).
  2. Write the penalty of each row to its right and of each column below it: second-smallest minus smallest remaining cost.
  3. Circle the largest penalty; allocate as much as possible to the cheapest cell of that line; cross out the exhausted line (only one, if both run out — and note the $0$).
  4. Recompute only the penalties that changed (lines meeting the crossed-out line). Repeat until one row or column is left, then fill it.
  5. Check: $m+n-1$ basic cells, row and column totals, and the cost $\sum c_{ij}x_{ij}$. VAM is usually close to optimal — but not always optimal, so the MODI test is still needed.
✏️ Example 2 — Three plants, four sites: the three starting rules compared
Plants $P_1,P_2,P_3$ supply $30,55,20$ tonnes; sites $S_1,\dots,S_4$ need $25,45,10,25$. The costs per tonne are $P_1:(9,7,2,11)$, $P_2:(14,15,4,9)$, $P_3:(12,3,12,13)$. Find the initial BFS and its cost by the NW rule, the least-cost method and VAM.
Balance $30+55+20=105=25+45+10+25$; $m+n-1=6$ basic cells.
NW corner $x_{11}=25$ ($S_1$ done, $P_1$ has $5$ left), $x_{12}=5$ ($P_1$ done, $S_2$ needs $40$), $x_{22}=40$ ($P_2$ has $15$), $x_{23}=10$, $x_{24}=5$ ($P_2$ done, $S_4$ needs $20$), $x_{34}=20$. Cost $225+35+600+40+45+260=1205$.
Least cost Cheapest cell $(1,3)$, cost $2$: $x_{13}=10$ ($S_3$ out). Next $(3,2)$, cost $3$: $x_{32}=20$ ($P_3$ out). Next $(1,2)$, cost $7$: $x_{12}=20$ ($P_1$ out). Only $P_2$ is left: $x_{24}=25$, $x_{21}=25$, $x_{22}=5$. Cost $20+60+140+225+350+75=870$.
VAM Penalties and choices:
roundrow penalties $P_1,P_2,P_3$column penalties $S_1,\dots,S_4$largestallocation
1$5,\ 5,\ \mathbf{9}$$3,\ 4,\ 2,\ 2$$P_3$$x_{32}=20$, $P_3$ out
2$5,\ 5,\ -$$5,\ \mathbf{8},\ 2,\ 2$$S_2$$x_{12}=25$, $S_2$ out
3$\mathbf{7},\ 5,\ -$$5,\ -,\ 2,\ 2$$P_1$$x_{13}=5$, $P_1$ out
4only $P_2$ remains$x_{21}=25$, $x_{23}=5$, $x_{24}=25$
(Round 1: $P_3$'s costs $12,3,12,13$ give $12-3=9$. Round 2, with $P_3$ gone: $S_2$'s costs $7,15$ give $8$. Round 3: $P_1$'s remaining costs $9,2,11$ give $7$.) Cost $60+175+10+350+20+225=840$.
Compare Each solution has exactly $6$ positive cells: all three are nondegenerate BFSs. NW $1205$, least cost $870$, VAM $840$. The optimum turns out to be $825$ (Example 3), so even VAM is not optimal here.

The MODI (u–v) Method: Optimality, Loops and Degeneracy

To improve a BFS we need the net evaluations of §12.1. For a TP they come from the dual, which has one free variable $u_i$ per source and $v_j$ per destination (the constraints are equations).

📐 Theorem 12.17 — The MODI test
Let $x$ be a BFS of a balanced TP with basis $S$.
  1. The dual of the TP is $\ \max\sum_ia_iu_i+\sum_jb_jv_j\ $ s.t. $u_i+v_j\le c_{ij}$ for all $(i,j)$, with $u,v$ free.
  2. The equations $u_i+v_j=c_{ij}$, $(i,j)\in S$, have a solution, unique once one value is fixed (say $u_1=0$). The numbers $d_{ij}=c_{ij}-u_i-v_j$ are the reduced costs — exactly the net evaluations $\Delta_{ij}$ of the simplex method (§12.1) when the TP is written as the maximisation of $-\sum c_{ij}x_{ij}$ — and $d_{ij}=0$ on $S$.
  3. For a nonbasic cell $(p,q)$, $d_{pq}$ equals the alternating sum $c_{pq}-c_{\cdot}+c_{\cdot}-\cdots$ of the costs around the loop of $(p,q)$ with the basic cells (Theorem 12.18): the change in total cost per unit sent round that loop.
  4. If $d_{ij}\ge0$ for every cell, $x$ is optimal, $(u,v)$ is an optimal dual solution, and the two optimal values are equal. If $d_{ij}\gt0$ for every nonbasic cell, $x$ is the unique optimal solution.

Proof. (1) Apply the rules for forming a dual (§12.1): a minimisation with equation constraints gives free dual variables; $x_{ij}\ge0$ gives the constraint $u_i+v_j\le c_{ij}$. (2) Since $G(S)$ is a spanning tree, fixing $u_1$ and moving along tree edges determines each neighbour uniquely ($v_j=c_{ij}-u_i$ or $u_i=c_{ij}-v_j$), and every vertex is reached exactly once. The vector $(u,v)$ then plays the role of the simplex multipliers $\pi=c_{\mathcal B}^{\mathsf T}B^{-1}$: $\pi^{\mathsf T}(e_i+e_{m+j})=u_i+v_j$ equals $c_{ij}$ on basic columns, so $d_{ij}=c_{ij}-\pi^{\mathsf T}a_{ij}$ is the reduced cost. (3) Around the loop $(p,q)=\ell_1,\ell_2,\dots,\ell_{2k}$, with $\ell_2,\dots,\ell_{2k}$ basic, the sum $\sum_t(-1)^{t+1}(u_{i_t}+v_{j_t})$ telescopes to $0$ (each row and column of the loop appears once with each sign); hence $\sum_t(-1)^{t+1}c_{\ell_t}=\sum_t(-1)^{t+1}d_{\ell_t}=d_{pq}$, since $d=0$ on basic cells. Sending one unit round the loop ($+1$ on odd corners, $-1$ on even ones) keeps all row and column totals and changes the cost by exactly this sum. (4) If all $d_{ij}\ge0$, $(u,v)$ is dual feasible, and because $x_{ij}=0$ off $S$, $$\sum_{i,j}c_{ij}x_{ij}=\sum_{(i,j)\in S}(u_i+v_j)x_{ij}=\sum_ia_iu_i+\sum_jb_jv_j ,$$ so the primal and dual values agree and both are optimal by weak duality. If moreover $d_{ij}\gt0$ off $S$ and $x'$ is another feasible solution, then $\sum c_{ij}x'_{ij}=\sum_ia_iu_i+\sum_jb_jv_j+\sum_{(i,j)\notin S}d_{ij}x'_{ij}$ (expand $c_{ij}=u_i+v_j+d_{ij}$), which exceeds the optimum unless $x'$ vanishes off $S$ — and then $x'=x$, the unique basic solution of $S$. ∎

📐 Theorem 12.18 — The loop pivot
Let $S$ be a basis and $(p,q)\notin S$. Then $S\cup\{(p,q)\}$ contains exactly one loop, and it passes through $(p,q)$. Label its corners alternately $+$ (starting with $(p,q)$) and $-$, and let $\theta=\min\{x_{ij}:(i,j)\text{ a }-\text{ corner}\}$. Adding $\theta$ on the $+$ corners and subtracting it on the $-$ corners gives a feasible solution; removing one $-$ corner where the minimum is attained from $S\cup\{(p,q)\}$ gives a basis whose basic solution it is, and the cost changes by $\theta\,d_{pq}$.

Proof. Adding the edge $(p,q)$ to the spanning tree $G(S)$ creates exactly one cycle — the tree path from row $p$ to column $q$ closed by the new edge. Shifting $\pm\theta$ round it keeps every row and column total; the $+$ corners increase, and the $-$ corners stay $\ge0$ by the choice of $\theta$. Removing an edge of the cycle from a graph with exactly one cycle leaves a spanning tree, so the new set is a basis (Theorem 12.14); the new solution vanishes off it, so it is its basic solution. The cost change is $\theta$ times the alternating cost sum, which is $\theta d_{pq}$ by Theorem 12.17(3). This is exactly the simplex pivot of §12.1: $(p,q)$ enters, the ratio test is the minimum over the $-$ corners. ∎

🧭 Problem-solving strategy — the transportation (MODI) algorithm
  1. Balance; find an initial BFS (VAM is usually best). Make sure there are exactly $m+n-1$ basic cells: if a rule was not followed carefully and fewer cells are positive, add zero cells (the "$\varepsilon$" cells) that create no loop.
  2. Put $u_1=0$ and solve $u_i+v_j=c_{ij}$ along the basic cells.
  3. Compute $d_{ij}=c_{ij}-u_i-v_j$ for the nonbasic cells. If all $d_{ij}\ge0$: optimal (unique if all $\gt0$; a $d_{ij}=0$ signals a possible alternative optimum).
  4. Otherwise let $(p,q)$ have the most negative $d_{pq}$; trace its loop, mark $+,-$ alternately, set $\theta=$ smallest "$-$" allocation, shift, and drop one cell that became $0$ (only one, even if several did — the others stay as basic zeros). The cost falls by $\theta|d_{pq}|$; if $\theta=0$ only the basis changes (a degenerate pivot).
  5. Repeat from step 2. For a maximisation (profits $p_{ij}$), minimise $\sum(-p_{ij})x_{ij}$, or equivalently use costs $c_{ij}=P-p_{ij}$ with $P=\max p_{ij}$.
✏️ Example 3 — MODI from Vogel's start
Starting from the VAM solution of Example 2 (cost $840$), find an optimal shipping plan, verify optimality through the dual, and decide whether it is unique.
Potentials Basic cells $x_{12}=25$, $x_{13}=5$, $x_{21}=25$, $x_{23}=5$, $x_{24}=25$, $x_{32}=20$. With $u_1=0$: $v_2=7$, $v_3=2$; $(2,3)$: $u_2=4-2=2$; $(2,1)$: $v_1=12$; $(2,4)$: $v_4=7$; $(3,2)$: $u_3=3-7=-4$.
Reduced costs $d_{11}=9-0-12=-3$, $d_{14}=11-7=4$, $d_{22}=15-2-7=6$, $d_{31}=12+4-12=4$, $d_{33}=12+4-2=14$, $d_{34}=13+4-7=10$. Only $d_{11}\lt0$: every tonne sent round the loop of $(1,1)$ saves $3$.
Loop $(1,1)^+\to(1,3)^-\to(2,3)^+\to(2,1)^-$ (check: $9-2+4-14=-3=d_{11}$). The "$-$" cells hold $5$ and $25$, so $\theta=5$ and $(1,3)$ leaves: $x_{11}=5$, $x_{23}=10$, $x_{21}=20$. Cost $840-3\cdot5=825$.
Test again New potentials: $u_1=0$, $v_1=9$, $v_2=7$, $u_2=5$, $v_3=-1$, $v_4=4$, $u_3=-4$. Reduced costs: $d_{13}=3$, $d_{14}=7$, $d_{22}=3$, $d_{31}=7$, $d_{33}=17$, $d_{34}=13$ — all positive.
Answer Ship $P_1\to S_1$: $5$, $P_1\to S_2$: $25$, $P_2\to S_1$: $20$, $P_2\to S_3$: $10$, $P_2\to S_4$: $25$, $P_3\to S_2$: $20$; minimum cost $825$, and it is the unique optimum (Theorem 12.17(4)). Dual check: $\sum a_iu_i=0+275-80=195$ and $\sum b_jv_j=225+315-10+100=630$, total $825$. ✓
✏️ Example 4 — An unbalanced problem, a degenerate start and an alternative optimum
Plants $P_1,P_2,P_3$ can produce $20,30,25$ units; markets $M_1,M_2,M_3$ need $20,25,20$. Costs: $P_1:(3,10,2)$, $P_2:(10,8,2)$, $P_3:(4,8,12)$; unsold units cost nothing. Balance the problem, find the NW solution, and optimise it by MODI. Is the optimum unique?
Balance Supply $75$, demand $65$: add a dummy market $M_4$ with demand $10$ and costs $0$. Basic cells: $3+4-1=6$.
NW, degenerate $x_{11}=20$ exhausts both $P_1$ and $M_1$. Cross out $P_1$ only and move down: $x_{21}=0$ is a basic zero. Then $x_{22}=25$, $x_{23}=5$, $x_{33}=15$, $x_{34}=10$. Six basic cells, five positive: a degenerate BFS, cost $60+200+10+180=450$.
Iteration 1 $u_1=0$: $v_1=3$, $u_2=7$ (via the zero cell $(2,1)$ — this is why it is needed), $v_2=1$, $v_3=-5$, $u_3=17$, $v_4=-17$. Then $d_{31}=4-17-3=-16$ is the most negative ($d_{32}=-10$; the others are positive). Loop $(3,1)^+(3,3)^-(2,3)^+(2,1)^-$: the "$-$" cells hold $15$ and $0$, so $\theta=0$: a degenerate pivot. $(2,1)$ leaves, $(3,1)$ enters at level $0$; cost still $450$.
Iteration 2 $u_1=0$, $v_1=3$, $u_3=1$, $v_3=11$, $v_4=-1$, $u_2=-9$, $v_2=17$. Now $d_{12}=-7$, $d_{13}=-9$, $d_{32}=-10$ (most negative), the rest positive. Loop $(3,2)^+(3,3)^-(2,3)^+(2,2)^-$: $\theta=\min(15,25)=15$, $(3,3)$ leaves: $x_{32}=15$, $x_{23}=20$, $x_{22}=10$. Cost $450-10\cdot15=300$.
Iteration 3 $u_1=0$, $v_1=3$, $u_3=1$, $v_2=7$, $v_4=-1$, $u_2=1$, $v_3=1$. Reduced costs: $d_{12}=3$, $d_{13}=1$, $d_{14}=1$, $d_{21}=6$, $d_{24}=0$, $d_{33}=10$: optimal.
Answer $P_1\to M_1$: $20$, $P_2\to M_2$: $10$, $P_2\to M_3$: $20$, $P_3\to M_2$: $15$, and $P_3$ keeps $10$ units; minimum cost $300$. Since $d_{24}=0$, try the loop $(2,4)^+(2,2)^-(3,2)^+(3,4)^-$: $\theta=10\gt0$, giving $P_2$ keeping $10$, $P_2\to M_3$: $20$, $P_3\to M_2$: $25$, again of cost $60+40+200=300$. So the optimum is not unique: which plant keeps the surplus does not matter. (Both "$-$" cells drop to $0$ here; one leaves the basis and the other stays as a basic zero.)

The Assignment Problem and the Hungarian Method

📘 Definition 12.11 — Assignment problem; independent zeros; covering lines

Given an $n\times n$ cost matrix $C=(c_{ij})$ ($n$ workers, $n$ jobs), an assignment is a permutation $\sigma$ of $\{1,\dots,n\}$ (worker $i$ does job $\sigma(i)$), of cost $\sum_ic_{i\sigma(i)}$. The assignment problem asks for an assignment of least cost. As an LP: minimise $\sum c_{ij}x_{ij}$ subject to $\sum_jx_{ij}=1$, $\sum_ix_{ij}=1$, $x_{ij}\in\{0,1\}$ — a balanced TP with all $a_i=b_j=1$, plus integrality; dropping integrality ($x_{ij}\ge0$) gives the LP relaxation.

In a matrix, a set of zeros is independent if no two lie in the same row or column. A set of lines (rows and columns) covers the zeros if every zero lies in at least one of them.

📐 Theorem 12.19 — The assignment LP has integral corners (Birkhoff–von Neumann)
Every basic feasible solution of the LP relaxation is a permutation matrix. Hence the LP relaxation has an optimal solution that is an assignment, and its optimal value equals that of the assignment problem. For $n\ge2$ every such BFS is degenerate: only $n$ of its $2n-1$ basic cells are positive.

Proof. By Theorem 12.15 (with all $a_i=b_j=1$) a BFS is integral; integers $x_{ij}\ge0$ with row sums $1$ are $0$ or $1$, with exactly one $1$ in each row and (by the column sums) in each column: a permutation matrix. The relaxation has an optimal BFS (Theorem 12.12 and the fundamental theorem of §12.1), which is therefore an assignment; since every assignment is feasible for the relaxation, the two optimal values coincide. A basis has $m+n-1=2n-1$ cells (Theorem 12.13) but a permutation matrix has only $n\lt2n-1$ ones. ∎

The heavy degeneracy makes the MODI method clumsy for assignments. The Hungarian method exploits instead the fact that adding constants to rows and columns does not change which assignment is best.

📐 Theorem 12.20 — Row and column reductions
Let $C'=(c_{ij}-p_i-q_j)$ for numbers $p_1,\dots,p_n,q_1,\dots,q_n$.
  1. Every assignment costs exactly $\sum_ip_i+\sum_jq_j$ less under $C'$ than under $C$; hence $C$ and $C'$ have the same optimal assignments.
  2. If $C'\ge0$, then $L=\sum_ip_i+\sum_jq_j$ is a lower bound for the cost of every assignment under $C$.
  3. If $C'\ge0$ and $C'$ contains $n$ independent zeros, the assignment they define is optimal for $C$, and its cost is exactly $L$.

Proof. (1) An assignment uses exactly one entry in each row and each column, so its cost changes by $\sum_ip_i+\sum_jq_j$. (2) Under $C'\ge0$ every assignment costs $\ge0$; add $L$. (3) The $n$ independent zeros form an assignment of $C'$-cost $0$, the least possible by (2); its $C$-cost is $0+L$. (In LP terms, $(p,q)$ is a feasible solution of the dual $\max\sum p_i+\sum q_j$ s.t. $p_i+q_j\le c_{ij}$, and (2) is weak duality.) ∎

📐 Theorem 12.21 — Kőnig's theorem
In any square matrix, the largest number of independent zeros equals the smallest number of lines covering all the zeros.

Proof. No line contains two independent zeros, so covering $k$ independent zeros needs at least $k$ lines: max $\le$ min. For the reverse, let $Z$ be a largest set of independent zeros; call a row or column matched if it contains a zero of $Z$. Let $U$ be the unmatched rows, and let $\mathcal R$ be the set of rows and columns reachable from $U$ by alternating paths: from a row go to any column through a zero, from a column go back to a row only through the zero of $Z$ in that column. Every column in $\mathcal R$ is matched: otherwise the alternating path ending there could be "flipped" (its $Z$-zeros removed and its other zeros added), giving a larger independent set. Put $$K=\{\text{rows not in }\mathcal R\}\cup\{\text{columns in }\mathcal R\}.$$ $K$ covers every zero $(i,j)$: if row $i\notin\mathcal R$ it is covered; if row $i\in\mathcal R$, then column $j\in\mathcal R$ (reached through the zero $(i,j)$, or, if $(i,j)\in Z$, because $i\notin U$ was reached from $j$). Each line of $K$ contains exactly one zero of $Z$ (columns in $\mathcal R$ are matched; rows outside $\mathcal R$ are not in $U$, so matched), and no zero of $Z$ lies in two lines of $K$ (if its column is in $\mathcal R$, so is its row). Hence $|K|=|Z|$: min $\le$ max. ∎

🧭 Problem-solving strategy — the Hungarian method
  1. Prepare. Make the matrix square with dummy rows or columns of zeros (unbalanced problems). For a maximisation, replace each profit $p_{ij}$ by $P-p_{ij}$ with $P=\max p_{ij}$ (or by $-p_{ij}$). Give forbidden pairs the cost $M$.
  2. Reduce. Subtract each row's minimum from the row, then each column's minimum from the column. Keep the running total $L$ of everything subtracted.
  3. Cover. Cover all zeros with the fewest lines (by inspection, or by Kőnig's construction). If $n$ lines are needed, go to step 5.
  4. Adjust. Let $k$ be the smallest uncovered entry. Subtract $k$ from every uncovered entry and add $k$ to every entry covered twice (entries covered once do not change). $L$ increases by $k(n-r)$, where $r$ is the number of lines. Return to step 3.
  5. Assign. Choose $n$ independent zeros: repeatedly take a row or column with a single available zero, assign it, and strike out its row and column. The optimal cost is $L$ — check it against the original matrix.
📐 Theorem 12.22 — Correctness and termination of the Hungarian method
For an integer (or rational) cost matrix, the Hungarian method stops after finitely many adjustments, and the assignment it produces is optimal, of cost equal to the final value of $L$.

Proof. Suppose the zeros of the current matrix $C'\ge0$ are covered by $r\lt n$ lines, $\rho$ rows and $\gamma$ columns ($\rho+\gamma=r$). The adjustment is the same as subtracting $k$ from each of the $n-\rho$ uncovered rows and adding $k$ to each of the $\gamma$ covered columns: an uncovered entry changes by $-k$, an entry covered once by $0$ or $-k+k=0$, an entry covered twice by $+k$. So by Theorem 12.20(1) the optimal assignments are unchanged; the new matrix is $\ge0$ because $k$ was the least uncovered entry, and that entry becomes a new zero. The total subtracted grows by $k(n-\rho)-k\gamma=k(n-r)\gt0$. With integer data $k\ge1$, so $L$ grows by at least $1$ per round, while $L$ never exceeds the optimal cost (Theorem 12.20(2)); hence there are finitely many rounds (scale rational data to integers). When the method stops, $n$ lines are needed, so by Kőnig's theorem there are $n$ independent zeros, and Theorem 12.20(3) shows that they give an optimal assignment of cost $L$. ∎

✏️ Example 5 — Four crews, four jobs by the Hungarian method
Crew $i$ needs $c_{ij}$ hours for job $j$: $C=\begin{pmatrix}9&3&6&3\\11&5&7&9\\5&11&4&12\\7&11&13&5\end{pmatrix}$. Assign the crews to minimise the total time, and check the result with the lower bound $L$.
Reduce Row minima $3,5,4,5$ (total $17$), then column minima $1,0,0,0$ (total $1$), $L=18$: $$\begin{pmatrix}6&0&3&0\\6&0&2&4\\1&7&0&8\\2&6&8&0\end{pmatrix}\ \to\ \begin{pmatrix}5&0&3&0\\5&0&2&4\\0&7&0&8\\1&6&8&0\end{pmatrix}.$$
Cover The zeros lie at $(1,2),(1,4),(2,2),(3,1),(3,3),(4,4)$. Rows $1$ and $2$ both have zeros only in columns $2$ and $4$, and row $4$ only in column $4$, so at most $3$ independent zeros exist (rows $1,2,4$ share two columns); three lines suffice: row $3$, columns $2$ and $4$. As $3\lt4$, adjust.
Adjust The uncovered entries (rows $1,2,4$, columns $1,3$) are $5,3,5,2,1,8$: $k=1$. Subtract $1$ from them and add $1$ to the doubly covered $(3,2)$, $(3,4)$; $L=18+1\cdot(4-3)=19$: $$\begin{pmatrix}4&0&2&0\\4&0&1&4\\0&8&0&9\\0&6&7&0\end{pmatrix}.$$ Now there are four independent zeros, e.g. $(1,4),(2,2),(3,3),(4,1)$, so four lines are needed (Kőnig).
Assign Row $2$ has a single zero: crew $2\to$ job $2$. Then row $1$'s only free zero is job $4$, row $4$'s is job $1$, and row $3$ takes job $3$.
Answer Crew $1\to4$, $2\to2$, $3\to3$, $4\to1$: $3+5+4+7=19$ hours, equal to $L=19$, so it is optimal (Theorem 12.20(3)). A check of all $24$ assignments (the teaser of the chapter introduction) confirms $19$ as the unique minimum.
✏️ Example 6 — An unbalanced maximisation with a forbidden pairing
Three sales officers $A,B,C$ are to be posted to three of four territories $T_1,\dots,T_4$, one each; the expected monthly profits (lakh rupees) are $A:(27,29,13,15)$, $B:(31,15,30,21)$, $C:(36,\text{—},20,21)$, where $C$ may not be posted to $T_2$. Maximise the total profit. Which territory stays unserved?
Prepare Add a dummy officer $D$ with profit $0$ everywhere (the territory "given" to $D$ is unserved). Convert to costs $36-p_{ij}$ ($36$ is the largest profit) and give $(C,T_2)$ the cost $M$: $$\begin{pmatrix}9&7&23&21\\5&21&6&15\\0&M&16&15\\36&36&36&36\end{pmatrix}.$$
Reduce Row minima $7,5,0,36$ ($L=48$); every column then already contains a $0$: $$\begin{pmatrix}2&0&16&14\\0&16&1&10\\0&M&16&15\\0&0&0&0\end{pmatrix}.$$ Rows $A$ and $D$ and column $T_1$ cover all zeros: $3$ lines.
Adjust Smallest uncovered entry: $k=1$ (at $(B,T_3)$). Subtract $1$ from the uncovered entries, add $1$ at $(A,T_1)$ and $(D,T_1)$; $L=49$: $$\begin{pmatrix}3&0&16&14\\0&15&0&9\\0&M&15&14\\1&0&0&0\end{pmatrix}.$$
Assign $C$ has a single zero: $C\to T_1$. Then $B\to T_3$, $A\to T_2$, and $D\to T_4$.
Answer $A\to T_2$, $B\to T_3$, $C\to T_1$, with $T_4$ unserved: profit $29+30+36=95$ lakh per month. Check: the converted cost is $7+6+0+36=49=L$, and $4\cdot36-49=95$. Note that the "greedy" choice of giving $B$ its best territory $T_1$ would block $C$, whose only good option is $T_1$.
✏️ Example 7 — Prove or disprove
(a) Every basic feasible solution of a $3\times4$ balanced transportation problem has exactly $6$ positive allocations. (b) Adding the same constant $k$ to every cost in one row of a balanced TP does not change its optimal solutions. (c) For $n\ge2$, every basic feasible solution of an $n\times n$ assignment problem, regarded as a TP, is degenerate. (d) If the cheapest job of each worker is different for different workers, giving every worker their cheapest job is optimal; but letting the workers choose in turn, each taking the cheapest job still free, need not be optimal. (e) Vogel's method always gives an optimal solution.
(a) False A BFS has $m+n-1=6$ basic cells, but some may be $0$: in Example 4 (a $3\times4$ balanced table) the NW solution has only $5$ positive cells.
(b) True The cost becomes $\sum_{j}(c_{ij}+k)x_{ij}+\cdots$ $=\text{old cost}+k\sum_jx_{ij}$ $=\text{old cost}+ka_i$, the same shift for every feasible solution. (The same holds for columns; but adding $k$ to a single cell can change the optimum.)
(c) True Theorem 12.19: a BFS is a permutation matrix with $n$ ones, but a basis has $2n-1\gt n$ cells.
(d) True, then false If the row minima lie in different columns, row reduction already produces $n$ independent zeros, which are optimal (Theorem 12.20(3)). For the "choose in turn" rule, take $C=\begin{pmatrix}1&2\\2&10\end{pmatrix}$: worker $1$ takes job $1$, worker $2$ is left with cost $10$, total $11$, while the other assignment costs $2+2=4$.
(e) False In Example 2, VAM gives $840$ but the optimum is $825$ (Example 3).
⚠️ Counterexamples and pitfalls
  1. $m+n-1$ basic cells, not $m+n$ — and not necessarily positive. One constraint is redundant (Theorem 12.13). A degenerate BFS (Example 4, Example 1(c)) has fewer positive cells; the zero basic cells must still be recorded.
  2. Without enough basic cells the potentials cannot be found. In Example 4, $u_2$ is reached only through the zero cell $(2,1)$. Add "$\varepsilon$" cells that form no loop.
  3. Not every set of $m+n-1$ cells is a basis. It must contain no loop (Example 1(b)).
  4. The starting rules are heuristics with no ordering. NW ignores costs; least cost is not always better than NW (in GATE corner E3, NW gives the optimum $345$ and least cost gives $395$); VAM is not always optimal (Example 2) and not always better than least cost (for supplies $25,25,35$, demands $20,45,20$ and costs $(8,9,7),(3,3,7),(1,6,2)$, least cost gives the optimum $340$ but VAM gives $350$).
  5. Balance first. The rules and the MODI test assume a balanced table. Dummy costs are $0$ unless the problem prices storage or shortage.
  6. $d_{ij}=0$ at an optimum does not by itself prove another optimum. Pivot and check $\theta$: with $\theta\gt0$ a different optimal solution appears (Example 4); with $\theta=0$ only the basis changes.
  7. When several "$-$" cells reach $0$ at once, remove only one. Removing both leaves too few basic cells.
  8. Loops turn only at basic cells (and the entering cell), may pass over other cells, and can have $6$ or more corners (Exercise III.2).
  9. Maximisation needs a conversion. The MODI test "all $d_{ij}\ge0$" and the Hungarian method are for minimisation; use $P-p_{ij}$ or $-p_{ij}$ (or reverse the test consistently).
  10. Use the fewest covering lines. "$n$ lines" in the Hungarian method means that no fewer than $n$ lines can cover the zeros. Covering them wastefully (say, one line through every row that contains a zero) can suggest that an assignment exists when it does not, and gives the wrong uncovered entries for the adjustment.
  11. The optimal assignment cost is not the sum of row minima. That sum is only a lower bound ($17\lt19$ in Example 5).
  12. A travelling-salesman problem is not an assignment problem. With $c_{ii}=M$, the best assignment may split the cities into separate cycles (Exercise IV.8).

Two Labs

Interactive 1 — Transportation Table: Starting Rules, then MODI Loops

Each cell shows its cost (top corner) and its allocation (centre). Press Step or Play. First the chosen starting rule fills the table one allocation at a time — crossed-out lines are greyed, and for Vogel's method the penalties appear beside the rows and below the columns. Then the MODI phase computes $u_i$, $v_j$ and the reduced costs $d_{ij}$ (red when negative), draws the loop of the entering cell with its $+$ and $-$ corners, and shifts $\theta$ round it, until every $d_{ij}\ge0$. Compare how far each rule starts from the optimum; the second problem has a degenerate start and an alternative optimum.

phase—
basic cells—
cost—
status—
Interactive 2 — The Hungarian Method, Step by Step

Watch the cost matrix being reduced: row minima, column minima, then the fewest lines covering all zeros (found by Kőnig's construction). While fewer than $n$ lines suffice, the smallest uncovered entry $k$ is subtracted from the uncovered entries and added where two lines cross. The running total $L$ of everything subtracted is a lower bound for every assignment; when $n$ lines are needed, $n$ independent zeros (green) give an assignment whose cost equals $L$.

step—
lines needed / n—
lower bound L—
assignment cost—

Exercises

I
Formulation and the structure of bases.
  • 1 Supplies $40,60,50$; demands $30,45,35$. Balance the problem. How many basic cells does a BFS have, and what do allocations in the new cells mean?
  • 2 Supplies $25,35$; demands $20,30,25$; each unit of unmet demand at the three destinations costs $5,3,4$. Set up the balanced problem.
  • 3 Prove that a balanced TP with $a_i,b_j\gt0$ is feasible and has an optimal solution.
  • 4 Write the $4\times4$ constraint matrix of a $2\times2$ TP and show directly that its rank is $3$.
  • 5 In a $3\times3$ table, which of these sets of cells are bases? (a) $\{11,12,22,23,33\}$; (b) $\{11,12,21,22,33\}$; (c) $\{11,21,31,12,13\}$; (d) $\{11,22,33,12,21\}$ (cell $ij$ = row $i$, column $j$).
  • 6 Give a balanced TP with integer data that has an optimal solution which is not integral. Does this contradict Theorem 12.15?
  • 7 Two factories make $10$ and $20$ units, two markets take $15$ each, and the profits per unit are $(5,3)$ from factory 1 and $(4,6)$ from factory 2. Maximise the total profit.
1 Supply $150$, demand $110$: add a dummy destination with demand $40$ and costs $0$. A BFS has $3+4-1=6$ basic cells; an allocation in the dummy column is stock left at that source.
2 Supply $60$, demand $75$: add a dummy source with supply $15$ and costs $(5,3,4)$; an allocation from it to destination $j$ is unmet demand at $j$, priced at its penalty. A BFS has $3+3-1=5$ basic cells.
3 Theorem 12.12(1): $x_{ij}=a_ib_j/T$ is feasible; the region is bounded ($0\le x_{ij}\le\min(a_i,b_j)$) and closed, and a linear function attains its minimum on a nonempty compact set.
4 Columns $x_{11},x_{12},x_{21},x_{22}$; rows $R_1=(1,1,0,0)$, $R_2=(0,0,1,1)$, $D_1=(1,0,1,0)$, $D_2=(0,1,0,1)$. $R_1+R_2=D_1+D_2$, so the rank is $\le3$; $R_1,R_2,D_1$ are independent (look at the columns of $x_{12}$, $x_{21}$, $x_{11}$), so it is $3$.
5 (a) Yes: a "staircase", a path through all six lines without a loop. (b) No: $11,12,22,21$ is a loop. (c) Yes: row 1 joins columns 1, 2, 3 and column 1 joins rows 2, 3 — a spanning tree. (d) No: $11,12,22,21$ again.
6 $a=b=(1,1)$ with all four costs equal to $1$: every feasible solution costs $2$, including $x_{ij}=\tfrac12$ for all cells. No contradiction: Theorem 12.15 says that basic solutions are integral, so some optimal solution is integral, not all of them.
7 Balanced ($30=30$). With $x_{11}=t$: $x_{12}=10-t$, $x_{21}=15-t$, $x_{22}=5+t$, $0\le t\le10$; profit $5t+3(10-t)+4(15-t)+6(5+t)$ $=120+4t$, largest at $t=10$: $x_{11}=10$, $x_{21}=5$, $x_{22}=15$, profit $160$. (By MODI on costs $6-p_{ij}$ the same plan has all $d_{ij}\ge0$.)
II
Starting rules. Parts 1–4 use supplies $35,45,20$, demands $10,40,50$ and costs $(1,9,2)$, $(8,5,6)$, $(6,7,9)$ (rows $S_1,S_2,S_3$).
  • 1 Find the north-west corner solution and its cost.
  • 2 Find the least-cost solution and its cost.
  • 3 Find the VAM solution and its cost, showing the penalties.
  • 4 Which of the three solutions are degenerate?
  • 5 Apply the NW rule to supplies $20,30,25$ and demands $20,25,30$. Which cells are basic, and which allocation is $0$?
  • 6 For supplies $10,15$, demands $12,13$ and costs $(1,2)$, $(3,10)$, compare the least-cost and VAM solutions with the optimum.
  • 7 Prove that the NW rule always makes exactly $m+n-1$ allocations, even when supplies and demands are exhausted simultaneously.
  • 8 Interpret the VAM penalty of a row as a "regret". Why does it make sense to serve first the line with the largest regret?
1 $x_{11}=10$, $x_{12}=25$, $x_{22}=15$, $x_{23}=30$, $x_{33}=20$; cost $10+225+75+180+180=670$.
2 $(1,1)$ cost $1$: $x_{11}=10$; $(1,3)$ cost $2$: $x_{13}=25$ ($S_1$ out); $(2,2)$ cost $5$: $x_{22}=40$; $(2,3)$ cost $6$: $x_{23}=5$; $(3,3)$: $x_{33}=20$. Cost $10+50+200+30+180=470$.
3 Round 1: rows $1,1,1$, columns $5,2,4$: column 1, $x_{11}=10$. Round 2: rows $7,1,2$, columns $2,4$: row 1, $x_{13}=25$. Round 3: rows $1,2$, columns $2,3$: column 3, $x_{23}=25$. Then column 2 alone: $x_{22}=20$, $x_{32}=20$. Cost $10+50+150+100+140=450$.
4 None: each has $5=m+n-1$ positive cells.
5 $x_{11}=20$ exhausts row 1 and column 1 together; cross out row 1 and continue in column 1: $x_{21}=0$ (basic zero). Then $x_{22}=25$, $x_{23}=5$, $x_{33}=25$. Basic cells $11,21,22,23,33$ ($5=m+n-1$), four of them positive: degenerate.
6 Least cost: $x_{11}=10$, then $x_{21}=2$, $x_{22}=13$: cost $10+6+130=146$. VAM: penalties rows $1,7$, columns $2,8$; column 2's cheapest cell is $(1,2)$: $x_{12}=10$, then $x_{21}=12$, $x_{22}=3$: cost $20+36+30=86$. With $x_{11}=t$ the cost is $86+6t$, so VAM is optimal and least cost is far off: grabbing the cheapest cell forced the expensive $(2,2)$.
7 Each allocation crosses out exactly one line (only the row when both are exhausted), except the last, which crosses out the final row and column together; there are $m+n$ lines, so $m+n-1$ allocations (Theorem 12.16).
8 The penalty is the extra cost per unit that the line will suffer if its cheapest cell becomes unavailable and it must use its second-cheapest. Serving the line with the largest regret first protects against the most expensive mistakes; lines with a small penalty lose little whichever of their cheap cells they get.
III
The MODI method. Parts 1–5 continue Card II.
  • 1 For the VAM solution of II.3 compute $u_i$, $v_j$ and all $d_{ij}$. Is it optimal?
  • 2 Trace the loop of the entering cell, find $\theta$ and the new solution. How many corners does the loop have?
  • 3 Show that the new solution is the unique optimum.
  • 4 Verify that the optimal dual value $\sum a_iu_i+\sum b_jv_j$ equals the optimal cost.
  • 5 Starting instead from the NW solution, how many MODI iterations (most negative $d_{ij}$ entering) reach the optimum? List the costs.
  • 6 With the degenerate NW solution of II.5 and costs $(4,6,3)$, $(5,2,7)$, $(6,4,3)$, carry out MODI. What role does the basic zero play?
  • 7 In the optimum of III.3, by how much can the cost $c_{11}$ fall before the optimal plan changes?
1 Basic: $x_{11}=10$, $x_{13}=25$, $x_{22}=20$, $x_{23}=25$, $x_{32}=20$. $u_1=0$, $v_1=1$, $v_3=2$, $u_2=4$, $v_2=1$, $u_3=6$. $d_{12}=8$, $d_{21}=3$, $d_{31}=-1$, $d_{33}=1$: not optimal ($d_{31}\lt0$).
2 $(3,1)^+\to(3,2)^-\to(2,2)^+$ $\to(2,3)^-\to(1,3)^+\to(1,1)^-$: six corners (check: $6-7+5-6+2-1=-1=d_{31}$). "$-$" cells hold $20,25,10$: $\theta=10$, $(1,1)$ leaves. New: $x_{13}=35$, $x_{22}=30$, $x_{23}=15$, $x_{31}=10$, $x_{32}=10$; cost $450-10=440$.
3 $u_1=0$, $v_3=2$, $u_2=4$, $v_2=1$, $u_3=6$, $v_1=0$; $d_{11}=1$, $d_{12}=8$, $d_{21}=4$, $d_{33}=1$, all positive: unique optimum (Theorem 12.17(4)).
4 $35\cdot0+45\cdot4+20\cdot6$ $+10\cdot0+40\cdot1+50\cdot2$ $=180+120+40+100=440$. ✓
5 Three: $670\to470$ ($(1,3)$ enters, $\theta=25$) $\to450$ ($(3,1)$ enters, $\theta=10$) $\to440$ ($(3,2)$ enters, $\theta=10$).
6 NW cost $80+0+50+35+75=240$. $u_1=0$, $v_1=4$; through the zero cell $(2,1)$: $u_2=1$; then $v_2=1$, $v_3=6$, $u_3=-3$. $d_{12}=5$, $d_{13}=-3$, $d_{31}=5$, $d_{32}=6$. Loop $(1,3)^+(1,1)^-(2,1)^+(2,3)^-$, $\theta=\min(20,5)=5$: $x_{13}=5$, $x_{11}=15$, $x_{21}=5$, $(2,3)$ leaves; cost $240-15=225$. New $d$'s: $5,3,2,3$, all positive: optimal. The basic zero was needed to compute $u_2$, and it became a positive allocation — the zero is a genuine basic variable.
7 $(1,1)$ is nonbasic with $d_{11}=c_{11}-u_1-v_1=c_{11}-0-0$. The potentials depend only on basic costs, so the plan stays optimal while $c_{11}\ge0$: $c_{11}$ may fall by $1$ (to $0$, where an alternative optimum appears).
IV
Assignment problems.
  • 1 Solve the assignment problem with costs $\begin{pmatrix}9&6&13\\14&5&11\\3&7&2\end{pmatrix}$ by the Hungarian method.
  • 2 Solve the assignment problem with costs $\begin{pmatrix}8&8&10&9\\2&3&9&11\\4&3&12&10\\4&3&8&6\end{pmatrix}$ (two adjustments are needed).
  • 3 Maximise the total profit for the profit matrix $\begin{pmatrix}13&10&12\\8&10&15\\5&12&14\end{pmatrix}$.
  • 4 Three machines, four jobs, one job per machine, costs $(6,9,7,5)$, $(8,5,9,7)$, $(7,8,6,9)$. Which job is left undone?
  • 5 Solve IV.1 again when worker 3 may not do job 3.
  • 6 Show that the optimal cost of an assignment problem equals $\max\{\sum_ip_i+\sum_jq_j:$ $p_i+q_j\le c_{ij}\ \text{for all }i,j\}$.
  • 7 Show that the $3\times3$ matrix with all entries $\tfrac13$ is feasible for the LP relaxation and write it as a convex combination of permutation matrices.
  • 8 Four cities have distances $d_{12}=d_{34}=1$ and $d_{ij}=9$ for the other pairs ($d_{ij}=d_{ji}$, $d_{ii}=M$). Solve the assignment problem with these costs and explain why it does not give a travelling salesman's tour. What is the shortest tour?
1 Row minima $6,5,2$ and column minima $1,0,0$ give $\begin{pmatrix}2&0&7\\8&0&6\\0&5&0\end{pmatrix}$ ($L=14$); row 3 and column 2 cover the zeros. $k=2$: $\begin{pmatrix}0&0&5\\6&0&4\\0&7&0\end{pmatrix}$, $L=16$. Assignment $1\to1$, $2\to2$, $3\to3$: $9+5+2=16$.
2 Row minima $8,2,3,3$, column minima $0,0,2,1$: $L=19$; the zeros are covered by rows 1, 2 and column 2. $k=1$, $L=20$; now rows 1 and columns 1, 2 cover them. $k=1$, $L=21$, and four lines are needed: $1\to3$, $2\to1$, $3\to2$, $4\to4$, cost $10+2+3+6=21$.
3 Costs $15-p_{ij}$: $\begin{pmatrix}2&5&3\\7&5&0\\10&3&1\end{pmatrix}$; row minima $2,0,1$ and then column minima $0,2,0$ give $\begin{pmatrix}0&1&1\\7&3&0\\9&0&0\end{pmatrix}$, which has the independent zeros $(1,1),(2,3),(3,2)$. Profit $13+15+12=40$.
4 Add a dummy machine (row of zeros). Row reduction ($5,5,6,0$) gives zeros at $(1,4),(2,2),(3,3)$ and the dummy row, already four independent zeros: machine 1 → job 4, 2 → job 2, 3 → job 3, cost $5+5+6=16$; job 1 is left undone.
5 Put $c_{33}=M$. Row minima $6,5,3$, column minima $0,0,6$: zeros at $(1,2),(2,2),(2,3),(3,1)$, and $(1,2),(2,3),(3,1)$ are independent. Cost $6+11+3=20$.
6 Every feasible $(p,q)$ gives a lower bound (Theorem 12.20(2)), so max $\le$ optimal cost. The Hungarian method ends with reductions $(p,q)$ such that $C'=(c_{ij}-p_i-q_j)\ge0$ — a feasible pair — whose total $L$ equals the optimal cost (Theorem 12.22). So the maximum is attained and equals the optimal cost: LP duality for the assignment problem.
7 Row and column sums are $1$. With $P$ the cyclic permutation matrix ($1\to2\to3\to1$), $\tfrac13J=\tfrac13(I+P+P^2)$, since $I,P,P^2$ have their $1$'s in disjoint positions covering all nine cells.
8 The assignment $1\to2$, $2\to1$, $3\to4$, $4\to3$ costs $4$, which is the minimum (every row has smallest entry $1$). It is two separate cycles $1\leftrightarrow2$ and $3\leftrightarrow4$, not one tour. The three tours cost $1+9+1+9=20$ (twice) and $36$: the shortest tour, e.g. $1\to2\to3\to4\to1$, costs $20$.
🎯 GATE corner GATE MA · MCQGATE MA · MSQGATE MA · NAT

E1. GATE MA · MCQ Three sources with supplies $25,25,35$ and three destinations with demands $20,45,20$ have unit costs $(8,9,7)$, $(3,3,7)$, $(1,6,2)$ (rows = sources). The cost of the initial basic feasible solution given by the north-west corner rule is (A) $340$; (B) $350$; (C) $410$; (D) $430$.

NW $x_{11}=20$ (column 1 done, row 1 has $5$), $x_{12}=5$ (row 1 done), $x_{22}=25$ (row 2 done, column 2 needs $15$), $x_{32}=15$, $x_{33}=20$.
Cost $8\cdot20+9\cdot5+3\cdot25+6\cdot15+2\cdot20$ $=160+45+75+90+40=410$. ($340$ is the optimum, $350$ the VAM start — see E5.)
Answer (C).

E2. GATE MA · MCQ For a balanced transportation problem with $4$ sources and $5$ destinations, which statement about every basic feasible solution is correct? (A) It has exactly $9$ positive allocations. (B) It has exactly $8$ basic cells, at most $8$ of them positive. (C) It has at least $9$ positive allocations. (D) It has $20$ basic cells.

Rank The constraint matrix has rank $m+n-1=8$ (Theorem 12.13), so a basis has $8$ cells; a degenerate BFS has fewer than $8$ positive ones. (A) and (C) confuse $m+n-1$ with $m+n$; (D) counts all cells.
Answer (B).

E3. GATE MA · MSQ Sources with supplies $40,40,30$ and destinations with demands $30,35,45$ have unit costs $(1,9,9)$, $(9,3,2)$, $(5,7,4)$. Which of the following is/are true? (One or more options may be correct.) (A) The north-west corner solution is optimal. (B) The least-cost method gives a cheaper initial solution than the north-west corner rule. (C) Vogel's method gives an initial solution of cost $355$. (D) The problem has a unique optimal solution.

NW $x_{11}=30$, $x_{12}=10$, $x_{22}=25$, $x_{23}=15$, $x_{33}=30$: cost $30+90+75+30+120=345$. Potentials $u=(0,-6,-4)$, $v=(1,9,8)$; $d_{13}=1$, $d_{21}=14$, $d_{31}=8$, $d_{32}=2$, all positive.
(A) True, (D) True All $d_{ij}\ge0$: optimal; all nonbasic $d_{ij}\gt0$: unique (Theorem 12.17(4)).
(B) False Least cost: $x_{11}=30$, $x_{23}=40$, $x_{33}=5$, $x_{32}=25$, $x_{12}=10$: cost $30+80+20+175+90=395\gt345$.
(C) True VAM, round 1: row penalties $8,1,1$, column penalties $4,4,2$; row 1 wins and $x_{11}=30$. Round 2: rows $0,1,3$, columns $4,2$; column 2 wins and $x_{22}=35$. Only column 3 is left: $x_{13}=10$, $x_{23}=5$, $x_{33}=30$. Cost $30+105+90+10+120=355$.
Answer (A), (C) and (D).

E4. GATE MA · MSQ CSIR Part C For the $n\times n$ assignment problem (minimise cost), which of the following is/are true? (One or more options may be correct.) (A) Subtracting the minimum of each row from that row does not change the set of optimal assignments. (B) If, after reductions, the zeros of the nonnegative reduced matrix cannot be covered by fewer than $n$ lines, an optimal assignment can be chosen among those zeros. (C) The optimal cost equals the sum of the row minima of the original matrix. (D) To maximise total profit, the Hungarian method may be applied to the matrix $(P-p_{ij})$, where $P$ is the largest profit.

(A) True Theorem 12.20(1): every assignment's cost drops by the same amount.
(B) True Kőnig's theorem gives $n$ independent zeros, an assignment of reduced cost $0$ (Theorem 12.20(3)).
(C) False It is only a lower bound: in Example 5 the row minima add to $17$, the optimum is $19$.
(D) True Every assignment's cost under $P-p_{ij}$ is $nP-\text{profit}$, so minimising it maximises profit, and the entries are $\ge0$.
Answer (A), (B) and (D).

E5. GATE MA · NAT For the transportation problem of E1, the minimum total transportation cost is ______ (rounded off to the nearest integer).

Start Least cost: $x_{31}=20$ (cost $1$), $x_{33}=15$ (cost $2$, row 3 done), $x_{22}=25$ (cost $3$), $x_{13}=5$, $x_{12}=20$: cost $20+30+75+35+180=340$.
MODI $u_1=0$, $v_2=9$, $v_3=7$, $u_2=-6$, $u_3=-5$, $v_1=6$: $d_{11}=2$, $d_{21}=3$, $d_{23}=6$, $d_{32}=2$, all $\ge0$: optimal. (Starting from VAM, cost $350$, one MODI pivot on $(1,3)$ with $d_{13}=-2$, $\theta=5$, gives the same $340$.)
Answer $340$.

E6. GATE MA · NAT Four agents are assigned to four tasks, one each, to maximise the total profit; the profit matrix (rows = agents) is $\begin{pmatrix}33&35&28&24\\40&39&14&38\\21&13&11&14\\25&16&18&40\end{pmatrix}$. The maximum total profit is ______ (rounded off to the nearest integer).

Convert Costs $40-p_{ij}$: $\begin{pmatrix}7&5&12&16\\0&1&26&2\\19&27&29&26\\15&24&22&0\end{pmatrix}$. Row minima $5,0,19,0$, column minima $0,0,7,0$: $L=31$, and rows $1,4$ with column $1$ cover the zeros (3 lines).
Adjust $k=1$ ($L=32$): the reduced matrix $\begin{pmatrix}3&0&0&11\\0&0&18&1\\0&7&2&6\\16&24&15&0\end{pmatrix}$ has the independent zeros $(1,3),(2,2),(3,1),(4,4)$.
Answer Agent $1\to$ task $3$, $2\to2$, $3\to1$, $4\to4$: profit $28+39+21+40=128$ (cost $160-128=32=L$ ✓). Note that agent 2's best task (task 1, profit $40$) is not used. Answer: $128$.
🧑‍🏫 For the teacher

Suggested plan — 3 lectures × 60 min.

  1. Structure. Definition 12.8 and Theorem 12.12 (balancing as a bijection of feasible sets). Theorem 12.13 with the "$x_{i n}$ then $x_{1j}$" argument. Loops and the bipartite graph (Definition 12.9): draw $G(S)$ next to the table for Example 1 — students find the loop in (b) and the tree in (c) themselves. Theorems 12.14–12.15 and leaf peeling.
  2. Starting rules and MODI. Definition 12.10 and Theorem 12.16 (the "first loop cell" argument). Example 2 in three groups (one rule each), then compare costs. Project Interactive 1 with VAM, then NW. Theorem 12.17 via the dual, the telescoping loop sum, Theorem 12.18; Example 3 on the board; Example 4 with the degenerate pivot (Interactive 1, second problem). E1, E3 live.
  3. Assignment. Definition 12.11, Theorem 12.19, reductions (Theorem 12.20) and the lower bound $L$. Kőnig's theorem with a $4\times4$ picture of the alternating-path construction. Hungarian method, Theorem 12.22, Example 5 with Interactive 2 projected; Example 6 for the variants. Example 7 and E4 as a class discussion.

Discussion questions. (1) Why does the transportation problem have one redundant constraint, and which one would you drop? (2) Starting rules are judged by how close they come to the optimum; can you invent a $2\times2$ problem on which NW beats VAM? (3) The Hungarian method keeps a lower bound $L$ and an infeasible "assignment of zeros" until they meet — where else have you seen an algorithm that closes a primal–dual gap?

Misconceptions to watch for. Expecting $m+n$ basic cells; forgetting the basic zero of a degenerate start; accepting $m+n-1$ cells that contain a loop; dropping two cells at a degenerate pivot; believing VAM is always optimal or that least cost always beats NW; forgetting to balance, or giving dummy cells nonzero costs without reason; running the Hungarian method on profits without converting; equating the optimal cost with the sum of row minima; covering zeros with more lines than necessary.

Suggested homework. I(1, 2, 5, 7), II(1–3, 5, 6), III(1–3, 6), IV(1–4, 8); GATE corner E1, E5, E6.

🔬 Research–Teaching NexusResearch-tutored · optional, about 60–90 minutes

Research question. A ride-hailing platform must match $n$ waiting riders with $n$ free drivers. How much longer is the total pick-up distance if each rider, in order of request, simply gets the nearest free driver, instead of an optimal assignment — and does the gap grow with $n$?

Why it matters. Matching markets are everywhere: taxis and food delivery, organ (kidney-exchange) programmes, school and college admissions, the allocation of hospital beds. The assignment problem is the mathematical core of many of them, and the Hungarian method (or its modern relatives, such as auction algorithms) is what platforms run in "batched" matching every few seconds. Greedy rules are simpler and faster, so it is worth knowing what they cost.

What to do.

  1. Place $n$ riders and $n$ drivers uniformly at random in the unit square; let $c_{ij}$ be the distance from driver $j$ to rider $i$.
  2. Greedy: for $i=1,\dots,n$ give rider $i$ the nearest driver not yet used. Optimal: solve the assignment problem (your own Hungarian code for $n\le10$, then a library routine such as SciPy's linear_sum_assignment).
  3. For $n=10,50,200$ and $40$ random instances each, record the average ratio greedy/optimal and the average optimal distance per pair.
  4. Check one small instance by hand-running the Hungarian method, and compare the optimal value with the lower bound $L$ after the first two reductions.

Tools: Python with numpy and scipy, or a spreadsheet for $n=4$.

Hand in: a table of the ratios, a plot of the average optimal distance per pair against $n$ (try log–log axes), and a short memo to the platform recommending — or not — batched optimal matching.

Going further. Read about the stable-marriage algorithm of Gale and Shapley (used in school choice), about Bertsekas' auction algorithm for assignment, and about how the optimal matching distance for random points scales with $n$.

Instructor note: in our runs (40 instances each) the greedy rule was on average about $19\%$, $31\%$ and $43\%$ worse than optimal for $n=10,50,200$, and the optimal distance per pair fell from about $0.25$ to $0.14$ to $0.075$ — roughly like $n^{-1/2}$ (up to a slowly varying factor), whereas greedy's late riders are left with distant drivers. Exact figures vary with the random seed.

🧪 Self-check quiz

0/5 correct

Q1. A basic feasible solution of a balanced transportation problem with $5$ sources and $6$ destinations has how many basic cells?

Q2. A set of $m+n-1$ cells of a transportation table is a basis exactly when

Q3. In the MODI method, a nonbasic cell has $d_{pq}=c_{pq}-u_p-v_q=-4$. Then

Q4. Total supply is $120$ and total demand is $100$. To balance the problem we add

Q5. After row and column reductions of a $4\times4$ cost matrix, all zeros can be covered by $3$ lines. The next step of the Hungarian method is to