Explain ‘Hungarian method’ of solving assignment problem


0

Whenever the pay off matrix of any assignment problem is not a square matrix i.e. no. of rows not equal to number of columns the problem is called unbalanced assignment problem. Hungarian method of solving such problem is as follows:

1.         Insert row or column with all values zero such that pay off matrix become square matrix.

2.         Row minima : Subtract smallest element of each row from corresponding element of that row.

3.         Column minima : Subtract smallest element of each column from corresponding element of that column.

4.         Draw minimum number of vertical and horizontal lines which can cover all zeros of pay off matrix.

5.         Total number of lines drawn is not equal to size of pay off matrix then select smallest uncovered number, subtract it from every uncovered number, add it to point of intersection and no change in other element. Repeat this step till
we get optimum matrix.

6.         This second phase of solution. Select any row or column with single zero and make allocation cancel out other zeros in corresponding row and column.

 


Like it? Share with your friends!

0
MT UVA BMS

MT UVA- University, Vocational and Affiliated Education for BMS

One Comment

Facebook comments:

Choose A Format
Personality quiz
Series of questions that intends to reveal something about the personality
Trivia quiz
Series of questions with right and wrong answers that intends to check knowledge
Poll
Voting to make decisions or determine opinions
Story
Formatted Text with Embeds and Visuals
List
The Classic Internet Listicles
Countdown
The Classic Internet Countdowns
Open List
Submit your own item and vote up for the best submission
Ranked List
Upvote or downvote to decide the best list item
Meme
Upload your own images to make custom memes
Video
Youtube, Vimeo or Vine Embeds
Audio
Soundcloud or Mixcloud Embeds
Image
Photo or GIF
Gif
GIF format