Assignment problems and the Hungarian algorithm (QCE General Mathematics Unit 4)

Syllabus dot point

“Use a bipartite graph and its tabular or matrix form to represent possible assignments for an allocation problem, determine the optimum (minimum and maximum) assignment/s by inspection for small-scale problems, and use the Hungarian algorithm (3 x 3 up to 5 x 5 square matrices) to determine the optimum (minimum and maximum) assignment/s for larger practical problems”

15 min readUpdated 23 Sep 2026

Quick answer

An assignment problem matches each worker to one task. Represent it as a bipartite graph or a cost matrix. For small problems, list every allocation and compare totals. For 3 x 3 to 5 x 5 problems, use the Hungarian algorithm: reduce rows, reduce columns, cover the zeros with the fewest lines, and if there are fewer lines than rows, subtract the smallest uncovered entry from uncovered entries and add it at crossings. When the lines equal the matrix size, choose one zero per row and column and total the original entries. To maximise, first subtract every entry from the largest entry. There may be more than one optimal allocation.

Jump to a section

What this dot point is asking
The answer
Exam-style questions
Practice questions

What this dot point is asking

In an assignment (allocation) problem, each member of one group (workers, machines, athletes) must be matched with exactly one member of another group (tasks, jobs, sections) so that the total cost, time or distance is as small as possible, or the total profit or score is as large as possible.

The QCAA General Mathematics 2025 syllabus (Unit 4, Topic 5, Networks and decision mathematics 2, "Assigning order and the Hungarian algorithm") asks you to

use a bipartite graph and its tabular or matrix form to represent the possible assignments,
determine the optimum (minimum and maximum) assignment or assignments by inspection for small problems, and
use the Hungarian algorithm, for 3 x 3 up to 5 x 5 square matrices, to determine the optimum (minimum and maximum) assignment or assignments for larger problems.

The answer

Bipartite graphs and matrices

A bipartite graph has two sets of vertices, with edges only between the sets, never within one. In an allocation problem one set is the workers and the other the tasks; each edge is labelled with the cost of that pairing. The same information is usually written as a cost matrix: one row per worker, one column per task.

Courier	Delivery 1	Delivery 2	Delivery 3
X	15	12	19
Y	10	7	15
Z	11	19	13

An allocation picks one entry in each row and each column, so no worker does two tasks and no task is done twice.

By inspection

For a small problem, list every possible allocation and total it. A 3 x 3 problem has only $3 \times 2 \times 1 = 6$ allocations; a 4 x 4 problem has 24, and a 5 x 5 problem has 120, which is why an algorithm is needed for larger problems. For the couriers:

X	Y	Z	Total (min)
1	2	3	$15 + 7 + 13 = 35$
1	3	2	$15 + 15 + 19 = 49$
2	1	3	$12 + 10 + 13 = 35$
2	3	1	$12 + 15 + 11 = 38$
3	1	2	$19 + 10 + 19 = 48$
3	2	1	$19 + 7 + 11 = 37$

The minimum is 35 minutes, and it is reached by two allocations. That is why the syllabus says "assignment/s": always check whether the optimum is shared.

A useful shortcut by inspection: start with each worker's cheapest task. If no two workers want the same task, that allocation is optimal. If they clash (here X and Y both prefer delivery 2), you have to compare alternatives.

The Hungarian algorithm (minimising)

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. (A column that already contains 0 is unchanged.)
Cover the zeros with the fewest horizontal and vertical lines possible.
Test. If the number of lines equals the size of the matrix ( $n$ ), an optimal assignment exists: go to step 6.
Adjust. Find the smallest entry not covered by any line. Subtract it from every uncovered entry, add it to every entry covered by two lines, and leave entries covered by one line unchanged. Return to step 3.
Assign. Choose $n$ zeros, one in each row and each column. Start with a row or column that has only one zero, then cross off that row and column and repeat.
Total the original entries at the chosen positions.

Why it works: subtracting the same amount from a whole row (or column) changes every allocation's total by the same amount, because every allocation uses exactly one entry from that row. So the best allocation stays the best, and zeros mark the cheapest choices.

Maximising

