# Using The Hungarian Algorithm to Find the Least Cost Allocation

It's only fair to share...

The Hungarian algorithm provides a method of allocating workers to tasks, with each worker doing one tak, so that the total cost of doing all the tasks is minimized.

The steps in the algorithm are:

1. Find the reduced cost matrix.

2. Determine the minimum number of straight lines – horizontal or vertical – which will cover all the zeros in the reduced cost matrix.

3. If you cannot cover all the zeros in anmatrix with fewer thanlines, then you have found an optimal solution.

4. If you can cover all the zeros in anmatrix with fewer thanlines – vertical or horizontal – the solution can be improved.

5. Draw in these lines and look for the smallest uncovered element

6. Add x to the element in each covered row and column, adding it twice to any element crossed by vertical and horizontal lines.

7. Subtract x from every elemt of the matrix.

8. Repeat 2 to 7 until an optimal solution is found.

For example, consider the cost matrix below, which shows the costs of workers Andrew, Boris and Charles to do tasks 1, 2 and 3.

 Task 1 Task 2 Task 3 Andrew 30 45 12 Boris 40 39 80 Charles 64 36 28
1. Subtract the smallest element in each row from all the entries in that row. Subtract 12 from each element in row 1, 39 from each element in row 2 and 28 from each element in row 3 to give

 Task 1 Task 2 Task 3 Andrew 18 33 0 Boris 1 0 41 Charles 36 8 0

Subtract the smallest element in each column from all the entries in that column. Subtract 1 from each element in column 1, 0 from each element in row 2 and 0 from each element in row 3 to give

 Task 1 Task 2 Task 3 Andrew 17 33 0 Boris 0 0 41 Charles 35 8 0
1. All the zeros in the last matrix above can be covered by two lines – a horizontal line in the second (Boris’s) row and a vertical line in the third column (Task 3).
 Task 1 Task 2 Task 3 Andrew 17 33 0 Boris 0 0 41 Charles 35 8 0
2. Since all the zeros can be covered by two lines, the solution is not optimal.
3. The solution can be improved.
4. The smallest uncovered element is 8.
5. Add 8 to each covered element (and twice to elemts crossed by vertical and horizontal lines) to give the matrix
 Task 1 Task 2 Task 3 Andrew 17 33 8 Boris 8 8 57 Charles 35 8 8
1. Subtract 8 from every element.
 Task 1 Task 2 Task 3 Andrew 9 25 0 Boris 0 0 49 Charles 27 0 0
1. Now we need three lines to cover all the zeros, as shown.
 Task 1 Task 2 Task 3 Andrew 9 25 0 Boris 0 0 49 Charles 27 0 0

The solution is now optimal, with Andrew doing task 3, Boris doing task 1 and Charles doing task 2. The cost is found by referring to the original cost matrix: 12+40+36=88.