One-to-one task allocation and minimum cost; Hungarian row/column reduction, zero cover and uncovered-value adjustment; Maximum-profit conversion; Non-square arrays/dummy rows or columns; Multiple optima and model assumptions
Example 1
Cost table, rows workers and columns jobs: [[4,9,12],[6,2,9],[10,7,4]]. Assign each worker one different job. Find the minimum total cost.
Show worked answer
Answer: 10
- Choosing each diagonal entry gives the sum of the three row minima, with no job repeated. This attains a lower bound and is optimal.
Example 2
For cost row [4,9,12], subtract its row minimum as in the Hungarian method. What is the final entry of the reduced row?
Show worked answer
Answer: 8
- Subtract a from all entries, obtaining [0,5,8]. Row reductions do not change which complete assignment is optimal.
Example 3
There are 3 workers and 4 jobs in a one-job-per-worker minimum-cost assignment. How can a square Hungarian table be formed?
Show worked answer
Answer: Add a dummy worker with zero cost for each job
- The dummy worker absorbs the one unassigned job without changing real assignment costs.