Transcript Presentation Notes

HUNGARIAN
ALGORITHM
Abstract
Unfinished business from 2015 - where
many participants did not get to experience
all the depth of questions possible with the
Hungarian Algorithm. This session will be
organised in the form of a workshop in
which teachers can work collaboratively to
use the algorithm for assignment/allocation
applications. Prior knowledge of the
algorithm is not required.
Syllabus reference
Assignment problems
4.3.10 use a bipartite graph and/or its tabular or
matrix form to represent an assignment/
allocation problem
4.3.11 determine the optimum assignment(s), by
inspection for small-scale problems, or by use of
the Hungarian algorithm for larger problems
Glossary: The Hungarian algorithm is used to
solve assignment (allocation) problems.
ACTIVITIES
1.
WACE 2016 exam question
2. For beginners – The Simpsons at work
3. Multiple steps and more than 1 solution
4. Maximising
a. Outings for the elderly
b. An engineering competition
5.
6.
7.
8.
More tasks than people
5 by 5 matrix
Investigate – making more matrices
Writing interesting (?) questions
A1: WACE exam : 2016
Complete the matrix for the bipartite graph
WACE exam : 2016
Complete the matrix for the bipartite graph
4
2
3
9
7
6
4
7
7
3
5
4
8
4
2
6
From every number in each row subtract the smallest
number in that row
WACE exam : 2016
Subtracting the smallest number in each row
0
0
1
5
3
4
2
3
3
1
3
0
4
2
0
2
From every number in each column subtract the smallest
number in that column
WACE exam : 2016
Subtracting the smallest number in each column
0
0
1
5
1
2
0
1
3
1
3
0
4
2
0
2
Using vertical or horizontal lines across rows or down
columns, cross out all zeroes using as few lines as
possible
WACE exam : 2016
Crossing out zeroes using as few lines as possible
0
0
1
5
1
2
0
1
3
1
3
0
4
2
0
2
Note: the number of lines is less than the dimensions of
the matrix so a solution does not exist yet.
WACE exam : 2016
Subtract the lowest uncovered number from all
uncovered numbers and add it to the numbers at
the intersections.
0
0
1 2
5 6
1 0
2 1
0
1
3 2
1 0
3
0
4 3
2 1
0
2
Using vertical or horizontal lines across rows or down
columns, cross out all zeroes using as few lines as
possible
WACE exam : 2016
Cross out zeroes using horizontal or vertical lines across
rows or down columns – use as few lines as possible
0
0
2
6
0
1
0
1
2
0
3
0
3
1
0
2
Note: the number of lines is equal to the dimensions of
the matrix so a solution exists.
WACE exam : 2016
To assign – locate row or column with only 1 zero.
Allocate ... that person or job is no longer available.
Continue until all jobs assigned.
0
0
2
6
0
1
0
1
2
0
3
0
3
1
0
2
Row 4 column 3 OR Row 3 column 4 then the other.
Then row 2 column 1 and then row 1 column 2.
Assignment to minimise total time
• In each row take the smallest number off every number in
that row
• In each column take the smallest number off every number in
that column
• ** Using the least number of vertical or horizontal lines across
columns or rows, cover all zeroes
• If the number of lines equals the dimensions of the matrix a
solution is “found” – Go to END – otherwise continue
• Locate smallest number not crossed out
• Take this number off every uncovered number and add it to
numbers at the intersections of the lines
• “Remove” vertical and horizontal lines
• Back to **
• END: Locate a zero in each row and column so that there is
“one for each”
• Determine the total minimum time for all tasks.
ACTIVITIES
1.
WACE 2016 exam question 
2. For beginners – The Simpsons at work
3. Multiple steps and more than 1 solution
4. Maximising
a. Outings for the elderly
b. An engineering competition
5. More tasks than people
6. 5 by 5 matrix
7. Investigate – making more matrices
A2: The Simpsons at work
Minimising total time
• In each row take the smallest number off every
number in that row
• In each column take the smallest number off every
number in that column
• Using as few vertical or horizontal lines as possible,
remove all zeroes
• If no. lines = matrix dimensions, solution exists
• Locate a zero in each row and column so that there
is “one for each”
• Determine the total minimum time for all 4 tasks.
Can a bipartite graph be used to represent the
solution?
A3: Event Managers
Minimising total time
• In each row subtract the smallest number from every number
in that row
• In each column subtract the smallest number from every
number in that column
• ** Using as few vertical or horizontal lines as possible, cover
all zeroes
• If the number of lines equals the dimensions of the matrix a
solution is “found” – Go to END – otherwise continue
• Locate smallest number not crossed out
• Take this number off every uncovered number and add it to
numbers at the intersections of the lines
• Back to **
• END: Locate a zero in each row and column so that there is
“one for each”
• Determine the total minimum time for all 4 bulldozers. How
can a bipartite graph be used to represent the solution?
A4: Maximising
• Firstly – take every number in the matrix off the
largest number and then proceed as before.
• Council outings for the elderly
• Mathematics competition for students
A5: Cleaning up the Art room
How is this situation different
to the ones presented earlier?
Cleaning up the Art room
• There are more people than tasks
• Number of supply sources exceeds number of
demand depots
• The matrix formed is not square
• We make it square by adding a row or column
• By convention the row or column added is filled
with the largest number in the matrix
• Proceed as before
A6: 5 x 5
A7: Investigation
• Writing questions on the Hungarian algorithm
• The context
• The numbers
How can you make up a set of numbers for the HA
manipulating a matrix that already works in the
desired manner?
• Group 1
▫ Add the same number to every number in the matrix
• Group 2
▫ Add a different number to the elements in each row
• Group 3
▫ Multiply all the numbers in the matrix by the same
number
• Group 4
▫ Multiply every number in each row by a different
number for each row
• Make a conjecture. Test it with two matrices.
• What can you conclude? Share your findings.
Further resources
• https://www.youtube.com/watch?v=cQ5MsiGa
DY8
• https://www.youtube.com/watch?v=7hbrtwvKV
PM
• http://www.vcaa.vic.edu.au/Pages/vce/studies/
mathematics/further/exams.aspx
▫ See paper 2 – 2012, 2014
• MAWA – IQ Topic 4.3