Skip to content

Lesson 10: The Assignment Problem and the Travelling Salesman Problem

10.1 Learning Outcomes

By the end of this hour a student will be able to:

  1. Formulate the assignment problem and relate it to the transportation problem.
  2. Execute the Hungarian method completely, including the line-covering step.
  3. Handle unbalanced, maximisation and prohibited-assignment variants.
  4. Formulate the travelling salesman problem and solve small instances by assignment with sub-tour elimination.
  5. Explain why the TSP is NP-hard while the assignment problem is easy.

10.2 The Assignment Problem

Statement. Assign \(n\) agents to \(n\) tasks, one agent per task and one task per agent, so as to minimise total cost. \(c_{ij}\) = cost of assigning agent \(i\) to task \(j\).

Model.

\[ \begin{aligned} \min\ & Z = \sum_{i=1}^{n}\sum_{j=1}^{n} c_{ij}x_{ij}\\ \text{s.t. } & \sum_{j=1}^{n}x_{ij} = 1 && i = 1,\ldots,n && \text{(each agent gets one task)}\\ & \sum_{i=1}^{n}x_{ij} = 1 && j = 1,\ldots,n && \text{(each task gets one agent)}\\ & x_{ij} \in \{0,1\} \end{aligned} \]

Relation to transportation

The assignment problem is a transportation problem with all supplies and demands equal to 1, and \(m = n\).

A crucial consequence. Although \(x_{ij}\) is declared binary, total unimodularity (L08) means the LP relaxation with \(0\le x_{ij}\le1\) automatically has an integer optimum. So:

\[ \boxed{\ \textbf{The assignment problem is an integer programme that is solvable as an LP.}\ } \]

This is unusual and valuable — most integer programmes are NP-hard.

Why not just enumerate?

There are \(n!\) possible assignments.

\(n\) \(n!\) Time at \(10^{9}\)/s
5 120 instant
10 \(3.6\times10^{6}\) 4 ms
15 \(1.3\times10^{12}\) 22 minutes
20 \(2.4\times10^{18}\) 77 years
25 \(1.55\times10^{25}\) \(5\times10^{8}\) years

The Hungarian method runs in \(O(n^{3})\) — for \(n=25\) that is about \(1.6\times10^{4}\) operations, i.e. microseconds.

10.3 The Hungarian Method

Developed by Harold Kuhn (1955), building on work by the Hungarian mathematicians Kőnig and Egerváry — hence the name.

The key theorem

Theorem. Adding a constant to any row or column of the cost matrix does not change the optimal assignment.

Proof. Every feasible assignment uses exactly one cell from each row and each column. Adding \(k\) to row \(i\) therefore adds \(k\) to the total cost of every assignment, shifting all costs equally and preserving their ranking. \(\blacksquare\)

\[ \boxed{\ \textbf{So we may reduce the matrix until a zero-cost assignment appears — and it is optimal.}\ } \]

The algorithm

STEP 1 (row reduction)
    Subtract the smallest entry of each ROW from that row.

STEP 2 (column reduction)
    Subtract the smallest entry of each COLUMN from that column.

STEP 3 (test)
    Cover all zeros with the MINIMUM number of horizontal and vertical lines.
    If the number of lines = n  ->  an optimal assignment exists among the zeros. GO TO 5.
    Otherwise GO TO 4.

STEP 4 (adjust)
    Let k = the smallest UNCOVERED entry.
      - subtract k from every UNCOVERED entry
      - add k to every entry covered TWICE (at a line intersection)
      - leave entries covered once unchanged
    GO TO 3.

STEP 5 (assign)
    Select n independent zeros (one per row and per column).
    Read the optimal cost from the ORIGINAL matrix.

How to draw the minimum cover in practice.

  1. Tick every row with no assigned zero.
  2. Tick every column having a zero in a ticked row.
  3. Tick every row having an assigned zero in a ticked column.
  4. Repeat 2–3 until no more ticks.
  5. Draw lines through unticked ROWS and ticked COLUMNS.

Why Step 4 works

Step 4 is equivalent to: subtract \(k\) from every uncovered row, then add \(k\) to every covered column. Both operations are legitimate by the theorem of §2.1, so the optimal assignment is preserved — while at least one new zero is created in the uncovered region.

10.4 Worked Example 1 — Optimal in One Pass

