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. 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.