|
I |
II |
III |
IV |
---|
A |
8 |
26 |
17 |
11 |
B |
13 |
28 |
4 |
26 |
C |
38 |
19 |
18 |
15 |
D |
19 |
26 |
24 |
10 |
Step 1:Identity the minimum element in each row and subtract it from every element of that row
|
I |
II |
III |
Iv |
A |
0 |
18 |
9 |
3 |
B |
9 |
24 |
0 |
22 |
C |
23 |
4 |
3 |
0 |
D |
9 |
16 |
14 |
0 |
Step 2:Identity the minimum element in each column and subtract it from every element of that column
|
I |
II |
III |
Iv |
A |
0 |
14 |
9 |
3 |
B |
9 |
20 |
0 |
22 |
C |
23 |
0 |
3 |
0 |
D |
9 |
12 |
14 |
0 |
Step 3:Cover all 0's with a minimum number of lines
|
I |
II |
III |
Iv |
A |
0 |
14 |
9 |
3 |
B |
9 |
20 |
0 |
22 |
C |
23 |
0 |
3 |
0 |
D |
9 |
12 |
14 |
0 |
Step 4: (Optimal Assignment) There are 4 lines required.The 0's covers an optimal assignment.
|
I |
II |
III |
Iv |
A |
0 |
14 |
9 |
3 |
B |
9 |
20 |
0 |
22 |
C |
23 |
0 |
3 |
0 |
D |
9 |
12 |
14 |
0 |
This corresponds to the following optimal assignment in original cost matrix
|
I |
II |
III |
Iv |
A |
8 |
26 |
17 |
11 |
B |
13 |
28 |
4 |
26 |
C |
38 |
19 |
18 |
15 |
D |
39 |
26 |
24 |
10 |
The total cost of assignment=A(I) +B(III)+C(II)+D(Iv)=8+19+4+10=41
Hence,Option(B) A(I) B(III) C(II) D(Iv)is the correct choice here.
References:http://www.universalteacherpublications.com/univ/ebooks/or/Ch6/hungar.htm
http://www.math.harvard.edu/archive/20_spring_05/handouts/assignment_overheads.pdf
http://www.hungarianalgorithm.com/solve.php (Online Calculator)