← Networks and Decision Mathematics › Assignment Problems and the Hungarian Algorithm
Assignment Problems and the Hungarian Algorithm
Key Terms
- An assignment problem: assign n workers to n tasks to minimise total cost
- A cost matrix: entry (i,j) = cost of assigning worker i to task j
- The Hungarian algorithm finds the optimal (minimum cost) assignment
- Step 1
- Subtract the minimum value from each row (row reduction)
- Step 2
- Subtract the minimum value from each column (column reduction)
- Step 3
- Cover all zeros with minimum number of lines
- If lines = n: optimal assignment found (use the zero positions)
- If lines < n: find minimum uncovered value θ; subtract from uncovered cells, add to cells covered twice; repeat from Step 3
Hungarian Algorithm Summary:
1. Row reduction: subtract row minimum from each row
2. Column reduction: subtract column minimum from each column
3. Cover zeros with minimum lines
4. If lines = n: assign using zeros
5. If lines < n: find θ = minimum uncovered value;
subtract θ from all uncovered entries;
add θ to all entries covered twice;
go to Step 3
1. Row reduction: subtract row minimum from each row
2. Column reduction: subtract column minimum from each column
3. Cover zeros with minimum lines
4. If lines = n: assign using zeros
5. If lines < n: find θ = minimum uncovered value;
subtract θ from all uncovered entries;
add θ to all entries covered twice;
go to Step 3
Worked Example: Assign workers 1, 2, 3 to tasks A, B, C. Cost matrix:
Row reduction (mins: 2,1,3): rows become [2,0,6], [2,5,0], [2,0,4].
Column reduction (mins: 2,0,0): columns become [0,0,6], [0,5,0], [0,0,4].
Zeros at (1,A),(1,B),(2,A),(2,C),(3,A),(3,B). Cover with 2 lines (rows 1 and 3 OR columns A and B).
Lines = 2 < 3. θ = min uncovered = 4 (entry 1C or 2A... need to find uncovered).
After adjustment: optimal solution found: 1→B (2), 2→C (1), 3→A (5). Total = 8.
| A | B | C | |
| 1 | 4 | 2 | 8 |
| 2 | 3 | 6 | 1 |
| 3 | 5 | 3 | 7 |
Column reduction (mins: 2,0,0): columns become [0,0,6], [0,5,0], [0,0,4].
Zeros at (1,A),(1,B),(2,A),(2,C),(3,A),(3,B). Cover with 2 lines (rows 1 and 3 OR columns A and B).
Lines = 2 < 3. θ = min uncovered = 4 (entry 1C or 2A... need to find uncovered).
After adjustment: optimal solution found: 1→B (2), 2→C (1), 3→A (5). Total = 8.
Hot Tip: The Hungarian algorithm finds the MINIMUM cost assignment. If you need the MAXIMUM (e.g. maximise profit), convert the problem: subtract every entry from the maximum value in the matrix, then apply the algorithm to find the minimum — this gives the maximum-profit assignment.
What Is an Assignment Problem?
An assignment problem involves assigning n workers (or machines, tasks, resources) to n jobs (or locations, activities) on a one-to-one basis to minimise total cost. Each worker must be assigned to exactly one job, and each job must be done by exactly one worker.
Applications include: scheduling, workforce allocation, routing, matching problems.
The Hungarian Algorithm
The Hungarian algorithm is an efficient method (polynomial time) for solving assignment problems:
- Row reduction: from each row, subtract its minimum value. Each row now has at least one zero.
- Column reduction: from each column, subtract its minimum value. Each column now has at least one zero.
- Cover zeros: find the minimum number of lines (rows or columns) needed to cover all zeros.
- Check: if the number of lines = n, an optimal assignment exists using the zeros. Find n independent zeros (one per row, one per column) and assign.
- Adjust (if lines < n): find the smallest uncovered value (θ). Subtract θ from every uncovered cell; add θ to every cell covered by two lines. (Cells covered by one line are unchanged.) Return to Step 3.
Reading the Assignment
Once n lines suffice to cover all zeros, find n zeros such that no two are in the same row or column (independent zeros). Each zero position (row i, column j) means worker i is assigned to task j. The minimum cost equals the sum of the original costs at those positions.
Strategy: After row and column reduction, if you can immediately find n independent zeros, you’re done — no adjustment step needed. Check the simplest case first before applying adjustments.
Mastery Practice
- Fluency Perform row reduction on the cost matrix:
X Y Z 1 5 3 9 2 4 8 2 3 7 1 6 - Fluency After row and column reduction, the resulting matrix has zeros at positions: (1,X), (2,Z), (3,Y). Is the assignment complete? If so, state the optimal assignment and find the minimum cost from the original matrix in Q1.
- Fluency Explain the purpose of the adjustment step (Step 5) in the Hungarian algorithm. What does it achieve?
- Fluency A 3×3 cost matrix has been reduced. It takes 2 lines to cover all zeros. What does this tell you, and what must you do next?
- Understanding Apply the full Hungarian algorithm to find the minimum cost assignment:
A B C P 9 2 7 Q 3 6 4 R 5 8 1 - Understanding Four employees (W, X, Y, Z) are to be assigned to four tasks (1, 2, 3, 4). The cost matrix is:
Apply the Hungarian algorithm to find the optimal assignment and minimum cost.Task 1 Task 2 Task 3 Task 4 W 8 4 6 3 X 5 7 2 8 Y 3 6 9 4 Z 7 2 5 6 - Understanding A manager wants to maximise profit (not minimise cost). The profit matrix is:
Convert to a minimisation problem and find the maximum profit assignment.J1 J2 J3 A 10 6 8 B 4 9 5 C 7 3 11 - Understanding After row reduction and column reduction of a 4×4 assignment matrix, you need 3 lines to cover all zeros. The minimum uncovered value is 2. Show what happens to the matrix after the adjustment step.
- Problem Solving Three volunteers (A, B, C) are to be assigned to three charity booths (X, Y, Z). The expected donations raised (in hundreds of dollars) by each volunteer at each booth are:
Find the assignment that maximises total donations raised. Show all working.X Y Z A 15 9 12 B 8 13 10 C 11 7 14 - Problem Solving A transport company must assign 4 drivers (1–4) to 4 routes (A–D) to minimise total travel time (hours):
Apply the Hungarian algorithm to find the optimal assignment and minimum total time.A B C D 1 10 14 8 12 2 6 9 11 7 3 13 7 5 9 4 8 11 13 6