The Hungarian algorithm only minimises. To maximise profit, sales or scores, first subtract every entry from the largest entry in the matrix. Large profits become small "regrets", so minimising the regrets maximises the profit. Apply the algorithm to the new matrix, then total the original entries.

Key fact

Hungarian algorithm: reduce rows, reduce columns, cover the zeros with the fewest lines; if lines $= n$ , assign one zero per row and column; if lines $< n$ , subtract the smallest uncovered entry from uncovered entries and add it at crossings, then repeat. For a maximum, first subtract every entry from the largest entry. Total the original matrix at the chosen positions, and check for more than one optimal allocation.

Worked examples: the Hungarian algorithm

1. A 3 x 3 problem with one adjustment

Three machines A, B and C can do jobs 1, 2 and 3. Costs ($): A: 12, 9, 15. B: 10, 14, 11. C: 13, 8, 16. Find the minimum-cost allocation.

Row reduction. Subtract 9, 10 and 8:

	1	2	3
A	3	0	6
B	0	4	1
C	5	0	8

Column reduction. Columns 1 and 2 contain 0; column 3's smallest entry is 1:

	1	2	3
A	3	0	5
B	0	4	0
C	5	0	7

Cover. Row B and column 2 cover every zero: 2 lines, fewer than 3.

Adjust. The uncovered entries are 3, 5, 5 and 7; the smallest is 3. Subtract 3 from them and add 3 at the crossing (B, 2):

	1	2	3
A	0	0	2
B	0	7	0
C	2	0	4

Cover again: Now 3 lines are needed, so an assignment exists.
Assign: C has only one zero (job 2). Then A takes job 1 and B takes job 3.
Total: $12 + 11 + 8 = 31$ , so $31.

2. A 4 x 4 problem

Four volunteers A, B, C and D take these times (minutes) for jobs W, X, Y and Z. A: 14, 5, 8, 7. B: 2, 12, 6, 5. C: 7, 8, 3, 9. D: 2, 4, 6, 10. Minimise the total time.

Row reduction. Subtract 5, 2, 3 and 2. Column reduction. Only column Z needs it (smallest 2):

	W	X	Y	Z
A	9	0	3	0
B	0	10	4	1
C	4	5	0	4
D	0	2	4	6

Cover. Rows A and C with column W: 3 lines, fewer than 4.

Adjust. The smallest uncovered entry is 1 (B, Z). Subtract 1 from all uncovered entries; add 1 at the crossings (A, W) and (C, W):

	W	X	Y	Z
A	10	0	3	0
B	0	9	3	0
C	5	5	0	4
D	0	1	3	5

Cover again: 4 lines are now needed.
Assign: D's only zero is W. C's only zero is Y. B then takes Z (W is used). A takes X.
Total: $5 + 5 + 3 + 2 = 15$ minutes (A-X, B-Z, C-Y, D-W).

Marker's note: show each matrix, state the number of lines each time, and name the smallest uncovered entry. Those are the method marks.

3. Maximising sales

Four salespeople and four regions (North, South, East, West), expected weekly sales in #39;000. P: 37, 34, 40, 37. Q: 31, 35, 27, 22. R: 22, 22, 22, 13. S: 25, 30, 22, 11. Maximise total sales.

Convert. The largest entry is 40. Subtract every entry from 40:

	N	S	E	W
P	3	6	0	3
Q	9	5	13	18
R	18	18	18	27
S	15	10	18	29

Reduce. Rows minus 0, 5, 18 and 10; then column W minus 3:

	N	S	E	W
P	3	6	0	0
Q	4	0	8	10
R	0	0	0	6
S	5	0	8	16

Cover and adjust. Rows P and R and column S: 3 lines. The smallest uncovered entry is 4:

	N	S	E	W
P	3	10	0	0
Q	0	0	4	6
R	0	4	0	6
S	1	0	4	12

Assign. S: South (only zero). Q: North. R: East. P: West.

Total from the original matrix. $37 + 31 + 22 + 30 = 120$ , so $120 000 a week. Notice P does not get East, P's best region: the algorithm finds the best total, not the best for each person.

4. More than one optimal allocation

For the couriers (X: 15, 12, 19; Y: 10, 7, 15; Z: 11, 19, 13), the algorithm gives, after reduction and one adjustment of 3:

	2	3
