The idea, step by step
Why reductions are legitimate
Subtract the smallest entry in each row, then subtract the smallest entry in each column of the resulting matrix. Every complete assignment uses one entry from each row and column, so these operations subtract the same total from every feasible complete assignment. They preserve which assignment minimises the original cost.
A zero now represents a favourable relative choice, not a task that originally cost nothing. Look for n independent zeros in an n×n table: their positions must occupy different rows and columns. Once a complete zero assignment exists, return to the original table to calculate the real total.
| Person | X | Y | Z |
|---|---|---|---|
| Amy | 4 | 1 | 3 |
| Ben | 2 | 0 | 5 |
| Cal | 3 | 2 | 2 |
When zeros conflict
If a complete independent-zero assignment is impossible, cover every zero using the fewest horizontal and vertical lines. Find the smallest uncovered entry. Subtract it from every uncovered entry and add it at intersections of two covering lines; entries covered by one line stay unchanged. Then look for a complete independent-zero assignment again.
For the displayed table, row reduction gives [3,0,2], [2,0,5], [1,0,0]. Column reduction gives [2,0,2], [1,0,5], [0,0,0]. Cover column Y and Cal's row. The smallest uncovered entry is 1. The adjustment creates [1,0,1], [0,0,4], [0,1,0], which has the independent zeros Amy→Y, Ben→X, Cal→Z.
A common trap
Adding the selected zeros and reporting that the real assignment has zero cost.
Instead: Zeros belong to the transformed problem. Evaluate the selected pairing in the original table.
See the thinking
A reduction that is already enough
Apply row and column reductions to the technician costs and find an independent-zero assignment.
| Technician | Job 1 | Job 2 | Job 3 |
|---|---|---|---|
| Ali | 9 | 2 | 7 |
| Bea | 6 | 4 | 3 |
| Chen | 5 | 8 | 1 |
- Subtract row minima 2,3,1 to obtain [7,0,5], [3,1,0], [4,7,0].
- Subtract column minima 3,0,0 to obtain [4,0,5], [0,1,0], [1,7,0].
- Select Ali→2, Bea→1 and Chen→3; these zeros use distinct rows and columns.
- Read the original costs 2+6+1.
An adjustment is needed
Solve the Amy/Ben/Cal problem by the Hungarian algorithm.
| Person | X | Y | Z |
|---|---|---|---|
| Amy | 4 | 1 | 3 |
| Ben | 2 | 0 | 5 |
| Cal | 3 | 2 | 2 |
- After reductions use [2,0,2], [1,0,5], [0,0,0].
- Two lines—column Y and row Cal—cover all zeros. A complete assignment does not yet exist.
- Subtract 1 from uncovered entries and add 1 at the double-covered Cal/Y entry.
- Use the adjusted independent zeros Amy→Y, Ben→X, Cal→Z.
- Original time=1+2+2=5 hours.
Check your understanding
Why does subtracting 7 from every entry of just one row preserve the optimal complete square assignment?
Show answer
Every feasible complete assignment selects one entry from that row, so every total falls by exactly 7.
All feasible totals shift by the same amount; their ordering is unchanged.
Your turn
6 questions · 17 marks · Work at your own pace.
Read the questions online
- For the matrix rows [8,5,7], [6,9,4], [3,7,6], perform row reduction.3 marks
- For the reduced matrix [3,0,2], [2,5,0], [0,4,3], is a further column reduction needed? Find a complete zero assignment.2 marks
- Use the Amy/Ben/Cal table to show why two independent zeros are not enough for a complete allocation.3 marks
Times in hours for one person to perform one task. Person X Y Z Amy 4 1 3 Ben 2 0 5 Cal 3 2 2 - Zeros are covered by row 3 and column 2 in [2,0,2], [1,0,5], [0,0,0]. Carry out the adjustment.4 marks
- For the original Amy/Ben/Cal table, compare the algorithm's -hour assignment with Amy→X, Ben→Y, Cal→Z.2 marks
Times in hours for one person to perform one task. Person X Y Z Amy 4 1 3 Ben 2 0 5 Cal 3 2 2 - A student draws one line through every row, covering all zeros in any 3×3 reduced matrix, and immediately stops. Explain the error.3 marks
Read the worked solutions
Equivalent correct methods earn the corresponding marks. Include units where asked.
- For the matrix rows [8,5,7], [6,9,4], [3,7,6], perform row reduction.3 marks
The row minima are 5,4 and 3.
Subtract each minimum from every entry in its row.
[3,0,2], [2,5,0], [0,4,3]. - For the reduced matrix [3,0,2], [2,5,0], [0,4,3], is a further column reduction needed? Find a complete zero assignment.2 marks
The three zeros occupy distinct rows and columns.
No; each column minimum is 0. Choose row 1→column 2, row 2→column 3, row 3→column 1. - Use the Amy/Ben/Cal table to show why two independent zeros are not enough for a complete allocation.3 marks
Times in hours for one person to perform one task. Person X Y Z Amy 4 1 3 Ben 2 0 5 Cal 3 2 2 After reductions, Amy and Ben initially both rely on column Y for their zero.
Cal can use another column, but Amy and Ben still conflict.
There are three people/jobs, so three independent zeros are required. - Zeros are covered by row 3 and column 2 in [2,0,2], [1,0,5], [0,0,0]. Carry out the adjustment.4 marks
The smallest uncovered entry is 1.
Subtract 1 at (1,1),(1,3),(2,1),(2,3).
Add 1 at the double-covered entry (3,2); other covered entries stay unchanged.
[1,0,1], [0,0,4], [0,1,0]. - For the original Amy/Ben/Cal table, compare the algorithm's -hour assignment with Amy→X, Ben→Y, Cal→Z.2 marks
Times in hours for one person to perform one task. Person X Y Z Amy 4 1 3 Ben 2 0 5 Cal 3 2 2 The zero in Ben/Y was originally zero but cannot alone determine the optimum.
Use original entries for both totals.
The alternative is 4+0+2=6 hours, one hour slower. - A student draws one line through every row, covering all zeros in any 3×3 reduced matrix, and immediately stops. Explain the error.3 marks
Three row lines always cover everything, even when the zeros cannot form a feasible allocation.
An arbitrary cover does not establish optimality.
The algorithm needs the minimum number of covering lines or an explicit complete independent-zero assignment.
Curriculum reference & lesson scope
SACE Board of South Australia
Stage 2 General Mathematics: discrete models, project scheduling and assignment. Activity-on-arrow conventions are used for project networks; technology may verify calculations but does not replace interpreting the model.
Official curriculum source ↗