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.

Â