25 slides. In 25 slides you would have seen
everything about, you know, the Simplex algorithm to actually code it and know
exactly how it works. Okay?
So this is what we're going to do today, we're going to talk about the last steps
of the Simplex algorithm and some of the most complicated stuff.
Okay? So we know, what do we know so far?
So we know that the optimal solution is located on a vertex, and a vertex is a
basic feasible solution. What is a basic feasible solution?
That's a solution is in which you isolate, you know, as many variables as
there are constraints. Okay?
These are the basic variables. You express them in terms of the
non-basic variables. Okay?
And if the Bs you know, the constants that you get on the right hand side are
all nonnegative, you have a basic feasible solution.
Okay? So we know that in a very, very, very
naive algorithm which was basically any variable on this basic feasible solution.
And look at the one which has the best cost, and that would be your solution.
The issue with this is that this will take a long, long, long time.
Okay? Because there are many combinations of of
basic feasible variables that you can select.
Okay, so what the simplex algorithm is, is a better way of actually doing this,
okay, and so the key point, the third thing is going to basically telling you
that we want a numeric. All these basic feasible solutions, we
are basically going to move from basic feasible solution to basic feasible
solution, and trying to improve the value of the objective function all the time.
So, in a sense you know, the simplex algorithm is a local search algorithm,
okay? And the basic move is you know, the basic
local move that is applied is moving from a beautiful fantastic spot to another
one. Okay.
Moving from a basic feasible basic solution to an adjacent basic feasible
solution, and will tell you exactly, you know, how we move from one to another.
That's the key point of this lecture. Okay.
And so, the only thing which is really nice about the simplex algorithm is that
because of complex, convexity. Okay.
It's guaranteed to find the global optimum.
So it's a local search algorithm, but it's guaranteed to find the global
optimum. Okay, so the key idea is basically going
to be telling you how we can move from BFS to BFS.
Okay so this is essentially what we're going to be doing.
Okay so you have this systems of equations that you see on the top, right?
And then we find a basic feasible solution and that's what you see here, so
we isolated x3, x4, x5, okay, we re-express them in terms of the other
basic variables, in this particular case x1, x2 and xx, okay, and now we have a
basic feasible solution, okay so we give the value to x...
3 in x4 and 5 and give the value 1 to 3 and that's the basic feasible solution.
All the non basic variables are assiged to 0.
Okay? So, now, how do we, so, so, basically the
local move that is simplex algorithm is going to do is taking one of the non
basic variable, okay, and moving it inside the bases, which basically taking
to basic variables. And of course, you have to keep one out,
okay? So you're going to take one of the basic
variables and kick it out, okay? So this is the basic idea, that's a very
simple local move, you swap two variables, okay?
One which is basic, one which is non-basic and the status of these two
variables is basically changing, okay? The basic becomes non-basic, the
non-basic becomes basic, okay? So this is the local move right, so you
select a non-basic variable And that known basic variables has to be a
coefficient, okay, negative has to have a negative coefficient.
We want to take it from the right hand side and moving to the left hand side,
okay? And to do that you have to have a
negative sign, okay? So you take the value that is negative
side, you're going to move it on the other side, and of course the other
variable's going to move to the non-basic site and also change, you know, sign.
Okay? So, in a sense we find the entering
variables. That's the variable which is non-basic
and has a negative coefficient. Okay?
And then, we going to find the value in the, in, in basic variable is, one
constraint and one basic variables that we going to kick out of the basics.
Okay? Make, you know, non-basic And then what
we going to do is re-express all the equations in terms of the new basic
variables, okay?. So we going to basically eliminate the
new basic variable from the other equations, okay?
And so that's essentially the local move that we are doing.
So basically local move here swapping a basic variable and a non-basic variable,
okay? And the way you do it, you choose an
entering variable, you choose a leaving variable, and then you do Gaussian
elimination to eliminate the new basic variables that you selected.
Okay, so I'm going to show you example, okay.
So once again, this is a system of equations, okay.
You see the beautiful basic variables there, the non-basic variables over
there, okay. Now, I'm looking at the non-basic
variable in this particular case X2, okay.
It has a negative coefficient, minus 2, and therefore I decide that I want this
variable to go into the bases. Okay.
I select the first constraints here, that's the only one that it appears to,
so it's easy. Okay.
And essentially what I'm going to do is swap x2 with the variable which is on, is
in bases inside the first constraints, and that's x3.
Okay, so I'm basically swapping these two guys, now x2 is going to move on that
side. x three is going to move on the other
side. Know the coefficient is minus two so I
will have to divide the equation by two such that the coeffiecient of x two is
going to be one over there and so I get these constraints, no?
Where you see that this is one half you know and then the coefficient of x one is
minus three half and the coefficient of x three is minus one half.
Okay, and that's the constraint that you see there.
Now, you know, in this particular case it was very convenient because x2 didn't
appear in any one of the, the other constraints.
And therefore I don't even have to eliminate it with the other constraints.
In general, you would have to actually take the volume of the, of the right-hand
side on, in, in, in this equation and remove it from the other equation.
Okay? But this is basically telling you what we do. Okay?
So we select the variable that we want to enter the basis.
X2 in this particular case. We select the constraints, and by
selecting the constraints, you select a variable that you want to kick out of the
basis, x3 in this particular case, and you swap these two variables.
You make sure that you get a basic feasible solution by you know, making
sure the coefficient of x2 is 1 and then by removing you know x2 in this
particular case from all the other equations.
Okay? So that's the basic move that the simplex
algorithm does. Okay?
Now, I selected x2 to enter the basics, I could have selected x1.
Right? So because x one also appear with a
negative coefficients there and therefore I could have selected x one from, you
know, as, as the, as, as the entering variables for the local move.
Now if I select x1 here, I have basically three negative coefficients.
And therefore, I can choose which constraint, you know, I want to, which
non, which basic, existing basic variables I want to kick out, out of the
basics - I want to make non-basic. Right?
So can I take any of these num, the, these basic variables and make them
non-basic? Well, look at this, okay?
If I take the third one, okay? So I'm basically saying, oh, you know, I
want to kick out, you know, x y for all of the bases.
Okay, so what is going to happen? Well I perform Gaussian elimination for
all the three constraints, and then what do I get?
I get that x three now is a sign of value minus x, x four is a sign of value minus
4, and that's terrible right? So because this is not a basic feasible
solution. I told you that a basic feasible solution
assign only positive values to the variable because all the variables have
to get a positive value. Okay, so what happens, okay?
So what happens is that I selected the mentoring variable.
That's all fine. You know, I, I can do that.
But then I selected one particular constraints, and one particular basic
variables to remove from the basics, to make non-basic, okay?
And when doing that I perform Gaussian elimination, and then suddenly, what
happens is that the value of the, the existing basic variables, okay, was
becoming negative. And that's terrible, okay.
So what does that mean? Does that mean that at that point, I'm
stuck on this beautiful, fantastic spot, and I can't move?
No, it just means that I have to move a little bit more carefully, okay?
And so the key point is that you have to choose, essentially, the leading
variable, using the formula that I'm showing you here.
And I'm going to give you an intermission here.
Okay? So, when you look at this column, okay,
so essentially you see various coefficients for these nonbasic variable.
Okay? And so this coefficient is large, okay?
This coefficent here is much smaller. Now, I also look at the b variables
there, okay? And so what you can do is if I take the
first constraints here, if I take the first constraint.
And to, to make x one into the basics and, and for that popular constraints and
therefore remove x three, the value of x one is going to be what?
It's going to be basically dividing this coefficient, dividing the b by this
coefficicent three over there. So it's going to be one third.
Okay? And so that's a small number compared to
what would happen if I make it, if I move it.
You know, if, if I, if I make it enter the basis using the 3rd constraints.
In which case, x1 is going to take the value of 3.
Now why is this important? Because if x1 is the value 3 here, it's
going to be multiplied by this 3 there, and that's you going to get a minus 9
there. Okay?
And therefore, 1 minus 9 is going to be the minus a that you seen before.
So if i take a very large value here, okay, and I substitute it the other ones
you going to get these negative values. So what I need to do is to find the
smallest ratio between the B's, okay the B's that you see there, and the
coefficient of the variables that has to enter the basis.
Okay, and so this is, these are the ratios that I have shown you.
This is basically the bi, you know, divided by minus the coefficient of the
entering variables, okay. And you see that the one which is the
smallest ones at the top, and if you actually, you know, choose the first
constraints, as the constraint from which you select the basic variables that you
will remove from the basis, then you are guaranteed in a sense to make sure that
you go to a basic feasible solution. Because you are making sure that the
other constraints, when you do the Gaussian elimination, are going to stay
positive, okay? So essentially what we do, we use this
ratio to select the leaving variables, okay?
Using this formula, here. And we are guaranteed to maintain
feasibility, okay? So, in a sense, the look and move, you
have to be a little bit careful. You take any kind of entering variables,
okay, and then you use this route to find the variables that you have to kick out
of the basis, okay? So, and you compute this ratio, it's very
easy to do. But you have to be careful in do that.
Okay? So, in this, this particular case, you
get this beautiful basis where, as I, you know, alluded to, x1 is going to be 1
3rd, and then you see x4 and x5 we get also fractional value, you know, 4 3rd
and 8 3rd. But this is a basic feasible solution.
These guys now are positive, okay? And so, essentially when you move from
basis to basis, you have to make sure that you get a basic feasible solution
there, and so you have to make sure that when you perform the Gaussian
elimination, the right value are going to emerge.
And that's what you do, by selecting this the, the, the leaving variable, using the
rules that I've shown you. Okay?
So, to summarize, we move from basic feasible solution to basic feasible
solution by selecting an entering variables that is to be a non-basic
variables, which has a negative coefficient in some of the, in some of
these constraints. Then you choose a leaving variable,
giving the, the, the, you know, the formula that I've shown you.
You compute these ratio, you select the constraint which is the smallest ratio,
okay, and then that's the variable that, that's the basic variable that will leave
the bases and then you perform, you know, Gaussian elimination.
Now, this entire set of operation here is called pivoting, okay, and pivoting is
basically the name of the local move in linear programming but that's basically
choosing this entering variable, choosing this leaving variable.
And performing, you know, Gaussian elimination.
So the local move is called pivoting and basically swap one basic variable and a
non basic variable, okay? So at this point we have seen a lot of
thing already, okay, so if you want to solve this linear problem, we know that
this solution is at the vertex, you know that the vertex is a basic feasible
solution. And now we know how to move from a basic
feasible solution to another basic feasible solution so we can look at the
four points, you know, when do we need to stop?
Okay. And we need to stop, you know, when you
see the basic feasible solution is optimal.
And I'm going to give you very, very simple criteria to actually detect that.
And this is the criteria, right? So we have this basic feasible solution.
We have these equations, right? And these equation are expressing the
basic variables in terms of the non-basic variables.
Okay, take the objective. Okay, take the objective, remove all the
basic variables which basically mean replace them with the non-basic variables
and you get an expression of the form you know, 'c' zero which is going to be a
constant plus 'c' one is one, well this is a coefficient of you know the variable
'x' one plus 'c' two, 'x' two and so on when I have basically replaced all the
basic variables way off, you know on the right hand side, the non-basic variables.
The expression with the non basic rivals, okay.
Now, if I have an expression like this, okay, and all the CIs are strictly, are
greater or equal to 0 then I know that I'm optimum, so I have a very, very, very
very simple way for actually detecting that I'm optimum.
I'll rewrite the objective function, remove all the basic variables, look at
the expression, which is only in terms... Of the non-basic variables, and if all
the coefficients there are greater or equal to zero, I'm done.
Okay? I'm at the top of the world, okay?
Now, I'm going to give you a little intuition why this is true, a little bit.
Or actually, the inverse. But, but we're going to go through some
examples so that you can, I can convey that intuition, right?
So we had this beautiful problem that we were trying to solve for a long time.
So we have variable x1 for x5. You have inequality, equalities here and
so the first thing of use is to find a basic feasible solution.
That's what we find here. Okay.
Now look, When I take the basic variables here, right?
So x three to x five, okay, remove them from the objective functions there.
This is the objective function that I get.
Okay? As you see, the constant is six.
Why? Because x three, x four and x five, you
know, I assigned one through three and there are the coefficients of one at the
top. Okay?
So I know that I will have, you know, the value six.
But then I give a minus you know, 3x1 and then a minus 3x2 okay?
Now this is not an optimal solution right?
Because these guys are negative okay, they are not, non negative the
coefficients of you know, x1 and x2. So what is the intuition here?
Well, you know that these guys x1 and x2 okay they have to take non negative value
okay? So currently they are not in the business
right so their value is what? Zero, right.
OK since they are zero you know may wonder oh but if I put them in the bases
there going to get a positive value, a nonnegative value and therefore I can
drive this objective function down because you know a negative times a
positive value is going to decrease this objective function and that's the
intuition here. If they were positive you know they had
to take a positive value this objective function is going to go up.
Okay, so essentially they are negative. That means that I can drive this
objective function down, okay, so this is what you have there.
You know, we have these objective functions, we select x2, which is a
negative coefficient, and we want this x2 to enter the basis, okay, so how do we do
that, we have to select a variable to leave the basis, you know, once again we
look at the coefficient 1 divided by 2... Okay and then three, three divided by by
three, so that's one. So we're going to basically use the first
constraints to remove to make x two inside the bases, removing x three from
the bases and this is what you obtain. Okay?
At this point this is the new basic feasible solution.
And this basic feasible solution is the value of nine and a half, okay, so which
is four point five, so it's going to then six with decreased value of the objective
function. But the now the two co, the two
coefficients that you see are positive which basically means that at this point
this is the optimal solution. There is no way I can drive the objective
function down. I have an optimal solution to my problem.
Okay, and I can detect that and just look at this line and all the coefficients are
going to the zero, great. >> I am, I'm optimum, okay, so this is
basically the idea. So you go, you go, you move from basics
to basics, select this entering variable, you know, select this leading variable,
performing the pivoting operation and look at your function though.
Is it all positive? If it's all positive you're down, okay.
So that's the basic idea... Okay, so in a sense what we have seen at
this point are basically the first four points.
Okay, so we have seen, you know, the fact that an optimal solution is located at a
vertex, okay. A vertex is a basic feasible solution.
I can move from BFS's to BFS's, okay. And I can detect that BFS is optimal.
I haven't shown you the proof yet, okay, I will show you in the next lecture
because it's much easier. To actually prove this thing, if I can
use Matrix notation. But it's a beautiful single proof like
five lines if I can use matrix notation. Which I'm not doing here because it's
simpler. Okay?
So now, the only thing that I have to tell you is that from any kind of BFS, I
can move to another BFS which has a better cust, okay?
And that's the case, okay? Provided that I put some conditions,
okay? Once again, I want to prove this but
this, there is a simple algebraic proof to do that but the basic idea is the
following, okay? So if all the bi's, okay, I'm assuming
that all the bi's are strictly greater than 0, okay, that I can find an entering
variable. So there is an entering variable
somewhere in the constraints with the negative coefficient.
I can find the leaving variables, okay, then the pivoting operation is going to
give me a new BFS. Which is improving.
Great, I am improving the solution. Okay, and so once I have that, you know,
this is the only, so I'm ready in a sense to tell you what the simplex algorithm
is, and this basically these five lines that you see here, these four lines that
you see there, okay. So what you do is, as long there is a
coefficient in the objective function, which is, which is negative, okay, I need
to perform a pivot operation. Okay, so I select an entering variable,
that's a variable which has a negative, it has to have a negative coefficient in
the objective function. That's how I can drive this objective
function down, okay, then I select a leaving variable, okay, such that, such
that, I preserve visibility, so I have to use the rule that I've shown you before,
and then I basically pivot... Okay?
So once again choosing and entering variables and in the centering variables,
how you have to be a little bit careful, right?
I want to take one, which is a negative coefficient in the objective function.
Why? Because I want this objective function to
have only positive coefficient. Right?
I select the centering variable, I select the leaving variable, I pivot and I keep
doing that until the objective function is going to be all, you know, all
positive coefficients. Okay?
So that 's the Simplex Algorithm. And if I guarantee that during the
execution, these B I stays strictly positive, okay?
It can't, I don't want them to fall to zero, and we'll discuss that in a moment.
And if the, the, the objective function is bounded by below.
Okay, so you can't drop, you cannot drive it down infinitely low.
Okay. Then you are guaranteed that the simplex
algorithm is going to terminate, and it will give you an ultimate solution.
So it's going to convert with, a bfs where all these cis are going to be
greater than zero. Okay?
So that's the simplex algorithm. Okay?
Now, there are a couple of nasty cases that I need to discuss with you, and
that's what I'm going to do in the next couple of slides.
Okay? Now the first one is this one, right?
So I told you that, you know, knowing we are choosing the entering variable using
a very interesting criteria. The fact that the objective function,
okay, has a coefficient which is negative for that variable.
Okay, so that's what I told you. We want to do that to convert to an
optimal solution. But, you know, at the beginning of the
lecture, what I was telling you is that we select the entering variable with,
because it has a negative coefficient inside some of these constraints.
So, it may happen that the variable that I'm choosing there has a beautiful
column, okay? Where essentially, all the coefficients
are greater than 0. What does that mean?
None of them is negative, so really the two things that I've told you in this
lecture are contradictory. I want to introduce the variable into the
basis to drive the objective function down, but at the same time, I also want a
negative coefficient and I don't have one.
What is happening? What is happening?
Okay? So think about it.
So what is the basic feasible solution here, okay?
It takes, you know, the basic variables and assigns them the value, in this
particular case one, two, three, okay? This is the objective function that I
have. What is the value of X one in the basic
feasible solution? It's zero.
Alright? But you see these coefficents, okay?
They are all greater than zero. Okay?
What does that mean? Can you think about what that means?
So can you think of the case where I say, you know, in the basic feasible solution
X one okay is basically assigned to zero. What if I assign it to 10,000?
What am I going to get, okay? Well, this equation is going to be fine,
right? So x2 is equal to 1, if I give 10,000 to
this guy, you know, multiplying by 3 that's going to be 30,000.
You know, I'm going to get the value for x3 which is going to be 30,000 and whah,
okay? That's fine, that's still feasible.
What about the second one? Same thing right?
This is positive. I'm going to add a positive number to x4
and that's fine. And same thing for x5.
So if I take, you know, 10,000, I have another solution, okay.
It's not a basic feasible solution, but it's a solution right.
What about if I give a million to x1? That's fine as well right.
If I give 10 million it's going to be fine.
What do these values do to the objective function?
They are driving this objective function down.
Why? Because this guy is a negative
coefficient. So what this really means here is that I
can take the value of x1 and giving arbitrarily large positive values, and
that's going to make the objective function arbitrarily large.
So which basically means that my algorithm here is not bounded by below.
I can drive the objective function as low as I want, okay?
Which is one of the hypotheses that I told you that I needed to have for
actually terminating. So in a sense what I'm telling you is
that the simplest algorithm is not bounded by below.
You will come to a situation where you see this volume you want to put inside
the basics but you cannot. And so that's the case where you, you can
jet, you can detect that your product is actually unbonded.
And you can stop executing at this point. You can report to the user that, you
know, that you can drive this optimization function arbitrarily, you
know down, okay, low. And typically that means that there is a
mistake in the modeling. Right?
So because if you think of a factory which is trying to decrease its costs.
And the solution of this complex algorithm is basically telling the
manager you can drive your cost arbitrarily low.
Something should be fundamentally wrong. Now if you maximize you can drive it
arbitrarily high. >> Its like you know telling the CEO of
Apple you can maximize your profit arbitrarily high That's probably not
right, okay? So essentially, you can detect that the
problem is unbounded and make sure that the user actually knows that.
They have to look at their model and try to do it better.
Now, there is the other things that I mentioned is that one of the hypothesis
that I told you about is that I don't want the bi's to become zero.
What happens if a bi happen's to be zero, right?
So look at these constraints here. I'm basically letting x3 be equal to 0.
That's fine. This is a basic feasible solution.
It's just that there is a basic variable known and that is the value zero.
The known basic variable views the other value zero.
But now what happens if I select a variable to enter the basis?
Remember the pivoting rule, you know, computes as a ratio.
I know I have a ratio zero divided by something is always going to be zero.
That value is always going to be the smallest one.
So you always select that constraint to enter the basics, which basically means.
That when you do the pivot thing, okay. So you going to stay at the same value of
the objective function. Because x3 you know, is going to be
kicked out of the basis, okay. So you, you, nothing happens there.
But x2 is going to basically enter the basis but get a value zero obviously.
And therefore, the objective function is basically not changing.
The objective value is not changing, okay?
So what does that mean? That means that the hypothesis that I
told you before, okay, is wrong. Well valid, it's not valid, it's not
satisfied and I have to find essentially another way to guarantee termination.
So one of the things that I told you about this five facts, okay So is wrong.
Its not always possible to move from a basic feasible solution to another basic
feasible solution with the better cost. I can actually move to another you know
another top of the mountain which is exactly the same height.
OK. So what do we do?
OK so we have to use, we have to be a little bit careful in how we implement
the algorithm and there are very useful ways to do that.
I, I will mention that two of them in a little bit of details and they are all at
once, okay, but you can use essentially a selection of the variables that you want
to make enter the basis in a very specific way and that will garauntee your
race termination, okay, and so the key point is that you look at the objective
function. If you only select the first variable
which is a negative sign, okay, negative coefficient, then you are going to
terminate... But sometimes you really don't want to do
that. For instance a lot of the, a lot of the
simplex algorithm will take a value which coefficient, which is highly negative.
Because if you give a positive value to that particular variable it's going to
drive this, you know, down very quickly, okay.
So this is somewhat restrictive. This is, this is putting some limitation.
To what you can do. The other thing that you can do is do a
pivoting rule, which is a little bit more complex.
Instead of choosing the ratio that I've shown you, you can actually see, you can
actually generalize it to a lexicographic order.
So if the, if the, if there are ties when you do this ratio You move to the next
column, you know, the first coefficient, and you do the same thing and so on and
so forth and if you do that once again. If you do, if you select the leaving
variable in that particular way you will also guarantee termination, so this is
interesting, right, there is somewhat of a duality and it's interesting to talk
about duality for linear programming... But you can, you can put a role you know
which select the entering variable rule that select the leaving variables, and
both of them would guarantee termination. And then you know typical implementation
of also methods for perturbing the basis, so you change a little bit the problem
and then you go back to that later on. But you basically make sure that, you
know, you you don't have this. You don't stay the same place when you
are doing these pivoting operations. Okay.
So I won't go into the details but there are ways to actually address them and,
you know, actual implementation will combine these with better pivoting rule
to actually drive the search quickly. But we can make this algorithm termanate
even if the bis are actually. getting to zeroes.
Okay, so, we know when the, so, so the two things that I've shown you is that we
know or we can predict that the problem is unbounded, that's one of the
hypothesis that I did and we can also detect that, we can also insure
termination if the BI's are actually getting to zero by using this more
clever, you know, People think selections.
So there is one more thing I need to do before we know exactly how to implement
the algorithm and this is actually really beautiful.
This is really clever. So essentially What I've been doing the
entire lecture, I've always assumed that we had a basic feasible solution to start
with, right. But in practice, you won't necessarily
have that, yeah. The user is basically giving you this set
of equations, okay, and these objective function You have actually no clue that
these equations are actually, you know, feasible.
Okay, now there is a feasible solution to these equations.
So, so the problem is the how do I find my first BFS?
Okay? I may not have it.
And it may not be a obvious, obvious how to actually get it, okay?
So what I'm going to do, is I'm going to do a very simple trace, right?
I'm going to add a new set of variables, okay?
Just step out here so that you can see them, okay?
But I'm adding one. We call artificial variables, so y1, yi,
you know, ym, are artificial variables. They are new variables that are just
created out of nowhere, right? And I put them into the equations of the
simplex algorithm, okay? Now, I put them in a very, you know,
simple way, right? So, y1 for the first constraint, y2 for
the second one, yi for the i n. For constraint i, and ym for the last
one. So now, essentially, when you see this
thing, you are like, smiling, right? Because now I have an easy BFS, right?
So this is essentially a BFS. This is essentially a, a, this, I can use
these variables to put inside a basis, and I have a BFS, okay?
But obviously, you know it's a BFS for another problem.
A problem where, you know the y's are actually the variables.
So now I have an obvious solution which is assigning these y's to the other ones,
which basically means that all of the other guys are zero.
But that's not a feasible solution to my initial problem, right?
Because I wanted these guys to be equal to the BI's okay so what am I going to
do? Okay, and this is where the beauty is
Right? So the beauty is so so the beauty here is
that we are going to the simplest algorithm to actually find the real BFS
from this fake BFS. Okay?
So this is what we are going to do so so
so this is called a two faced method. Okay.
And the first step is going to be, I want to find the BFS if there is one, okay?
And then the second step is, once I have one of these BFS, I'm great, right?
So I can apply the simplex algorithm for optimizing.
But the first one, I want, I will use essentially the simplex algorithm to find
a basic feasible solution. How do I do that?
Well, it's very simple, right? So, if I have a feasible solution to this
set of equation, that means that the y variable should be assigned to 0, OK?
So what I'm going to do is basically minimize the sum of these y's.
And remember, these y's have to be, you know, they are greater than or equal to
0, so If, if essentially this function goes to 0, it means that every 1 of them
is equal to 0 and therefore these, these values here have the value 0 and that
means that I have a feasible solution to this particular set of contraints.
Okay, so what I do? No but this is beautiful, right.
Why is it beautiful? Because I have this basis here.
I love this basis, right. I have this basis, I have all this
variables that I can put inside you know as basic variables and then I have an
offical. Then I can optimize this thing [SOUND],
and then I look at what the objective function is, if it's greater than zero I
know that I don't have a feasible solution to this, to this constraint.
So an initial set of constraints is wrong, okay?
It's basically not feasible. So you go back to the user and say, you
know, please give me a problem with this constraint that satisfies because
otherwise, you know there's little purpose to actually optimize Okay?
But if these values, see if the objective function is 0, that means that this set
of constraint is feasible, and now, I'm ready to do the optimization.
Right? Because at this point I have a basic
feasible solution. Okay?
And this basic, basic feasible solution is in the, in terms of the other
variables. Right?
So So, in a sense, there you can take the basic feasible solution.
We move up, you know, this, this objective, you know, function, use the
original objective function. Remove the non basic variable, the basic
variables from these active function, and start again the simplex algorithm using
that new objective function, which is the one you wanted to optimize in the first
place. So, all the things that I told you are
almost right, okay? So, they only I put it as I told you,
when we complete this optimization, we have a basic feasible solution, where the
basic variable are all the varibale, which are, you know, the original
varibles of the problem. They are not the basic variable.
That's not entirely true. It can be the case that one of these
basic values, these, these artificial variables in, in the basis.
But no you just need to think about it. If one of these variables is inside the
basis, what does it mean? What is the value of that artificial
variable, okay? Well, we know that the objective function
is zero, okay? So that variable has to be zero, okay?
So, at that point, what you can do is transform this, you know, remove it from
the basis, introduce someone else inside the basis.
And now you will have really a basic feasible solution expressed only in terms
of the basic variables and then you can solve the optimization phase, okay?
So this is it, you know, you have seen the entire simplex algorithm now, okay?
You have a two-phase method. First, find the BFS and then optimize.
How do you optimize, okay? Basically, what you do is you move from
basic solution to basic solution, okay? You can detect that you're already at the
end when all the coefficients of the variables, okay, in the objective
functions are greater than zero, okay, and every time the BIs are strictly
positive essentially what you do is you decrease the value of this objective
function. If you use one of the rules that I told
you you are garaunteed to terminate, okay.
Beautiful algorithm, local search, garaunteed to find the optimal
solution... Thank You. [BLANK_AUDIO]