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

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

=>      15005
0502030
355015
0655070
      2. step:
From each column, we find the column minimum
and subtract it from all entries on that column.
=>      15000
0502025
355010
0655065
      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.

=>      35000
03005
555010
0453045
      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)

=>      40050
02500
55005
0403040
      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