Understand the idea.
Why reductions are legitimate
The Hungarian algorithm first subtracts each row minimum, then each column minimum. A complete assignment uses one entry from every row and column, so every feasible total falls by the same amount. The allocation with minimum cost is therefore preserved.
Seek a complete set of independent zeros: one in each row and column. They indicate favourable relative positions after reduction, not free original tasks. Calculate the actual cost or time from the original entries at the chosen positions.
| Person | X | Y | Z |
|---|---|---|---|
| Amy | 4 | 1 | 3 |
| Ben | 2 | 0 | 5 |
| Cal | 3 | 2 | 2 |
When zeros conflict
If independent zeros cannot fill the table, cover all zeros using the fewest row and column lines. Subtract the smallest uncovered entry from uncovered positions and add it at double-covered intersections. Leave single-covered entries unchanged, then search again.
For Amy, Ben and Cal, reductions give rows , , . Column Y and Cal's row cover every zero. Adjusting by the uncovered minimum 1 creates zeros that allow Amy→Y, Ben→X and Cal→Z.
See the method in action.
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 |
Worked solution
- 1
Subtract each row minimum.
The row minima are 2, 3 and 1; each complete assignment loses their sum, six.
- 2
Subtract the new column minima.
Only column 1 has a positive minimum, three; every complete assignment loses another three.
- 3
Select independent zeros.
These three zeros use each row and column once. Since all reduced entries are nonnegative, their zero total attains the reduced lower bound.
- 4
Return to the original costs.
The chosen original entries give the real minimum cost, consistent with the nine subtracted during reduction.
Minimum cost $9.
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 |
Worked solution
- 1
Reduce rows and then columns.
Subtract row minima 1, 0 and 2, followed by column minima 1, 0 and 0.
- 2
Cover the conflicting zeros.
Amy and Ben both have only Y as a zero, so three independent zeros are impossible. Two lines cover all zeros, and the smallest uncovered entry is one.
- 3
Adjust uncovered and double-covered entries.
Subtract one from Amy/X, Amy/Z, Ben/X and Ben/Z; add one at Cal/Y. Entries covered exactly once retain their values.
- 4
Choose one zero from each row and column.
The adjusted matrix now has a feasible zero assignment, which certifies the optimum of the original assignment problem.
- 5
Add the original times.
Use Amy/Y, Ben/X and Cal/Z from the original table to obtain the minimum total task time.
Amy→Y, Ben→X, Cal→Z; minimum total 5 hours.
Try it yourself.
Check your understanding
Why does subtracting 7 from every entry of just one row preserve the optimal complete square assignment?
Show answer & reasoning
Every feasible complete assignment selects one entry from that row, so every total falls by exactly 7.
Every complete feasible assignment uses exactly one entry from the altered row, so each total falls by exactly 7. Equal shifts preserve the ordering of totals and hence preserve all minimum assignments.
Keep practising
6 worksheet questions · 17 marks
Read the questions online
- For the matrix rows , perform row reduction.3 marks
- For the reduced matrix , 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 . 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 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 , perform row reduction.3 marks
The row minima are 5,4 and 3.
Subtract each minimum from every entry in its row.
. - For the reduced matrix , 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 . Carry out the adjustment.4 marks
The smallest uncovered entry is 1.
Subtract 1 at ,,,.
Add 1 at the double-covered entry ; other covered entries stay unchanged.
. - 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 hours, one hour slower. - A student draws one line through every row, covering all zeros in any 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 ↗