X	0	2
Y	0	3
Z	11	0

Assign. Z could take 1 or 3, but if Z takes 1, X and Y cannot both be placed in columns 2 and 3 on zeros. So Z takes 3. Then X and Y can take 1 and 2 either way round: both X-1, Y-2 and X-2, Y-1 use only zeros.

Answer. Two optimal allocations, each totalling 35 minutes, matching the list made by inspection.

Common traps

Forgetting to convert a maximisation: Applied directly to profits, the algorithm finds the least profitable allocation.
Using more lines than necessary: The test depends on the fewest lines. Covering with extra lines can make you stop too early with no valid assignment.
Adjusting the wrong entries: Subtract from uncovered entries only, add at crossings only, and leave singly covered entries alone.
Choosing two zeros in one row or column: The final allocation needs exactly one per row and one per column.
Totalling the reduced matrix: The reduced matrix only locates the allocation; the total comes from the original entries.
Stopping at one optimal allocation: If there is a choice of zeros at the assignment step, there may be more than one optimum. Check and state all of them when asked for "assignment/s".

Exam technique

Write each matrix after each step with row and column labels. After each cover, write "lines $=$ ... $<n$ , so adjust" or "lines $= n$ , so optimal". Name the smallest uncovered value. Make the assignment starting from a row or column with a single zero and explain the order. Finish with a sentence in context: who does what, and the total with units, from the original matrix. For small problems where you are asked "by inspection", a neat list of all allocations is a complete method.

Note

Imagine sharing out jobs among friends so the whole lot gets done as quickly as possible. Each person is good at different things. You cannot just give everyone their favourite job, because two people might want the same one. The Hungarian method is a recipe: take away the same amount from every number in a row or a column (which does not change which sharing-out is best), until you can find a zero for every person in a different job. Those zeros show the best way to share the jobs. Then add up the real times to get the answer.

Exam-style questions

Questions in the style of QCAA 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.

Practice4 marks

The table summarises the distances in kilometres between three flower stores and three delivery locations A, B and C. Store 1: A 19, B 17, C 24. Store 2: A 15, B 14, C 22. Store 3: A 23, B 16, C 40. Use the Hungarian algorithm to determine the minimum total distance needed to deliver flowers to all locations if each store delivers flowers to only one location.

Show worked answer →

Step 1: row reduction (1 mark): Subtract each row's smallest entry (17, 14, 16): rows become (2, 0, 7), (1, 0, 8), (7, 0, 24).
Step 2: column reduction (1 mark): Subtract each column's smallest entry (1, 0, 7): rows become (1, 0, 0), (0, 0, 1), (6, 0, 17).
Step 3: cover and assign (1 mark): The zeros need three lines to cover (for example column B, row 1 and row 2), which equals the matrix size, so an optimal assignment exists. Store 3's only zero is B; then Store 2 takes A and Store 1 takes C.
Step 4: total from the original table (1 mark): $24 + 15 + 16 = 55$ km.

Always total the original entries; the reduced matrix only locates the assignment.

Practice5 marks

A triathlon relay has three sections: swim (S), cycle (C) and run (R). The matrix shows the average number of minutes for three athletes, Jane (J), Knox (K) and Levi (L), to complete each section. J: S 40, C 56, R 66. K: S 36, C 60, R 72. L: S 25, C 48, R 78. Use the Hungarian algorithm to predict the minimum total relay time if assigning each athlete to completing one section.

Show worked answer →

Step 1: row reduction (1 mark): Subtract 40, 36 and 25: J (0, 16, 26), K (0, 24, 36), L (0, 23, 53).
Step 2: column reduction (1 mark): Subtract 0, 16 and 26: J (0, 0, 0), K (0, 8, 10), L (0, 7, 27).
Step 3: adjust (1 mark): Row J and column S cover every zero: 2 lines, fewer than 3. The smallest uncovered entry is 7. Subtract 7 from the uncovered entries and add 7 where the lines cross: J (7, 0, 0), K (0, 1, 3), L (0, 0, 20). Now 3 lines are needed, so an optimal assignment exists.
Step 4: assign (1 mark): Knox's only zero is swim. Levi then takes cycle (his zero at swim is used). Jane takes run.
Step 5: total (1 mark): $66 + 36 + 48 = 150$ minutes, from the original matrix.

