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

Hungarian Method