1 00:00:00,280 --> 00:00:03,380 Okay guys, so this is discrete optimization, linear programming. 2 00:00:03,380 --> 00:00:05,750 Okay. And this is part four. 3 00:00:05,750 --> 00:00:08,060 Okay? So this is going to be a transition 4 00:00:08,060 --> 00:00:09,025 lecture. Okay? 5 00:00:09,025 --> 00:00:13,230 Between the basic you know, simplex algorithm and duality theory, which is 6 00:00:13,230 --> 00:00:17,420 this beautiful marvelous thing that you need absolutely to know baout, okay. 7 00:00:17,420 --> 00:00:21,190 This is essentially introducing a bunch of notations, okay, of what we have seen 8 00:00:21,190 --> 00:00:23,910 already. Re-proving, proving some of the results 9 00:00:23,910 --> 00:00:26,910 we saw, we've all proved before, using that notation so you don't have to get 10 00:00:26,910 --> 00:00:29,970 familiar with yourself, and then introducing this tableau. 11 00:00:29,970 --> 00:00:32,050 Okay? Which is really a very useful tool when 12 00:00:32,050 --> 00:00:35,310 you actually implement the simplex algorithm, or you do things by hand to 13 00:00:35,310 --> 00:00:36,840 actually understand them better. Okay? 14 00:00:36,840 --> 00:00:42,260 So, this is a lot of notations today, I'm trying to make it easy for you, but this 15 00:00:42,260 --> 00:00:45,690 is also very useful is you start reading papers, if you start reading books You 16 00:00:45,690 --> 00:00:48,980 need to understand, you need to understand some of these notations. 17 00:00:48,980 --> 00:00:51,010 Okay? It's all trivial, but it's kind of 18 00:00:51,010 --> 00:00:54,340 boring, right? and it's kind of confusing. 19 00:00:54,340 --> 00:00:57,650 So, this is essentially a system of linear equations. 20 00:00:57,650 --> 00:00:59,980 Okay? And one of the things that we need to do 21 00:00:59,980 --> 00:01:04,440 when we talk about matrix notation, or the table, is to basically view this as a 22 00:01:04,440 --> 00:01:05,470 big matrix. Okay? 23 00:01:05,470 --> 00:01:08,670 So, our Yeah. So essentially what you see here, you 24 00:01:08,670 --> 00:01:10,510 have all the coefficients of all these variables. 25 00:01:10,510 --> 00:01:14,480 You can view them as a matrix, right? So first column, second column, third 26 00:01:14,480 --> 00:01:16,890 column and so on. So there are as many columns as there are 27 00:01:16,890 --> 00:01:18,780 variables. There are as many rows as there are 28 00:01:18,780 --> 00:01:20,940 constraints. And these guys are going to be the right 29 00:01:20,940 --> 00:01:24,211 hand side, so we're going to see that you know, as well, inside the tableau at some 30 00:01:24,211 --> 00:01:27,460 point. Okay, so typically what we do when we are 31 00:01:27,460 --> 00:01:30,260 doing the simplex algorithm is that we have the basis, you know these are going 32 00:01:30,260 --> 00:01:32,660 to be the basic variables. The other ones are going to be the 33 00:01:32,660 --> 00:01:35,470 non-basic variables. All of this you have seen, mastered, you 34 00:01:35,470 --> 00:01:40,240 love this thing, hopefully, so the basis here is variable three, four, and five. 35 00:01:40,240 --> 00:01:43,270 Sometimes we've gotta call this guy, the matrix there, the basis as well. 36 00:01:43,270 --> 00:01:46,204 You know this is kind of abusing notational language. 37 00:01:46,204 --> 00:01:49,619 Okay, so remember in most of the other lecture work we were doing is basically 38 00:01:49,619 --> 00:01:53,070 taking the basic variable, isolating them, they become part of the left side. 39 00:01:53,070 --> 00:01:54,720 Okay. They are expressed in terms of the 40 00:01:54,720 --> 00:01:58,638 constant and then the rest of the non-basic variables. 41 00:01:58,638 --> 00:02:03,670 Okay, and so that's what we did. Okay, so once again, you can view this 42 00:02:03,670 --> 00:02:07,260 thing here as a matrix. It's part of the big matrix here okay, 43 00:02:07,260 --> 00:02:11,099 once we do some operation on it. And this is kind of also a part of the 44 00:02:11,099 --> 00:02:14,730 matrix, but which is very nice like, it's like, you know, a diagonal matrix. 45 00:02:14,730 --> 00:02:16,944 Okay? So I'm going to show you that in detail. 46 00:02:16,944 --> 00:02:19,660 Okay? So essentially you can re-express the 47 00:02:19,660 --> 00:02:23,350 whole thing here in terms of basically two matrices. 48 00:02:23,350 --> 00:02:25,680 Okay? And then some you know, vectors, call 49 00:02:25,680 --> 00:02:27,920 them vectors, okay? For the variables, for the basic 50 00:02:27,920 --> 00:02:30,100 variables and the non-basic variables. Okay. 51 00:02:30,100 --> 00:02:33,440 So the basis is always going to be, you know, in general, well yeah. 52 00:02:33,440 --> 00:02:37,120 So, so let's forget, so this basis here is a very nice form, but it's not always 53 00:02:37,120 --> 00:02:39,610 going to be the cases. But let's say this is the part of the 54 00:02:39,610 --> 00:02:42,040 matrix associated with the basic variables. 55 00:02:42,040 --> 00:02:45,550 You see the basic variables over there. This is essentially the part of the 56 00:02:45,550 --> 00:02:47,880 matrix which is associated with that. Okay. 57 00:02:47,880 --> 00:02:51,860 In this particular case is 1, 0, 0, 0, 1, 0, 0, 0, 1. 58 00:02:51,860 --> 00:02:54,570 Okay. And then the rest here is the part of the 59 00:02:54,570 --> 00:02:56,780 matrix when you see this big thing over there. 60 00:02:56,780 --> 00:02:59,410 Right. Associated with the non-basic variable. 61 00:02:59,410 --> 00:03:06,090 Okay, which is x, x1, x2 and then x6 over there. 62 00:03:06,090 --> 00:03:09,320 Okay? So you see the first vol, the first basic 63 00:03:09,320 --> 00:03:14,135 variables there, you know, Well the first non-basic variable there, 64 00:03:14,135 --> 00:03:17,090 x1. It has, it has a column which is 3 to 1 65 00:03:17,090 --> 00:03:19,820 and that's the column that you see here. Right? 66 00:03:19,820 --> 00:03:22,895 So 3 to 1. Then you see the next variable there, x 67 00:03:22,895 --> 00:03:27,080 2, okay so the column is 1 0 0. Okay, this is the column that you see 68 00:03:27,080 --> 00:03:28,260 there, 1 0 0. Okay? 69 00:03:28,260 --> 00:03:33,400 And then finally you have the column for x 6, which is basically 0 1 1, okay? 70 00:03:33,400 --> 00:03:36,350 And you see 0 1 1 there. I mean, you see it, I don't see it, I 71 00:03:36,350 --> 00:03:38,980 can't tell you the screen that I'm looking there, is so tiny and is 72 00:03:38,980 --> 00:03:41,580 reversed, there is no way I can see anything. 73 00:03:41,580 --> 00:03:43,870 And so, but this is very interesting and exciting, right? 74 00:03:43,870 --> 00:03:47,350 And then you see the right column there which is basically the coefficients that 75 00:03:47,350 --> 00:03:48,210 you see there. Okay? 76 00:03:48,210 --> 00:03:51,990 So, this is basically the, the matrix notation, and then we're going to use 77 00:03:51,990 --> 00:03:55,710 some, you know, nice algebraic notation for you know, representing this. 78 00:03:55,710 --> 00:04:00,680 This is A Substraited by B because this is associated with the basic variable Xb 79 00:04:00,680 --> 00:04:04,820 the basic variable this is An that's a part of the big matrix which is 80 00:04:04,820 --> 00:04:08,910 associated with the non basic variable these are the basic variables and this B. 81 00:04:08,910 --> 00:04:13,570 Okay so once again the formula that I'm always going to tell is we have what. 82 00:04:13,570 --> 00:04:22,690 Ab times Xb plus An times Xn okay. is equal to b. 83 00:04:22,690 --> 00:04:24,900 Okay. So this is basically reformulating this 84 00:04:24,900 --> 00:04:30,215 entire system of equation, as a formula about, you know with matrix notation. 85 00:04:30,215 --> 00:04:33,420 Okay? So in a sense, everything that I told you 86 00:04:33,420 --> 00:04:37,290 last time can be summarized in this particular form, okay. 87 00:04:37,290 --> 00:04:41,340 So we have a system of equations A x is equal to b, okay. 88 00:04:41,340 --> 00:04:44,240 Now I have to find a basic feasible solution, how do I do that? 89 00:04:44,240 --> 00:04:50,300 I take a set of linearly independent columns in, in the matrix A, okay? 90 00:04:50,300 --> 00:04:52,975 These columns are called A-B. These are columns, the columns of the 91 00:04:52,975 --> 00:04:57,800 basic variables. And then I start re-expressing these 92 00:04:57,800 --> 00:05:00,950 basic variables in terms of the non-basic variables. 93 00:05:00,950 --> 00:05:04,310 So I have these first constraints that I've just described on the previous 94 00:05:04,310 --> 00:05:08,450 slide, right? A b times x b plus A n times x n is equal 95 00:05:08,450 --> 00:05:09,490 to b. Okay? 96 00:05:09,490 --> 00:05:12,760 Now I want to isolate the, the basic variables, okay? 97 00:05:12,760 --> 00:05:17,390 So I have A x. You know, ABXB on the left hand side. 98 00:05:17,390 --> 00:05:23,760 And on the right hand side what do I get? I get B minus ANXN, Okay? 99 00:05:23,760 --> 00:05:26,630 So once again, basic variable, non-basic variable. 100 00:05:26,630 --> 00:05:30,390 I still have a matrix there, Okay? So, if it's not you know, the nice 101 00:05:30,390 --> 00:05:34,340 diagonal matrix, unit diagonal matrix, I have to basically get rid of it. 102 00:05:34,340 --> 00:05:38,830 So I basically compute its inverse, you know, multiply you know, the inverse by 103 00:05:38,830 --> 00:05:42,090 the matrix itself, which is basically the diagonal matrix that I wanted. 104 00:05:42,090 --> 00:05:45,550 But then on the right hand side, you see basically the inverse of the basis. 105 00:05:45,550 --> 00:05:51,090 A b minus one times b this time, and then you see A B minus one times A N times x 106 00:05:51,090 --> 00:05:52,150 N. Okay. 107 00:05:52,150 --> 00:05:56,770 And these, and these basically give you the expression of the basic variable in 108 00:05:56,770 --> 00:05:59,290 terms of non-basic variables. Okay. 109 00:05:59,290 --> 00:06:03,240 Now when we do these operations you know, in the equation before, what we get is we 110 00:06:03,240 --> 00:06:08,280 get a new set of right hand side b prime, which is equal to this Ab minus 1 times 111 00:06:08,280 --> 00:06:10,740 b, okay? That was you have there and then you get 112 00:06:10,740 --> 00:06:14,258 new coefficient for the non-basic variables, which you know, I'm courting 113 00:06:14,258 --> 00:06:17,990 you here is. And prime, which is basically that's a 114 00:06:17,990 --> 00:06:21,100 type of the matrix which is associated with the non basic variable. 115 00:06:21,100 --> 00:06:24,590 Okay? So, so this is essentially a basic 116 00:06:24,590 --> 00:06:27,850 solution, right? And it's going to be feasible if all the 117 00:06:27,850 --> 00:06:31,480 b primes are greater than 0. So, this is how I compute A basic 118 00:06:31,480 --> 00:06:35,980 feasible solution, right? So, I'll select this, you know m linearly 119 00:06:35,980 --> 00:06:38,870 independent column. I'm re-expressing the basic variables in 120 00:06:38,870 --> 00:06:41,990 terms of the other one, and I'm testing feasibility here, right? 121 00:06:41,990 --> 00:06:45,360 So, same thing as we have seen in the previous lecture, but just in matrix 122 00:06:45,360 --> 00:06:48,590 notation, okay? Now, the matrix AB is also called a 123 00:06:48,590 --> 00:06:50,510 basis. As I told you, you know, we call basis a 124 00:06:50,510 --> 00:06:54,680 lot of things, okay. So, in a sense, linear programming, okay. 125 00:06:54,680 --> 00:06:56,390 So, this is the, the statement of the problem. 126 00:06:56,390 --> 00:07:00,210 You minimize cx, you know, we've the constraints Ax equals b, okay. 127 00:07:00,210 --> 00:07:04,250 And then you get this basic feasible solution here which express xB in terms 128 00:07:04,250 --> 00:07:07,560 of the non basic variable using this matrix notation. 129 00:07:07,560 --> 00:07:10,890 Inverse of the basis times b minus, you know, inverse of the basis. 130 00:07:11,910 --> 00:07:17,410 Inverse of the basis times ANxN, okay. And now one of the things you may ask is, 131 00:07:17,410 --> 00:07:20,160 oh, what is the cost, because I haven't covered the cost yet. 132 00:07:20,160 --> 00:07:22,780 But the cost we can express in exactly the same fashion, all right. 133 00:07:22,780 --> 00:07:27,740 So we can see set at cx equal to what, cB times, you know, xB. 134 00:07:27,740 --> 00:07:31,610 So these are the basic variables. And then cN times xN which shall, done on 135 00:07:31,610 --> 00:07:34,610 basic variable. Of course once you have that well we know 136 00:07:34,610 --> 00:07:39,270 value of the xb the the basic variable so we can reexpress them in this in some 137 00:07:39,270 --> 00:07:43,610 sort of this equation and that's what I'm going to do in the next equation okay so 138 00:07:43,610 --> 00:07:46,220 take a deep breath because that's going to be. 139 00:07:46,220 --> 00:07:50,740 Ugly formula, okay, but very simple. So what we know is that we want to 140 00:07:50,740 --> 00:07:56,650 compute CX, okay? So you have CX times B plus CN times XN, 141 00:07:56,650 --> 00:07:59,140 okay? Now we know the value of XB, this is this 142 00:07:59,140 --> 00:08:04,350 ugly, you know, inverse of the basis time B minus inverse of the basis time AN time 143 00:08:04,350 --> 00:08:07,680 you know, X, XN okay, and that's what we just did here, okay? 144 00:08:07,680 --> 00:08:12,070 So we just substituted inside the val, for the value of XB, okay? 145 00:08:12,070 --> 00:08:14,970 So you see this is the second equation, okay? 146 00:08:14,970 --> 00:08:18,330 Now I invite you to look at the third equation which is basically a simple 147 00:08:18,330 --> 00:08:21,640 distribution. A simple algebraic manipulation there. 148 00:08:21,640 --> 00:08:26,600 So that I can isolate, you know, the constant term and then the term which is 149 00:08:26,600 --> 00:08:31,580 only associated with the variable the non-basic variables. 150 00:08:31,580 --> 00:08:36,410 Now the next line, actually the next two lines, so what we do here is interesting, 151 00:08:36,410 --> 00:08:38,070 alright? So when you look at the, when you look at 152 00:08:38,070 --> 00:08:41,290 what we have done so far, you see this expression which is multiplying, 153 00:08:41,290 --> 00:08:45,900 multiplying the non-basic variables. So, so, so essentially this expression is 154 00:08:45,900 --> 00:08:51,610 in terms of the nonbasic variable, using also you know, the notation cN and AN 155 00:08:51,610 --> 00:08:55,510 which is part of the matrix which are used in, for, only for the nonbasic 156 00:08:55,510 --> 00:08:57,720 variables. What I would like is to have this 157 00:08:57,720 --> 00:09:01,810 expression, but to re-express in terms of the whole overall matrix. 158 00:09:01,810 --> 00:09:03,650 And that's what I'm going to do in the next two lines. 159 00:09:03,650 --> 00:09:05,720 Okay? The first thing that I do is that I say, 160 00:09:05,720 --> 00:09:10,960 okay, so this is about cN And A N, I want to have the same kind of relationship, 161 00:09:10,960 --> 00:09:15,645 but for the cBs and the ABs okay? Because if I do that then I can merge the 162 00:09:15,645 --> 00:09:20,290 cB and the cN, the AN and the AB, and I have the global matrix and the global 163 00:09:20,290 --> 00:09:22,130 cost. And that's what I'm doing here, I'm 164 00:09:22,130 --> 00:09:24,350 adding a term for the cBs. Okay? 165 00:09:24,350 --> 00:09:26,450 And this term is essentially zero. Why? 166 00:09:26,450 --> 00:09:30,840 Because I have cB over here, okay? And then I have cB times the inverse of 167 00:09:30,840 --> 00:09:33,142 the basis Times AB. Okay? 168 00:09:33,142 --> 00:09:36,710 Now, the inverse of the basis, you know, time, times the basis. 169 00:09:36,710 --> 00:09:40,545 That's going to be the diagonal matrix. So, what I get here is basically cB minus 170 00:09:40,545 --> 00:09:42,060 cB, which is 0. Okay? 171 00:09:42,060 --> 00:09:45,620 So this is why this term is 0. But now when I basically re-express these 172 00:09:45,620 --> 00:09:50,445 two terms together, I get this beautiful, really beautiful, truly beautiful 173 00:09:50,445 --> 00:09:53,990 expression, which is what? Which we see, you know, no basic 174 00:09:53,990 --> 00:09:57,550 variables, no non-basic variables is the entire coefficient, that row of 175 00:09:57,550 --> 00:10:01,480 coefficients, Okay? And then I get one CB here, you know, 176 00:10:01,480 --> 00:10:04,780 times AB minus 1, Okay? And then I have the real matrix, A. 177 00:10:04,780 --> 00:10:07,450 Right? So in a sense the only thing here which 178 00:10:07,450 --> 00:10:10,250 depends on the basis are basically this expression in the middle. 179 00:10:10,250 --> 00:10:12,410 And this is actually very important and you'll see why. 180 00:10:12,410 --> 00:10:15,720 But the c here is a real, you know, doesn't depends on the basic or nonbasic 181 00:10:15,720 --> 00:10:17,740 variable, and you have the real matrix A, okay? 182 00:10:17,740 --> 00:10:21,370 So this is essentially all you can re-express cx, cx is equal this 183 00:10:21,370 --> 00:10:24,620 expression. Where you have the value of the constant 184 00:10:24,620 --> 00:10:27,400 there, you know, and then you have basically the non-basic variables over 185 00:10:27,400 --> 00:10:30,000 there. You know, we try expressing sums of C and 186 00:10:30,000 --> 00:10:34,610 then A, and then these things. And this thing, we're going to denote 187 00:10:34,610 --> 00:10:37,490 them pi. And this pi, so very important. 188 00:10:37,490 --> 00:10:41,280 Okay, you'll see them all, you know, all over in the next two lectures They are 189 00:10:41,280 --> 00:10:46,230 called simplex multipers. So pie is equal to Cb times inverse of 190 00:10:46,230 --> 00:10:47,610 the bases. Okay. 191 00:10:47,610 --> 00:10:52,840 Now sometimes I'm going to say P because Pie in Greek is P and I'm going to be 192 00:10:52,840 --> 00:10:55,200 confused. But you know i'm trying to pie all the 193 00:10:55,200 --> 00:10:57,530 time but in Greek is P so I'm confused alright. 194 00:10:57,530 --> 00:11:03,134 so, but this complex multiplier, I have this value which is very important, it's 195 00:11:03,134 --> 00:11:05,810 cb times the inverse of the bases. Okay? 196 00:11:05,810 --> 00:11:11,675 Now so this cost here, cx, I can reexpress in terms of these simplest 197 00:11:11,675 --> 00:11:18,050 multipliers, as simply Pi B minus C, minus Pi A times X, okay? 198 00:11:18,050 --> 00:11:21,840 So, this is, this, this equality is very nice, because no, it's only expressed in 199 00:11:21,840 --> 00:11:25,540 terms of this simplex multipliers, and it becomes this beautiful thing, you know. 200 00:11:25,540 --> 00:11:30,690 C minus...so, C minus Pie A over there. And this is very important. 201 00:11:30,690 --> 00:11:34,000 Why is it very important because at optimality we know that we have a 202 00:11:34,000 --> 00:11:35,410 property of these guys. Right? 203 00:11:35,410 --> 00:11:38,100 What is the property, do you remember that beautiful property? 204 00:11:38,100 --> 00:11:41,330 These guys have to be greater or equal to zero, okay. 205 00:11:41,330 --> 00:11:47,938 So the relation here C minus PA has to be non-negative. 206 00:11:47,938 --> 00:11:50,350 Okay, so this is what I'm basically trying to do. 207 00:11:50,350 --> 00:11:55,410 So this thing here is the same as that, expressing the, the simplex multiplier, I 208 00:11:55,410 --> 00:11:58,580 know that c is to be greater or equal to pi A. 209 00:11:58,580 --> 00:12:02,280 Okay? So, which is essentially equivalent to 210 00:12:02,280 --> 00:12:06,070 this because pi is equal to cB times the inverse of the basis. 211 00:12:06,070 --> 00:12:08,720 okay? Now once you have that, this is very 212 00:12:08,720 --> 00:12:11,330 interesting. Okay, so I know that the basis is optimal 213 00:12:11,330 --> 00:12:14,580 if these costs are non-negative. And I have this relationship between C 214 00:12:14,580 --> 00:12:18,700 and PiA, okay? And once I have done, I can very easily 215 00:12:18,700 --> 00:12:24,660 prove now that optimality, you know these these these you know, these concepts to 216 00:12:24,660 --> 00:12:29,640 be greater than zero, okay? So let's see, let's denote C star, okay? 217 00:12:29,640 --> 00:12:35,280 You see C star, okay? C star is equal to C minus PiA, okay? 218 00:12:35,280 --> 00:12:40,410 And I also have c 0 star which is the value of pi b which is like c b times the 219 00:12:40,410 --> 00:12:45,796 inverse of the bases times b. And so this is the value of the function 220 00:12:45,796 --> 00:12:48,702 atop finality, right? And so what I need to prove is that these 221 00:12:48,702 --> 00:12:56,770 guys So that, the, the solution where c is greater than pi A is an optimal 222 00:12:56,770 --> 00:12:58,430 solution. I need to prove that. 223 00:12:58,430 --> 00:13:00,030 Okay. So what am I going to do. 224 00:13:00,030 --> 00:13:05,120 I know that I have detected, I believe I have detected optimality, which is the 225 00:13:05,120 --> 00:13:08,300 property that c is greater than pi A, okay? 226 00:13:08,300 --> 00:13:11,850 And that's what you see there. and now what i'm going to do is that I'm 227 00:13:11,850 --> 00:13:16,830 going to take another arbitrary feasible solution y, and i'm going to show you 228 00:13:16,830 --> 00:13:20,790 that the cost of y, the objective function for that basic feasible 229 00:13:20,790 --> 00:13:25,670 solution, is going to be greater than c zero star. 230 00:13:25,670 --> 00:13:30,190 If I show you that it means basically when I get To a particular basic feasible 231 00:13:30,190 --> 00:13:35,450 solution where c is greater than pi a, then I know that I am at the optimal 232 00:13:35,450 --> 00:13:37,210 solution. And how do I do that? 233 00:13:37,210 --> 00:13:40,050 It's very simple, this one. Okay, so what do I know about y? 234 00:13:40,050 --> 00:13:43,250 I know that it has to be a feasible solution, right. 235 00:13:43,250 --> 00:13:48,934 So what I know is that it has to satisfy this constraint, which is Ay is equal to 236 00:13:48,934 --> 00:13:54,710 b, okay And I just have to this the following manipulation okay. 237 00:13:54,710 --> 00:13:59,500 So I have the cost Cy so that's the cost of the feasible solution Y. 238 00:13:59,500 --> 00:14:06,390 Now I know I know because you know I'm basically detecting these property that C 239 00:14:06,390 --> 00:14:08,480 great than. Pi a. 240 00:14:08,480 --> 00:14:14,910 So I can replace this c by pi a, and so c y is going to be greater than pi a times 241 00:14:14,910 --> 00:14:16,370 y. Okay? 242 00:14:16,370 --> 00:14:18,820 Now, you look at this expression here. It's nice, right? 243 00:14:18,820 --> 00:14:23,059 So it's pi a y. But what do I know about y? 244 00:14:23,059 --> 00:14:28,000 I know that y is to satisfy this condition, so Pi y is to be equal to b, 245 00:14:28,000 --> 00:14:31,000 okay? So I get essentially the value pi b and 246 00:14:31,000 --> 00:14:37,100 pi b is the value of the solution at that base when this condition is satisfied. 247 00:14:37,100 --> 00:14:40,640 So I end, so this is the optimal solution because essentially any of the feasible 248 00:14:40,640 --> 00:14:41,916 solution is going to be greater than that. 249 00:14:41,916 --> 00:14:45,800 So what I'm basically going to be showing you here, with matrix notation, is that 250 00:14:45,800 --> 00:14:51,240 every time I detect that this property is, you know, satisfied, the constantly 251 00:14:51,240 --> 00:14:56,755 objective functions are all positive now, I'm basically optimum. 252 00:14:56,755 --> 00:15:01,040 Okay, so that's why, you know, this matrix notation is some, is used for some 253 00:15:01,040 --> 00:15:04,720 of these properties are easier to state. Okay, now the other things that I need to 254 00:15:04,720 --> 00:15:07,960 tell you, and this is really important, is the tableau. 255 00:15:07,960 --> 00:15:10,930 Okay, so a lot of the papers, a lot of the books that you're going to read, I'm 256 00:15:10,930 --> 00:15:13,650 going to work with this tableau. And essentially this tableau is going to 257 00:15:13,650 --> 00:15:17,330 put everything together in, you know, the right hand side, the left hand side. 258 00:15:17,330 --> 00:15:21,620 All this the basis, everything in one big matrix, okay. 259 00:15:21,620 --> 00:15:24,200 One big array. Okay? 260 00:15:24,200 --> 00:15:27,680 So, so we're going to put all these coefficients, we're going to put all, all 261 00:15:27,680 --> 00:15:29,070 these coefficients of the objective function. 262 00:15:29,070 --> 00:15:32,090 All the coefficients of the matrix here. The right hand sides, you know. 263 00:15:32,090 --> 00:15:34,530 All these things are going to be in one big tableau. 264 00:15:34,530 --> 00:15:38,100 And then you can do pivoting, or simple naive implementation of the the, the 265 00:15:38,100 --> 00:15:41,030 simplex algorithm very easily with one big matrix. 266 00:15:41,030 --> 00:15:43,560 Of course, you know, practical implementatoin, don't do that. 267 00:15:43,560 --> 00:15:45,960 There are much, you know, th-, th-, th-, th-, th-, they are, they are much more 268 00:15:45,960 --> 00:15:49,300 efficient representation, because most of the time this matrix is sparse and you 269 00:15:49,300 --> 00:15:52,380 want to, you know, exploit that sparsity. But this is the tableau. 270 00:15:52,380 --> 00:15:54,590 Okay? And this is all you can actually compute 271 00:15:54,590 --> 00:15:57,930 these things, you know by hand or simple implementation. 272 00:15:57,930 --> 00:16:00,410 Okay? So this is essentially the system of 273 00:16:00,410 --> 00:16:04,810 equations that I've shown you, and this is the first basic feasible solution that 274 00:16:04,810 --> 00:16:06,830 I'm showing you for that particular system, okay? 275 00:16:06,830 --> 00:16:10,520 And so what I want to show you is that we have the basis, we gotta have the right 276 00:16:10,520 --> 00:16:13,580 end side, we gotta have the you know, we gotta have the objective function 277 00:16:13,580 --> 00:16:16,480 represented there, okay? There are some convention and some of 278 00:16:16,480 --> 00:16:19,305 them may not be natural but these are the convention most people are using. 279 00:16:19,305 --> 00:16:22,850 Okay? So what you see there, the first row here 280 00:16:22,850 --> 00:16:27,439 is going to be the negation of the objective volume. 281 00:16:27,439 --> 00:16:29,650 Okay? So the way to think about this, in terms 282 00:16:29,650 --> 00:16:32,800 of what we have done before, it's like exactly, you know, when we were looking 283 00:16:32,800 --> 00:16:35,930 at the objective function, that's what was on the right-hand side. 284 00:16:35,930 --> 00:16:41,630 Except the value here, which is going to be negated. 285 00:16:41,630 --> 00:16:43,260 Okay? The va, the, the constant is going to be 286 00:16:43,260 --> 00:16:45,800 negated but, all these guys think of that. 287 00:16:45,800 --> 00:16:49,240 They were on the right hand side of this, this, of, of the formulation that we 288 00:16:49,240 --> 00:16:52,750 have, that we were using when we were doing you know the representation where 289 00:16:52,750 --> 00:16:56,960 the, the, the basic variables were isolated from the non-basic variable. 290 00:16:56,960 --> 00:16:59,450 What you there you see the basic variable. 291 00:16:59,450 --> 00:17:02,160 The basis okay. And the basic variable is always going to 292 00:17:02,160 --> 00:17:04,680 be a nice matrix you know 1 0 0 0 0 0 1 0 0 0 the 0 1 0 0 0 1. 293 00:17:04,680 --> 00:17:06,720 That matrix can be anywhere it's going to move right. 294 00:17:06,720 --> 00:17:16,381 And it doesn't have to be that order but somewhere they will be basic variables 295 00:17:16,381 --> 00:17:21,590 with 1 0 0. 010 and 001 and of course you can 296 00:17:21,590 --> 00:17:24,640 generalize that, okay? And then you see the right inside over 297 00:17:24,640 --> 00:17:27,300 there, these are the b values that you see over there, okay? 298 00:17:27,300 --> 00:17:31,550 So basically, this is a particular, this is the basic feasible representation 299 00:17:31,550 --> 00:17:34,559 expressed by the tableau. So you see the basic variables there, 300 00:17:34,559 --> 00:17:36,447 okay? So they are one, you know, the, the, the, 301 00:17:36,447 --> 00:17:39,102 they are there. The other ones are like what we have seen 302 00:17:39,102 --> 00:17:42,996 before but we brought them in a sense you have to think about them, we brought them 303 00:17:42,996 --> 00:17:45,390 to the left side. Okay, and so the coefficient that they 304 00:17:45,390 --> 00:17:49,480 have are the negation of the coefficient. When we were represented that as a set of 305 00:17:49,480 --> 00:17:52,230 equation, okay? So instead of leaving a 2, you have a 306 00:17:52,230 --> 00:17:55,770 minus 2, instead of leaving a minus 3, you get a 3, okay? 307 00:17:55,770 --> 00:17:59,130 So this is basically the tubler representation, okay? 308 00:17:59,130 --> 00:18:02,300 So we look again at this tubler representation and see that we are doing 309 00:18:02,300 --> 00:18:04,540 the simplex algorithm on top of this one, okay? 310 00:18:04,540 --> 00:18:07,760 So what we're going to do is going to, we're going to look at basically the 311 00:18:07,760 --> 00:18:12,170 objective function, and once again. If all the values there are strictly 312 00:18:12,170 --> 00:18:16,940 positive okay well greater or or not negative okay, we will be at optimality. 313 00:18:16,940 --> 00:18:19,460 In this particular case it's not the case. 314 00:18:19,460 --> 00:18:23,770 Okay, so you can see that we have a minus 3 and minus 3 over there and so that 315 00:18:23,770 --> 00:18:26,260 basically means that these two variables want to enter the basis, okay. 316 00:18:26,260 --> 00:18:28,600 They say, ooh, I want to go into the basis, okay. 317 00:18:28,600 --> 00:18:32,590 And so we can actually, you know and, you know, select a variable to enter the 318 00:18:32,590 --> 00:18:35,060 basis. And now we left to select a variable to 319 00:18:35,060 --> 00:18:37,790 lift the basis. And once again remember you know we flip 320 00:18:37,790 --> 00:18:40,940 the size of this non basic variable. So before we were looking at variables 321 00:18:40,940 --> 00:18:43,810 with a negative coefficient. since we flipped them, you know, from one 322 00:18:43,810 --> 00:18:45,940 side to the other. In this box, in this case, we have to 323 00:18:45,940 --> 00:18:48,620 look with values that are, that are positive. 324 00:18:48,620 --> 00:18:52,180 So, for these particular guys, we going to look at the first equation. 325 00:18:52,180 --> 00:18:55,070 We going to look at the last one. These are the two equations that we can 326 00:18:55,070 --> 00:18:57,170 select. We are going to compute the ratio between 327 00:18:57,170 --> 00:19:02,410 that co-efficient and the value B. In the first case, it's going to be 1/2, 328 00:19:02,410 --> 00:19:06,160 in the second case it's going to be 1. So the variable, the, the constraints 329 00:19:06,160 --> 00:19:09,400 that we are going to use to pivot is going to be the first constraint. 330 00:19:09,400 --> 00:19:13,620 We're going to do the pivoting operation, and this is the resulting tableau, okay? 331 00:19:13,620 --> 00:19:17,510 So once again, what you're going to see is the objective function in the top row, 332 00:19:17,510 --> 00:19:20,630 okay? And know, the nice thing is that you see 333 00:19:20,630 --> 00:19:23,920 these guys, they are strictly positive which basic they are, which basically 334 00:19:23,920 --> 00:19:28,260 means that we are a toptemality, okay? And these are the values of the non-basic 335 00:19:28,260 --> 00:19:30,980 variables, okay? So now, once again, you see the tableau 336 00:19:30,980 --> 00:19:34,800 there you see the variable x2 there? One, zero, zero, that's part of the 337 00:19:34,800 --> 00:19:37,460 basis. You see zero, one, zero and then you see 338 00:19:37,460 --> 00:19:38,800 zero, zero, one. Okay? 339 00:19:38,800 --> 00:19:41,380 This is the basis. You see that, you know some of the column 340 00:19:41,380 --> 00:19:45,710 of this basis, basis are not interleafed with some of the column of the non basic 341 00:19:45,710 --> 00:19:46,710 variables. Okay? 342 00:19:46,710 --> 00:19:49,690 And obviously you see the value of the non basic variables. 343 00:19:49,690 --> 00:19:52,548 Okay? x2 now is equal to three and a half. 344 00:19:52,548 --> 00:19:59,240 You know x4, somewhere here, is equal to seven and a half and so on, okay. 345 00:19:59,240 --> 00:20:04,530 And the value of the objective function at this point can be found in this column 346 00:20:04,530 --> 00:20:10,690 and it's can be found in this column. And its value here is minus nine and a 347 00:20:10,690 --> 00:20:14,030 half which means that. The real, the, but this is minus the 348 00:20:14,030 --> 00:20:16,520 effective function, so this is going to be four and a half. 349 00:20:16,520 --> 00:20:18,540 Okay? So, this is what the tableau does, okay? 350 00:20:18,540 --> 00:20:22,700 Basically the same information that we have seen before, but it's kind of put in 351 00:20:22,700 --> 00:20:27,320 one big matrix, with the, with various convention, okay? 352 00:20:27,320 --> 00:20:30,600 So, this is essentially this transition lecture, so I'm done, so I've shown you 353 00:20:30,600 --> 00:20:33,980 how actually we can use this matrix notation, it's very convenient in 354 00:20:33,980 --> 00:20:37,620 general, okay, once you get used to it. And the tableau is also something that is 355 00:20:37,620 --> 00:20:41,380 very nice, and we'll be able to express some beautiful property, just reasoning 356 00:20:41,380 --> 00:20:43,060 about this tableau later on. Okay? 357 00:20:43,060 --> 00:20:44,160 So thank you very much.