Inverse of the basis times ANxN, okay. And now one of the things you may ask is,

oh, what is the cost, because I haven't covered the cost yet.

But the cost we can express in exactly the same fashion, all right.

So we can see set at cx equal to what, cB times, you know, xB.

So these are the basic variables. And then cN times xN which shall, done on

basic variable. Of course once you have that well we know

value of the xb the the basic variable so we can reexpress them in this in some

sort of this equation and that's what I'm going to do in the next equation okay so

take a deep breath because that's going to be.

Ugly formula, okay, but very simple. So what we know is that we want to

compute CX, okay? So you have CX times B plus CN times XN,

okay? Now we know the value of XB, this is this

ugly, you know, inverse of the basis time B minus inverse of the basis time AN time

you know, X, XN okay, and that's what we just did here, okay?

So we just substituted inside the val, for the value of XB, okay?

So you see this is the second equation, okay?

Now I invite you to look at the third equation which is basically a simple

distribution. A simple algebraic manipulation there.

So that I can isolate, you know, the constant term and then the term which is

only associated with the variable the non-basic variables.

Now the next line, actually the next two lines, so what we do here is interesting,

alright? So when you look at the, when you look at

what we have done so far, you see this expression which is multiplying,

multiplying the non-basic variables. So, so, so essentially this expression is

in terms of the nonbasic variable, using also you know, the notation cN and AN

which is part of the matrix which are used in, for, only for the nonbasic

variables. What I would like is to have this

expression, but to re-express in terms of the whole overall matrix.

And that's what I'm going to do in the next two lines.

Okay? The first thing that I do is that I say,

okay, so this is about cN And A N, I want to have the same kind of relationship,

but for the cBs and the ABs okay? Because if I do that then I can merge the

cB and the cN, the AN and the AB, and I have the global matrix and the global

cost. And that's what I'm doing here, I'm

adding a term for the cBs. Okay?

And this term is essentially zero. Why?

Because I have cB over here, okay? And then I have cB times the inverse of

the basis Times AB. Okay?

Now, the inverse of the basis, you know, time, times the basis.

That's going to be the diagonal matrix. So, what I get here is basically cB minus

cB, which is 0. Okay?

So this is why this term is 0. But now when I basically re-express these

two terms together, I get this beautiful, really beautiful, truly beautiful

expression, which is what? Which we see, you know, no basic

variables, no non-basic variables is the entire coefficient, that row of

coefficients, Okay? And then I get one CB here, you know,

times AB minus 1, Okay? And then I have the real matrix, A.

Right? So in a sense the only thing here which

depends on the basis are basically this expression in the middle.

And this is actually very important and you'll see why.

But the c here is a real, you know, doesn't depends on the basic or nonbasic

variable, and you have the real matrix A, okay?

So this is essentially all you can re-express cx, cx is equal this

expression. Where you have the value of the constant

there, you know, and then you have basically the non-basic variables over

there. You know, we try expressing sums of C and

then A, and then these things. And this thing, we're going to denote

them pi. And this pi, so very important.

Okay, you'll see them all, you know, all over in the next two lectures They are

called simplex multipers. So pie is equal to Cb times inverse of

the bases. Okay.

Now sometimes I'm going to say P because Pie in Greek is P and I'm going to be

confused. But you know i'm trying to pie all the

time but in Greek is P so I'm confused alright.

so, but this complex multiplier, I have this value which is very important, it's

cb times the inverse of the bases. Okay?

Now so this cost here, cx, I can reexpress in terms of these simplest

multipliers, as simply Pi B minus C, minus Pi A times X, okay?

So, this is, this, this equality is very nice, because no, it's only expressed in

terms of this simplex multipliers, and it becomes this beautiful thing, you know.

C minus...so, C minus Pie A over there. And this is very important.

Why is it very important because at optimality we know that we have a

property of these guys. Right?

What is the property, do you remember that beautiful property?

These guys have to be greater or equal to zero, okay.

So the relation here C minus PA has to be non-negative.

Okay, so this is what I'm basically trying to do.

So this thing here is the same as that, expressing the, the simplex multiplier, I

know that c is to be greater or equal to pi A.

Okay? So, which is essentially equivalent to

this because pi is equal to cB times the inverse of the basis.

okay? Now once you have that, this is very

interesting. Okay, so I know that the basis is optimal

if these costs are non-negative. And I have this relationship between C

and PiA, okay? And once I have done, I can very easily

prove now that optimality, you know these these these you know, these concepts to

be greater than zero, okay? So let's see, let's denote C star, okay?

You see C star, okay? C star is equal to C minus PiA, okay?

And I also have c 0 star which is the value of pi b which is like c b times the

inverse of the bases times b. And so this is the value of the function

atop finality, right? And so what I need to prove is that these

guys So that, the, the solution where c is greater than pi A is an optimal

solution. I need to prove that.

Okay. So what am I going to do.

I know that I have detected, I believe I have detected optimality, which is the

property that c is greater than pi A, okay?

And that's what you see there. and now what i'm going to do is that I'm

going to take another arbitrary feasible solution y, and i'm going to show you

that the cost of y, the objective function for that basic feasible

solution, is going to be greater than c zero star.

If I show you that it means basically when I get To a particular basic feasible

solution where c is greater than pi a, then I know that I am at the optimal

solution. And how do I do that?

It's very simple, this one. Okay, so what do I know about y?

I know that it has to be a feasible solution, right.

So what I know is that it has to satisfy this constraint, which is Ay is equal to

b, okay And I just have to this the following manipulation okay.

So I have the cost Cy so that's the cost of the feasible solution Y.

Now I know I know because you know I'm basically detecting these property that C

great than. Pi a.

So I can replace this c by pi a, and so c y is going to be greater than pi a times

y. Okay?

