Hungarian Method to solve Assignment Problem
For obtaining an optimal assignment, Hungarian method involves following steps :
Subtract the minimum of each row of the cost matrix,from all the elements of respective rows.
Subtract the minimum of each column of the modified cost matrix, from all the elements of respective columns.
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.
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.
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$.
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.
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.
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.