Hungarian Method to solve Assignment Problem

Hungarian Algorithm to solve Assignment Problem

The Hungarian algorithm of assignment is an efficient algorithm of finding an optimal solution to the assignment problem. Hungarian method is applicable to a Balanced Assignment problem, i.e., number of rows equals to the number of columns of an assignment problem.

Step by Step procedure

Hungarian algorithm of assignment 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.

Endnote

In this tutorial, you learned about step by step procedure of Hungarian Algorithm to solve assignment problem.

To learn more about Assignment problems please refer to the following tutorials:

Assignment Problems

Read step by step solution

Let me know in the comments if you have any questions on Hungarian Algorithm to solve Assignment problems and your thought on this article.