The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+2 votes
1.4k views

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

  I II III IV
A 8 26 17 11
B 13 28 4 26
C 38 19 18 15
D 19 26 24 10
  A B C D
A I II III IV
B I III II IV
C I III IV II
D I IV II III
in IS&Software Engineering by Veteran (98.4k points)
recategorized by | 1.4k views

3 Answers

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

by Boss (40.8k points)
selected by
+1
Hi Leen tell me seriously how much time did you take to solve it .....Great efforts
+1

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 muchfrown

0
this topic from which subject?
+2 votes

ANS IS B

by Boss (48.2k points)
0 votes

check by options

by (407 points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
49,845 questions
54,785 answers
189,431 comments
80,452 users