An assignment problem involves optimally matching a set of agents (workers, machines, tasks) to a set of jobs in a one-to-one fashion to minimise (or maximise) total cost, time, or distance.
This is represented as a cost matrix $C$ where $c_{ij}$ = cost of assigning agent $i$ to job $j$.
Goal: Find the minimum-cost perfect matching.
Row reduction: subtract the minimum entry of each row from all entries in that row.
Column reduction: subtract the minimum entry of each column from all entries in that column.
Cover zeros: find the minimum number of horizontal/vertical lines that cover all zeros.
Optimality check: if the number of lines equals $n$ (matrix dimension), an optimal assignment exists. Identify the zeros forming an assignment (one zero per row, one per column).
If not optimal: find the smallest uncovered entry $k$. Subtract $k$ from all uncovered entries, add $k$ to all doubly-covered entries. Repeat from step 3.
Cost matrix (time in hours to complete task):
$$C = \begin{pmatrix} 9 & 2 & 7 \ 3 & 6 & 3 \ 5 & 8 & 1 \end{pmatrix}$$
Step 1 — Row reduction (subtract row min: 2, 3, 1):
$$\begin{pmatrix} 7 & 0 & 5 \ 0 & 3 & 0 \ 4 & 7 & 0 \end{pmatrix}$$
Step 2 — Column reduction (subtract col min: 0, 0, 0 — already done):
$$\begin{pmatrix} 7 & 0 & 5 \ 0 & 3 & 0 \ 4 & 7 & 0 \end{pmatrix}$$
Step 3 — Cover zeros: Row 2 covers zeros in columns 1 and 3; Column 2 covers zero in row 1. Lines needed = 2 < 3, so not optimal.
Smallest uncovered entry = 4. Subtract 4 from uncovered; add 4 to doubly-covered:
$$\begin{pmatrix} 3 & 0 & 1 \ 0 & 7 & 0 \ 0 & 7 & 0 \end{pmatrix}$$
Re-cover. Now 3 lines suffice. Assignment: Worker 1 → Job 2, Worker 2 → Job 1, Worker 3 → Job 3.
Original costs: \$2 + 3 + 1 = 6$ hours (minimum).
To maximise: subtract all entries from the maximum entry, then apply the minimisation algorithm.
APPLICATION: The Hungarian algorithm is used in workforce scheduling, ride-sharing assignment, logistics routing, and tournament scheduling.
EXAM TIP: In VCAA exams, the cost matrix is usually \$3 \times 3$ or \$4 \times 4$. Show each step clearly — row reduction table, column reduction table, line covers, and the final assignment. Partial marks are awarded at each stage.
