State the algorithm of solving an Assignment problem

5

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!

5

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