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 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 From every number in each row subtract the smallest number in that row

8 4 2 6 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=cQ5M siGaDY8 https://www.youtube.com/watch?v=7hbrt wvKVPM http://www.vcaa.vic.edu.au/Pages/vce/stud ies/mathematics/further/exams.aspx See paper 2 2012, 2014 MAWA IQ Topic 4.3