Example 1: Hungarian method
A building firm possesses four cranes each of which has a distance(km) from four different construction sites as shown in the table:
Construction site #
   1  2  3  4 
Crane #  1   90  75  75  80 
2   35  85  55  65 
3   125  95  90  105 
4   45  110  95  115 
Place the cranes (one for each construction sites) in such a way that the overall distance required for the transfer is as small as possible.
Solution:
The cost matrix is

90  75  75  80  
35  85  55  65 
125  95  90  105 
45  110  95  115  

  
1. step: 
From each row, we find the row minimum 
and subtract it from all entries on that row.  

=>   
15  0  0  5  
0  50  20  30 
35  5  0  15 
0  65  50  70  

  
2. step: 
From each column, we find the column minimum 
and subtract it from all entries on that column.  

=>   
15  0  0  0  
0  50  20  25 
35  5  0  10 
0  65  50  65  

  
3. step: 
We draw lines across rows and columns in such a way that all zeros are covered and that the minimun 
number of lines have been used
(in this case lines across the 1st and the 3rd row and across the 1st column).
 

4. step: A test for optimality;
If the number of lines just drawn is n (number of rows of the cost matrix), we are done.
If the number of lines < n, we go to step 5.
Now the number of lines is 3 < n = 4.
5. step:
We find the smallest entry which is not covered by the lines, which in this case is the (2,3)entry 20, and subtract
it from each entry not covered by the lines. We also add it to each entry which is covered by a vertical and a horizontal line.
Now we can go back to step 3.
=>   
35  0  0  0  
0  30  0  5 
55  5  0  10 
0  45  30  45  

  
3. step: 
Draw lines across zeros 
(1st and 3rd column, 1st row)  

  
4. step: 
Number of lines = 3 < n 
=> Step 5 and then Step 3 (smallest entry = 5)  

=>   
40  0  5  0  
0  25  0  0 
55  0  0  5 
0  40  30  40  

  
3. step: 
Draw lines across zeros 
(1st and 3rd column, 1st row)  

  
4. step: 
Number of lines = 4 = n 
=> We are done.  

0's positions determine the possible combinations. We have two choices.
Solution:
Crane1  Constuction site4, Crane2  Constuction site3, Crane3  Constuction site2, Crane4  Constuction site1 ( => overall distance 275 km)
OR
Crane1  Constuction site2, Crane2  Constuction site4, Crane3  Constuction site4, Crane4  Constuction site1 ( => overall distance 275 km)
Go back to theory