So we're going to now talk about the assignment problem that you work for a toy company and you have
to send yourself.
3 salespeople to different places.
Mr. the guy from Austin can go to Denver for 250 Edmonton for 400 or Fargo for 350.
The problem is you know we want to limit that so if we just said OK anybody go anywhere you know we
could you know let's pick something cheap so we'll say OK Austin go to Denver for 250 that's the cheapest
for you.
But then we'd have to say even if we send the Boston guy to Fargo and the Chicago guy to for 400 to
Edmonton he could have done 200 and that would have been cheaper.
So maybe we should start with him.
You know we should we can pick something that you know start with him for 200.
OK.
So that's going to be 200.
So then Austin guy would have to go to Fargo because that's that.
But then he'd have to go to Edmonton so maybe he should go to Denver and he should go to Fargo and he
should go to Edmonton.
Right so we have to figure out instead of just trying every possibility an algorithm that would allow
us to ship each person to each place.
So here's what you do.
OK.
We're going to set up a cost matrix that's going to look like this.
And we can then find a way to pick the three possibilities that would work and there might be more than
one possibility in this case it would be sending him there him there and him there and you can notice
that in the row and column it's exclusive to the row and column because each one person goes to one
place OK.
So this picture over here just shows us that we have to be careful not to be doing it in an factorial
time because it goes so much quicker in other words to track every possibility.
We don't want to do that.
OK.
So there are a bunch of steps but the easiest thing to do is to look at the problem and then to just
walk through the steps first step.
You set it up your problem just in this matrix.
Subtract the minimum from each row.
So that means 250 from each row subtract 250 from each one 350 from everybody in that row 270 in that
row.
Then subtract the minimum from each column with a minimum.
Here is zero the minimum is $150 check 150 from everybody and then another zero.
This is what we get.
Now what we do is we cover it with the minimum number of lines it doesn't matter what the organization
of those lines are just the minimum.
So for instance this line is going to be here or this line is going to be there.
Etc..
OK.
So when we do this we're going to get our lines.
Sorry OK when we do this that's ok.
When we do this we're going to get our lines here here and here.
And those lines are going to be the minimum that we that we can do and the minimum number of lines we
can cover every zero cover zero cover zero cover zeroes.
Good.
Perfect.
We got all the zeros.
Now if we have three variables and three lines that means we have a solution.
So then we just uncover them and we can find the solution set and then we just replace it with the numbers
that they are.
So 400 would be in that position 350 in this 200 and that and we're that.
Now let's take another example if we have bulldozers going to different construction sites we need to
minimize that already with four variables that's a little hard but we can follow the same procedure.
Now the beginning steps are the same the beginning steps are you get the minimum of each row subtract
it off you get that minimum of this row subtract it off and get that minimum a distro minimum.
This route you subtract to get that.
Now we do the columns take the minimum of each column that 0 0 and 5 0 0 and 5.
So that's all zeroes.
That's not going to change.
But this when we subtract 5 from each column we get this.
The problem is that if we want to cover with the minimum number of ones we have four variables we need
to cover with four lines but we can't.
But we can actually cover it with three.
The way we did it so therefore we're not done yet.
So we pick the minimum value that's uncover five is them and value uncover.
We're going to subtract five from each and covered row.
So subtract five from each uncovered Roe.
This was an uncovered row.
This was an uncovered wrote this was an uncle of a row subtracts five from each of those.
OK.
Then we add five to the covered columns.
This was a covered column and this was a covered column.
So we add five to this column into that column and this is what we get now that we do that we can cover
it in the minimum that we can covered with his 3s.
That means we're still not done yet.
So we have to do it again.
The minimum value in here is 20.
So shipwrecked 20 from each uncovered row.
So you subtract 20 from these rows which are coming from these robes.
Then I add 20 to each covered column which in this case is just this 20.
And now I see if I can do it for if I need four rows for bars I do in fact so therefore I'm done which
means I just need to find my zeros and then plug it in.
And those are the positions those are the numbers that would be in each of those years.
OK.
So that's all you do.
Let's look through an Excel example.
Just so you see it in a different format.
These are my numbers over here and what I do is I find the minimum of each row I subtract 39 from everybody
in this row 31 from everybody in this row to 37 from nobody in this row etc..
This is what I get.
Now I did the rose.
Now I have to do the columns so I find the minimum of each column minimum minimum at a minimum minimum.
I subtract the minimum of each column so I subtract zero subtract zero subtracts six subtract 17 etc.
and this is what I get.
Now I get the minimum I can cover this in is one two three four lines but there's five variables.
So therefore I take the minimum of the uncovered the minimum of the uncovered as 121 right there.
So I have that and I subtract 120 and from this row from this row from this row and then I'm going to
add it to each covered column from this column and this comes so you do subtract from the rows that
are uncovered.
Add to the columns that are covered subtract from the rows that are uncovered.
Add to the columns that are covered this one and this one.
Now can I cover this.
Yes.
Let's see how many.
One two three four five.
So I covered all the zeros.
But it took me five bars.
That means that I've arrived at a solution.
I just have to find a zero.
For instance this one that's that's isolate in its row and column this on isolators row and column etc.
those are the numbers that present themselves when doing this.
OK.
So it's the same procedure I did one with three four and five.
You it you just have to do subtract the rows and the columns then take the minimum value subtract from
the uncovered rows and to the covered columns and you keep doing that until you get something that's
covers it with the lines that are the same as the variables that are there.
So this is the Hungarian method.
This will work to get you a solution to this if you follow along.