Maths › Decision Mathematics 2 › Allocation and the Hungarian algorithm
Allocation and the Hungarian algorithm
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.
Builds on The stepping-stone method and Linear programming: formulation.
IN THIS TOPIC
- Reduce a cost matrix by rows and then by columns.
- Use the minimum-lines test and augment the matrix when it fails.
- Adapt the method for maximisation, dummies and forbidden allocations.
COMMON MISCONCEPTION
In the Hungarian algorithm you can subtract the smallest entry in the whole matrix from every element.
Why reduction is safe
Subtract the smallest entry of each row from every entry in that row, then do the same for each column. Every complete allocation uses exactly one cell from each row and each column, so every allocation loses exactly the same total. The cheapest allocation before reduction is still the cheapest afterwards, and the reduced matrix now carries zeros where the bargains are.
That argument depends on the subtraction being done row by row or column by column. Take the same amount off every entry in the whole matrix instead, and each allocation loses n times it, so the ranking does survive. What does not survive is the point of the exercise. You get one zero somewhere instead of a zero in every row and every column, and the line test then has nothing to bite on. The specification wants rows reduced first, then columns.
WORKED EXAMPLE
A three by three allocation
Workers A, B, C are to be given jobs 1, 2, 3 at costs A 20, 15, 18; B 22, 19, 17; C 16, 14, 19. Find the least cost allocation.
Row minima are 15, 17, 14, giving rows 5, 0, 3; 5, 2, 0; 2, 0, 5.
Column minima are then 2, 0, 0, giving 3, 0, 3; 3, 2, 0; 0, 0, 5.
Three lines cover all the zeros, matching the three rows, so an allocation exists: A to 2, B to 3, C to 1.
Cost = 15 + 17 + 16 = 48, and checking all six allocations confirms it is the least.
When the test fails, and the variations
Count the minimum number of horizontal and vertical lines needed to cover every zero. If that number equals the size of the matrix, an allocation using only zeros exists. If it is smaller, find the smallest uncovered entry, subtract it from every uncovered element and add it to every element covered twice, then test again. The count rises each time, so the process terminates.
Three variations come up. A dummy row or column of zeros squares up an unequal problem. A forbidden allocation is given a cost so large that the algorithm will never choose it. To maximise, subtract every entry from the largest entry in the matrix and minimise as usual, since the biggest profit has become the smallest cost.
GUIDED PRACTICE
Maximising instead
Treat the same table as profits and find the allocation of greatest total profit.
Show the working
The largest entry is 22, so subtract every entry from 22.
That gives 2, 7, 4; 0, 3, 5; 6, 8, 3, which is now minimised in the ordinary way.
The best allocation is A to 1, B to 2, C to 3.
Profit = 20 + 19 + 19 = 58, which is the largest of the six possible totals.
ASSESSMENT FOCUS
- Reduce rows before columns, and show both reduced matrices.
- State the number of lines you used and compare it with the size of the matrix.
- For maximisation, say that you are subtracting from the largest entry, and give that entry.
- Give the allocation in words and its total cost or profit from the original matrix.
- Square up an unequal problem with a dummy before doing anything else.
CHECK YOURSELF
A 4 by 4 reduced matrix needs only 3 lines to cover its zeros. What is the next step?
Show a hint
Three is fewer than four.
Show the answer
No allocation using only zeros exists yet. Find the smallest uncovered entry, subtract it from every uncovered element, add it to every element covered by two lines, and test the line count again.
Reducing by rows then columns removes the same amount from every complete allocation, so the cheapest one is unchanged.
If the minimum covering lines number fewer than the matrix size, augment using the smallest uncovered entry and test again.
WORKBOOK
Printable practice for this topic: original exam-style questions with room to work, and a fully worked answer book. Free to use; please do not redistribute or sell.
Or read them with their worked answers on the allocation and the hungarian algorithm questions page.
CHECK YOUR PROGRESS
Rate how confident you feel with each objective for this lesson. Ratings are saved in this browser, on this device, unless you sign in.
- Reduce a cost matrix by rows and then by columns.
- Use the minimum-lines test and augment the matrix when it fails.
- Adapt the method for maximisation, dummies and forbidden allocations.
Open the full revision checklist to see every objective in the course in one place.