Assignment Problem: - The Hungarian Method - ObjectiveBooks
Assignment Problem: - The Hungarian Method

Assignment Problem: - The Hungarian Method

The easiest way to solve assignment problem by Hungarian Method is described here step by step with example:-


Step 1: Problem is “n*n” cost matrix to find an optimal assignment. If the matrix is not a square one, make it a square one by adding a dummy row or column and give values 0 to that row or column.

Step 2: Find the smallest entry in 1st row. Now subtract this smallest entry from all the entries of that row including the smallest entry itself.
Do this step for all other rows i.e. for 2nd, 3rd, 4th......by the same process.

Step 3: Find the smallest entry in 1st column. Now subtract this entry from other entries of the same column and do this step for all other columns i.e. for 2nd, 3rd, 4th......

Step 4: Draw horizontal and vertical lines through appropriate rows and columns so that all zero entries of the cost matrix are covered and the minimum number of such lines is used (line should cover maximum zeros).

Step 5: Test for optimality:-
(A)     If minimum number of covering lines is “n”, an optimal assignment of zeros is possible and we are finished.
(B)   If the minimum number of covering lines is less than “n”, an optimal assignment of zeros is not yet possible. In that case proceed to the next step.

Step 6: Determine the smallest entry not covered by any line, subtract this from the rest of all uncovered entries but add to the number having cross line.


Step 7: Repeat step 4 & 5.

Example: A food processing company has four empty trucks located at four different places. The trucks are to be moved to four different stores to carry some product. The distance in kilometer between the trucks and the stores are given in the table below.
   How the trucks should be moved to the stores in order to minimize the total distance traveled by the trucks?
Given Table:-

Trucks/Stores
A
B
C
D
1
90
75
75
80
2
35
85
55
65
3
125
95
90
105
4
45
110
95
115

Solution:-

Step 1: The given problem is “n*n” i.e. 4*4 square matrix. So, proceed to step 2.

Step 2: The smallest entry in the 1st row is 75. So subtract this from the rest all entries of that row and do this step for all other rows i.e. for 2nd, 3rd, 4th rows. i.e. Subtract 75 from Row 1, 35 from Row 2, 90 From Row 3, and 45 from Row 4.

90-75=15
75-75=0
75-75=0
80-75=5
35-35=0
85-35=50
55-35=20
65-35=30
125-90=35
95-90=5
90-90=0
105-90=15
45-45=0
110-45=65
95-45=50
115-45=70

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





Step 3: Now the smallest entry in 1st column is 0. Subtract this entry from other entries of the same column and do this step for all other columns i.e. for 2nd, 3rd, 4th columns. i.e. Subtract 0 from Column 1, 0 from Column 2, 0 from Column 3, and 5 from Column 4.

15-0=15
0-0=0
0-0=0
5-5=0
0-0=0
50-0=50
20-0=20
30-5=25
35-0=35
5-0=5
0-0=0
15-5=10
0-0=0
65-0=65
50-0=50
70-5=65

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






Step 4: Cover all the zeros of the matrix with the minimum number of horizontal or vertical lines.
hungarian method

Step 5: Test for optimality. Since the minimum number of lines is less than 4, we have to proceed to step 6.
Step 6: The smallest entry uncovered by any line is 5. So subtract 5 from the rest of all uncovered entries but add to the number having cross line.
Then repeat step 4 & 5 again.

15+5=20
0
0+5=5
0
0
50-5=45
20
25-5=20
35
5-5=0
0
10-5=5
0
65-5=60
50
65-5=60







Since again the minimum number of lines is less than 4, we have to proceed to step 6.
The smallest entry uncovered by any line is 20. So subtract 20 from the rest of all uncovered entries but add to the number having cross line. Then repeat step 4 & 5 again.

20+20=40
0
5
0
  0
45-20=25
20-20=0
20-20=0
35+20=55
0
0
5
0
60-20=40
50-20=30
60-20=40



Since the minimum number of lines is 4, an optimal assignment of zero is possible and we are finished.
Now for assign the task, we have to put the assignment to the zero which is the least value corresponding to the given question table and also if any row is having only one zero (as any other assignment is not possible in that row), starts from that zero value. Put the assignment to that zero value and proceed for assign further assignment.

Here row 4 is having only 1 zero, so starts from that.

40
0
5
0
0
25
0
0
55
0
0
5
0
40
30
40

So the solution is,

Trucks/Stores
A
B
C
D
1
90
75
75
80
2
35
85
55
65
3
125
95
90
105
4
45
110
95
115


So we should send the trucks as:        Truck 1 to store D
                                                            Truck 2 to store C
                                                            Truck 3 to store B
                                                            Truck 4 to store A

The minimum distance covered is 80+55+95+45 = 275 Kilometres. (Answer)

Also, we have another solution, as there is a possibility of assign to other zero entries in
row 3, row 2 and row 1 as, 


40
0
5
0
0
25
0
0
55
0
0
5
0
40
30
40

So we should send the trucks as:        Truck 1 to store B 
                                                            Truck 2 to store D
                                                            Truck 3 to store C
                                                            Truck 4 to store A

The minimum distance covered is 75+65+90+45 = 275 Kilometres. (Answer)

In both the cases, the minimum distance travelled is same. So, both the solution is optimal and both the solution is considerable.


Note: - By this trial method, we have to choose the solution which gives the minimum value. For problems of 2 or 3 square matrix, i.e. for simple problems. We can get the answer by direct trial method without all these steps which is not possible for bigger problems.

                                                                           *****                                                               

    Blogger Comment
    Facebook Comment