How do we assign workers to tasks to minimise total cost or time?
Solve allocation problems using the Hungarian algorithm to find an optimal assignment.
The assignment problem, bipartite matching, and the Hungarian algorithm for optimal allocation of workers to tasks in TCE Mathematics Applications.
Reviewed by: AI editorial process; not yet individually human-reviewed
Have a quick question? Jump to the Q&A page
What this dot point is asking
The assignment problem allocates one worker to each task on a one-to-one basis, choosing the matching that minimises total cost, time, or distance. It is a bipartite matching: workers on one side, tasks on the other, with a cost for each pairing.
The Hungarian algorithm
The method works on the cost matrix directly, creating zeros that mark cheap pairings, then testing whether a complete set of independent zeros (one in each row and column) exists.
Testing and adjusting
After reduction you cover all zeros with as few lines as possible. If the minimum number of covering lines equals the size of the matrix, you can pick one zero in each row and column, and that is the optimal assignment. If fewer lines suffice, the matrix needs adjusting before an optimal assignment is possible.
Maximisation problems
If the goal is to maximise (profit or score) rather than minimise, first convert it. Subtract every entry from the largest entry in the matrix, then run the Hungarian algorithm on the resulting matrix as a minimisation. The assignment found maximises the original quantity.
A complete answer reduces by rows then columns, covers the zeros with the fewest lines, adjusts until the line count equals the matrix size, then states the one-to-one assignment and totals its cost from the original matrix.
Exam-style practice questions
Practice questions written in the style of TASC exam questions on this dot point, with worked answer explainers. The year tag is the paper they imitate, not the source.
2021 TASC General Mathematics6 marksA table gives the time (in minutes) each of four girls (Anna, Bonnie, Claire, Danni) takes for each of four sports including a mountain bike leg. Represent the table as a matrix and use the Hungarian method to reduce it to a form where it is possible to allocate each girl to a sport in a way that minimises total time taken.Show worked answer →
(6 marks) Apply the Hungarian algorithm to the cost matrix.
Row reduction: subtract the smallest entry in each row from every entry in that row, creating at least one zero per row.
Column reduction: subtract the smallest entry in each column from every entry in that column.
Cover all zeros with the minimum number of horizontal and vertical lines. If the number of lines equals the number of rows (4), an optimal assignment exists.
If fewer than 4 lines are needed, find the smallest uncovered entry, subtract it from all uncovered entries and add it to entries covered twice, then re-cover. Repeat until 4 lines are required.
Read off the assignment by choosing one independent zero in each row and column; this allocation minimises the total time.
2024 TASC General Mathematics3 marksFour friends plan to enter a wilderness multi-sport event requiring teams of four (road bike, mountain bike, kayak, run). The skills are: Peta (road bike, kayak, run); Taylor (road bike, run); Charlie (run); Frankie (mountain bike, kayak). a) Draw a bi-partite graph to represent the table. b) Use your bi-partite graph to assign team members to a sport, or leg of the event.Show worked answer →
a) (2 marks) Draw two columns of vertices: team members on one side, the four legs on the other. Join each person to every leg they can do (Peta to road bike, kayak, run; Taylor to road bike, run; Charlie to run; Frankie to mountain bike, kayak).
b) (1 mark) Work from the most constrained member. Charlie can only run, so Charlie does the run. Taylor can then only do road bike (run taken), so Taylor takes road bike. Frankie does mountain bike or kayak, and Peta takes the remaining leg. A valid allocation is Charlie run, Taylor road bike, Frankie mountain bike, Peta kayak.