Now, you look at this expression here. It's nice, right?

So it's pi a y. But what do I know about y?

I know that y is to satisfy this condition, so Pi y is to be equal to b,

okay? So I get essentially the value pi b and

pi b is the value of the solution at that base when this condition is satisfied.

So I end, so this is the optimal solution because essentially any of the feasible

solution is going to be greater than that.

So what I'm basically going to be showing you here, with matrix notation, is that

every time I detect that this property is, you know, satisfied, the constantly

objective functions are all positive now, I'm basically optimum.

Okay, so that's why, you know, this matrix notation is some, is used for some

of these properties are easier to state. Okay, now the other things that I need to

tell you, and this is really important, is the tableau.

Okay, so a lot of the papers, a lot of the books that you're going to read, I'm

going to work with this tableau. And essentially this tableau is going to

put everything together in, you know, the right hand side, the left hand side.

All this the basis, everything in one big matrix, okay.

One big array. Okay?

So, so we're going to put all these coefficients, we're going to put all, all

these coefficients of the objective function.

All the coefficients of the matrix here. The right hand sides, you know.

All these things are going to be in one big tableau.

And then you can do pivoting, or simple naive implementation of the the, the

simplex algorithm very easily with one big matrix.

Of course, you know, practical implementatoin, don't do that.

There are much, you know, th-, th-, th-, th-, th-, they are, they are much more

efficient representation, because most of the time this matrix is sparse and you

want to, you know, exploit that sparsity. But this is the tableau.

Okay? And this is all you can actually compute

these things, you know by hand or simple implementation.

Okay? So this is essentially the system of

equations that I've shown you, and this is the first basic feasible solution that

I'm showing you for that particular system, okay?

And so what I want to show you is that we have the basis, we gotta have the right

end side, we gotta have the you know, we gotta have the objective function

represented there, okay? There are some convention and some of

them may not be natural but these are the convention most people are using.

Okay? So what you see there, the first row here

is going to be the negation of the objective volume.

Okay? So the way to think about this, in terms

of what we have done before, it's like exactly, you know, when we were looking

at the objective function, that's what was on the right-hand side.

Except the value here, which is going to be negated.

Okay? The va, the, the constant is going to be

negated but, all these guys think of that.

They were on the right hand side of this, this, of, of the formulation that we

have, that we were using when we were doing you know the representation where

the, the, the basic variables were isolated from the non-basic variable.

What you there you see the basic variable.

The basis okay. And the basic variable is always going to

be a nice matrix you know 1 0 0 0 0 0 1 0 0 0 the 0 1 0 0 0 1.

That matrix can be anywhere it's going to move right.

And it doesn't have to be that order but somewhere they will be basic variables

with 1 0 0. 010 and 001 and of course you can

generalize that, okay? And then you see the right inside over

there, these are the b values that you see over there, okay?

So basically, this is a particular, this is the basic feasible representation

expressed by the tableau. So you see the basic variables there,

okay? So they are one, you know, the, the, the,

they are there. The other ones are like what we have seen

before but we brought them in a sense you have to think about them, we brought them

to the left side. Okay, and so the coefficient that they

have are the negation of the coefficient. When we were represented that as a set of

equation, okay? So instead of leaving a 2, you have a

minus 2, instead of leaving a minus 3, you get a 3, okay?

So this is basically the tubler representation, okay?

So we look again at this tubler representation and see that we are doing

the simplex algorithm on top of this one, okay?

So what we're going to do is going to, we're going to look at basically the

objective function, and once again. If all the values there are strictly

positive okay well greater or or not negative okay, we will be at optimality.

In this particular case it's not the case.

Okay, so you can see that we have a minus 3 and minus 3 over there and so that

basically means that these two variables want to enter the basis, okay.

They say, ooh, I want to go into the basis, okay.

And so we can actually, you know and, you know, select a variable to enter the

basis. And now we left to select a variable to

lift the basis. And once again remember you know we flip

the size of this non basic variable. So before we were looking at variables

with a negative coefficient. since we flipped them, you know, from one

side to the other. In this box, in this case, we have to

look with values that are, that are positive.

So, for these particular guys, we going to look at the first equation.

We going to look at the last one. These are the two equations that we can

select. We are going to compute the ratio between

that co-efficient and the value B. In the first case, it's going to be 1/2,

in the second case it's going to be 1. So the variable, the, the constraints

that we are going to use to pivot is going to be the first constraint.

We're going to do the pivoting operation, and this is the resulting tableau, okay?

So once again, what you're going to see is the objective function in the top row,

okay? And know, the nice thing is that you see

these guys, they are strictly positive which basic they are, which basically

means that we are a toptemality, okay? And these are the values of the non-basic

variables, okay? So now, once again, you see the tableau

there you see the variable x2 there? One, zero, zero, that's part of the

basis. You see zero, one, zero and then you see

zero, zero, one. Okay?

This is the basis. You see that, you know some of the column

of this basis, basis are not interleafed with some of the column of the non basic

variables. Okay?

And obviously you see the value of the non basic variables.

Okay? x2 now is equal to three and a half.

You know x4, somewhere here, is equal to seven and a half and so on, okay.

And the value of the objective function at this point can be found in this column

and it's can be found in this column. And its value here is minus nine and a

half which means that. The real, the, but this is minus the

effective function, so this is going to be four and a half.

Okay? So, this is what the tableau does, okay?

Basically the same information that we have seen before, but it's kind of put in

one big matrix, with the, with various convention, okay?

So, this is essentially this transition lecture, so I'm done, so I've shown you

how actually we can use this matrix notation, it's very convenient in

general, okay, once you get used to it. And the tableau is also something that is

very nice, and we'll be able to express some beautiful property, just reasoning

about this tableau later on. Okay?

So thank you very much.