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:

Find the reduced cost matrix.

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

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

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

Draw in these lines and look for the smallest uncovered element

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

Subtract x from every elemt of the matrix.

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 

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 
 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
 Since all the zeros can be covered by two lines, the solution is not optimal.
 The solution can be improved.
 The smallest uncovered element is 8.
 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 
 Subtract 8 from every element.
Task 1 
Task 2 
Task 3 

Andrew 
9 
25 
0 
Boris 
0 
0 
49 
Charles 
27 
0 
0 
 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.
Comments are closed.