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.
WHAT YOU PROBABLY THINK
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 it loses exactly the same total whichever allocation it is. The cheapest allocation before reduction is therefore still the cheapest afterwards, and the reduced matrix has zeros where the bargains are.
That argument needs the subtraction to be by rows or by columns. Taking the same amount off every entry, as the opening claim suggests, subtracts n times it from every allocation, which happens to preserve the ranking here but creates no useful zeros and gets the method nowhere. Rows first is the specification's convention.
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. And to maximise, subtract every entry from the largest entry in the matrix and then minimise as usual: the biggest profit becomes the smallest cost.
YOUR TURN
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.
THE EXAM BIT
- 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.
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
N
o
a
l
l
o
c
a
t
i
o
n
u
s
i
n
g
o
n
l
y
z
e
r
o
s
e
x
i
s
t
s
y
e
t
.
F
i
n
d
t
h
e
s
m
a
l
l
e
s
t
u
n
c
o
v
e
r
e
d
e
n
t
r
y
,
s
u
b
t
r
a
c
t
i
t
f
r
o
m
e
v
e
r
y
u
n
c
o
v
e
r
e
d
e
l
e
m
e
n
t
,
a
d
d
i
t
t
o
e
v
e
r
y
e
l
e
m
e
n
t
c
o
v
e
r
e
d
b
y
t
w
o
l
i
n
e
s
,
a
n
d
t
e
s
t
t
h
e
l
i
n
e
c
o
u
n
t
a
g
a
i
n
.
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.
CHECK YOUR PROGRESS
Rate how confident you feel with each objective for this lesson. Ratings are saved in this browser, on this device only.
- 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.
No animated video for this topic yet; these notes stand alone.