Try each one on paper first, then check a single step. That is worth far more than reading a finished solution.
Example 1 — a full Hungarian algorithm
Assign three workers to three jobs at minimum cost, given the matrix 965248731.
- 1Row reduction: subtract the row minima 2, 3, 1.
- 2734017500Every row now contains a zero.
- 3Column reduction: the column minima are now 3, 0, 0.
- 4401017500Every column now contains a zero too.
- 5Cover the zeros: column 2, row 2 and column 3 — three lines, and n=3.So an optimal assignment exists among the zeros.
- 6Row 1 has one zero: W1→J2. Row 3 has one zero: W3→J3. That leaves W2→J1.Start where the choice is forced.
- 7Total from the ORIGINAL matrix: 2+6+1=9.Never total the reduced matrix.
Example 2 — converting a maximisation
A profit matrix has entries ranging up to 20. How is the Hungarian algorithm applied?
- 1The algorithm minimises, so the matrix must be converted.
- 2Subtract every entry from 20, the largest entry in the whole matrix.Not from each row's largest — that would distort comparisons between rows.
- 3The largest profits become the smallest values.A profit of 20 becomes 0; a profit of 5 becomes 15.
- 4Run the algorithm on the converted matrix as a minimisation.
- 5Read the total from the ORIGINAL profit matrix.The assignment is right; the converted numbers are not the answer.
Example 3 — an unbalanced problem
Five jobs must be shared among four workers, one each. How is this handled?
- 1The Hungarian algorithm needs a square matrix.Here it is 4 × 5.
- 2Add a dummy fifth worker.A row, since workers are the rows.
- 3Fill the dummy row with zeros.So it contributes nothing to any total.
- 4Run the algorithm on the 5 × 5 matrix.
- 5The job assigned to the dummy worker is the one left undone.Say so explicitly rather than reporting the dummy as real.