Step 1:
First, check whether the number of rows is equal to the number of columns. If it is equal, then the problem is a balanced one. If this is not equal, then we have to add one dummy row or column to make it a balanced one. And for that, we have to add zero to each dummy row or column as per the case.
Step 2:
Subtract the minimum value or least value that is present in each row from all other elements (cells) of the same row.
Step 3:
Subtract the minimum value or least value that is present in each column from all other elements of the same column.
Step 4:
Drawthe minimum numbers of straight lines, both horizontally and vertically to cover all zeros in the cost matrix. Following steps should be followed while performing this operation:
- Select a row that contains exactly one uncovered zero to draw a vertical line. Repeat the step until there will be no zero in any of the rows.
- Select a column that contains exactly one uncovered zero to draw a horizontal line. Repeat the step until there will be no zero in any of the columns.
Step 5:
Check whether the numbers of minimum lines covering all zeros is exactly equal to order of matrix or not. If yes, then it is the optimal solution to the assignment problem and there is no need to repeat the same process further.
Step 6:
If this is not reached, then we have to subtract minimum uncovered element from all uncovered elements. Now, add it to all elements at the intersection points of lines that cover the zeros.
Step 7:
Repeat the Step 4, Step 5 and Step 6 until we get the minimum numbers of lines that cover all zeroes will be equal to order of the matrix.
Step 8:
Now, to make the assignment, select a row that contains exactly one unmarked zero. Put a square () there. Draw a vertical line that contains this zero through the column. Repeat this process to cover all such rows.
Select a column that contains exactly one unmarked zero. Put a square () there. Draw a horizontal line that contains this zero through the row. Repeat this process to cover all such columns.
Thus, if any row or column contains more than one zeros, then select any one arbitrarily to pass two lines i.e. horizontally and vertically.
Step 9:
After this, find the optimal value by simply adding the values of final assignment.
Maximization Problems
Step 1:
Rewrite the assignment problem as minimization problem by subtracting all the elements from the largest element.
Step 2:
Follow the similar procedure that is discussed in Step 2 to Step 9.
