What is 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.

§-Syllabus dot point

WAMathematics ApplicationsSyllabus dot point

How do we allocate workers to tasks for the lowest total cost?

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

How to model an allocation as a bipartite matching, apply the Hungarian algorithm of row and column reduction and covering zeros, and read off the optimal minimum-cost assignment.

Generated by Claude Opus 4.88 min answerUpdated 2026-06-02

Reviewed by: AI editorial process; not yet individually human-reviewed

Have a quick question? Jump to the Q&A page

Jump to a section

What this dot point is asking
Modelling the problem
The Hungarian algorithm
Unbalanced problems
Maximisation problems

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.

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 optimal cost is found by reading the original-matrix costs of the chosen zero positions.

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.

Exam-style practice questions

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

WACE 20227 marksThree 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 20245 marksExplain 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.