Hungarian Method to solve Assignment Problem
For obtaining an optimal assignment, Hungarian method involves following steps :
Step 1
Subtract the minimum of each row of the cost matrix,from all the elements of respective rows.
Step 2
Subtract the minimum of each column of the modified cost matrix, from all the elements of respective columns.
Step 3
Then draw the minimum number of horizontal and vertical line to cover all the zeros in the modified cost matrix.
Let the number of lines be $N$.
- If $N=n$, the number of rows (columns) of given cost matrix, then an optimal assignment can be made. Go to Step 6.
- If $N<n$, then go to next step.
Step 4
Determine the smallest element in the matrix, not covered by the $N$ lines. Subtract this smallest element from all the uncovered elements and add the same element at the intersection of horizontal and vertical lines. And obtain the second modified matrix.
Step 5
Repeat Steps 3 and 4 until minimum number of lines become equal to the number of rows (columns) of the given matrix i.e. $N =n$.
Step 6
Examine the row successively until a row-wise exactly single zero is found, mark this zero by $\square$ to make the assignment and mark cross $(\times)$ over all zeros in that column. Continue in this manner until all the rows have been examined. Repeat the same procedure for columns also.
Step 7
Repeat the Step 6 successively until one of the following situations arise :
- if no unmarked zero is left, the process ends; or
- if there lie more than one of the unmarked zeros in any column or row, then mark $\square$ one of the unmarked zeros arbitrarily and cross over all zeros lying in that row or column. Repeat the process until no unmarked zero is left in the matrix.
Step 8
Thus, in each row and in each column exactly one marked $\square$ zero is obtained. The assignment corresponding to these marked zeros will give an optimal assignment.