Example for the Hungarian Method for Assignment problem.
Cost Table for the Assignment Problem.
Original Cost Table :
columns 1 2 3 4 5
row
1 820 810 840 960 0
2 820 810 840 960 0
3 800 870 M 920 0
4 800 870 M 920 0
5 740 900 810 840 M
Equivalent Cost Table after step 1-2 :
columns 1 2 3 4 5
row
1 80 0 30 120 0
2 80 0 30 120 0
3 60 60 M 80 0
4 60 60 M 80 0
5 0 90 0 0 M
Equivalent Cost Table after step 3 with lines:
columns 1 2 3 4 5
row
1 80 0 30 120 0
2 80 0 30 120 0
3 60 60 M 80 0
4 60 60 M 80 0
5 0 90 0 0 M
Equivalent Cost Table after step 3 :
columns 1 2 3 4 5
row
1 50 0 0 90 0
2 50 0 0 90 0
3 30 60 M 50 0
4 30 60 M 50 0
5 0 120 0 0 M
Equivalent Cost Table after step 3 with lines:
columns 1 2 3 4 5
row
1 50 0 0 90 0
2 50 0 0 90 0
3 30 60 M 50 0
4 30 60 M 50 0
5 0 120 0 0 M
Equivalent Cost Table after step 3 :
columns 1 2 3 4 5
row
1 50 0* 0 90 30
2 50 0 0* 90 30
3 0* 30 M 20 0
4 0 30 M 20 0*
5 0 120 0 0* M
This table has several ways of making a complete assignments to zero element positions, including the one shown by the five stared(*) .
The resulting total cost is
Z = 810 + 840 + 800 + 0 + 840 = 3,290