Hungarian Method to solve Assignment Problem

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.