The hungarian algorithm for weighted assignments

okay so the hungarian algorithm for weighted assignments so imagine you had four employees okay w x y and z and let's say you had four different jobs to do okay and those jobs were a b c and d so maybe you've got uh maybe you're like a construction crew right and you've got four people working in the construction crew and you need to do some bricklaying and you need someone to do like the mixing of the cement and you need someone to level something off and you need some other job done okay now all of your employees are capable of doing all of these jobs so w say wendy is capable of doing all of those jobs and x is capable of doing all of those jobs and why he's capable of doing all of those jobs and zed is capable of doing all oops all of those jobs how do you assign them well what about if w say only took 10 minutes to do job a but x took 15 minutes to do job a and y took 17 minutes to do job a and zed took eight minutes to do job a well maybe it would make sense to get zed to do job a but maybe zed's great at all the jobs maybe zed only takes five minutes to do job d and w takes uh six minutes to do job d and maybe it would be better to get w to do d and z to do a but maybe it would be better to get them to do the other way you can see that i'm creating a weighted bipartite graph and you can see that there's going to be like four four four four there's going to be like 16 different numbers here and i'm going to have to come up with a way to come up with the most efficient way to use my crew and assign them to these jobs now first of all the graph is a mess it's going to be way way easier to put all of this information into a table so here's a table employees and jobs along here so wendy takes 30 minutes to do job a zen zenon takes 30 minutes to do job b um yolanda takes 60 minutes to do job c and so on all right now we're going to use the hungarian algorithm to assign our employees now what's an algorithm it's just a series of steps so as long as you follow this series of steps you can't go too far wrong so first step so first step subtract the lowest value in each row from every element in the row okay so a row is across right that's row one row two row three row four let's look at row one the lowest value is 30. all right so i'm going to take every element in that row and subtract 30 from it so 30 minus 30 is 0. 40 minus 30 is 10 50 minus 30 is 20 and 60 minus 30 is 30. so from here we just do it for the other rows as well so the lowest value here is 30 so now we subtract 30 from all of the things in that row so 70 minus 30 is 40 30 minus 30 is 0 40 minus 30 is 10 and 70 minus 30 is 40. all right uh this row 60 50 60 30 our lowest one is here so 60 minus 30 is 30 50 minus 30 is 20 60 minus 30 is 30 and 30 minus 30 is zero and the lowest value here is 20 so 20 minus 20 is 0 80 minus 20 is 60 50 minus 20 is 30 and 70 minus 20 is 50. okay that's step one what that's given us is a zero in every single one of the rows all right so now you do a little bit of drawing right you can draw a horizontal or a vertical line through the zeros and your goal is to draw lines through the zeros covering them all up with the minimum amount you can all right so you can see that there's two zeros here in a line so i'm going to cover them up right with one line now i can cover that zero up with this line like this and i can cover that will zero up by just drawing a line like that or by drawing a line like that it doesn't matter okay that is the minimum amount of lines that i can do draw to cover up the zeros how many lines did i draw one two three okay that's a problem because if i could if the minimum amount required was four lines then my job would be finished but because the minimum amount is three which is less than the number of assignments i need to make because i need to make four assignments then i have to keep going all right so on to step two okay step two last time we did the rows we looked at all the rows and subtracted the lowest amount in that row step two is all about columns if a column doesn't contain a zero subtract the lowest value from every element in the column okay so let's look at column one first of all if a column doesn't contain a zero well column one contains a zero so we can leave it exactly how it is 0 40 30 and zero column b 10 0 oh it does contain a 0 so i can leave it exactly how it was 10 0 20 60. what about column c oh column c does not contain a zero so i find the lowest value 20 10 30 30 that's 10 and i subtract it from all of the values in that column so 20 minus 10 is 10 10 minus 10 is 0 30 minus 10 is 20 and 30 minus 10 is 20. and finally the last one contains a zero so it can stay exactly as it is all right so from here we want to cover up all of the zeros with the minimum number of lines possible all right let's see i see two zeros there and i see two zeros there right so i can cover up those two zeros like that i can cover up those two zeros like that and i can cover up that zero with a line like that or a line like that okay three lines oh all right because it's only taken three lines and i want to do four assignments i'm still not finished i need to do more work on to step three all right step three is complicated add the smallest uncovered value to elements that are covered by two lines subtract it from all uncovered elements all right so look at where you drew your lines i drew three lines one two and three add the smallest uncovered value so where are uncovered values or values that aren't covered by a line here here here here here and here okay the smallest uncovered value is 10 and now it says add the smallest uncovered value to elements that are covered by two lines this element is covered by two lines it's 40 so i need to add 10 to it to make 50. this element is covered by two lines it's also 40 so i need to add 10 to it to make 50. now these elements are only covered by one line and they're the zeros so i can put well actually some of them are not zeros i can write them in because i don't have to do anything with the ones that are covered so 0 0 0 30 0 50 0 and 30. okay and finally we come to the subtraction bit subtract it that being the lowest value that was uncovered from all uncovered elements so 10 minus 10 is 0 10 minus 10 is 0. 20 minus 10 is 10 20 minus 10 is 10 60 minus 10 is 50 and 20 minus 10 is 10. okay i really hope we're at the end here let's try to cover up all of the zeros with our minimum number of lines all right there's three zeros here all in a line so i should try to cover them up there are two zeros they're all in a line i should try to cover them up two more zeros okay it looks like i can't cover them with one line i'm going to have to cover them with two lines either downwards or crosswords it doesn't matter which way cover them like that and i feel very confident that that is the minimum number of lines i could have used to cover those zeros how many lines did i use four how many assignments do i need to make four that means that i am finished i just have to do the assignments now now before i go on i should say that um if there were only three lines if you got to this step and you got stuck and you went wait a minute i'm still only using three lines then just keep repeating step three okay repeat as necessary so you might need to do step three a couple of times if uh you only get three lines you have to keep adding the smallest uncovered value to those that are covered by two lines okay but i'm lucky here i don't have to keep repeating step three so rows columns this weird double line uncovered thing and then keep repeating step three until you're done let's do the assignment so as i'm doing my assignment i'm going to talk to you about wendy and x and y and z whatever their names are right wendy's a gun wendy is great at job a great at job b and great at job c she'd be a great choice for all three of those uh x is great at job b and great at job c that'd be a great choice for both yolanda is only really good at doing job d so we should only really consider it for job d and z zelda is only good for doing job a all right so we start filling in our less useful employees first so y is great at d so let's put y with d z is great at a so let's put z with a okay now uh our next most our next most not as awesome employee is x so they can do b or c now b and c actually it doesn't matter because b and c are both there so i can choose to put x with b or c because wendy can also do b or c so they can play like rock scissors and paper to decide who does b and who does c i'm just going to choose x to do c and wendy to do b that's a pretty good assignment now we can figure out how many say minutes this job's going to take right wendy is going to be doing job b and it's going to take her 40 minutes to do that job x is going to be doing job c and it's going to take him 40 minutes y is going to be doing job d and it's going to take 30 minutes and zed is going to be doing job a and it's going to take them 20 minutes and that's going to be 80 plus 30 110 130. now just to show you what i meant about it doesn't really matter what we've done with w and x if w had done c it would have taken them 50 minutes wc 50 minutes and if x had done b it would have taken them 30 minutes so we'd be replacing 40 and 40 with 50 and 30 which would still lead to the same amount of minutes 130. now obviously if they're all doing it at the same time it's not going to take 130 total minutes it's going to take the whatever the longest amount of time is which is 40 in this case okay that is the hungarian algorithm for weighted assignments

Channel: Joel Speranza Math

Views: 4,547

Keywords: teachers, math, high school, mathematics, math class, maths, Queensland Mathematics Methods, Queensland Mathematics Specialist, Queensland Mathematics General

Id: FCaD34z--bY

Length: 13min 37sec (817 seconds)

Published: Thu Jul 09 2020