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
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.
- 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.
- 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$).
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. ∎
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. ∎
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. ∎
| $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$ |
Initial Basic Feasible Solutions: North-West Corner, Least Cost, Vogel
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.
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. ∎
- Balance the table first (dummy row or column with zero or penalty costs).
- Write the penalty of each row to its right and of each column below it: second-smallest minus smallest remaining cost.
- 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$).
- Recompute only the penalties that changed (lines meeting the crossed-out line). Repeat until one row or column is left, then fill it.
- 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.
| round | row penalties $P_1,P_2,P_3$ | column penalties $S_1,\dots,S_4$ | largest | allocation |
|---|---|---|---|---|
| 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 |
| 4 | only $P_2$ remains | $x_{21}=25$, $x_{23}=5$, $x_{24}=25$ | ||
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).
- 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.
- 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$.
- 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.
- 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$. ∎
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. ∎
- 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.
- Put $u_1=0$ and solve $u_i+v_j=c_{ij}$ along the basic cells.
- 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).
- 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).
- 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}$.
The Assignment Problem and the Hungarian Method
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.
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.
- 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.
- If $C'\ge0$, then $L=\sum_ip_i+\sum_jq_j$ is a lower bound for the cost of every assignment under $C$.
- 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.) ∎
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. ∎
- 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$.
- 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.
- 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.
- 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.
- 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.
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$. ∎
- $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.
- 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.
- Not every set of $m+n-1$ cells is a basis. It must contain no loop (Example 1(b)).
- 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$).
- Balance first. The rules and the MODI test assume a balanced table. Dummy costs are $0$ unless the problem prices storage or shortage.
- $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.
- When several "$-$" cells reach $0$ at once, remove only one. Removing both leaves too few basic cells.
- 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).
- 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).
- 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.
- The optimal assignment cost is not the sum of row minima. That sum is only a lower bound ($17\lt19$ in Example 5).
- 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
Exercises
- 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 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 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 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?
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$.
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.
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.
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.
E5. GATE MA · NAT For the transportation problem of E1, the minimum total transportation cost is ______ (rounded off to the nearest integer).
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).
Suggested plan — 3 lectures × 60 min.
- 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.
- 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.
- 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 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.
- 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$.
- 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). - For $n=10,50,200$ and $40$ random instances each, record the average ratio greedy/optimal and the average optimal distance per pair.
- 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$.
🧪 Self-check quiz
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