The Gateway to Computer Science Excellence

+2 votes

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 |

+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)**

+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 much

52,345 questions

60,510 answers

201,925 comments

95,352 users