Previous section

## 1.2. Hungarian method

** A cost matrix**
| *c*_{11 } | *c*_{12 } | *c*_{13 } | *···* | *c*_{1n } | | *= C* | |

*c*_{21 } | *c*_{22 } | *c*_{23 } | *···* | *c*_{2n } |

: | : | : | | : |

*c*_{n1 } | *c*_{n2 } | *c*_{n3 } | *···* | *c*_{nn } |

For example: *c*_{ij } = is the wage paid to the *i*th worker
for the *j*th task. We want to hire *n* workers to complete *n* tasks with minimun costs, i.e.,
we have to pick exactly one element from each row and from each column of the cost matrix *C*
in such a way that the sum of these elements is as small as possible.

** Hungarian method: the algorithm**

1. Subtract the entries of each row by the row minimum.

=> Each row has at least one zero

=> All entries are positive or zero.

2. Subtract the entries of each column by the column minimum.

=> Each row and each column has at least one zero.

3. Select rows and columns
across which you draw lines, in such a way that all the zeros are covered and that no more lines have been drawn than necessary.

4. A test for optimality.

(i) If the number of the lines is *n*, choose a combination from the
modified cost matrix in such a way that the sum is zero.

(ii)
If the number of the lines is * < n*, go to 5.

5. Find the smallest element which is not covered by any of the lines. Then subtract it from each entry which is not covered by the lines and add it to each entry which is covered by a vertical and a horizontal line. Go back to 3.

If we have, instead of a minimization problem, a maximization problem, multiply the matrix *C* by -1
and proceed as above. If *C* is not a
square matrix
(there are more tasks than workers or conversely),
we have to augment *C* into a square matrix by adding zero rows or columns.

** Example 1: Hungarian method**

Exercises: E1

Previous section

Contents

Next section