Whenever the pay off matrix of any assignment problem is not a square matrix i.e.
no. of rows not equal to number of columns the problem is called unbalanced
assignment problem. Hungarian method of solving such problem is as follows :
1. Insert row or column with all values zero such that pay off matrix become
square matrix.
2. Row minima : Subtract smallest element of each row from corresponding
element of that row.
3. Column minima : Subtract smallest element of each column from
corresponding element of that column.
4. Draw minimum number of vertical and horizontal lines which can cover all
zeros of pay off matrix.
5. Total number of lines drawn is not equal to size of pay off matrix then select
smallest uncovered number, subtract it from every uncovered number, add it
to point of intersection and no change in other element. Repeat this step till
we get optimum matrix.
6. This second phase of solution. Select any row or column with single zero and
make allocation cancel out other zeros in corresponding row and column.
50 Comments