Model an allocation problem with a cost matrix and a bipartite graph, apply the Hungarian algorithm using row reduction, column reduction and line covering to find the minimum-cost one-to-one allocation

What this dot point is asking

VCAA wants you to solve an allocation (assignment) problem: matching workers to tasks one-to-one so the total cost or time is as small as possible. You set it up as a cost matrix (and recognise the underlying bipartite graph), then apply the Hungarian algorithm: reduce rows, reduce columns, cover the zeros with the fewest lines, adjust if needed, and read off the optimal assignment. This is the matching tool of the Networks module.

Setting up the cost matrix

Each row is a worker, each column a task, and each entry the cost (or time) of that worker doing that task. The bipartite graph has workers on one side and tasks on the other, with weighted edges. The goal is a perfect matching of least total weight. The matrix must be square; if it is not, a dummy row or column of zeros is added.

The Hungarian algorithm steps

1. Row reduction: subtract the smallest entry in each row from every entry in that row.
2. Column reduction: subtract the smallest entry in each column from every entry in that column.
3. Cover the zeros: draw the fewest horizontal and vertical lines that cover all zeros.
4. Test: if the number of lines equals the matrix size, an optimal assignment exists; jump to reading it off. Otherwise continue.
5. Adjust: find the smallest uncovered entry, subtract it from every uncovered entry, and add it to every entry covered by two lines. Return to step 3.

Why this matters for the exams

Allocation questions reward a disciplined run through the Hungarian steps and a final cost read from the original matrix. Markers check the reductions, the line-covering test, and a valid one-to-one assignment. The problem is the matching counterpart to maximum flow and critical path analysis, completing the decision-mathematics toolkit of the Networks module.