0:00

Okay guys, so this is discrete optimization, linear programming.

Okay. And this is part four.

Okay? So this is going to be a transition

lecture. Okay?

Between the basic you know, simplex algorithm and duality theory, which is

this beautiful marvelous thing that you need absolutely to know baout, okay.

This is essentially introducing a bunch of notations, okay, of what we have seen

already. Re-proving, proving some of the results

we saw, we've all proved before, using that notation so you don't have to get

familiar with yourself, and then introducing this tableau.

Okay? Which is really a very useful tool when

you actually implement the simplex algorithm, or you do things by hand to

actually understand them better. Okay?

So, this is a lot of notations today, I'm trying to make it easy for you, but this

is also very useful is you start reading papers, if you start reading books You

need to understand, you need to understand some of these notations.

Okay? It's all trivial, but it's kind of

boring, right? and it's kind of confusing.

So, this is essentially a system of linear equations.

Okay? And one of the things that we need to do

when we talk about matrix notation, or the table, is to basically view this as a

big matrix. Okay?

So, our Yeah. So essentially what you see here, you

have all the coefficients of all these variables.

You can view them as a matrix, right? So first column, second column, third

column and so on. So there are as many columns as there are

variables. There are as many rows as there are

constraints. And these guys are going to be the right

hand side, so we're going to see that you know, as well, inside the tableau at some

point. Okay, so typically what we do when we are

doing the simplex algorithm is that we have the basis, you know these are going

to be the basic variables. The other ones are going to be the

non-basic variables. All of this you have seen, mastered, you

love this thing, hopefully, so the basis here is variable three, four, and five.

Sometimes we've gotta call this guy, the matrix there, the basis as well.

You know this is kind of abusing notational language.

Okay, so remember in most of the other lecture work we were doing is basically

taking the basic variable, isolating them, they become part of the left side.

Okay. They are expressed in terms of the

constant and then the rest of the non-basic variables.

Okay, and so that's what we did. Okay, so once again, you can view this

thing here as a matrix. It's part of the big matrix here okay,

once we do some operation on it. And this is kind of also a part of the

matrix, but which is very nice like, it's like, you know, a diagonal matrix.

Okay? So I'm going to show you that in detail.

Okay? So essentially you can re-express the

whole thing here in terms of basically two matrices.

Okay? And then some you know, vectors, call

them vectors, okay? For the variables, for the basic

variables and the non-basic variables. Okay.

So the basis is always going to be, you know, in general, well yeah.

So, so let's forget, so this basis here is a very nice form, but it's not always

going to be the cases. But let's say this is the part of the

matrix associated with the basic variables.

You see the basic variables over there. This is essentially the part of the

matrix which is associated with that. Okay.

In this particular case is 1, 0, 0, 0, 1, 0, 0, 0, 1.

Okay. And then the rest here is the part of the

matrix when you see this big thing over there.

Right. Associated with the non-basic variable.

Okay, which is x, x1, x2 and then x6 over there.

Okay? So you see the first vol, the first basic

variables there, you know, Well the first non-basic variable there,

x1. It has, it has a column which is 3 to 1

and that's the column that you see here. Right?

So 3 to 1. Then you see the next variable there, x

2, okay so the column is 1 0 0. Okay, this is the column that you see

there, 1 0 0. Okay?

And then finally you have the column for x 6, which is basically 0 1 1, okay?

And you see 0 1 1 there. I mean, you see it, I don't see it, I

can't tell you the screen that I'm looking there, is so tiny and is

reversed, there is no way I can see anything.

And so, but this is very interesting and exciting, right?

And then you see the right column there which is basically the coefficients that

you see there. Okay?

So, this is basically the, the matrix notation, and then we're going to use

some, you know, nice algebraic notation for you know, representing this.

This is A Substraited by B because this is associated with the basic variable Xb

the basic variable this is An that's a part of the big matrix which is

associated with the non basic variable these are the basic variables and this B.

Okay so once again the formula that I'm always going to tell is we have what.

Ab times Xb plus An times Xn okay. is equal to b.

Okay. So this is basically reformulating this

entire system of equation, as a formula about, you know with matrix notation.

Okay? So in a sense, everything that I told you

last time can be summarized in this particular form, okay.

So we have a system of equations A x is equal to b, okay.

Now I have to find a basic feasible solution, how do I do that?

I take a set of linearly independent columns in, in the matrix A, okay?

These columns are called A-B. These are columns, the columns of the

basic variables. And then I start re-expressing these

basic variables in terms of the non-basic variables.

So I have these first constraints that I've just described on the previous

slide, right? A b times x b plus A n times x n is equal

to b. Okay?

Now I want to isolate the, the basic variables, okay?

So I have A x. You know, ABXB on the left hand side.

And on the right hand side what do I get? I get B minus ANXN, Okay?

So once again, basic variable, non-basic variable.

I still have a matrix there, Okay? So, if it's not you know, the nice

diagonal matrix, unit diagonal matrix, I have to basically get rid of it.

So I basically compute its inverse, you know, multiply you know, the inverse by

the matrix itself, which is basically the diagonal matrix that I wanted.

But then on the right hand side, you see basically the inverse of the basis.

A b minus one times b this time, and then you see A B minus one times A N times x

N. Okay.

And these, and these basically give you the expression of the basic variable in

terms of non-basic variables. Okay.

Now when we do these operations you know, in the equation before, what we get is we

get a new set of right hand side b prime, which is equal to this Ab minus 1 times

b, okay? That was you have there and then you get

new coefficient for the non-basic variables, which you know, I'm courting

you here is. And prime, which is basically that's a

type of the matrix which is associated with the non basic variable.

Okay? So, so this is essentially a basic

solution, right? And it's going to be feasible if all the

b primes are greater than 0. So, this is how I compute A basic

feasible solution, right? So, I'll select this, you know m linearly

independent column. I'm re-expressing the basic variables in

terms of the other one, and I'm testing feasibility here, right?

So, same thing as we have seen in the previous lecture, but just in matrix

notation, okay? Now, the matrix AB is also called a

basis. As I told you, you know, we call basis a

lot of things, okay. So, in a sense, linear programming, okay.

So, this is the, the statement of the problem.

You minimize cx, you know, we've the constraints Ax equals b, okay.

And then you get this basic feasible solution here which express xB in terms

of the non basic variable using this matrix notation.

Inverse of the basis times b minus, you know, inverse of the basis.

7:11

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.