edited by
6,402 views
2 votes
2 votes

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}$

  1. $\text{(A)-(I), (B)-(II), (C)-(III), (D)-(IV)}$
  2. $\text{(A)-(I), (B)-(III), (C)-(II), (D)-(IV)}$
  3. $\text{(A)-(I), (B)-(III), (C)-(IV), (D)-(II)}$
  4. $\text{(A)-(I), (B)-(IV), (C)-(II), (D)-(III)}$
edited by

3 Answers

Best answer
6 votes
6 votes
  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)

selected by
Answer:

Related questions

3 votes
3 votes
1 answer
1
2 votes
2 votes
1 answer
4
go_editor asked Jul 7, 2016
2,936 views
The feasible region represented by the constraints $x_1 - x_2 \leq 1, x_1 + x_2 \geq 3, x_1 \geq 0, x_2 \geq 0$ of the objective function Max $Z=3x_1 + 2x_2$ isA polygonU...