Assignment problems and the Hungarian algorithm in WACE Mathematics Applications Unit 4

Syllabus dot point

“Model an assignment problem as a bipartite graph and solve it with the Hungarian algorithm to minimise total cost.”

WACEMathematics ApplicationsUnit 48 min readUpdated 2 Jun 2026

Quick answer

An assignment problem matches each member of one set (workers) to one member of another set (jobs) so that the total cost is least. Model it as a bipartite graph or a cost matrix, then solve with the Hungarian algorithm: reduce each row by its minimum, reduce each column by its minimum, cover all zeros with the fewest lines, and if the number of lines equals the matrix size, read off a complete set of independent zeros as the optimal assignment.

Jump to a section

What this dot point is asking
Modelling the problem
The Hungarian algorithm
Unbalanced problems
Maximisation problems
Exam-style questions

What this dot point is asking

You must model the problem as a bipartite matching and apply the Hungarian algorithm to minimise total cost.

Modelling the problem

An assignment problem allocates each worker to exactly one task and each task to exactly one worker, minimising total cost (or time). The costs form a square matrix, with workers as rows and jobs as columns.

Bipartite graph

A bipartite graph has two disjoint sets of vertices (here, workers and jobs) with edges only between the sets, never within them. An assignment is a perfect matching: every worker paired to one job and every job to one worker.

The matrix must be square (equal numbers of workers and jobs); if not, add a dummy row or column of zeros.

The Hungarian algorithm

The algorithm creates zeros that mark a least-cost allocation.

The Hungarian algorithm (minimisation)

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 possible horizontal and vertical lines.
Test: if the number of lines equals the matrix size $n$ , an optimal assignment of independent zeros exists. If fewer than $n$ , adjust and repeat.
Adjust (if needed): find the smallest uncovered entry, subtract it from all uncovered entries, add it to entries covered twice, then return to step 3.

The optimal cost is found by reading the original-matrix costs of the chosen zero positions.

Lines equal to matrix size means optimal

After reduction, if you can cover all zeros with exactly $n$ lines for an $n \times n$ matrix, an optimal assignment exists among those zeros. If you can cover them with fewer than $n$ lines, the algorithm is not finished and you must do the adjustment step.

Worked example

Solving a 3x3 assignment

Assign three machinists to three jobs with cost matrix row $A = (8, 4, 7)$ , row $B = (5, 6, 5)$ , row $C = (9, 8, 4)$ .

Step 1: Perform row reduction by subtracting each row's minimum.

The purpose of row reduction is to introduce at least one zero into every row without changing the identity of the optimal assignment. The row minima are $4$ , $5$ , and $4$ for rows $A$ , $B$ , and $C$ respectively. Subtracting each minimum from its row gives the reduced matrix: $A = (4, 0, 3)$ , $B = (0, 1, 0)$ , $C = (5, 4, 0)$ .

Step 2: Perform column reduction by subtracting each column's minimum.

Column reduction similarly ensures every column contains at least one zero, which marks a candidate assignment cell. Inspecting the three columns of the row-reduced matrix, each column already contains a zero, so all three column minima are $0$ and the matrix is unchanged after this step.

Step 3: Cover all zeros with the fewest lines and test for optimality.

We cover every zero using the minimum number of horizontal or vertical lines. The zeros lie at positions $A_2$ , $B_1$ , $B_3$ , and $C_3$ . One valid covering uses three lines: column $1$ , column $3$ , and row $A$ (or an equivalent set of three). Because this $3 \times 3$ matrix requires exactly $3$ covering lines, an optimal complete assignment exists among these zeros.

Step 4: Read off the optimal assignment from the independent zeros.

We select a set of zeros with no two in the same row or column. Choosing $A \to J_2$ , $B \to J_1$ , $C \to J_3$ gives one such independent set. Reading the corresponding costs from the original matrix gives $4 + 5 + 4 = 13$ . This is the minimum possible total cost for this allocation.

Unbalanced problems

If there are more jobs than workers (or vice versa), the cost matrix is not square and the algorithm cannot run. Add a dummy row or column of zeros to make it square: a dummy worker assigned to a job means that job is left undone (at zero recorded cost), which models the situation that not every task can be covered. Always balance the matrix before reducing.

Maximisation problems

If the goal is to maximise (for example, total profit), convert to a minimisation first: subtract every entry from the largest entry in the matrix, then run the Hungarian algorithm as normal. The resulting assignment maximises the original profit, and you read the total profit from the original matrix at the chosen positions.

Common errors

Forgetting column reduction: Both row and column reductions are needed before covering zeros.
Stopping when lines are fewer than n: If the minimum covering lines are fewer than the matrix size, do the adjustment step and re-cover; do not assign yet.
Reading reduced values as the cost: The optimal total cost comes from the original matrix at the chosen positions, not the reduced zeros.
Not converting a maximisation: For a maximum, subtract every entry from the largest entry first; running the algorithm directly minimises and gives the wrong allocation.

Exam-style questions

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

WACE 2022-style7 marks

Three workers

W_1, W_2, W_3

must each do one of three jobs

J_1, J_2, J_3

. The cost matrix (hours) is row

W_1 = (9, 11, 14)

, row

W_2 = (6, 15, 13)

, row

W_3 = (12, 13, 6)

. Use the Hungarian algorithm to find the allocation that minimises total time.

Show worked answer →

Reduce rows, then columns, then cover the zeros.

Row reduction (subtract each row minimum, $9, 6, 6$ ): $W_1 = (0,2,5)$ , $W_2 = (0,9,7)$ , $W_3 = (6,7,0)$ . (2 marks)

Column reduction (column minima $0, 2, 0$ ): $W_1 = (0,0,5)$ , $W_2 = (0,7,7)$ , $W_3 = (6,5,0)$ . (2 marks)

Cover all zeros: minimum lines needed equals $3$ (size of matrix), so an optimal assignment exists. Assign zeros uniquely: $W_2 \to J_1$ ( $6$ ), $W_1 \to J_2$ ( $11$ ), $W_3 \to J_3$ ( $6$ ). Total $= 6 + 11 + 6 = 23$ hours. (3 marks)

Markers reward correct row and column reductions, the covering-lines test, and a unique zero assignment giving total $23$ .

WACE 2024-style5 marks

Explain why an assignment problem is modelled as a bipartite graph, and describe the first two steps of the Hungarian algorithm used to minimise total cost.

Show worked answer →

The two distinct sets being matched make the graph bipartite.

An assignment problem matches one set (workers) to a separate set (jobs), with each worker doing exactly one job and each job done by exactly one worker. The two disjoint sets with edges only between them make it a bipartite graph, and the goal is a minimum-cost perfect matching. (2 marks)

Step 1: subtract the smallest entry in each row from every entry in that row (row reduction). Step 2: subtract the smallest entry in each column from every entry in that column (column reduction), creating zeros that mark candidate assignments. (3 marks)

Markers reward the bipartite-matching description and the row-then-column reduction steps.