The Hungarian algorithmEdexcel A-Level Further Maths: Revision notes

In an allocation (assignment) problem, $n$ workers must be matched one-to-one with $n$ tasks so that the total cost is a minimum. The costs form an $n\times n$ cost matrix: the entry in row $i$, column $j$ is the cost of giving worker $i$ task $j$. Checking every one of the $n!$ possible allocations is hopeless for large $n$, so we use the Hungarian algorithm, which finds the optimum in a few steps. The algorithm works because subtracting the same number from every entry in a row, or in a column, changes the total cost of every complete allocation by the same amount, so the best allocation is unchanged.

Step 1: reduce the rows. Subtract the smallest entry in each row from every entry in that row, so each row has at least one zero. Step 2: reduce the columns. Subtract the smallest entry in each column from that column (a column that already contains a zero is unchanged). Always do rows first. Example: the matrix $\begin{pmatrix} 8 & 12 & 8 \\ 10 & 7 & 11 \\ 12 & 3 & 9 \end{pmatrix}$ has row minima $8, 7, 3$, giving $\begin{pmatrix} 0 & 4 & 0 \\ 3 & 0 & 4 \\ 9 & 0 & 6 \end{pmatrix}$. Every column already has a zero, so column reduction changes nothing.

Step 3: test. Draw the minimum number of straight lines (horizontal or vertical) that cover every zero. If the number of lines equals $n$, a complete allocation can be made using only zero entries: go to step 5. Step 4: augment. If fewer than $n$ lines are needed, find the smallest entry not covered by any line. Subtract it from every uncovered entry, and add it to every entry covered by two lines (where a horizontal and a vertical line cross). Entries covered by one line are unchanged. Return to step 3. Step 5: allocate. Choose a complete allocation using only zeros (start with a row or column that has a single zero). Add up the costs in the original matrix. In the example, two lines (row 1 and column 2) cover the zeros; the smallest uncovered entry is $3$, giving $\begin{pmatrix} 0 & 7 & 0 \\ 0 & 0 & 1 \\ 6 & 0 & 3 \end{pmatrix}$. Now Cleo takes column 2, Ben column 1 and Ana column 3: cost $8+10+3=21$.

The algorithm needs a square matrix. If there are more workers than tasks (or the reverse), add a dummy task (or worker) so the matrix is square. Fill the dummy row or column with the same value, normally $0$, so that it does not favour anyone. In the final allocation, whoever is matched with the dummy does not take part, and the dummy adds nothing to the cost. Example: four drivers and three deliveries. Add a dummy delivery with cost $0$ for every driver. Row reduction then changes nothing, because every row already has a zero.

Sometimes a worker cannot do a task (for example, no qualification). Put a very large number $M$ in that cell. It is so big that it can never appear in the least-cost allocation, but you can still apply the algorithm. After reducing, entries such as $M-40$ are still huge and stay out of the allocation. If a different matrix is needed later (for example, the worker is trained and can now do the task at cost $c$), replace $M$ by $c$ and run the algorithm again.

The algorithm finds a minimum. To maximise profit, convert the matrix: subtract every entry from the largest entry of the original matrix, then apply the algorithm to the new matrix. The allocation that minimises the converted total maximises the profit. Read the profit from the original matrix. Example: if the largest profit is $14$, a profit of $5$ becomes $9$ and a profit of $14$ becomes $0$. For $n=3$ the converted total is $3\times14-$(profit), so a converted minimum of $9$ means a maximum profit of $42-9=33$.