Check: the next best allocation (Jane run, Knox cycle, Levi swim) takes 151 minutes.

Original4 marks

Four cleaners take the following times (minutes) to clean four areas. Cleaner 1: 33, 35, 17, 16. Cleaner 2: 26, 25, 21, 33. Cleaner 3: 10, 10, 35, 18. Cleaner 4: 25, 18, 16, 32 (columns are areas A, B, C, D). Use the Hungarian algorithm to find the allocation that minimises the total time, and state the minimum total time.

Show worked answer →

Row reduction (1 mark): Subtract 16, 21, 10 and 16: rows (17, 19, 1, 0), (5, 4, 0, 12), (0, 0, 25, 8), (9, 2, 0, 16). Every column already contains a 0, so column reduction changes nothing.
Cover and adjust (1 mark): Rows 1 and 3 and column C cover all zeros: 3 lines, fewer than 4. The smallest uncovered entry is 2. Subtract 2 from uncovered entries and add 2 at the crossings: rows (17, 19, 3, 0), (3, 2, 0, 10), (0, 0, 27, 8), (7, 0, 0, 14). Now 4 lines are needed.
Assign (1 mark): Cleaner 1: D (only zero). Cleaner 2: C (only zero). Cleaner 4: B (C is taken). Cleaner 3: A.
Total (1 mark): $16 + 21 + 10 + 18 = 65$ minutes.

Original5 marks

Five technicians are assigned to five jobs, one each. The costs ($) are: T1: 24, 12, 36, 12, 40. T2: 18, 25, 32, 31, 12. T3: 11, 33, 32, 19, 30. T4: 28, 31, 36, 24, 19. T5: 32, 22, 38, 31, 21 (columns are jobs J1 to J5). Use the Hungarian algorithm to find the minimum total cost.

Show worked answer →

Row reduction (1 mark). Subtract 12, 12, 11, 19 and 21:

T1 (12, 0, 24, 0, 28), T2 (6, 13, 20, 19, 0), T3 (0, 22, 21, 8, 19), T4 (9, 12, 17, 5, 0), T5 (11, 1, 17, 10, 0).

Column reduction (1 mark). Column J3's smallest entry is 17; the other columns already contain 0:

T1 (12, 0, 7, 0, 28), T2 (6, 13, 3, 19, 0), T3 (0, 22, 4, 8, 19), T4 (9, 12, 0, 5, 0), T5 (11, 1, 0, 10, 0).

Adjust (1 mark). Rows T1 and T3 with columns J3 and J5 cover every zero: 4 lines, fewer than 5. The smallest uncovered entry is 1 (T5, J2). Subtract 1 from uncovered entries and add 1 at the four crossings:

T1 (12, 0, 8, 0, 29), T2 (5, 12, 3, 18, 0), T3 (0, 22, 5, 8, 20), T4 (8, 11, 0, 4, 0), T5 (10, 0, 0, 9, 0).

Now 5 lines are needed.

Assign (1 mark). T2: J5 (only zero). T3: J1 (only zero). T4: J3 (J5 taken). T5: J2 (J3, J5 taken). T1: J4.

Total (1 mark). $12 + 12 + 11 + 36 + 22 = 93$ , so $93.

Original4 marks

