Question 1 Foundation
What is the first step of the Hungarian algorithm?
Answer. Subtract the smallest entry in each row from every entry in that row.
This guarantees at least one zero in every row without changing which assignment is optimal.
Assignment Models
Original questions written at exam standard. Work each one before you open the solution.
Difficulty
Question 2 Foundation
Why does subtracting a constant from a row not change the optimal assignment?
Answer. Every possible assignment uses exactly one entry from that row, so all totals fall by the same amount.
The ordering of the totals is unchanged, so the best assignment stays the best.
Question 3 Standard
How many covering lines are needed before an optimal assignment can be read off a matrix?
Answer.
The minimum number of lines covering all zeros must equal . Fewer means another adjustment step is required.
Question 4 Standard
How is a maximisation problem converted for the Hungarian algorithm?
Answer. Subtract every entry from the largest entry in the whole matrix.
The largest profits become the smallest costs, so minimising the new matrix maximises the original.
Question 5 Stretch
Six jobs are to be shared among four workers. How is the matrix made square?
Answer. Add two dummy worker rows filled with zeros.
The two jobs assigned to the dummies are left undone. Zero costs ensure they do not affect the total.
Question 6 Stretch
The optimal assignment for is , , . Find the total cost.
Answer.
Read from the original matrix: . The next best assignment costs 10.