0:00

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?

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]