Using the Hungarian Algorithm to Find an Allocation That Maximises Profit

• Print

The Hungarian Algorithm is used to find an allocation to minimise cost, but can be adapted to find an allocation that maximises profit. This is done by making each entry in the profit matrix negative and and a fixed number to each element in the resulting table to make it non – zero.

The following table shows the profit made by each worker doing one of four tasks.

Making each entry negative gives the matrix:

The most negative entry is now -16, so add 16 to each entry to give the matrix below.

Subtract the smallest entry in each row from every element in that row to give the matrix below.

Subtracting the smallest element in each column from every entry in that column gives the matrix below.

Three lines are needed to cover all the zeros.

The smallest uncovered element is 2. Add 2 to each element covered by a line, and 4 to each element covered covered twice.

Now subtract 2 from each element, giving the matrix below. Four lines are required to cover all the zeros.

The allocation is:

Worker A does task 2, worker B does task 3, worker C does task 3 and worker D does task 1. The total profit produced is found by referring to the original matrix. It is 6+4+10+16=36.