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 1^{st}
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 2^{nd}, 3^{rd}, 4^{th}......by
the same process.
Step 3: Find
the smallest entry in 1^{st} column. Now subtract this entry from other
entries of the same column and do this step for all other columns i.e. for 2^{nd},
3^{rd}, 4^{th}......
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 1^{st} 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 2^{nd},
3^{rd}, 4^{th }rows. i.e. Subtract
75 from Row 1, 35 from Row 2, 90 From Row 3, and 45 from Row 4.
9075=15

7575=0

7575=0

8075=5

3535=0

8535=50

5535=20

6535=30

12590=35

9590=5

9090=0

10590=15

4545=0

11045=65

9545=50

11545=70

15

0

0

5

0

50

20

30

35

5

0

15

0

65

50

70

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

00=0

00=0

55=0

00=0

500=50

200=20

305=25

350=35

50=5

00=0

155=10

00=0

650=65

500=50

705=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.
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

505=45

20

255=20

35

55=0

0

105=5

0

655=60

50

655=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

4520=25

2020=0

2020=0

35+20=55

0

0

5

0

6020=40

5020=30

6020=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

25


0


55


0

5



40

30

40

So the solution is,
Trucks/Stores

A

B

C

D


1

90

75

75



2

35

85


65


3

125


90

105


4


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


5

0


0

25

0



55

0


5



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.
*****
*****
0 blogger:
Post a Comment