Solve assignment problems using the Hungarian algorithm to allocate agents to tasks for minimum total cost.

What this dot point is asking

You must set up a cost matrix and apply the Hungarian algorithm to find the minimum-cost allocation.

The assignment set-up

You have $n$ agents and $n$ tasks, with a cost (or time) for each agent doing each task, recorded in a square cost matrix. The goal is a one-to-one allocation: each agent gets exactly one task and each task exactly one agent, with the smallest possible total cost.

The Hungarian algorithm

The method works by creating zeros that mark cost-free choices.

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: cover all zeros using the fewest horizontal and vertical lines.
4. Test: if the number of lines equals the matrix size $n$, an optimal assignment exists among the zeros. If fewer, adjust and repeat.
5. Adjust: find the smallest uncovered entry, subtract it from all uncovered entries, add it to entries covered twice, then re-cover.

Why row and column reduction works

Subtracting a constant from every entry of a row does not change which assignment is cheapest, because every complete allocation uses exactly one entry from that row, so all allocations lose the same amount. The same holds for columns. Reduction therefore preserves the optimal assignment while creating zeros that mark the locally cheapest choices. The algorithm then hunts for a set of these zeros, one in each row and column - an allocation costing zero in the reduced matrix, which corresponds to the minimum-cost allocation in the original. Understanding this invariance is what makes the procedure more than a recipe.

Unbalanced and infeasible problems

Two practical adjustments arise often. When the numbers of agents and tasks differ, the matrix is not square, so a dummy row or column of zeros is added to balance it; the agent or task matched to a dummy is simply left unassigned. When a particular agent cannot do a particular task, that cell is given a prohibitively large cost so the algorithm never selects it. Both adjustments let the standard square-matrix method handle real situations, and SACE questions frequently test whether you can set up the matrix correctly before reducing.

Reading off the allocation and cost

Once the zeros allow one selection per row and column, those zeros give the assignment. Read the total cost from the original matrix, not the reduced one.

Maximisation problems

If the table gives profits or scores to be maximised, first convert to a minimisation problem by subtracting every entry from the largest entry in the table, then run the Hungarian algorithm as normal. The resulting allocation maximises the original total.