Practise › Questions › Allocation and the Hungarian algorithm
Allocation and the Hungarian algorithm questions
One worker per job and one job per worker, at least total cost. Subtracting the same amount from a whole row cannot change which allocation is best, and that single observation is the whole algorithm.
6 original questions · 25 marks · the allocation and the hungarian algorithm notes · Decision Mathematics 2
Every question here is written for this library rather than taken from a past paper. Write your answer out before opening the worked one: the answers award marks point by point, and the marks are easier to see when you have something of your own to compare against.
Explain why subtracting the smallest entry of a row from every entry in that row cannot change which allocation is cheapest.
Worked answer
Every complete allocation uses exactly one cell from each row. Subtracting the same amount from a whole row therefore reduces the total of every allocation by that same amount, so their order is unchanged and the cheapest one before the subtraction is still the cheapest after it. M1 for the observation that every allocation uses one cell from each row, A1 for the conclusion that the ordering is unchanged. The same argument applies to columns, since every allocation uses one cell from each column too.A 5 by 5 reduced matrix needs only 4 lines to cover its zeros. State the next step.
Worked answer
Four is fewer than five, so no allocation using only zeros exists yet. Find the smallest uncovered entry, subtract it from every uncovered element, and add it to every element covered by two lines. Then count the minimum covering lines again. M1 for the smallest uncovered entry, A1 for the augmenting step described in full.Workers P, Q and R are each to be given one of the jobs 1, 2 and 3. The cost of P doing the three jobs is 14, 9, 12; the cost of Q is 11, 8, 15; the cost of R is 13, 10, 9. Use the Hungarian algorithm to find the allocation of least total cost, showing each reduced matrix.
Worked answer
Row minima are 9, 8 and 9, so the row-reduced matrix is 5, 0, 3; 3, 0, 7; 4, 1, 0.
Its column minima are 3, 0 and 0, so the column-reduced matrix is 2, 0, 3; 0, 0, 7; 1, 1, 0. Write both matrices down; the method marks live in them, and an answer with only the final allocation scores almost nothing.
The zeros need 3 lines to cover, which matches the size of the matrix, so a complete allocation of zeros exists: P to 2, Q to 1, R to 3.
Read the cost off the original table, never the reduced one: 9 + 11 + 9 = 29.
M1 A1 for the row reduction, M1 A1 for the column reduction, A1 for the allocation, A1 for the cost.A table gives the profit made when each of P, Q and R does each of the jobs 1, 2 and 3. For P the profits are 14, 9, 12; for Q they are 11, 8, 15; for R they are 13, 10, 9. Find the allocation of greatest total profit.
Worked answer
The algorithm only minimises, so first turn the profits into costs. The largest entry is 15, so subtract every entry from 15 to get 1, 6, 3; 4, 7, 0; 2, 5, 6. Subtracting from anything smaller than the largest entry leaves negatives and loses the first method mark.
Row minima 1, 0, 2 then column minima 0, 3, 0 give 0, 2, 2; 4, 4, 0; 0, 0, 4, whose zeros need 3 lines.
The allocation is P to 1, Q to 3, R to 2, with profit 14 + 15 + 10 = 39.
M1 A1 for turning the profits into costs, M1 for the row and column reduction, A1 for the allocation, A1 for the profit.
As a check, the opportunity cost lost is 1 + 0 + 5 = 6 and 3(15) − 39 = 6.A firm has 4 workers and only 3 jobs, and one worker refuses job 2. Describe the two adjustments needed before the algorithm is applied.
Worked answer
Add a dummy job, a fourth column of zeros, so the matrix is square. Whoever is allocated the dummy is the worker left idle, at no cost.
For the refusal, give that one cell a cost large enough that the algorithm will never choose it, and say in your working that you have done so. The rest of the method runs unchanged. B1 for the dummy column of zeros, M1 A1 for the prohibitive cost in the refused cell.Workers P, Q and R are each to be given one of the jobs 1, 2 and 3. The cost of P doing the three jobs is 6, 11, 11; the cost of Q is 9, 17, 13; the cost of R is 12, 7, 5. Reduce the matrix, show that the line test fails, augment, and give the allocation and its cost.
Worked answer
Row minima 6, 9, 5 give 0, 5, 5; 0, 8, 4; 7, 2, 0. Column minima 0, 2, 0 then give 0, 3, 5; 0, 6, 4; 7, 0, 0.
Every zero is covered by column 1 together with row 3, so only 2 lines are needed against a size of 3, and the test fails. State the number of lines explicitly; that sentence is a mark on its own.
The uncovered entries are 3, 5, 6 and 4, so the smallest is 3. Subtract 3 from every uncovered entry and add 3 to the entry covered twice, which is the 7 at the foot of column 1, giving 0, 0, 2; 0, 3, 1; 10, 0, 0. Forgetting the addition at the crossing point is the usual slip, and it leaves a matrix with no valid allocation.
Three lines are now needed, so an allocation exists: P to 2, Q to 1, R to 3, costing 11 + 9 + 5 = 25.
M1 A1 for the row and column reduction, B1 for stating that only two lines are needed, M1 for subtracting the smallest uncovered entry and adding it at the crossing, A1 for the augmented matrix, A1 for the allocation, A1 for the cost.
Checking all six allocations confirms 25 is the least.
The same practice on paper: the printable workbook for this topic, questions and a worked answer book.
Practise allocation and the hungarian algorithm one question at a time
The player marks nothing for you. It shows one question, waits, then shows the worked answer so you can mark yourself, and brings a question back sooner when it went badly.