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.
4 Comments