Using the Hungarian Algorithm - Examples and Practice January 2020
A - Regular - Minimising the allocation Note that there is often more
than one way to carry out the
This is the original cost matrix: algorithm and end up with the
66 64 2 12 best allocation/assignment.
40 61 8 21
81 74 37 99 For more help visit
94 73 66 53 www.hungarianalgorithm.com
1. We subtract the row minimum from each row:
64 62 0 10 ( -2)
32 53 0 13 ( -8)
44 37 0 62 (-37)
41 20 13 0 (-53)
2. We subtract the column minimum from each column:
32 42 0 10
0 33 0 13
12 17 0 62
9 0 13 0
(-32) (-20)
3A. Cover all zeros with the minimum number of lines:
32 42 0 10
0 33 0 13
12 17 0 62
9 0 13 0
3B. We can cover all zeroes with 3 lines - fewer than 4, so create additional zeros. The smallest uncovered
number above is 10. We subtract this number from all uncovered elements and add it to all elements that
are covered twice:
22 32 0 0
0 33 10 13
2 7 0 52
9 0 23 0
3A. Cover all zeros with the minimum number of lines:
22 32 0 0
0 33 10 13
2 7 0 52
9 0 23 0
4. Because 4 lines are now required to cover all zeroes, the zeros cover an optimal assignment:
22 32 0 0
0 33 10 13
2 7 0 52
9 0 23 0
This corresponds to the following optimal assignment in the original cost matrix:
66 64 2 12
40 61 8 21
81 74 37 99
94 73 66 53
The optimal value equals 162.
WA Exam Papers 1 www.waexams.com.au
Using the Hungarian Algorithm - Examples and Practice January 2020
B - Missing row or column (unbalanced)
This is the original cost matrix:
66 64 20 12
40 61 30 21
81 74 37 45
1. The cost matrix contains more columns than rows, we add dummy rows with zeros to make the matrix
square:
66 64 20 12
40 61 30 21
81 74 37 45
0 0 0 0
2. We subtract the row minimum from each row:
54 52 8 0 (-12)
19 40 9 0 (-21)
44 37 0 8 (-37)
0 0 0 0 NB Because each column contains
a zero, subtracting column minima
3A. Cover all zeros with the minimum number of lines: has no effect.
54 52 8 0
19 40 9 0
44 37 0 8
0 0 0 0
3B. We can cover all zeroes with 3 lines - fewer than 4, so create additional zeros. The smallest uncovered
number above is 8. We subtract this number from all uncovered elements and add it to all elements that are
covered twice:
46 44 0 0
11 32 1 0
44 37 0 16
0 0 0 8
3A. Cover all zeros with the minimum number of lines:
46 44 0 0
11 32 1 0
44 37 0 16
0 0 0 8
3B. We can still cover all zeroes with 3 lines, so create additional zeros. We subtract smallest uncovered
number of 11 from all uncovered elements and add it to all elements that are covered twice:
35 33 0 0
0 21 1 0
33 26 0 16
0 0 11 19
4. Because 4 lines are now required to cover all zeroes, the zeros cover an optimal assignment:
35 33 0 0
0 21 1 0
33 26 0 16
0 0 11 19
This corresponds to the following optimal assignment in the original cost matrix:
66 64 20 12
40 61 30 21
81 74 37 45
The optimal value equals 89.
WA Exam Papers 2 www.waexams.com.au
Using the Hungarian Algorithm - Examples and Practice January 2020
C - Maximising the allocation
This is the original cost matrix:
66 64 20
40 61 30
81 74 37
1. Subtract all elements from 81 (the largest element of cost matrix):
15 17 61
41 20 51
0 7 44
Note that we are now minimising the
2. We subtract the row minimum from each row: difference from 81, which has the effect
0 2 46 (-15) of maximising the allocation.
21 0 31 (-20)
0 7 44
3. We subtract the column minimum from each column:
0 2 15
21 0 0
0 7 13
(-31)
4A. Cover all zeros with the minimum number of lines:
0 2 15
21 0 0
0 7 13
4B. We can cover all zeroes with 2 lines - fewer than 3, so create additional zeros. The smallest uncovered
number above is 2. We subtract this number from all uncovered elements and add it to all elements that are
covered twice:
0 0 13
23 0 0
0 5 11
4A. Cover all zeros with the minimum number of lines:
0 0 13
23 0 0
0 5 11
5. Because 3 lines are now required to cover all zeroes, the zeros cover an optimal assignment:
0 0 13
23 0 0
0 5 11
This corresponds to the following optimal assignment in the original cost matrix:
66 64 20
40 61 30
81 74 37
The optimal value equals 175.
NB If an assignment problem is both unbalanced
and requires maximising, it's usually best to carry
out subtraction step first (example C) and then
add balancing row or column (example B).
WA Exam Papers 3 www.waexams.com.au
Using the Hungarian Algorithm - Examples and Practice January 2020
Three problems to practice
WA Exam Papers 4 www.waexams.com.au
