Understand assignment and the Hungarian procedure.
Key knowledgeUnderstand assignment and the Hungarian procedure.
The study design publishes this in the combined Units 3–4 list; the stated content applies to Unit 4.
Build the idea
An assignment pairs each person with one task and each task with one person. Subtracting a constant from every entry in a row or column changes every complete assignment by the same total, preserving the optimum. If reduced zero entries allow an independent assignment, the sum of the reductions gives a lower bound that this assignment reaches.
Try the sample task
Four workers A–D have task costs [[9,2,7,8],[6,4,3,7],[5,8,1,8],[7,6,9,4]]. Perform row and column reductions and choose independent zeroes to find a minimum-cost assignment.
The full worksheet includes the worked solution and remaining task set.
What this activity covers
This activity covers a case solved by row and column reductions and independent zero selection. More demanding Hungarian cases requiring additional zero-cover adjustments need further practice.