UGC NET CSE | June 2012 | Part 3 | Question: 62

Question

The optimal solution of the following assignment problem using Hungarian method is

$\begin{array}{|l|l|l|l|} \hline \text{ } & \text{I} & \text{II} & \text{III} & \text{IV} \\\hline \text{A } & \text{8} & \text{26} & \text{17} & \text{11} \\\hline  \text{B} & \text{13} & \text{28} & \text{4} & \text{26}  \\\hline  \text{C} & \text{38} & \text{19} & \text{18} & \text{15} \\\hline   \text{D} & \text{19} & \text{26} & \text{24} & \text{10} \\\hline  \end{array}$

• A. $\text{(A)-(I), (B)-(II), (C)-(III), (D)-(IV)}$
• B. $\text{(A)-(I), (B)-(III), (C)-(II), (D)-(IV)}$
• C. $\text{(A)-(I), (B)-(III), (C)-(IV), (D)-(II)}$
• D. $\text{(A)-(I), (B)-(IV), (C)-(II), (D)-(III)}$

Answer 1

	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)

Comments

Hi Leen tell me seriously how much time did you take to solve it .....Great efforts

---

Hello shekhar chauhan this topic was new for me. first i read about it from different-2 sources.After i solved it on white paper then i made this content.I took almost half an hour on it. i think that was too much

---

this topic from which subject?

Answer 2

ANS IS B

Answer 3

check by options