QLDGeneral MathematicsSyllabus dot point

Topic 3: Networks and decision mathematics - how do we allocate workers to tasks at the least total cost?

Represent an allocation as a bipartite graph or a cost matrix, solve a small assignment problem to minimise total cost or time using the Hungarian algorithm, handle maximisation by converting it to a minimisation, and interpret the optimal allocation

A focused answer to the QCE General Mathematics Unit 4 dot point on assignment problems. Covers modelling an allocation as a bipartite graph or cost matrix, the Hungarian algorithm steps for minimising total cost or time, converting maximisation problems, and interpreting the optimal one-to-one allocation, with arithmetic-verified worked examples for IA3 and the external assessment.

Generated by Claude Opus 4.76 min answerUpdated 2026-05-29

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

QCAA wants you to allocate a set of workers to a set of tasks, one each, so the total cost or time is as small as possible. You represent the allocation as a bipartite graph or, more usefully, as a cost matrix, then apply the Hungarian algorithm to find the optimal one-to-one assignment. You also need to handle problems that ask to maximise (for example, total output) by first turning them into minimisation problems. This is a distinct sub-topic of Unit 4 Topic 3 and a common short-answer item in IA3 and the external assessment.

The answer

Modelling the allocation

An assignment problem pairs each member of one group (workers) with one member of another group (tasks), one-to-one. It is naturally a bipartite graph with workers on one side and tasks on the other, and an edge weight for each possible pairing. In practice you record those weights in a square cost matrix, rows for workers and columns for tasks, where each entry is the cost or time if that worker does that task.

The Hungarian algorithm

The Hungarian algorithm finds the minimum-cost assignment by reducing the matrix.

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 with the fewest possible horizontal and vertical lines.
Test for optimality. If the number of covering lines equals the matrix size, an optimal assignment of zeros (one per row and column) exists. If not, find the smallest uncovered entry, subtract it from all uncovered entries, add it to entries covered twice, and repeat from the covering step.
Read the allocation. Choose one zero in each row and column; those positions are the optimal pairings.

Handling maximisation

If the problem asks to maximise (such as total sales or skill scores), you cannot apply the Hungarian algorithm directly because it minimises. Convert by subtracting every entry from the largest entry in the matrix, which turns the largest values into the smallest. Minimising this converted matrix maximises the original, and you then read the same positions back in the original matrix.

Interpreting the result

The optimal allocation is the set of worker-task pairings, one per row and column. Add the original costs (or times) at those positions to report the minimum total. State the answer in context: which worker does which task and the total cost.

Worked example

A two-by-two assignment

Two workers P and Q must each do one of two jobs, job 1 or job 2. The time in hours is: P on job 1 $= 4$ , P on job 2 $= 7$ , Q on job 1 $= 6$ , Q on job 2 $= 5$ . Find the allocation that minimises total time.

Step 1: Cost matrix (rows P, Q; columns job 1, job 2).

\begin{matrix} & J1 & J2 \\ P & 4 & 7 \\ Q & 6 & 5 \end{matrix}

Step 2: Row reduction. Smallest in row P is $4$ ; in row Q is $5$ . Subtract.

\begin{matrix} P & 0 & 3 \\ Q & 1 & 0 \end{matrix}

Step 3: Column reduction. Column J1 smallest is $0$ , column J2 smallest is $0$ , so no change.

Step 4: Read the zeros. There is a zero at P-J1 and a zero at Q-J2, one in each row and column, so this is optimal. Assign P to job 1 and Q to job 2.

Step 5: Total time from the original matrix.

\text{P-J1} + \text{Q-J2} = 4 + 5 = 9.

Verify the alternative: P-J2 and Q-J1 would give $7 + 6 = 13$ , which is worse. The minimum total time is $9$ hours with P on job 1 and Q on job 2.

Common traps

Applying the Hungarian algorithm to a maximisation without converting: The algorithm minimises. For maximising, subtract every entry from the largest entry first, then minimise the new matrix.
Choosing two zeros in the same row or column: The final allocation must use exactly one zero per row and one per column. Picking two in the same line is not a valid one-to-one assignment.
Subtracting the wrong value in the adjustment step: When lines do not yet equal the matrix size, subtract the smallest uncovered value from uncovered entries and add it to doubly covered entries; leaving singly covered entries unchanged.
Reading the total from the reduced matrix: The reduced matrix is only for finding positions. The actual total cost comes from the original matrix entries at the chosen positions.
Forgetting the matrix must be square: Assignment needs equal numbers of workers and tasks. If they differ, a dummy row or column of zeros is added before reducing.

Exam-style practice questions

Practice questions written in the style of QCAA exam questions on this dot point, with worked answer explainers. The year tag is the paper they imitate, not the source.

2022 QCAA4 marksThe 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 the smallest entry in each row. Row 1 minus 17, row 2 minus 14, row 3 minus 16 gives the matrix [[2, 0, 7], [1, 0, 8], [7, 0, 24]].

Step 2 - column reduction (1 mark). Subtract the smallest entry in each column. Column 1 minus 1 and column 3 minus 7 gives [[1, 0, 0], [0, 0, 1], [6, 0, 17]]. The zeros can now be covered, and an optimal assignment of one zero per row and column exists.

Step 3 - read off the allocation (1 mark). The independent zeros sit at Store 1 to C, Store 2 to A and Store 3 to B.

Step 4 - minimum total distance (1 mark). Read the original distances for that allocation: 24 + 15 + 16 = 55 km.

Always go back to the original cost matrix to total the chosen cells; the reduced matrix only locates the optimal assignment, it does not give the actual distance.

2023 QCAA5 marksA 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 each row's smallest value (J minus 40, K minus 36, L minus 25): [[0, 16, 26], [0, 24, 36], [0, 23, 53]].

Step 2 - column reduction (1 mark). Subtract each column's smallest value (column 2 minus 16, column 3 minus 26): [[0, 0, 0], [0, 8, 10], [0, 7, 27]].

Step 3 - test and adjust (1 mark). The zeros cannot yet be covered by three independent zeros in distinct rows and columns, so apply the algorithm's adjustment (cover the zeros with the fewest lines, subtract the smallest uncovered value and add it at the line intersections) until an assignment exists.

Step 4 - optimal allocation (1 mark). The optimal one-to-one assignment is Jane to run, Knox to swim and Levi to cycle.

Step 5 - minimum total time (1 mark). Total from the original matrix: 66 (J run) + 36 (K swim) + 48 (L cycle) = 150 minutes.

Knox is fastest at swimming and Levi at cycling, so the algorithm hands the run to Jane; reading the times back from the original matrix gives the 150-minute total.