State the algorithm of solving an Assignment problem


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


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.


Like it? Share with your friends!

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 !!


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
Voting to make decisions or determine opinions
Formatted Text with Embeds and Visuals
The Classic Internet Listicles
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
Upload your own images to make custom memes
Youtube, Vimeo or Vine Embeds
Soundcloud or Mixcloud Embeds
Photo or GIF
GIF format