1 00:00:00,006 --> 00:00:03,190 25 slides. In 25 slides you would have seen 2 00:00:03,190 --> 00:00:07,590 everything about, you know, the Simplex algorithm to actually code it and know 3 00:00:07,590 --> 00:00:09,700 exactly how it works. Okay? 4 00:00:09,700 --> 00:00:12,750 So this is what we're going to do today, we're going to talk about the last steps 5 00:00:12,750 --> 00:00:15,730 of the Simplex algorithm and some of the most complicated stuff. 6 00:00:15,730 --> 00:00:18,020 Okay? So we know, what do we know so far? 7 00:00:18,020 --> 00:00:23,860 So we know that the optimal solution is located on a vertex, and a vertex is a 8 00:00:23,860 --> 00:00:26,900 basic feasible solution. What is a basic feasible solution? 9 00:00:26,900 --> 00:00:30,718 That's a solution is in which you isolate, you know, as many variables as 10 00:00:30,718 --> 00:00:32,110 there are constraints. Okay? 11 00:00:32,110 --> 00:00:34,768 These are the basic variables. You express them in terms of the 12 00:00:34,768 --> 00:00:36,670 non-basic variables. Okay? 13 00:00:36,670 --> 00:00:41,020 And if the Bs you know, the constants that you get on the right hand side are 14 00:00:41,020 --> 00:00:43,210 all nonnegative, you have a basic feasible solution. 15 00:00:43,210 --> 00:00:45,910 Okay? So we know that in a very, very, very 16 00:00:45,910 --> 00:00:50,140 naive algorithm which was basically any variable on this basic feasible solution. 17 00:00:50,140 --> 00:00:54,200 And look at the one which has the best cost, and that would be your solution. 18 00:00:54,200 --> 00:00:57,790 The issue with this is that this will take a long, long, long time. 19 00:00:57,790 --> 00:01:00,483 Okay? Because there are many combinations of of 20 00:01:00,483 --> 00:01:03,900 basic feasible variables that you can select. 21 00:01:03,900 --> 00:01:08,490 Okay, so what the simplex algorithm is, is a better way of actually doing this, 22 00:01:08,490 --> 00:01:12,520 okay, and so the key point, the third thing is going to basically telling you 23 00:01:12,520 --> 00:01:17,170 that we want a numeric. All these basic feasible solutions, we 24 00:01:17,170 --> 00:01:21,215 are basically going to move from basic feasible solution to basic feasible 25 00:01:21,215 --> 00:01:25,490 solution, and trying to improve the value of the objective function all the time. 26 00:01:25,490 --> 00:01:31,400 So, in a sense you know, the simplex algorithm is a local search algorithm, 27 00:01:31,400 --> 00:01:34,010 okay? And the basic move is you know, the basic 28 00:01:34,010 --> 00:01:37,930 local move that is applied is moving from a beautiful fantastic spot to another 29 00:01:37,930 --> 00:01:38,960 one. Okay. 30 00:01:38,960 --> 00:01:42,400 Moving from a basic feasible basic solution to an adjacent basic feasible 31 00:01:42,400 --> 00:01:45,540 solution, and will tell you exactly, you know, how we move from one to another. 32 00:01:45,540 --> 00:01:47,310 That's the key point of this lecture. Okay. 33 00:01:47,310 --> 00:01:51,590 And so, the only thing which is really nice about the simplex algorithm is that 34 00:01:51,590 --> 00:01:54,080 because of complex, convexity. Okay. 35 00:01:54,080 --> 00:01:56,640 It's guaranteed to find the global optimum. 36 00:01:56,640 --> 00:01:59,830 So it's a local search algorithm, but it's guaranteed to find the global 37 00:01:59,830 --> 00:02:03,270 optimum. Okay, so the key idea is basically going 38 00:02:03,270 --> 00:02:06,994 to be telling you how we can move from BFS to BFS. 39 00:02:06,994 --> 00:02:10,680 Okay so this is essentially what we're going to be doing. 40 00:02:10,680 --> 00:02:14,370 Okay so you have this systems of equations that you see on the top, right? 41 00:02:14,370 --> 00:02:18,370 And then we find a basic feasible solution and that's what you see here, so 42 00:02:18,370 --> 00:02:22,560 we isolated x3, x4, x5, okay, we re-express them in terms of the other 43 00:02:22,560 --> 00:02:27,950 basic variables, in this particular case x1, x2 and xx, okay, and now we have a 44 00:02:27,950 --> 00:02:31,328 basic feasible solution, okay so we give the value to x... 45 00:02:31,328 --> 00:02:36,060 3 in x4 and 5 and give the value 1 to 3 and that's the basic feasible solution. 46 00:02:36,060 --> 00:02:41,110 All the non basic variables are assiged to 0. 47 00:02:41,110 --> 00:02:42,650 Okay? So, now, how do we, so, so, basically the 48 00:02:42,650 --> 00:02:46,550 local move that is simplex algorithm is going to do is taking one of the non 49 00:02:46,550 --> 00:02:50,720 basic variable, okay, and moving it inside the bases, which basically taking 50 00:02:50,720 --> 00:02:53,230 to basic variables. And of course, you have to keep one out, 51 00:02:53,230 --> 00:02:54,910 okay? So you're going to take one of the basic 52 00:02:54,910 --> 00:02:58,080 variables and kick it out, okay? So this is the basic idea, that's a very 53 00:02:58,080 --> 00:03:00,270 simple local move, you swap two variables, okay? 54 00:03:00,270 --> 00:03:03,790 One which is basic, one which is non-basic and the status of these two 55 00:03:03,790 --> 00:03:07,590 variables is basically changing, okay? The basic becomes non-basic, the 56 00:03:07,590 --> 00:03:11,170 non-basic becomes basic, okay? So this is the local move right, so you 57 00:03:11,170 --> 00:03:14,850 select a non-basic variable And that known basic variables has to be a 58 00:03:14,850 --> 00:03:17,810 coefficient, okay, negative has to have a negative coefficient. 59 00:03:17,810 --> 00:03:22,100 We want to take it from the right hand side and moving to the left hand side, 60 00:03:22,100 --> 00:03:24,470 okay? And to do that you have to have a 61 00:03:24,470 --> 00:03:27,460 negative sign, okay? So you take the value that is negative 62 00:03:27,460 --> 00:03:29,740 side, you're going to move it on the other side, and of course the other 63 00:03:29,740 --> 00:03:34,220 variable's going to move to the non-basic site and also change, you know, sign. 64 00:03:34,220 --> 00:03:36,610 Okay? So, in a sense we find the entering 65 00:03:36,610 --> 00:03:37,990 variables. That's the variable which is non-basic 66 00:03:37,990 --> 00:03:40,570 and has a negative coefficient. Okay? 67 00:03:40,570 --> 00:03:45,290 And then, we going to find the value in the, in, in basic variable is, one 68 00:03:45,290 --> 00:03:48,240 constraint and one basic variables that we going to kick out of the basics. 69 00:03:48,240 --> 00:03:51,140 Okay? Make, you know, non-basic And then what 70 00:03:51,140 --> 00:03:54,770 we going to do is re-express all the equations in terms of the new basic 71 00:03:54,770 --> 00:03:58,400 variables, okay?. So we going to basically eliminate the 72 00:03:58,400 --> 00:04:02,150 new basic variable from the other equations, okay? 73 00:04:02,150 --> 00:04:05,190 And so that's essentially the local move that we are doing. 74 00:04:05,190 --> 00:04:10,012 So basically local move here swapping a basic variable and a non-basic variable, 75 00:04:10,012 --> 00:04:11,500 okay? And the way you do it, you choose an 76 00:04:11,500 --> 00:04:15,780 entering variable, you choose a leaving variable, and then you do Gaussian 77 00:04:15,780 --> 00:04:19,740 elimination to eliminate the new basic variables that you selected. 78 00:04:19,740 --> 00:04:21,770 Okay, so I'm going to show you example, okay. 79 00:04:21,770 --> 00:04:25,170 So once again, this is a system of equations, okay. 80 00:04:25,170 --> 00:04:28,660 You see the beautiful basic variables there, the non-basic variables over 81 00:04:28,660 --> 00:04:31,460 there, okay. Now, I'm looking at the non-basic 82 00:04:31,460 --> 00:04:34,000 variable in this particular case X2, okay. 83 00:04:34,000 --> 00:04:38,800 It has a negative coefficient, minus 2, and therefore I decide that I want this 84 00:04:38,800 --> 00:04:40,900 variable to go into the bases. Okay. 85 00:04:40,900 --> 00:04:43,810 I select the first constraints here, that's the only one that it appears to, 86 00:04:43,810 --> 00:04:45,210 so it's easy. Okay. 87 00:04:45,210 --> 00:04:50,630 And essentially what I'm going to do is swap x2 with the variable which is on, is 88 00:04:50,630 --> 00:04:53,470 in bases inside the first constraints, and that's x3. 89 00:04:53,470 --> 00:04:57,020 Okay, so I'm basically swapping these two guys, now x2 is going to move on that 90 00:04:57,020 --> 00:04:58,690 side. x three is going to move on the other 91 00:04:58,690 --> 00:05:01,200 side. Know the coefficient is minus two so I 92 00:05:01,200 --> 00:05:04,820 will have to divide the equation by two such that the coeffiecient of x two is 93 00:05:04,820 --> 00:05:07,785 going to be one over there and so I get these constraints, no? 94 00:05:07,785 --> 00:05:13,270 Where you see that this is one half you know and then the coefficient of x one is 95 00:05:13,270 --> 00:05:17,045 minus three half and the coefficient of x three is minus one half. 96 00:05:17,045 --> 00:05:18,855 Okay, and that's the constraint that you see there. 97 00:05:18,855 --> 00:05:22,950 Now, you know, in this particular case it was very convenient because x2 didn't 98 00:05:22,950 --> 00:05:25,470 appear in any one of the, the other constraints. 99 00:05:25,470 --> 00:05:28,050 And therefore I don't even have to eliminate it with the other constraints. 100 00:05:28,050 --> 00:05:32,050 In general, you would have to actually take the volume of the, of the right-hand 101 00:05:32,050 --> 00:05:35,850 side on, in, in, in this equation and remove it from the other equation. 102 00:05:35,850 --> 00:05:38,570 Okay? But this is basically telling you what we do. Okay? 103 00:05:38,570 --> 00:05:41,255 So we select the variable that we want to enter the basis. 104 00:05:41,255 --> 00:05:44,660 X2 in this particular case. We select the constraints, and by 105 00:05:44,660 --> 00:05:48,120 selecting the constraints, you select a variable that you want to kick out of the 106 00:05:48,120 --> 00:05:51,990 basis, x3 in this particular case, and you swap these two variables. 107 00:05:51,990 --> 00:05:55,450 You make sure that you get a basic feasible solution by you know, making 108 00:05:55,450 --> 00:06:00,210 sure the coefficient of x2 is 1 and then by removing you know x2 in this 109 00:06:00,210 --> 00:06:01,884 particular case from all the other equations. 110 00:06:01,884 --> 00:06:05,270 Okay? So that's the basic move that the simplex 111 00:06:05,270 --> 00:06:06,530 algorithm does. Okay? 112 00:06:06,530 --> 00:06:11,320 Now, I selected x2 to enter the basics, I could have selected x1. 113 00:06:11,320 --> 00:06:13,300 Right? So because x one also appear with a 114 00:06:13,300 --> 00:06:17,980 negative coefficients there and therefore I could have selected x one from, you 115 00:06:17,980 --> 00:06:21,450 know, as, as the, as, as the entering variables for the local move. 116 00:06:21,450 --> 00:06:25,570 Now if I select x1 here, I have basically three negative coefficients. 117 00:06:25,570 --> 00:06:30,210 And therefore, I can choose which constraint, you know, I want to, which 118 00:06:30,210 --> 00:06:34,270 non, which basic, existing basic variables I want to kick out, out of the 119 00:06:34,270 --> 00:06:37,040 basics - I want to make non-basic. Right? 120 00:06:37,040 --> 00:06:40,985 So can I take any of these num, the, these basic variables and make them 121 00:06:40,985 --> 00:06:43,590 non-basic? Well, look at this, okay? 122 00:06:43,590 --> 00:06:46,870 If I take the third one, okay? So I'm basically saying, oh, you know, I 123 00:06:46,870 --> 00:06:50,575 want to kick out, you know, x y for all of the bases. 124 00:06:50,575 --> 00:06:54,210 Okay, so what is going to happen? Well I perform Gaussian elimination for 125 00:06:54,210 --> 00:06:56,700 all the three constraints, and then what do I get? 126 00:06:56,700 --> 00:07:03,365 I get that x three now is a sign of value minus x, x four is a sign of value minus 127 00:07:03,365 --> 00:07:06,990 4, and that's terrible right? So because this is not a basic feasible 128 00:07:06,990 --> 00:07:09,710 solution. I told you that a basic feasible solution 129 00:07:09,710 --> 00:07:13,240 assign only positive values to the variable because all the variables have 130 00:07:13,240 --> 00:07:16,540 to get a positive value. Okay, so what happens, okay? 131 00:07:16,540 --> 00:07:18,750 So what happens is that I selected the mentoring variable. 132 00:07:18,750 --> 00:07:20,930 That's all fine. You know, I, I can do that. 133 00:07:20,930 --> 00:07:25,520 But then I selected one particular constraints, and one particular basic 134 00:07:25,520 --> 00:07:29,480 variables to remove from the basics, to make non-basic, okay? 135 00:07:29,480 --> 00:07:34,270 And when doing that I perform Gaussian elimination, and then suddenly, what 136 00:07:34,270 --> 00:07:38,900 happens is that the value of the, the existing basic variables, okay, was 137 00:07:38,900 --> 00:07:41,390 becoming negative. And that's terrible, okay. 138 00:07:41,390 --> 00:07:44,010 So what does that mean? Does that mean that at that point, I'm 139 00:07:44,010 --> 00:07:47,600 stuck on this beautiful, fantastic spot, and I can't move? 140 00:07:47,600 --> 00:07:51,310 No, it just means that I have to move a little bit more carefully, okay? 141 00:07:51,310 --> 00:07:55,664 And so the key point is that you have to choose, essentially, the leading 142 00:07:55,664 --> 00:07:58,010 variable, using the formula that I'm showing you here. 143 00:07:58,010 --> 00:07:59,480 And I'm going to give you an intermission here. 144 00:07:59,480 --> 00:08:01,830 Okay? So, when you look at this column, okay, 145 00:08:01,830 --> 00:08:05,900 so essentially you see various coefficients for these nonbasic variable. 146 00:08:05,900 --> 00:08:08,860 Okay? And so this coefficient is large, okay? 147 00:08:08,860 --> 00:08:14,718 This coefficent here is much smaller. Now, I also look at the b variables 148 00:08:14,718 --> 00:08:18,556 there, okay? And so what you can do is if I take the 149 00:08:18,556 --> 00:08:23,240 first constraints here, if I take the first constraint. 150 00:08:23,240 --> 00:08:27,850 And to, to make x one into the basics and, and for that popular constraints and 151 00:08:27,850 --> 00:08:32,020 therefore remove x three, the value of x one is going to be what? 152 00:08:32,020 --> 00:08:36,295 It's going to be basically dividing this coefficient, dividing the b by this 153 00:08:36,295 --> 00:08:39,340 coefficicent three over there. So it's going to be one third. 154 00:08:39,340 --> 00:08:41,910 Okay? And so that's a small number compared to 155 00:08:41,910 --> 00:08:45,480 what would happen if I make it, if I move it. 156 00:08:45,480 --> 00:08:50,330 You know, if, if I, if I make it enter the basis using the 3rd constraints. 157 00:08:50,330 --> 00:08:53,010 In which case, x1 is going to take the value of 3. 158 00:08:53,010 --> 00:08:56,480 Now why is this important? Because if x1 is the value 3 here, it's 159 00:08:56,480 --> 00:09:00,060 going to be multiplied by this 3 there, and that's you going to get a minus 9 160 00:09:00,060 --> 00:09:00,849 there. Okay? 161 00:09:00,849 --> 00:09:05,020 And therefore, 1 minus 9 is going to be the minus a that you seen before. 162 00:09:05,020 --> 00:09:09,870 So if i take a very large value here, okay, and I substitute it the other ones 163 00:09:09,870 --> 00:09:13,610 you going to get these negative values. So what I need to do is to find the 164 00:09:13,610 --> 00:09:18,270 smallest ratio between the B's, okay the B's that you see there, and the 165 00:09:18,270 --> 00:09:22,650 coefficient of the variables that has to enter the basis. 166 00:09:22,650 --> 00:09:25,820 Okay, and so this is, these are the ratios that I have shown you. 167 00:09:25,820 --> 00:09:29,962 This is basically the bi, you know, divided by minus the coefficient of the 168 00:09:29,962 --> 00:09:32,770 entering variables, okay. And you see that the one which is the 169 00:09:32,770 --> 00:09:37,830 smallest ones at the top, and if you actually, you know, choose the first 170 00:09:37,830 --> 00:09:43,280 constraints, as the constraint from which you select the basic variables that you 171 00:09:43,280 --> 00:09:48,310 will remove from the basis, then you are guaranteed in a sense to make sure that 172 00:09:48,310 --> 00:09:51,270 you go to a basic feasible solution. Because you are making sure that the 173 00:09:51,270 --> 00:09:54,050 other constraints, when you do the Gaussian elimination, are going to stay 174 00:09:54,050 --> 00:09:57,330 positive, okay? So essentially what we do, we use this 175 00:09:57,330 --> 00:10:00,270 ratio to select the leaving variables, okay? 176 00:10:00,270 --> 00:10:03,678 Using this formula, here. And we are guaranteed to maintain 177 00:10:03,678 --> 00:10:07,380 feasibility, okay? So, in a sense, the look and move, you 178 00:10:07,380 --> 00:10:10,795 have to be a little bit careful. You take any kind of entering variables, 179 00:10:10,795 --> 00:10:14,800 okay, and then you use this route to find the variables that you have to kick out 180 00:10:14,800 --> 00:10:18,020 of the basis, okay? So, and you compute this ratio, it's very 181 00:10:18,020 --> 00:10:20,055 easy to do. But you have to be careful in do that. 182 00:10:20,055 --> 00:10:22,970 Okay? So, in this, this particular case, you 183 00:10:22,970 --> 00:10:27,652 get this beautiful basis where, as I, you know, alluded to, x1 is going to be 1 184 00:10:27,652 --> 00:10:32,207 3rd, and then you see x4 and x5 we get also fractional value, you know, 4 3rd 185 00:10:32,207 --> 00:10:34,910 and 8 3rd. But this is a basic feasible solution. 186 00:10:34,910 --> 00:10:39,080 These guys now are positive, okay? And so, essentially when you move from 187 00:10:39,080 --> 00:10:42,900 basis to basis, you have to make sure that you get a basic feasible solution 188 00:10:42,900 --> 00:10:46,410 there, and so you have to make sure that when you perform the Gaussian 189 00:10:46,410 --> 00:10:48,790 elimination, the right value are going to emerge. 190 00:10:48,790 --> 00:10:53,300 And that's what you do, by selecting this the, the, the leaving variable, using the 191 00:10:53,300 --> 00:10:54,720 rules that I've shown you. Okay? 192 00:10:54,720 --> 00:10:59,340 So, to summarize, we move from basic feasible solution to basic feasible 193 00:10:59,340 --> 00:11:03,090 solution by selecting an entering variables that is to be a non-basic 194 00:11:03,090 --> 00:11:06,980 variables, which has a negative coefficient in some of the, in some of 195 00:11:06,980 --> 00:11:09,910 these constraints. Then you choose a leaving variable, 196 00:11:09,910 --> 00:11:12,270 giving the, the, the, you know, the formula that I've shown you. 197 00:11:12,270 --> 00:11:16,070 You compute these ratio, you select the constraint which is the smallest ratio, 198 00:11:16,070 --> 00:11:19,580 okay, and then that's the variable that, that's the basic variable that will leave 199 00:11:19,580 --> 00:11:22,820 the bases and then you perform, you know, Gaussian elimination. 200 00:11:22,820 --> 00:11:28,810 Now, this entire set of operation here is called pivoting, okay, and pivoting is 201 00:11:28,810 --> 00:11:32,190 basically the name of the local move in linear programming but that's basically 202 00:11:32,190 --> 00:11:35,632 choosing this entering variable, choosing this leaving variable. 203 00:11:35,632 --> 00:11:38,810 And performing, you know, Gaussian elimination. 204 00:11:38,810 --> 00:11:43,550 So the local move is called pivoting and basically swap one basic variable and a 205 00:11:43,550 --> 00:11:47,492 non basic variable, okay? So at this point we have seen a lot of 206 00:11:47,492 --> 00:11:50,660 thing already, okay, so if you want to solve this linear problem, we know that 207 00:11:50,660 --> 00:11:53,650 this solution is at the vertex, you know that the vertex is a basic feasible 208 00:11:53,650 --> 00:11:56,110 solution. And now we know how to move from a basic 209 00:11:56,110 --> 00:11:59,875 feasible solution to another basic feasible solution so we can look at the 210 00:11:59,875 --> 00:12:02,580 four points, you know, when do we need to stop? 211 00:12:02,580 --> 00:12:05,380 Okay. And we need to stop, you know, when you 212 00:12:05,380 --> 00:12:07,210 see the basic feasible solution is optimal. 213 00:12:07,210 --> 00:12:10,740 And I'm going to give you very, very simple criteria to actually detect that. 214 00:12:10,740 --> 00:12:13,960 And this is the criteria, right? So we have this basic feasible solution. 215 00:12:13,960 --> 00:12:17,359 We have these equations, right? And these equation are expressing the 216 00:12:17,359 --> 00:12:19,760 basic variables in terms of the non-basic variables. 217 00:12:19,760 --> 00:12:23,700 Okay, take the objective. Okay, take the objective, remove all the 218 00:12:23,700 --> 00:12:27,890 basic variables which basically mean replace them with the non-basic variables 219 00:12:27,890 --> 00:12:31,550 and you get an expression of the form you know, 'c' zero which is going to be a 220 00:12:31,550 --> 00:12:36,184 constant plus 'c' one is one, well this is a coefficient of you know the variable 221 00:12:36,184 --> 00:12:39,940 'x' one plus 'c' two, 'x' two and so on when I have basically replaced all the 222 00:12:39,940 --> 00:12:43,720 basic variables way off, you know on the right hand side, the non-basic variables. 223 00:12:43,720 --> 00:12:46,240 The expression with the non basic rivals, okay. 224 00:12:46,240 --> 00:12:51,870 Now, if I have an expression like this, okay, and all the CIs are strictly, are 225 00:12:51,870 --> 00:12:57,040 greater or equal to 0 then I know that I'm optimum, so I have a very, very, very 226 00:12:57,040 --> 00:13:00,230 very simple way for actually detecting that I'm optimum. 227 00:13:00,230 --> 00:13:03,820 I'll rewrite the objective function, remove all the basic variables, look at 228 00:13:03,820 --> 00:13:07,410 the expression, which is only in terms... Of the non-basic variables, and if all 229 00:13:07,410 --> 00:13:09,980 the coefficients there are greater or equal to zero, I'm done. 230 00:13:09,980 --> 00:13:13,710 Okay? I'm at the top of the world, okay? 231 00:13:13,710 --> 00:13:16,170 Now, I'm going to give you a little intuition why this is true, a little bit. 232 00:13:16,170 --> 00:13:18,660 Or actually, the inverse. But, but we're going to go through some 233 00:13:18,660 --> 00:13:21,265 examples so that you can, I can convey that intuition, right? 234 00:13:21,265 --> 00:13:25,700 So we had this beautiful problem that we were trying to solve for a long time. 235 00:13:25,700 --> 00:13:30,580 So we have variable x1 for x5. You have inequality, equalities here and 236 00:13:30,580 --> 00:13:33,370 so the first thing of use is to find a basic feasible solution. 237 00:13:33,370 --> 00:13:35,080 That's what we find here. Okay. 238 00:13:35,080 --> 00:13:38,130 Now look, When I take the basic variables here, right? 239 00:13:38,130 --> 00:13:43,460 So x three to x five, okay, remove them from the objective functions there. 240 00:13:43,460 --> 00:13:45,690 This is the objective function that I get. 241 00:13:45,690 --> 00:13:47,510 Okay? As you see, the constant is six. 242 00:13:47,510 --> 00:13:49,960 Why? Because x three, x four and x five, you 243 00:13:49,960 --> 00:13:54,020 know, I assigned one through three and there are the coefficients of one at the 244 00:13:54,020 --> 00:13:54,710 top. Okay? 245 00:13:54,710 --> 00:13:57,380 So I know that I will have, you know, the value six. 246 00:13:57,380 --> 00:14:02,130 But then I give a minus you know, 3x1 and then a minus 3x2 okay? 247 00:14:02,130 --> 00:14:05,110 Now this is not an optimal solution right? 248 00:14:05,110 --> 00:14:08,730 Because these guys are negative okay, they are not, non negative the 249 00:14:08,730 --> 00:14:12,540 coefficients of you know, x1 and x2. So what is the intuition here? 250 00:14:12,540 --> 00:14:17,230 Well, you know that these guys x1 and x2 okay they have to take non negative value 251 00:14:17,230 --> 00:14:20,040 okay? So currently they are not in the business 252 00:14:20,040 --> 00:14:23,050 right so their value is what? Zero, right. 253 00:14:23,050 --> 00:14:27,800 OK since they are zero you know may wonder oh but if I put them in the bases 254 00:14:27,800 --> 00:14:31,590 there going to get a positive value, a nonnegative value and therefore I can 255 00:14:31,590 --> 00:14:36,210 drive this objective function down because you know a negative times a 256 00:14:36,210 --> 00:14:39,530 positive value is going to decrease this objective function and that's the 257 00:14:39,530 --> 00:14:42,030 intuition here. If they were positive you know they had 258 00:14:42,030 --> 00:14:44,804 to take a positive value this objective function is going to go up. 259 00:14:44,804 --> 00:14:48,190 Okay, so essentially they are negative. That means that I can drive this 260 00:14:48,190 --> 00:14:52,390 objective function down, okay, so this is what you have there. 261 00:14:52,390 --> 00:14:56,110 You know, we have these objective functions, we select x2, which is a 262 00:14:56,110 --> 00:15:00,460 negative coefficient, and we want this x2 to enter the basis, okay, so how do we do 263 00:15:00,460 --> 00:15:04,670 that, we have to select a variable to leave the basis, you know, once again we 264 00:15:04,670 --> 00:15:11,750 look at the coefficient 1 divided by 2... Okay and then three, three divided by by 265 00:15:11,750 --> 00:15:14,510 three, so that's one. So we're going to basically use the first 266 00:15:14,510 --> 00:15:19,130 constraints to remove to make x two inside the bases, removing x three from 267 00:15:19,130 --> 00:15:22,150 the bases and this is what you obtain. Okay? 268 00:15:22,150 --> 00:15:26,170 At this point this is the new basic feasible solution. 269 00:15:26,170 --> 00:15:31,840 And this basic feasible solution is the value of nine and a half, okay, so which 270 00:15:31,840 --> 00:15:35,080 is four point five, so it's going to then six with decreased value of the objective 271 00:15:35,080 --> 00:15:36,370 function. But the now the two co, the two 272 00:15:36,370 --> 00:15:41,110 coefficients that you see are positive which basically means that at this point 273 00:15:41,110 --> 00:15:45,470 this is the optimal solution. There is no way I can drive the objective 274 00:15:45,470 --> 00:15:48,540 function down. I have an optimal solution to my problem. 275 00:15:48,540 --> 00:15:52,170 Okay, and I can detect that and just look at this line and all the coefficients are 276 00:15:52,170 --> 00:15:56,450 going to the zero, great. >> I am, I'm optimum, okay, so this is 277 00:15:56,450 --> 00:15:59,480 basically the idea. So you go, you go, you move from basics 278 00:15:59,480 --> 00:16:03,260 to basics, select this entering variable, you know, select this leading variable, 279 00:16:03,260 --> 00:16:07,380 performing the pivoting operation and look at your function though. 280 00:16:07,380 --> 00:16:10,270 Is it all positive? If it's all positive you're down, okay. 281 00:16:10,270 --> 00:16:14,590 So that's the basic idea... Okay, so in a sense what we have seen at 282 00:16:14,590 --> 00:16:17,030 this point are basically the first four points. 283 00:16:17,030 --> 00:16:21,940 Okay, so we have seen, you know, the fact that an optimal solution is located at a 284 00:16:21,940 --> 00:16:24,460 vertex, okay. A vertex is a basic feasible solution. 285 00:16:24,460 --> 00:16:30,110 I can move from BFS's to BFS's, okay. And I can detect that BFS is optimal. 286 00:16:30,110 --> 00:16:33,580 I haven't shown you the proof yet, okay, I will show you in the next lecture 287 00:16:33,580 --> 00:16:36,500 because it's much easier. To actually prove this thing, if I can 288 00:16:36,500 --> 00:16:39,510 use Matrix notation. But it's a beautiful single proof like 289 00:16:39,510 --> 00:16:44,230 five lines if I can use matrix notation. Which I'm not doing here because it's 290 00:16:44,230 --> 00:16:45,000 simpler. Okay? 291 00:16:45,000 --> 00:16:50,480 So now, the only thing that I have to tell you is that from any kind of BFS, I 292 00:16:50,480 --> 00:16:53,920 can move to another BFS which has a better cust, okay? 293 00:16:53,920 --> 00:16:57,770 And that's the case, okay? Provided that I put some conditions, 294 00:16:57,770 --> 00:16:59,640 okay? Once again, I want to prove this but 295 00:16:59,640 --> 00:17:04,240 this, there is a simple algebraic proof to do that but the basic idea is the 296 00:17:04,240 --> 00:17:06,960 following, okay? So if all the bi's, okay, I'm assuming 297 00:17:06,960 --> 00:17:11,180 that all the bi's are strictly greater than 0, okay, that I can find an entering 298 00:17:11,180 --> 00:17:12,740 variable. So there is an entering variable 299 00:17:12,740 --> 00:17:14,990 somewhere in the constraints with the negative coefficient. 300 00:17:14,990 --> 00:17:19,710 I can find the leaving variables, okay, then the pivoting operation is going to 301 00:17:19,710 --> 00:17:22,445 give me a new BFS. Which is improving. 302 00:17:22,445 --> 00:17:28,040 Great, I am improving the solution. Okay, and so once I have that, you know, 303 00:17:28,040 --> 00:17:32,430 this is the only, so I'm ready in a sense to tell you what the simplex algorithm 304 00:17:32,430 --> 00:17:36,050 is, and this basically these five lines that you see here, these four lines that 305 00:17:36,050 --> 00:17:38,930 you see there, okay. So what you do is, as long there is a 306 00:17:38,930 --> 00:17:43,840 coefficient in the objective function, which is, which is negative, okay, I need 307 00:17:43,840 --> 00:17:47,500 to perform a pivot operation. Okay, so I select an entering variable, 308 00:17:47,500 --> 00:17:50,780 that's a variable which has a negative, it has to have a negative coefficient in 309 00:17:50,780 --> 00:17:53,199 the objective function. That's how I can drive this objective 310 00:17:53,199 --> 00:17:58,458 function down, okay, then I select a leaving variable, okay, such that, such 311 00:17:58,458 --> 00:18:05,627 that, I preserve visibility, so I have to use the rule that I've shown you before, 312 00:18:05,627 --> 00:18:08,890 and then I basically pivot... Okay? 313 00:18:08,890 --> 00:18:12,900 So once again choosing and entering variables and in the centering variables, 314 00:18:12,900 --> 00:18:14,700 how you have to be a little bit careful, right? 315 00:18:14,700 --> 00:18:17,830 I want to take one, which is a negative coefficient in the objective function. 316 00:18:17,830 --> 00:18:19,900 Why? Because I want this objective function to 317 00:18:19,900 --> 00:18:21,790 have only positive coefficient. Right? 318 00:18:21,790 --> 00:18:25,000 I select the centering variable, I select the leaving variable, I pivot and I keep 319 00:18:25,000 --> 00:18:29,620 doing that until the objective function is going to be all, you know, all 320 00:18:29,620 --> 00:18:31,680 positive coefficients. Okay? 321 00:18:31,680 --> 00:18:34,740 So that 's the Simplex Algorithm. And if I guarantee that during the 322 00:18:34,740 --> 00:18:37,850 execution, these B I stays strictly positive, okay? 323 00:18:37,850 --> 00:18:41,160 It can't, I don't want them to fall to zero, and we'll discuss that in a moment. 324 00:18:41,160 --> 00:18:44,510 And if the, the, the objective function is bounded by below. 325 00:18:44,510 --> 00:18:47,745 Okay, so you can't drop, you cannot drive it down infinitely low. 326 00:18:47,745 --> 00:18:49,820 Okay. Then you are guaranteed that the simplex 327 00:18:49,820 --> 00:18:53,040 algorithm is going to terminate, and it will give you an ultimate solution. 328 00:18:53,040 --> 00:18:57,840 So it's going to convert with, a bfs where all these cis are going to be 329 00:18:57,840 --> 00:18:59,470 greater than zero. Okay? 330 00:18:59,470 --> 00:19:01,420 So that's the simplex algorithm. Okay? 331 00:19:01,420 --> 00:19:05,350 Now, there are a couple of nasty cases that I need to discuss with you, and 332 00:19:05,350 --> 00:19:07,180 that's what I'm going to do in the next couple of slides. 333 00:19:07,180 --> 00:19:09,390 Okay? Now the first one is this one, right? 334 00:19:09,390 --> 00:19:14,650 So I told you that, you know, knowing we are choosing the entering variable using 335 00:19:14,650 --> 00:19:18,960 a very interesting criteria. The fact that the objective function, 336 00:19:18,960 --> 00:19:22,290 okay, has a coefficient which is negative for that variable. 337 00:19:22,290 --> 00:19:24,940 Okay, so that's what I told you. We want to do that to convert to an 338 00:19:24,940 --> 00:19:28,400 optimal solution. But, you know, at the beginning of the 339 00:19:28,400 --> 00:19:31,430 lecture, what I was telling you is that we select the entering variable with, 340 00:19:31,430 --> 00:19:35,430 because it has a negative coefficient inside some of these constraints. 341 00:19:35,430 --> 00:19:39,700 So, it may happen that the variable that I'm choosing there has a beautiful 342 00:19:39,700 --> 00:19:43,720 column, okay? Where essentially, all the coefficients 343 00:19:43,720 --> 00:19:47,320 are greater than 0. What does that mean? 344 00:19:47,320 --> 00:19:50,840 None of them is negative, so really the two things that I've told you in this 345 00:19:50,840 --> 00:19:54,245 lecture are contradictory. I want to introduce the variable into the 346 00:19:54,245 --> 00:19:57,880 basis to drive the objective function down, but at the same time, I also want a 347 00:19:57,880 --> 00:19:59,830 negative coefficient and I don't have one. 348 00:19:59,830 --> 00:20:02,040 What is happening? What is happening? 349 00:20:02,040 --> 00:20:03,990 Okay? So think about it. 350 00:20:03,990 --> 00:20:06,640 So what is the basic feasible solution here, okay? 351 00:20:06,640 --> 00:20:09,975 It takes, you know, the basic variables and assigns them the value, in this 352 00:20:09,975 --> 00:20:14,130 particular case one, two, three, okay? This is the objective function that I 353 00:20:14,130 --> 00:20:16,660 have. What is the value of X one in the basic 354 00:20:16,660 --> 00:20:18,405 feasible solution? It's zero. 355 00:20:18,405 --> 00:20:22,330 Alright? But you see these coefficents, okay? 356 00:20:22,330 --> 00:20:24,740 They are all greater than zero. Okay? 357 00:20:24,740 --> 00:20:29,830 What does that mean? Can you think about what that means? 358 00:20:29,830 --> 00:20:35,590 So can you think of the case where I say, you know, in the basic feasible solution 359 00:20:35,590 --> 00:20:40,720 X one okay is basically assigned to zero. What if I assign it to 10,000? 360 00:20:40,720 --> 00:20:44,750 What am I going to get, okay? Well, this equation is going to be fine, 361 00:20:44,750 --> 00:20:47,950 right? So x2 is equal to 1, if I give 10,000 to 362 00:20:47,950 --> 00:20:54,130 this guy, you know, multiplying by 3 that's going to be 30,000. 363 00:20:54,130 --> 00:20:55,210 You know, I'm going to get the value for x3 which is going to be 30,000 and whah, 364 00:20:55,210 --> 00:20:57,490 okay? That's fine, that's still feasible. 365 00:20:57,490 --> 00:20:59,080 What about the second one? Same thing right? 366 00:20:59,080 --> 00:21:02,350 This is positive. I'm going to add a positive number to x4 367 00:21:02,350 --> 00:21:04,290 and that's fine. And same thing for x5. 368 00:21:04,290 --> 00:21:07,950 So if I take, you know, 10,000, I have another solution, okay. 369 00:21:07,950 --> 00:21:10,860 It's not a basic feasible solution, but it's a solution right. 370 00:21:10,860 --> 00:21:16,230 What about if I give a million to x1? That's fine as well right. 371 00:21:16,230 --> 00:21:17,965 If I give 10 million it's going to be fine. 372 00:21:17,965 --> 00:21:20,960 What do these values do to the objective function? 373 00:21:20,960 --> 00:21:23,360 They are driving this objective function down. 374 00:21:23,360 --> 00:21:25,090 Why? Because this guy is a negative 375 00:21:25,090 --> 00:21:29,040 coefficient. So what this really means here is that I 376 00:21:29,040 --> 00:21:33,980 can take the value of x1 and giving arbitrarily large positive values, and 377 00:21:33,980 --> 00:21:37,000 that's going to make the objective function arbitrarily large. 378 00:21:37,000 --> 00:21:41,610 So which basically means that my algorithm here is not bounded by below. 379 00:21:41,610 --> 00:21:45,170 I can drive the objective function as low as I want, okay? 380 00:21:45,170 --> 00:21:48,750 Which is one of the hypotheses that I told you that I needed to have for 381 00:21:48,750 --> 00:21:51,700 actually terminating. So in a sense what I'm telling you is 382 00:21:51,700 --> 00:21:54,630 that the simplest algorithm is not bounded by below. 383 00:21:54,630 --> 00:21:58,500 You will come to a situation where you see this volume you want to put inside 384 00:21:58,500 --> 00:22:01,800 the basics but you cannot. And so that's the case where you, you can 385 00:22:01,800 --> 00:22:05,010 jet, you can detect that your product is actually unbonded. 386 00:22:05,010 --> 00:22:08,680 And you can stop executing at this point. You can report to the user that, you 387 00:22:08,680 --> 00:22:12,996 know, that you can drive this optimization function arbitrarily, you 388 00:22:12,996 --> 00:22:17,430 know down, okay, low. And typically that means that there is a 389 00:22:17,430 --> 00:22:18,760 mistake in the modeling. Right? 390 00:22:18,760 --> 00:22:23,260 So because if you think of a factory which is trying to decrease its costs. 391 00:22:23,260 --> 00:22:26,060 And the solution of this complex algorithm is basically telling the 392 00:22:26,060 --> 00:22:29,410 manager you can drive your cost arbitrarily low. 393 00:22:29,410 --> 00:22:33,550 Something should be fundamentally wrong. Now if you maximize you can drive it 394 00:22:33,550 --> 00:22:36,960 arbitrarily high. >> Its like you know telling the CEO of 395 00:22:36,960 --> 00:22:41,220 Apple you can maximize your profit arbitrarily high That's probably not 396 00:22:41,220 --> 00:22:43,900 right, okay? So essentially, you can detect that the 397 00:22:43,900 --> 00:22:47,710 problem is unbounded and make sure that the user actually knows that. 398 00:22:47,710 --> 00:22:50,220 They have to look at their model and try to do it better. 399 00:22:50,220 --> 00:22:53,470 Now, there is the other things that I mentioned is that one of the hypothesis 400 00:22:53,470 --> 00:22:56,970 that I told you about is that I don't want the bi's to become zero. 401 00:22:56,970 --> 00:22:59,880 What happens if a bi happen's to be zero, right? 402 00:22:59,880 --> 00:23:03,850 So look at these constraints here. I'm basically letting x3 be equal to 0. 403 00:23:03,850 --> 00:23:05,766 That's fine. This is a basic feasible solution. 404 00:23:05,766 --> 00:23:08,740 It's just that there is a basic variable known and that is the value zero. 405 00:23:08,740 --> 00:23:11,360 The known basic variable views the other value zero. 406 00:23:11,360 --> 00:23:14,017 But now what happens if I select a variable to enter the basis? 407 00:23:14,017 --> 00:23:17,800 Remember the pivoting rule, you know, computes as a ratio. 408 00:23:17,800 --> 00:23:20,870 I know I have a ratio zero divided by something is always going to be zero. 409 00:23:20,870 --> 00:23:23,040 That value is always going to be the smallest one. 410 00:23:23,040 --> 00:23:27,830 So you always select that constraint to enter the basics, which basically means. 411 00:23:27,830 --> 00:23:32,890 That when you do the pivot thing, okay. So you going to stay at the same value of 412 00:23:32,890 --> 00:23:35,560 the objective function. Because x3 you know, is going to be 413 00:23:35,560 --> 00:23:39,050 kicked out of the basis, okay. So you, you, nothing happens there. 414 00:23:39,050 --> 00:23:43,610 But x2 is going to basically enter the basis but get a value zero obviously. 415 00:23:43,610 --> 00:23:46,920 And therefore, the objective function is basically not changing. 416 00:23:46,920 --> 00:23:49,130 The objective value is not changing, okay? 417 00:23:49,130 --> 00:23:51,900 So what does that mean? That means that the hypothesis that I 418 00:23:51,900 --> 00:23:55,840 told you before, okay, is wrong. Well valid, it's not valid, it's not 419 00:23:55,840 --> 00:24:01,020 satisfied and I have to find essentially another way to guarantee termination. 420 00:24:01,020 --> 00:24:04,930 So one of the things that I told you about this five facts, okay So is wrong. 421 00:24:04,930 --> 00:24:09,400 Its not always possible to move from a basic feasible solution to another basic 422 00:24:09,400 --> 00:24:14,000 feasible solution with the better cost. I can actually move to another you know 423 00:24:14,000 --> 00:24:16,665 another top of the mountain which is exactly the same height. 424 00:24:16,665 --> 00:24:18,450 OK. So what do we do? 425 00:24:18,450 --> 00:24:22,510 OK so we have to use, we have to be a little bit careful in how we implement 426 00:24:22,510 --> 00:24:25,070 the algorithm and there are very useful ways to do that. 427 00:24:25,070 --> 00:24:29,650 I, I will mention that two of them in a little bit of details and they are all at 428 00:24:29,650 --> 00:24:34,330 once, okay, but you can use essentially a selection of the variables that you want 429 00:24:34,330 --> 00:24:37,900 to make enter the basis in a very specific way and that will garauntee your 430 00:24:37,900 --> 00:24:41,410 race termination, okay, and so the key point is that you look at the objective 431 00:24:41,410 --> 00:24:43,360 function. If you only select the first variable 432 00:24:43,360 --> 00:24:47,685 which is a negative sign, okay, negative coefficient, then you are going to 433 00:24:47,685 --> 00:24:50,510 terminate... But sometimes you really don't want to do 434 00:24:50,510 --> 00:24:52,719 that. For instance a lot of the, a lot of the 435 00:24:52,719 --> 00:24:56,430 simplex algorithm will take a value which coefficient, which is highly negative. 436 00:24:56,430 --> 00:24:59,760 Because if you give a positive value to that particular variable it's going to 437 00:24:59,760 --> 00:25:02,390 drive this, you know, down very quickly, okay. 438 00:25:02,390 --> 00:25:06,770 So this is somewhat restrictive. This is, this is putting some limitation. 439 00:25:06,770 --> 00:25:09,230 To what you can do. The other thing that you can do is do a 440 00:25:09,230 --> 00:25:11,500 pivoting rule, which is a little bit more complex. 441 00:25:11,500 --> 00:25:15,350 Instead of choosing the ratio that I've shown you, you can actually see, you can 442 00:25:15,350 --> 00:25:17,950 actually generalize it to a lexicographic order. 443 00:25:17,950 --> 00:25:22,050 So if the, if the, if there are ties when you do this ratio You move to the next 444 00:25:22,050 --> 00:25:25,310 column, you know, the first coefficient, and you do the same thing and so on and 445 00:25:25,310 --> 00:25:29,430 so forth and if you do that once again. If you do, if you select the leaving 446 00:25:29,430 --> 00:25:34,060 variable in that particular way you will also guarantee termination, so this is 447 00:25:34,060 --> 00:25:37,110 interesting, right, there is somewhat of a duality and it's interesting to talk 448 00:25:37,110 --> 00:25:41,010 about duality for linear programming... But you can, you can put a role you know 449 00:25:41,010 --> 00:25:44,780 which select the entering variable rule that select the leaving variables, and 450 00:25:44,780 --> 00:25:48,480 both of them would guarantee termination. And then you know typical implementation 451 00:25:48,480 --> 00:25:52,540 of also methods for perturbing the basis, so you change a little bit the problem 452 00:25:52,540 --> 00:25:55,920 and then you go back to that later on. But you basically make sure that, you 453 00:25:55,920 --> 00:25:59,300 know, you you don't have this. You don't stay the same place when you 454 00:25:59,300 --> 00:26:01,310 are doing these pivoting operations. Okay. 455 00:26:01,310 --> 00:26:05,030 So I won't go into the details but there are ways to actually address them and, 456 00:26:05,030 --> 00:26:09,770 you know, actual implementation will combine these with better pivoting rule 457 00:26:09,770 --> 00:26:14,030 to actually drive the search quickly. But we can make this algorithm termanate 458 00:26:14,030 --> 00:26:17,030 even if the bis are actually. getting to zeroes. 459 00:26:17,030 --> 00:26:21,260 Okay, so, we know when the, so, so the two things that I've shown you is that we 460 00:26:21,260 --> 00:26:24,220 know or we can predict that the problem is unbounded, that's one of the 461 00:26:24,220 --> 00:26:28,850 hypothesis that I did and we can also detect that, we can also insure 462 00:26:28,850 --> 00:26:33,470 termination if the BI's are actually getting to zero by using this more 463 00:26:33,470 --> 00:26:38,130 clever, you know, People think selections. 464 00:26:38,130 --> 00:26:43,210 So there is one more thing I need to do before we know exactly how to implement 465 00:26:43,210 --> 00:26:46,030 the algorithm and this is actually really beautiful. 466 00:26:46,030 --> 00:26:49,920 This is really clever. So essentially What I've been doing the 467 00:26:49,920 --> 00:26:54,140 entire lecture, I've always assumed that we had a basic feasible solution to start 468 00:26:54,140 --> 00:26:57,140 with, right. But in practice, you won't necessarily 469 00:26:57,140 --> 00:26:59,690 have that, yeah. The user is basically giving you this set 470 00:26:59,690 --> 00:27:04,350 of equations, okay, and these objective function You have actually no clue that 471 00:27:04,350 --> 00:27:07,480 these equations are actually, you know, feasible. 472 00:27:07,480 --> 00:27:10,040 Okay, now there is a feasible solution to these equations. 473 00:27:10,040 --> 00:27:13,920 So, so the problem is the how do I find my first BFS? 474 00:27:13,920 --> 00:27:15,550 Okay? I may not have it. 475 00:27:15,550 --> 00:27:18,990 And it may not be a obvious, obvious how to actually get it, okay? 476 00:27:18,990 --> 00:27:22,940 So what I'm going to do, is I'm going to do a very simple trace, right? 477 00:27:22,940 --> 00:27:25,720 I'm going to add a new set of variables, okay? 478 00:27:25,720 --> 00:27:27,520 Just step out here so that you can see them, okay? 479 00:27:27,520 --> 00:27:31,410 But I'm adding one. We call artificial variables, so y1, yi, 480 00:27:31,410 --> 00:27:36,150 you know, ym, are artificial variables. They are new variables that are just 481 00:27:36,150 --> 00:27:40,528 created out of nowhere, right? And I put them into the equations of the 482 00:27:40,528 --> 00:27:43,690 simplex algorithm, okay? Now, I put them in a very, you know, 483 00:27:43,690 --> 00:27:47,390 simple way, right? So, y1 for the first constraint, y2 for 484 00:27:47,390 --> 00:27:51,700 the second one, yi for the i n. For constraint i, and ym for the last 485 00:27:51,700 --> 00:27:53,870 one. So now, essentially, when you see this 486 00:27:53,870 --> 00:27:59,000 thing, you are like, smiling, right? Because now I have an easy BFS, right? 487 00:27:59,000 --> 00:28:03,320 So this is essentially a BFS. This is essentially a, a, this, I can use 488 00:28:03,320 --> 00:28:07,120 these variables to put inside a basis, and I have a BFS, okay? 489 00:28:07,120 --> 00:28:10,830 But obviously, you know it's a BFS for another problem. 490 00:28:10,830 --> 00:28:14,070 A problem where, you know the y's are actually the variables. 491 00:28:14,070 --> 00:28:18,010 So now I have an obvious solution which is assigning these y's to the other ones, 492 00:28:18,010 --> 00:28:19,990 which basically means that all of the other guys are zero. 493 00:28:19,990 --> 00:28:22,780 But that's not a feasible solution to my initial problem, right? 494 00:28:22,780 --> 00:28:27,650 Because I wanted these guys to be equal to the BI's okay so what am I going to 495 00:28:27,650 --> 00:28:30,080 do? Okay, and this is where the beauty is 496 00:28:30,080 --> 00:28:33,890 Right? So the beauty is so so the beauty here is 497 00:28:33,890 --> 00:28:39,190 that we are going to the simplest algorithm to actually find the real BFS 498 00:28:39,190 --> 00:28:41,967 from this fake BFS. Okay? 499 00:28:41,967 --> 00:28:45,060 Okay? So this is what we are going to do so so 500 00:28:45,060 --> 00:28:48,950 so this is called a two faced method. Okay. 501 00:28:48,950 --> 00:28:53,770 And the first step is going to be, I want to find the BFS if there is one, okay? 502 00:28:53,770 --> 00:28:57,950 And then the second step is, once I have one of these BFS, I'm great, right? 503 00:28:57,950 --> 00:29:00,960 So I can apply the simplex algorithm for optimizing. 504 00:29:00,960 --> 00:29:04,780 But the first one, I want, I will use essentially the simplex algorithm to find 505 00:29:04,780 --> 00:29:07,160 a basic feasible solution. How do I do that? 506 00:29:07,160 --> 00:29:11,050 Well, it's very simple, right? So, if I have a feasible solution to this 507 00:29:11,050 --> 00:29:16,050 set of equation, that means that the y variable should be assigned to 0, OK? 508 00:29:16,050 --> 00:29:20,200 So what I'm going to do is basically minimize the sum of these y's. 509 00:29:20,200 --> 00:29:23,600 And remember, these y's have to be, you know, they are greater than or equal to 510 00:29:23,600 --> 00:29:28,510 0, so If, if essentially this function goes to 0, it means that every 1 of them 511 00:29:28,510 --> 00:29:33,450 is equal to 0 and therefore these, these values here have the value 0 and that 512 00:29:33,450 --> 00:29:37,170 means that I have a feasible solution to this particular set of contraints. 513 00:29:37,170 --> 00:29:39,660 Okay, so what I do? No but this is beautiful, right. 514 00:29:39,660 --> 00:29:41,750 Why is it beautiful? Because I have this basis here. 515 00:29:41,750 --> 00:29:44,470 I love this basis, right. I have this basis, I have all this 516 00:29:44,470 --> 00:29:48,431 variables that I can put inside you know as basic variables and then I have an 517 00:29:48,431 --> 00:29:50,640 offical. Then I can optimize this thing [SOUND], 518 00:29:50,640 --> 00:29:55,030 and then I look at what the objective function is, if it's greater than zero I 519 00:29:55,030 --> 00:29:57,680 know that I don't have a feasible solution to this, to this constraint. 520 00:29:57,680 --> 00:30:00,250 So an initial set of constraints is wrong, okay? 521 00:30:00,250 --> 00:30:03,260 It's basically not feasible. So you go back to the user and say, you 522 00:30:03,260 --> 00:30:06,610 know, please give me a problem with this constraint that satisfies because 523 00:30:06,610 --> 00:30:09,850 otherwise, you know there's little purpose to actually optimize Okay? 524 00:30:09,850 --> 00:30:13,960 But if these values, see if the objective function is 0, that means that this set 525 00:30:13,960 --> 00:30:17,990 of constraint is feasible, and now, I'm ready to do the optimization. 526 00:30:17,990 --> 00:30:19,980 Right? Because at this point I have a basic 527 00:30:19,980 --> 00:30:21,610 feasible solution. Okay? 528 00:30:21,610 --> 00:30:26,230 And this basic, basic feasible solution is in the, in terms of the other 529 00:30:26,230 --> 00:30:27,620 variables. Right? 530 00:30:27,620 --> 00:30:32,130 So So, in a sense, there you can take the basic feasible solution. 531 00:30:32,130 --> 00:30:36,420 We move up, you know, this, this objective, you know, function, use the 532 00:30:36,420 --> 00:30:39,890 original objective function. Remove the non basic variable, the basic 533 00:30:39,890 --> 00:30:44,020 variables from these active function, and start again the simplex algorithm using 534 00:30:44,020 --> 00:30:46,990 that new objective function, which is the one you wanted to optimize in the first 535 00:30:46,990 --> 00:30:50,280 place. So, all the things that I told you are 536 00:30:50,280 --> 00:30:54,590 almost right, okay? So, they only I put it as I told you, 537 00:30:54,590 --> 00:30:58,750 when we complete this optimization, we have a basic feasible solution, where the 538 00:30:58,750 --> 00:31:01,898 basic variable are all the varibale, which are, you know, the original 539 00:31:01,898 --> 00:31:05,190 varibles of the problem. They are not the basic variable. 540 00:31:05,190 --> 00:31:08,150 That's not entirely true. It can be the case that one of these 541 00:31:08,150 --> 00:31:12,340 basic values, these, these artificial variables in, in the basis. 542 00:31:12,340 --> 00:31:15,980 But no you just need to think about it. If one of these variables is inside the 543 00:31:15,980 --> 00:31:19,375 basis, what does it mean? What is the value of that artificial 544 00:31:19,375 --> 00:31:22,660 variable, okay? Well, we know that the objective function 545 00:31:22,660 --> 00:31:25,830 is zero, okay? So that variable has to be zero, okay? 546 00:31:25,830 --> 00:31:30,280 So, at that point, what you can do is transform this, you know, remove it from 547 00:31:30,280 --> 00:31:32,730 the basis, introduce someone else inside the basis. 548 00:31:32,730 --> 00:31:37,330 And now you will have really a basic feasible solution expressed only in terms 549 00:31:37,330 --> 00:31:40,870 of the basic variables and then you can solve the optimization phase, okay? 550 00:31:40,870 --> 00:31:45,390 So this is it, you know, you have seen the entire simplex algorithm now, okay? 551 00:31:45,390 --> 00:31:48,540 You have a two-phase method. First, find the BFS and then optimize. 552 00:31:48,540 --> 00:31:52,380 How do you optimize, okay? Basically, what you do is you move from 553 00:31:52,380 --> 00:31:55,569 basic solution to basic solution, okay? You can detect that you're already at the 554 00:31:55,569 --> 00:31:58,950 end when all the coefficients of the variables, okay, in the objective 555 00:31:58,950 --> 00:32:02,700 functions are greater than zero, okay, and every time the BIs are strictly 556 00:32:02,700 --> 00:32:06,340 positive essentially what you do is you decrease the value of this objective 557 00:32:06,340 --> 00:32:08,320 function. If you use one of the rules that I told 558 00:32:08,320 --> 00:32:09,950 you you are garaunteed to terminate, okay. 559 00:32:09,950 --> 00:32:13,038 Beautiful algorithm, local search, garaunteed to find the optimal 560 00:32:13,038 --> 00:32:21,654 solution... Thank You. [BLANK_AUDIO]