State the algorithm of solving an Assignment problem


0

State the algorithm of solving an Assignment problem.(Apr 2002) (Apr 2005)

Advertisement

 

Algorithm of solving an Assignment problem is as follows –

1] Check if the problem is Balanced or Unbalanced. If no. of rows = no. of columns, problem is balanced. If unbalanced, take Dummy row or column as required. All values for Dummy =0.

2] Check if the problem is of Minimization type (cost) or Maximization type (profit). If Maximization, convert to Minimization by finding Regret matrix.

3] Do row minima. Find minimum value in each row and subtract it from all values in that row.

4] Do column minima. Find minimum value in each column and subtract it from all values in that column.

5] Check for optimality. Draw minimum no. of straight lines to cover all zeroes in the matrix. If Minimum no. of lines= Size of matrix (e. g. 4 x 4, 5 x 5 etc.) then solution is optimal. If not, do iteration.

6] Iteration –   A} Find minimum uncovered value in the matrix.

B} Subtract it from all uncovered values.

C} Add it to all double covered values.

D} Other values remain same.

7] Again check for optimality. Continue procedure till we get optimal solution.

 

Advertisement
The following two tabs change content below.

Score Tutorial

S’COrE Education is a professional coaching institute to coach for new generation courses. S’COrE has highly experienced faculty with enormous experience and achievement in teaching and industry. We teach each subject in such a manner that even complicated subject feels simple. This helps student to S’COrE-the-Max. Since 1998 S’COrE had university toppers accross courses and subjects. Once you are our student you will also believe S’COrE - the - Best !!

Like it? Share with your friends!

0
Score Tutorial
S’COrE Education is a professional coaching institute to coach for new generation courses. S’COrE has highly experienced faculty with enormous experience and achievement in teaching and industry. We teach each subject in such a manner that even complicated subject feels simple. This helps student to S’COrE-the-Max. Since 1998 S’COrE had university toppers accross courses and subjects. Once you are our student you will also believe S’COrE - the - Best !!

4 Comments

Ask Us On WhatsApp
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