Previous section

1.2. Hungarian method

A cost matrix

c11 c12 c13 ···c1n = C
c21 c22 c23 ···c2n
: : : :
cn1 cn2 cn3 ···cnn

For example: cij = is the wage paid to the ith worker for the jth 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