Hungarian Method

Five step Procedure:

1.

Subtract the smallest entry in each row from all the entries of its row. $\left[ \begin{array}{rrr} 25 & 44 & 36 \\ 28 & 41 & 40 \\ 23 & 50 & 35 \end... ...in{array}{rrr} 0 & 19 & 11 \\ 0 & 13 & 12 \\ 0 & 27 & 12 \end{array}\right]$

2.

Subtract the smallest entry in each column from all the entries of its column. $\left[ \begin{array}{rrr} 0 & 19 & 11 \\ 0 & 13 & 12 \\ 0 & 27 & 12 \end{ar... ... \begin{array}{rrr} 0 & 6 & 0 \\ 0 & 0 & 1 \\ 0 & 14 & 1 \end{array}\right]$

3.

Cover all zero entries by drawing line through appropiate rows and columns, use minimal number of lines.

$\left[ \begin{array}{rrr} 0 & 6 & 0 \\ 0 & 0 & 1 \\ 0 & 14 & 1 \end{array}\right] \Longrightarrow$ 3 minimal number of lines that cover all zeros. We are done!

4.

If the minimal number of lines is 3 ( or n for an n x nand optimal a ssignment of zereod is possible and we are done. An optimal assignment obtained by selecting a zero entry from each row.

5.

If minimal number of lines is less than 3 ( or less than n, for an n x n matrix), go to step 5.

6.

Consider the entries that are not covered by any line. Subtract the smallest of these uncovered entries from all uncovered entries, then add it to all entries coved by a horizontal and a vertical line. Return to Step 3.