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 the reductions preserve the optimal allocation

It is natural to wonder why subtracting a constant from a whole row or column does not change which allocation is best. The reason is that every valid one-to-one assignment uses exactly one entry from each row and one from each column. Subtracting a constant from a row therefore reduces the total of every possible assignment by the same constant, so the relative ordering of assignments is untouched and the cheapest assignment stays cheapest. The same holds for column reduction. This is why the algorithm can drive entries down to zeros and find the optimum among the zeros, then recover the true cost from the original matrix.

Handling unbalanced and maximising problems

Two variations appear in exams. If the cost matrix is not square (more tasks than workers, say), you add a dummy row or column of zeros to make it square; the dummy agent or task contributes zero cost and is ignored when reading the final allocation. If the problem asks to maximise rather than minimise (for example, maximising total profit or satisfaction), convert it to a minimisation by subtracting every entry from the largest entry in the matrix, then run the Hungarian algorithm as usual. Recognising which variation you face, and converting before reducing, is essential because the standard steps only minimise.

Reading off and verifying the final cost

Once the minimum number of covering lines equals the matrix size, an optimal assignment of zeros exists. Choose zeros so that there is exactly one in each row and each column, starting with any row or column that contains a single zero to avoid clashes. Then, and this is the step students most often miss, compute the total cost by adding the corresponding entries from the original cost matrix, not the reduced zeros. Stating the assignment in words (which worker does which task) and the original-matrix total gives the marker both the solution and its verifiable cost.

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.