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):
Step 1 — Row reduction (subtract row min: 2, 3, 1):
Step 2 — Column reduction (subtract col min: 0, 0, 0 — already done):
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:
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.
