Assignment and Matching - TCE Mathematics Applications (Tasmania)
“Solve allocation problems using the Hungarian algorithm to find an optimal assignment.”
You must solve the assignment problem, matching each worker to exactly one task so the total cost or time is least, using the Hungarian algorithm: reduce the cost matrix by rows then columns, cover the zeros with the fewest lines, and adjust until an optimal zero-assignment exists.
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.
A problem of pairing workers with tasks so that each worker does exactly one task and each task is done by exactly one worker, with the goal of minimising the total of the chosen costs from a square cost matrix.
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.
- Row reduction: subtract the smallest entry in each row from every entry in that row. 2. Column reduction: subtract the smallest entry in each column from every entry in that column. 3. Cover all zeros with the fewest possible horizontal and vertical lines. 4. If the number of lines equals the matrix size, an optimal assignment exists; otherwise adjust and repeat step 3.
Three workers, three jobs, with cost matrix rows: worker 1 (9, 11, 14), worker 2 (6, 15, 13), worker 3 (12, 13, 6).
Step 1: row reduction
Subtract each row minimum (9, 6, 6): row 1 becomes (0, 2, 5); row 2 becomes (0, 9, 7); row 3 becomes (6, 7, 0).
Step 2: column reduction
Column minimums are now (0, 2, 0). Subtract: column 2 reduces by 2. Matrix becomes row 1 (0, 0, 5), row 2 (0, 7, 7), row 3 (6, 5, 0).
Zeros now mark the cheapest candidate pairings to test for a complete assignment.
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.
When the covering lines number fewer than the matrix size, find the smallest uncovered entry. Subtract it from every uncovered entry and add it to every entry covered by two lines. Then re-cover the zeros and test again.
From the reduced matrix above, row 3 (6, 5, 0) has its zero in job 3, so worker 3 takes job 3. Row 2 (0, 7, 7) has its zero in job 1, so worker 2 takes job 1. That leaves worker 1 for job 2.
Total cost from the original matrix
Worker 1 to job 2: 11. Worker 2 to job 1: 6. Worker 3 to job 3: 6. Total .
This is the least total cost, found by matching along the independent zeros and reading the original costs.
The reduced matrix only locates the best pairings; its zeros are not the actual costs. Once you have the assignment, look up each chosen pairing in the original cost matrix and add those to report the true minimum total.
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.
An assignment must use exactly one zero in each row and one in each column. Picking two zeros from the same row or column gives one worker two tasks and leaves another idle, which breaks the one-to-one rule. Check that your chosen zeros form a complete, non-repeating set across all rows and columns.
Bipartite matching without costs
Not every assignment question carries a cost matrix. When the data is simply who can do what, the problem becomes a bipartite matching: workers on one side, tasks on the other, joined by an edge when that worker can do that task. The aim is a complete matching that pairs every worker with a task they can do, one to one. The practical method is to start with the most constrained vertex, the worker (or task) with the fewest options, and assign it first, then repeat with the next most constrained. This forced-choice approach, used in the multi-sport exam answer above, quickly settles whether a complete matching exists.
Three workers can do: W1 (task A only); W2 (tasks A, B); W3 (tasks B, C).
Assign the most constrained first
W1 can only do A, so W1 takes A. W2 can now only do B (A is taken), so W2 takes B. W3 then takes C.
Conclude
The complete matching is W1 to A, W2 to B, W3 to C. Starting from the most constrained worker avoided a dead end where two workers competed for the same single option.
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 questions
Questions in the style of TASC 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.
Practice6 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.
Practice3 marksFour friends enter a multi-sport event with legs 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 bipartite graph for the table. b) Use it to assign each team member to a leg.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.