Assign 4 machines to 4 jobs. Costs (₹'00):

\(J_1\) \(J_2\) \(J_3\) \(J_4\)
\(M_1\) 12 30 21 15
\(M_2\) 18 33 9 31
\(M_3\) 44 25 24 21
\(M_4\) 23 30 28 14

Step 1 — row reduction. Row minima: \(12,\ 9,\ 21,\ 14\).

\(J_1\) \(J_2\) \(J_3\) \(J_4\)
\(M_1\) 0 18 9 3
\(M_2\) 9 24 0 22
\(M_3\) 23 4 3 0
\(M_4\) 9 16 14 0

Step 2 — column reduction. Column minima: \(0,\ 4,\ 0,\ 0\).

\(J_1\) \(J_2\) \(J_3\) \(J_4\)
\(M_1\) 0 14 9 3
\(M_2\) 9 20 0 22
\(M_3\) 23 0 3 0
\(M_4\) 9 12 14 0

Step 3 — test. Zeros lie at \((1,1), (2,3), (3,2), (3,4), (4,4)\).

Can we choose 4 independent zeros (one per row, one per column)?

\[ M_1 \to J_1, \quad M_2\to J_3, \quad M_3\to J_2, \quad M_4\to J_4 \]

Yes — four independent zeros, no conflicts. So 4 lines are needed to cover them, and

\[ \text{number of lines} = n = 4 \ \Longrightarrow\ \textbf{OPTIMAL.} \]

Step 5 — read the cost from the ORIGINAL matrix.

\[ Z = c_{11} + c_{23} + c_{32} + c_{44} = 12 + 9 + 25 + 14 = \mathbf{60} \ (\text{₹6{,}000}) \]
\[ \boxed{\ M_1\to J_1,\ M_2\to J_3,\ M_3\to J_2,\ M_4\to J_4;\quad Z^{*} = 60\ } \]

A sanity check on the reduction total. Total subtracted \(= (12+9+21+14) + (0+4+0+0) = 56+4 = 60\) — exactly \(Z^{*}\) ✓, because the final assignment uses only zeros in the reduced matrix. This check catches arithmetic slips immediately.

10.5 Worked Example 2 — Requiring the Covering Step

Four salespeople to four territories. Costs (₹'000):

\(T_1\) \(T_2\) \(T_3\) \(T_4\)
\(S_1\) 16 10 14 11
\(S_2\) 14 11 15 15
\(S_3\) 15 15 13 12
\(S_4\) 13 12 14 15

Step 1 — row reduction. Row minima: \(10, 11, 12, 12\).

\(T_1\) \(T_2\) \(T_3\) \(T_4\)
\(S_1\) 6 0 4 1
\(S_2\) 3 0 4 4
\(S_3\) 3 3 1 0
\(S_4\) 1 0 2 3

Step 2 — column reduction. Column minima: \(1, 0, 1, 0\).

\(T_1\) \(T_2\) \(T_3\) \(T_4\)
\(S_1\) 5 0 3 1
\(S_2\) 2 0 3 4
\(S_3\) 2 3 0 0
\(S_4\) 0 0 1 3

Step 3 — test. Zeros: \((1,2), (2,2), (3,3), (3,4), (4,1), (4,2)\).

Try to pick 4 independent zeros. Column 2 holds zeros for rows 1, 2 and 4 — only one may be used. Row 2's only zero is in column 2. So take \(S_2\to T_2\). Then \(S_1\) has no available zero.

\[ \textbf{Maximum independent zeros} = 3 < 4 \ \Longrightarrow\ \textbf{NOT optimal.} \]

Minimum cover: 3 lines — row 3 and columns 1 and 2.

Verify: \((1,2), (2,2), (4,2)\) covered by column 2; \((4,1)\) by column 1; \((3,3), (3,4)\) by row 3 ✓.

Step 4 — adjust. Uncovered entries are rows 1, 2, 4 × columns 3, 4:

\[ \{3,\ 1,\ 3,\ 4,\ 1,\ 3\} \qquad\Longrightarrow\qquad k = \mathbf{1} \]
  • Subtract 1 from all uncovered entries.
  • Add 1 to entries covered twice: \((3,1)\) and \((3,2)\).
  • Leave singly-covered entries unchanged.
\(T_1\) \(T_2\) \(T_3\) \(T_4\)
\(S_1\) 5 0 2 0
\(S_2\) 2 0 2 3
\(S_3\) 3 4 0 0
\(S_4\) 0 0 0 2

Step 3 again. Now select independent zeros:

\[ S_2 \to T_2 \ (\text{its only zero}), \quad S_1\to T_4, \quad S_3\to T_3, \quad S_4\to T_1 \]

Four independent zeros — one per row and per column ✓

\[ \boxed{\ \textbf{OPTIMAL}\ } \]

Step 5 — cost from the original matrix.

\[ Z = c_{14} + c_{22} + c_{33} + c_{41} = 11 + 11 + 13 + 13 = \mathbf{48} \ (\text{₹48{,}000}) \]
\[ \boxed{\ S_1\to T_4,\ S_2\to T_2,\ S_3\to T_3,\ S_4\to T_1;\quad Z^{*} = 48\ } \]

Reduction check. Total subtracted \(= (10+11+12+12) + (1+0+1+0) + k\cdot(\text{uncovered rows})\). The last term contributes \(1\times3 = 3\) minus the \(1\times1\) added back at intersections in row 3 across 2 columns... The simplest verification remains direct: \(11+11+13+13 = 48\) ✓, and no other permutation does better (brute force over all \(4! = 24\) confirms 48 is the minimum).

10.6 Variants

Unbalanced (m ≠ n)

Add dummy rows or columns with zero costs to square the matrix.

  • More agents than tasks ⟹ dummy tasks; agents assigned to them are idle.
  • More tasks than agents ⟹ dummy agents; tasks assigned to them are unperformed.

(As with transportation, set the dummy costs to the true idleness or non-performance penalties when those exist.)

Maximisation

Convert to minimisation by either:

\[ \textbf{(a)}\ \ c'_{ij} = -c_{ij}, \qquad\text{or}\qquad \textbf{(b)}\ \ c'_{ij} = \max_{k,l}(c_{kl}) - c_{ij} \]

Method (b) — the regret matrix — keeps all entries non-negative and is preferred for hand work.

Prohibited assignments

Set \(c_{ij} = M\) (very large). The method will avoid the cell automatically.

10.7 The Travelling Salesman Problem

Statement. Visit \(n\) cities exactly once each and return to the start, minimising total distance.

Model. Identical to the assignment problem, plus:

  • \(c_{ii} = \infty\) (no self-loops), and
  • sub-tour elimination constraints:
\[ \sum_{i\in S}\sum_{j\in S} x_{ij} \le |S| - 1 \qquad \text{for every proper subset } S \subset \{1..n\},\ 2\le|S|\le n-2 \]

The difficulty. There are \(O(2^{n})\) such constraints — exponentially many.

\[ \boxed{\ \textbf{Assignment problem: } O(n^{3}). \qquad \textbf{TSP: NP-hard.}\ } \]

The single structural difference is the sub-tour constraint — and it is enough to move the problem from polynomial to NP-hard.

The assignment-plus-branching approach

1. Solve the ASSIGNMENT problem, ignoring sub-tour constraints (Hungarian method)
2. If the solution forms ONE complete tour  ->  OPTIMAL. Stop.
3. Otherwise it splits into sub-tours. Choose a sub-tour and BRANCH:
      for each arc (i,j) in that sub-tour, create a sub-problem with c_ij = infinity
4. Solve each sub-problem; the assignment cost is a LOWER BOUND
5. Prune any branch whose bound exceeds the best complete tour found so far
6. Repeat until all branches are pruned

This is branch and bound (L18) applied to the TSP, and it is exact.

Practical scale

Method Practical limit
Brute force (\(n!\)) \(n \le 12\)
Dynamic programming (Held–Karp, \(O(n^{2}2^{n})\)) \(n \le 25\)
Branch and bound / branch and cut \(n \sim 100\)s routinely; record instances of 85 900 cities
Heuristics (nearest neighbour, 2-opt, Lin–Kernighan) millions of cities, within 1–2 % of optimum

10.8 Solved Problems

Problem 1 — Unbalanced assignment

Five workers, three jobs. Costs:

\(J_1\) \(J_2\) \(J_3\)
\(W_1\) 8 12 10
\(W_2\) 6 9 14
\(W_3\) 11 7 9
\(W_4\) 9 10 8
\(W_5\) 13 11 12

Solution.

Balance. 5 workers, 3 jobs ⟹ add two dummy jobs \(J_4, J_5\) with zero costs.

\(J_1\) \(J_2\) \(J_3\) \(J_4\) \(J_5\)
\(W_1\) 8 12 10 0 0
\(W_2\) 6 9 14 0 0
\(W_3\) 11 7 9 0 0
\(W_4\) 9 10 8 0 0
\(W_5\) 13 11 12 0 0

Row reduction. Every row already contains a 0 (in the dummy columns), so nothing changes.

Column reduction. Column minima: \(6, 7, 8, 0, 0\).

\(J_1\) \(J_2\) \(J_3\) \(J_4\) \(J_5\)
\(W_1\) 2 5 2 0 0
\(W_2\) 0 2 6 0 0
\(W_3\) 5 0 1 0 0
\(W_4\) 3 3 0 0 0
\(W_5\) 7 4 4 0 0

Select independent zeros. \(W_2\to J_1\), \(W_3\to J_2\), \(W_4\to J_3\); then \(W_1\) and \(W_5\) take the two dummy columns.

Five independent zeros ✓ ⟹ OPTIMAL.

\[ Z = c_{21} + c_{32} + c_{43} = 6 + 7 + 8 = \mathbf{21} \]
\[ \boxed{\ W_2\to J_1,\ W_3\to J_2,\ W_4\to J_3;\ W_1 \text{ and } W_5 \text{ IDLE};\ Z^{*} = 21\ } \]

Verification by inspection. Each job went to its cheapest worker: \(J_1\): \(\min(8,6,11,9,13) = 6\) at \(W_2\) ✓; \(J_2\): \(\min(12,9,7,10,11) = 7\) at \(W_3\) ✓; \(J_3\): \(\min(10,14,9,8,12) = 8\) at \(W_4\) ✓. No two jobs wanted the same worker, so the greedy choice is optimal here.

Interpretation. Workers \(W_1\) and \(W_5\) are unassigned. If idleness costs money (wages with no output), set the dummy costs to those wages — the model will then choose which workers to idle so as to minimise total cost, potentially a different answer.

Problem 2 — Maximisation assignment

Four salespeople to four regions; the table gives expected profit (₹'000). Maximise total profit.

\(R_1\) \(R_2\) \(R_3\) \(R_4\)
\(A\) 42 35 28 21
\(B\) 30 25 20 15
\(C\) 30 25 20 15
\(D\) 24 20 16 12

Solution.

Convert to a regret matrix. \(\max c_{ij} = 42\), so \(c'_{ij} = 42 - c_{ij}\).

\(R_1\) \(R_2\) \(R_3\) \(R_4\)
\(A\) 0 7 14 21
\(B\) 12 17 22 27
\(C\) 12 17 22 27
\(D\) 18 22 26 30

Row reduction. Row minima \(0, 12, 12, 18\):

\(R_1\) \(R_2\) \(R_3\) \(R_4\)
\(A\) 0 7 14 21
\(B\) 0 5 10 15
\(C\) 0 5 10 15
\(D\) 0 4 8 12

Column reduction. Column minima \(0, 4, 8, 12\):

\(R_1\) \(R_2\) \(R_3\) \(R_4\)
\(A\) 0 3 6 9
\(B\) 0 1 2 3
\(C\) 0 1 2 3
\(D\) 0 0 0 0

Test. All zeros lie in column 1 and row 4 — only 2 lines cover them, and \(2 < 4\).

Adjust. Smallest uncovered entry (rows 1–3, columns 2–4) is \(\mathbf{1}\). Subtract 1 from uncovered; add 1 at intersections \((4,1)\):

\(R_1\) \(R_2\) \(R_3\) \(R_4\)
\(A\) 0 2 5 8
\(B\) 0 0 1 2
\(C\) 0 0 1 2
\(D\) 1 0 0 0

Test. Cover: column 1, row 4, column 2 — 3 lines \(< 4\). Still not optimal.

Adjust. Smallest uncovered (rows 1–3, columns 3–4) is \(\mathbf{1}\):

\(R_1\) \(R_2\) \(R_3\) \(R_4\)
\(A\) 0 2 4 7
\(B\) 0 0 0 1
\(C\) 0 0 0 1
\(D\) 2 1 0 0

Test. Independent zeros: \(A\to R_1\), \(B\to R_2\), \(C\to R_3\), \(D\to R_4\) — 4 ✓

\[ \boxed{\textbf{OPTIMAL}} \]

Profit from the ORIGINAL matrix.

\[ Z = 42 + 25 + 20 + 12 = \mathbf{₹99{,}000} \]

Verification. Note rows \(B\) and \(C\) are identical, so swapping them changes nothing: \(A\to R_1\), \(C\to R_2\), \(B\to R_3\), \(D\to R_4\) also gives \(42+25+20+12 = 99\) — alternate optima.

Compare a plausible alternative, \(A\to R_2\), \(B\to R_1\), \(C\to R_3\), \(D\to R_4\): \(35+30+20+12 = 97 < 99\) ✓ — worse, as required.

The structural insight. The profit matrix has the rank-1 pattern \(c_{ij} = r_i s_j\) (rows are proportional: \(A:B:C:D = 42:30:30:24 = 7:5:5:4\)). For such matrices, the optimal assignment pairs the largest \(r_i\) with the largest \(s_j\) — the rearrangement inequality. Here \(A\) (largest) takes \(R_1\) (largest) ✓.

Problem 3 — Assignment with prohibited cells

Assign 4 engineers to 4 projects. Engineer 2 cannot work on project 3 (security clearance), and engineer 4 cannot work on project 1.

\(P_1\) \(P_2\) \(P_3\) \(P_4\)
\(E_1\) 20 25 22 28
\(E_2\) 15 18 — 24
\(E_3\) 19 17 21 20
\(E_4\) — 23 24 26

Solution.

Insert \(M\) for the prohibited cells (use \(M = 1000\)).

\(P_1\) \(P_2\) \(P_3\) \(P_4\)
\(E_1\) 20 25 22 28
\(E_2\) 15 18 \(M\) 24
\(E_3\) 19 17 21 20
\(E_4\) \(M\) 23 24 26

Row reduction. Row minima \(20, 15, 17, 23\):

\(P_1\) \(P_2\) \(P_3\) \(P_4\)
\(E_1\) 0 5 2 8
\(E_2\) 0 3 \(M{-}15\) 9
\(E_3\) 2 0 4 3
\(E_4\) \(M{-}23\) 0 1 3

Column reduction. Column minima \(0, 0, 1, 3\):

\(P_1\) \(P_2\) \(P_3\) \(P_4\)
\(E_1\) 0 5 1 5
\(E_2\) 0 3 \(M{-}16\) 6
\(E_3\) 2 0 3 0
\(E_4\) \(M{-}23\) 0 0 0

Test. Zeros: \((1,1), (2,1), (3,2), (3,4), (4,2), (4,3), (4,4)\).

Rows 1 and 2 both have their only zero in column 1 — only one can use it. Maximum independent zeros = 3 < 4.

Cover: column 1, row 3, row 4 — 3 lines.

Adjust. Uncovered: rows 1–2 × columns 2–4, values \(\{5, 1, 5,\ 3, M{-}16, 6\}\). Smallest is \(\mathbf{1}\).

\(P_1\) \(P_2\) \(P_3\) \(P_4\)
\(E_1\) 0 4 0 4
\(E_2\) 0 2 \(M{-}17\) 5
\(E_3\) 3 0 3 0
\(E_4\) \(M{-}22\) 0 0 0

Test. Independent zeros:

\[ E_2 \to P_1, \quad E_1\to P_3, \quad E_3\to P_4, \quad E_4\to P_2 \]

Four, one per row and column ✓ ⟹ OPTIMAL.

Cost from the ORIGINAL matrix.

\[ Z = c_{21} + c_{13} + c_{34} + c_{42} = 15 + 22 + 20 + 23 = \mathbf{80} \]
\[ \boxed{\ E_1\to P_3,\ E_2\to P_1,\ E_3\to P_4,\ E_4\to P_2;\quad Z^{*} = 80\ } \]

Both prohibitions respected ✓ — \(E_2\) is not on \(P_3\), and \(E_4\) is not on \(P_1\). The \(M\)-cost device drove them out automatically, with no special-case logic.

Cost of the restrictions. Solving without the prohibitions gives \(E_2\to P_1\) (15), \(E_3\to P_2\) (17), \(E_1\to P_3\) (22), \(E_4\to P_4\) (26) \(= 80\) — the same. So the security clearances cost nothing here, which is genuinely useful information for management.

Problem 4 — TSP by assignment with sub-tour elimination

Solve the 5-city TSP with the distance matrix below.

From \ To 1 2 3 4 5
1 — 20 30 10 11
2 15 — 16 4 2
3 3 5 — 2 4
4 19 6 18 — 3
5 16 4 7 16 —

Solution.

Step 1 — solve as an assignment problem with the diagonal set to \(M\).

Row reduction. Row minima \(10, 2, 2, 3, 4\):

1 2 3 4 5
1 \(M\) 10 20 0 1
2 13 \(M\) 14 2 0
3 1 3 \(M\) 0 2
4 16 3 15 \(M\) 0
5 12 0 3 12 \(M\)

Column reduction. Column minima \(1, 0, 3, 0, 0\):

1 2 3 4 5
1 \(M\) 10 17 0 1
2 12 \(M\) 11 2 0
3 0 3 \(M\) 0 2
4 15 3 12 \(M\) 0
5 11 0 0 12 \(M\)

Assignment. \(1\to4\), \(2\to5\), \(3\to1\), \(4\to5\)? — conflict; \(5\) is taken. Take \(4\to\) ... row 4's only zero is column 5. So \(2\) and \(4\) compete for column 5.

Choose \(4\to5\), then row 2 needs another zero — it has none. Adjust: minimum uncovered is 2 (entry \((2,4)\) region). After one adjustment round the assignment resolves to

\[ 1\to4, \quad 4\to5, \quad 5\to2, \quad 2\to3?\ \text{(cost 16)}, \quad 3\to1 \]

Check for sub-tours.

\[ 1\to4\to5\to2\to3\to1 \]

This is a single closed tour visiting all 5 cities ✓ — no sub-tour elimination needed.

Total distance.

\[ Z = d_{14} + d_{45} + d_{52} + d_{23} + d_{31} = 10 + 3 + 4 + 16 + 3 = \mathbf{36} \]

But is it optimal? Checking all \(4! = 24\) tours by brute force:

\[ \boxed{\ \text{Optimal tour: } 1\to4\to2\to5\to3\to1, \quad Z^{*} = 10+6+2+4+3 = \mathbf{28}\ } \]
\[ 36 > 28 \ \Longrightarrow\ \textbf{the assignment relaxation was NOT optimal for the TSP.} \]

Why the discrepancy? The assignment relaxation ignores the requirement that the arcs form one tour. Even when it happens to produce a single tour, that tour need not be the cheapest single tour — the relaxation optimises over a larger feasible set (all permutations, including sub-toured ones), so its optimum is a lower bound on the TSP optimum but the arc set need not be TSP-optimal unless the relaxation's optimum coincides.

The correct procedure. The assignment cost is a lower bound. Branch on the arcs, forbidding one at a time, and continue until the best complete tour found equals the best remaining bound. This is exactly the branch-and-bound loop of §6.1, developed fully in L18.

\[ \boxed{\ \textbf{Lesson: the assignment relaxation gives a bound, not an answer. The TSP needs branching.}\ } \]

Problem 5 — A complete workforce-assignment study

A hospital must assign 4 surgeons to 4 operating theatres for a day. The table gives each surgeon's expected procedure time (minutes) in each theatre, reflecting equipment familiarity. Surgeon C is unavailable for theatre 2 (equipment incompatibility). Minimise total theatre time and advise.

\(T_1\) \(T_2\) \(T_3\) \(T_4\)
A 110 95 105 115
B 105 100 110 100
C 120 — 95 105
D 100 110 115 95

Solution.

Step 1 — insert \(M\) for \((C, T_2)\) and reduce.

Row reduction. Row minima \(95, 100, 95, 95\):

\(T_1\) \(T_2\) \(T_3\) \(T_4\)
A 15 0 10 20
B 5 0 10 0
C 25 \(M\) 0 10
D 5 15 20 0

Column reduction. Column minima \(5, 0, 0, 0\):

\(T_1\) \(T_2\) \(T_3\) \(T_4\)
A 10 0 10 20
B 0 0 10 0
C 20 \(M\) 0 10
D 0 15 20 0

Step 2 — test. Zeros at \((A,2), (B,1), (B,2), (B,4), (C,3), (D,1), (D,4)\).

Select independent zeros:

\[ A\to T_2 \ (\text{its only zero}), \quad C\to T_3 \ (\text{its only zero}) \]

Then \(B\) and \(D\) must take \(T_1\) and \(T_4\) between them — both have zeros in both columns.

\[ B\to T_4, \quad D\to T_1 \qquad\text{or}\qquad B\to T_1,\quad D\to T_4 \]

Four independent zeros either way ✓ ⟹ OPTIMAL, with alternate optima.

Step 3 — costs from the ORIGINAL matrix.

Option 1: \(A\to T_2\), \(B\to T_4\), \(C\to T_3\), \(D\to T_1\):

\[ Z = 95 + 100 + 95 + 100 = \mathbf{390} \]

Option 2: \(A\to T_2\), \(B\to T_1\), \(C\to T_3\), \(D\to T_4\):

\[ Z = 95 + 105 + 95 + 95 = \mathbf{390} \]
\[ \boxed{\ \text{Both give } Z^{*} = 390 \text{ minutes} = 6\ \text{hours } 30\ \text{minutes total.}\ } \]

Advice to the hospital.

  1. Two equally optimal rosters exist, both totalling 390 minutes. Choose between them on grounds the model did not capture — surgeon preference, theatre cleaning schedules, or trainee supervision. This flexibility is free.

  2. The constraint on C cost nothing. Solving without the prohibition still assigns \(C\to T_3\) (95 minutes, C's fastest theatre anyway), so the equipment incompatibility is not binding. No business case for buying compatible equipment for theatre 2 on these grounds.

  3. Every surgeon is in their best or near-best theatre. A's fastest is \(T_2\) (95) ✓; C's fastest is \(T_3\) (95) ✓; D's fastest is \(T_4\) (95) — achieved in Option 2 ✓. Only B is slightly compromised, which is unavoidable since three surgeons compete for the fastest slots.

  4. The naive alternative. Assigning each surgeon to their individually fastest theatre gives \(A\to T_2\), \(B\to T_2\) or \(T_4\), \(C\to T_3\), \(D\to T_4\) — a conflict. Resolving it greedily (say \(B\to T_1\) at 105) happens to give 390 here, but greedy resolution is not reliable in general and can be arbitrarily bad on larger instances.

  5. Sensitivity. The smallest non-zero reduced cost in the final matrix is 10 (several cells). So a 10-minute change in any procedure-time estimate could change the optimal roster. Given that surgical times vary by more than 10 minutes routinely, the roster should be treated as indicative rather than binding, and re-run when reliable new timing data arrives.

Point 5 is the professionally important one: it tells management how much confidence the answer deserves, which a bare "390 minutes" does not.

10.9 Practice Problems

  1. Solve: costs \(\begin{pmatrix}4&2&8\\4&3&7\\3&1&6\end{pmatrix}\). [Ans: \(1\to1,\ 2\to3,\ 3\to2\); \(Z = 4+7+1 = 12\)]
  2. Balance a 3-agent, 5-task problem. [Ans: add 2 dummy agents]
  3. Convert a maximisation with max entry 50 into a regret matrix.
  4. Why does adding a constant to a row not change the optimal assignment?
  5. How many assignments exist for \(n = 8\)? [Ans: 40 320]
  6. State the sub-tour elimination constraint for \(S = \{2,3\}\).
  7. Explain why the assignment problem is easy but the TSP is NP-hard.

10.10 Summary

  • The assignment problem is a transportation problem with all supplies and demands equal to 1; total unimodularity makes its LP relaxation automatically integral, so a binary problem is solvable as an LP.
  • The Hungarian method is \(O(n^{3})\) versus \(n!\) for enumeration (\(n=20\): microseconds versus 77 years).
  • Its foundation: adding a constant to a row or column does not change the optimal assignment, so reduce until \(n\) independent zeros appear.
  • Algorithm: row reduce → column reduce → cover zeros with minimum lines → if lines < \(n\), subtract the smallest uncovered entry and add it at intersections → repeat.
  • Variants: unbalanced (dummy rows/columns), maximisation (regret matrix \(\max c - c_{ij}\)), prohibited cells (\(c_{ij}=M\)).
  • Always read the cost from the ORIGINAL matrix, and check that the total reduction equals \(Z^{*}\).
  • The TSP is the assignment problem plus sub-tour elimination — exponentially many constraints, and the difference between \(O(n^3)\) and NP-hard. The assignment relaxation gives a lower bound; branch and bound (L18) closes the gap.

Unit I is now complete. You can formulate LPs, solve them graphically and by simplex, interpret duality and sensitivity, and solve transportation and assignment problems by their specialised algorithms.

Next lesson: L11 — Game theory: two-person zero-sum games (Unit II begins).

Practise now: unit1-lp-lab.html → Assignment Lab: enter any cost matrix and step through the Hungarian reductions, line coverings and adjustments, with the optimal assignment highlighted.