Assignment problems (SACE Stage 2 General Mathematics)
“Solve assignment problems using the Hungarian algorithm to allocate agents to tasks for minimum total cost.”
An assignment problem allocates each agent to exactly one task (and each task to one agent) to minimise total cost. The Hungarian algorithm reduces a cost matrix by rows and columns, covers the zeros with the fewest lines, and adjusts until an optimal zero-cost allocation appears.
Jump to a section
What this dot point is asking
You must set up a cost matrix and apply the Hungarian algorithm to find the minimum-cost allocation.
The assignment set-up
You have agents and tasks, with a cost (or time) for each agent doing each task, recorded in a square cost matrix. The goal is a one-to-one allocation: each agent gets exactly one task and each task exactly one agent, with the smallest possible total cost.
A problem of matching agents to tasks one-to-one so that the total cost (or time) is minimised. Each row of the cost matrix is an agent, each column a task, and a complete allocation chooses exactly one entry from each row and each column.
The Hungarian algorithm
The method works by creating zeros that mark cost-free choices.
- Row reduction: subtract the smallest entry in each row from every entry in that row.
- Column reduction: subtract the smallest entry in each column from every entry in that column.
- Cover the zeros: cover all zeros using the fewest horizontal and vertical lines.
- Test: if the number of lines equals the matrix size , an optimal assignment exists among the zeros. If fewer, adjust and repeat.
- Adjust: find the smallest uncovered entry, subtract it from all uncovered entries, add it to entries covered twice, then re-cover.
The minimum number of covering lines equals the matrix size exactly when an optimal assignment is possible. You then select a set of zeros with one in each row and each column; those positions give the lowest-cost allocation.
A two-agent reduction
Two workers W1, W2 are assigned to jobs J1, J2 with cost matrix rows W1: (4, 7), W2: (6, 5). Reduce and assign.
Row reduction (subtract each row's minimum): W1 min is 4, giving (0, 3); W2 min is 5, giving (1, 0).
Each column already contains a zero, so no column reduction is needed. The zeros lie at W1-J1 and W2-J2, one in each row and column, so assign W1 to J1 and W2 to J2.
Total cost from the original matrix: , the minimum.
Why row and column reduction works
Subtracting a constant from every entry of a row does not change which assignment is cheapest, because every complete allocation uses exactly one entry from that row, so all allocations lose the same amount. The same holds for columns. Reduction therefore preserves the optimal assignment while creating zeros that mark the locally cheapest choices. The algorithm then hunts for a set of these zeros, one in each row and column - an allocation costing zero in the reduced matrix, which corresponds to the minimum-cost allocation in the original. Understanding this invariance is what makes the procedure more than a recipe.
Unbalanced and infeasible problems
Two practical adjustments arise often. When the numbers of agents and tasks differ, the matrix is not square, so a dummy row or column of zeros is added to balance it; the agent or task matched to a dummy is simply left unassigned. When a particular agent cannot do a particular task, that cell is given a prohibitively large cost so the algorithm never selects it. Both adjustments let the standard square-matrix method handle real situations, and SACE questions frequently test whether you can set up the matrix correctly before reducing.
Reading off the allocation and cost
Once the zeros allow one selection per row and column, those zeros give the assignment. Read the total cost from the original matrix, not the reduced one.
Checking against the alternative
For the workers above, confirm the assignment W1-J1, W2-J2 beats the other option.
The only alternative one-to-one allocation is W1-J2, W2-J1, costing . The chosen allocation costs , which is lower, confirming it is optimal.
Maximisation problems
If the table gives profits or scores to be maximised, first convert to a minimisation problem by subtracting every entry from the largest entry in the table, then run the Hungarian algorithm as normal. The resulting allocation maximises the original total.
For a "maximum profit" question, subtract all entries from the biggest value in the matrix first. Forgetting this step and minimising the profits directly gives the worst allocation instead of the best, a costly slip in an exam.
Do not read the final total from the reduced matrix; always sum the chosen positions in the original cost matrix. Also do not stop reducing too early: if the fewest covering lines is less than , you must do the adjustment step before an optimal assignment is guaranteed.
Exam-style questions
Questions in the style of SACE Board exam questions on this dot point, each with a worked answer. They are written by ExamExplained unless tagged "Past paper"; the year shows the paper a question is modelled on.
SACE 2022-style2 marksCalculator-assumed. Four buyers bid on four auction items. The original bid array has been transformed into a new array for the Hungarian algorithm. Explain what was done to the original array and why it is necessary.Show worked answer →
The auction is a maximisation problem (the charity wants the most money), but the Hungarian algorithm minimises. Each bid has been subtracted from the largest value in the array, converting it to an equivalent minimisation (opportunity-cost) array. (1 mark)
Subtracting every entry from the same constant reverses the ordering, so the highest bid becomes the smallest entry. Minimising the new array therefore maximises the original total, which is necessary because the algorithm only minimises. (1 mark)
SACE 2023-style1 markCalculator-assumed. Four children are allocated four chores with the Hungarian algorithm. When a fifth person is added, the array becomes 5 by 4. State why a dummy column of zeros must be added.Show worked answer →
The Hungarian algorithm requires a square array, with equal numbers of agents and tasks, so every row matches exactly one column.
With five people but four chores the array is 5 by 4; adding one dummy column makes it 5 by 5. The dummy column is filled with zeros because it represents a "no chore" assignment adding no time. The mark is for stating the array must be square.
SACE 2021-style1 markCalculator-assumed. The Hungarian algorithm is used to maximise the total training hours allocated to four apprentices. State one limitation of using the algorithm in this context.Show worked answer →
Any one valid limitation earns the mark. For example: the algorithm forces a strict one-to-one allocation, even if it would be better for one person to do two tasks; or it assumes the listed values are the only factor, ignoring availability, difficulty or aptitude; or it assumes every assignment is feasible when an apprentice may be unable to do a particular task.