Four salespeople are to be assigned to four regions, one each, to maximise total weekly sales. Expected sales ($'000): P: 37, 34, 40, 37. Q: 31, 35, 27, 22. R: 22, 22, 22, 13. S: 25, 30, 22, 11 (columns North, South, East, West). Use the Hungarian algorithm to find the allocation and the maximum total sales.

Show worked answer →

Convert (1 mark): Subtract every entry from the largest entry, 40: P (3, 6, 0, 3), Q (9, 5, 13, 18), R (18, 18, 18, 27), S (15, 10, 18, 29). Minimising this matrix maximises sales.
Reduce (1 mark): Rows minus 0, 5, 18, 10, then column West minus 3: P (3, 6, 0, 0), Q (4, 0, 8, 10), R (0, 0, 0, 6), S (5, 0, 8, 16).
Adjust (1 mark): Rows P and R with column South cover all zeros: 3 lines. The smallest uncovered entry is 4: P (3, 10, 0, 0), Q (0, 0, 4, 6), R (0, 4, 0, 6), S (1, 0, 4, 12). Now 4 lines are needed.
Assign and total (1 mark): S: South (only zero). Q: North. R: East. P: West. Sales $= 37 + 31 + 22 + 30 = 120$ , so $120 000 a week.

Practice questions

Original practice questions graded from foundation to exam level, each with a full worked solution. Try them before revealing the solution.

foundation2 marks

Two workers P and Q do two jobs, one each. Times (hours): P: job 1 4, job 2 7. Q: job 1 6, job 2 5. Find the allocation with the minimum total time by inspection.

Show worked solution →

The two possible allocations: P1 and Q2 $= 4 + 5 = 9$ hours; P2 and Q1 $= 7 + 6 = 13$ hours. (1 mark)

P does job 1 and Q does job 2, for 9 hours. (1 mark)

foundation2 marks

Row-reduce and then column-reduce the matrix with rows (8, 5, 9), (6, 7, 4) and (7, 9, 8).

Show worked solution →

Rows minus 5, 4, 7: (3, 0, 4), (2, 3, 0), (0, 2, 1). (1 mark)

Every column already has a 0, so column reduction changes nothing. (1 mark)

foundation1 mark

A maximisation matrix has largest entry 50. What is the first step before applying the Hungarian algorithm?

Show worked solution →

Subtract every entry from 50, turning it into an equivalent minimisation problem. (1 mark)

core3 marks

Couriers X, Y and Z take the following times (minutes) for deliveries 1, 2 and 3. X: 15, 12, 19. Y: 10, 7, 15. Z: 11, 19, 13. By listing all possible allocations, find every optimal allocation.

Show worked solution →

The six allocations (X, Y, Z): (1, 2, 3) $= 35$ ; (1, 3, 2) $= 49$ ; (2, 1, 3) $= 35$ ; (2, 3, 1) $= 38$ ; (3, 1, 2) $= 48$ ; (3, 2, 1) $= 37$ . (2 marks)

The minimum is 35 minutes, and there are two optimal allocations: X-1, Y-2, Z-3 and X-2, Y-1, Z-3. (1 mark)

core3 marks

Use the Hungarian algorithm on the matrix with rows (12, 9, 15), (10, 14, 11) and (13, 8, 16) (rows A, B, C; columns 1, 2, 3) to find the minimum total.

Show worked solution →

Rows minus 9, 10, 8: (3, 0, 6), (0, 4, 1), (5, 0, 8). Column 3 minus 1: (3, 0, 5), (0, 4, 0), (5, 0, 7). (1 mark)

Row B and column 2 cover all zeros: 2 lines. Smallest uncovered entry 3: (0, 0, 2), (0, 7, 0), (2, 0, 4). Now 3 lines are needed. (1 mark)

C-2, A-1, B-3: $12 + 11 + 8 = 31$ . (1 mark)

exam3 marks

After reduction, a 4 x 4 matrix can have all its zeros covered by 3 lines. The uncovered entries are 4, 6, 2, 9, 5 and 3. Describe the next step exactly, including what happens to entries covered by one line and by two lines.

Show worked solution →

The smallest uncovered entry is 2. (1 mark)

Subtract 2 from every uncovered entry (giving 2, 4, 0, 7, 3, 1), and add 2 to every entry covered by two lines (at a crossing). (1 mark)

Entries covered by exactly one line are unchanged. Then cover the zeros again with the fewest lines and test whether 4 lines are now needed. (1 mark)

exam2 marks

A student applies the Hungarian algorithm to a matrix of profits and reports the "minimum profit allocation". Explain the error and how to fix it.

Show worked solution →

The Hungarian algorithm minimises, so applying it directly to profits finds the least profitable allocation. (1 mark)

Convert first: subtract every profit from the largest profit, apply the algorithm to the new matrix, then total the original profits at the chosen positions. (1 mark)

Practise this

Sources & how we know this

General Mathematics General senior syllabus 2025 — QCAA