How do we assign workers to tasks for the lowest total cost or time?
Solve assignment problems using the Hungarian algorithm to allocate agents to tasks for minimum total cost.
How to set up an assignment cost matrix and use the Hungarian algorithm (row and column reduction, covering zeros) to allocate agents to tasks for the lowest total cost.
Reviewed by: AI editorial process; not yet individually human-reviewed
Have a quick question? Jump to the Q&A page
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.
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.
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.
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.
Exam-style practice questions
Practice questions written in the style of SACE Board exam questions on this dot point, with worked answer explainers. The year tag is the paper they imitate, not the source.
2021 SACE Stage 22 marksFour buyers place bids on four auction items. The original bid array has been transformed into a new array used for the Hungarian algorithm. Explain what has been done to the original array to produce the new one, and why it is necessary to do this.Show worked answer →
The auction is a maximisation problem (the charity wants the most money), but the Hungarian algorithm minimises. So each bid has been subtracted from the largest value in the array, converting it into an equivalent minimisation problem (an opportunity-cost or "regret" array).
Subtracting every entry from the same constant reverses the ordering: the highest bid becomes the smallest entry (a zero). Minimising the total of this new array therefore maximises the total of the original bids.
Award 1 mark for stating the transformation (subtract each value from the maximum element), and 1 mark for explaining that this is necessary because the Hungarian algorithm minimises, so a maximisation problem must first be converted to a minimisation one.
2022 SACE Stage 21 marksFour children are each allocated one of four weekly chores using the Hungarian algorithm. After their father offers to do one chore, a fifth person is added so the array becomes 5 rows by 4 columns. State why a dummy column of zeros must be added to the right of the dusting column in order for the Hungarian algorithm to be applied.Show worked answer →
The Hungarian algorithm requires a square array, with an equal number of agents and tasks, so that every row can be matched to exactly one column.
Here there are five people (four children plus the father) but only four chores, giving a 5 by 4 array. Adding one dummy column makes it 5 by 5, so it is square.
The dummy column is filled with zeros because it represents a "no chore" assignment that adds no time to the total. The person matched to the dummy column simply does no chore. Award the mark for stating the array must be square (equal rows and columns) for the algorithm to work.
2023 SACE Stage 21 marksThe Hungarian algorithm is used to maximise the total combined training hours allocated to four apprentices. State one limitation of using the Hungarian algorithm to allocate tasks to the apprentices in this context.Show worked answer →
Any one valid limitation earns the mark. Suitable answers include:
The algorithm forces a strict one-to-one allocation: each apprentice must be given exactly one task and each task exactly one apprentice, even if it would be better for one person to do two tasks or for tasks to be shared.
It assumes the listed values (training hours) are the only factor, ignoring real-world considerations such as availability, the difficulty of each task, individual aptitude, or whether the most-trained worker is actually the best choice.
It assumes every assignment is feasible, when in practice an apprentice may be unable to perform a particular task. State one such limitation clearly to earn the mark.