1 00:00:00,320 --> 00:00:04,739 Okay, so discrete optimization, part six, last part, okay? 2 00:00:04,739 --> 00:00:09,480 And, so what I am going to talk about today is where these, this dual coming 3 00:00:09,480 --> 00:00:13,800 from and why it is useful, okay? So, we saw that it was beautiful, okay? 4 00:00:13,800 --> 00:00:16,710 We have no idea, you know, where magically it came from, okay? 5 00:00:16,710 --> 00:00:19,990 And so, that's what I want to talk about, you know, in this, in this lecture. 6 00:00:19,990 --> 00:00:22,430 And then, I want to also tell you a little bit what it means. 7 00:00:22,430 --> 00:00:24,000 How you can understand these things, okay? 8 00:00:24,000 --> 00:00:27,760 What is the meaning of these dual variables, and then I want to talk about, 9 00:00:27,760 --> 00:00:31,950 you know, what it's useful for. Okay, so this is, you know, the mod, you 10 00:00:31,950 --> 00:00:34,170 know, understanding where it came from, okay? 11 00:00:34,170 --> 00:00:36,570 So this is an example that I took from [UNKNOWN] book. 12 00:00:36,570 --> 00:00:40,980 If you have to read two books on linear programming, this, this has to be one of 13 00:00:40,980 --> 00:00:43,330 them, okay? So, what you see there is basically 14 00:00:43,330 --> 00:00:46,170 linear programming. I'm maximizing my profit here, I'm 15 00:00:46,170 --> 00:00:49,988 maximizing this objective function, you know, subject to these constraints. 16 00:00:49,988 --> 00:00:52,730 Okay? And the, the question is that, you know, 17 00:00:52,730 --> 00:00:57,170 I'm asking, you know, the question, you know, can I bound this maximum? 18 00:00:57,170 --> 00:01:00,600 Is there an optimistic evaluation of that maximum? 19 00:01:00,600 --> 00:01:03,480 Okay? And so what I'm showing you here is one 20 00:01:03,480 --> 00:01:05,620 of them. I'm basically telling you here, okay? 21 00:01:05,620 --> 00:01:11,478 That the maximum value that is objective function in everything is 110, okay? 22 00:01:11,478 --> 00:01:12,670 Why? Okay? 23 00:01:12,670 --> 00:01:14,880 So, look at this constraints and look at this one. 24 00:01:14,880 --> 00:01:18,880 Look at these two constraints, okay? So, this is 55, this is 110, okay? 25 00:01:18,880 --> 00:01:19,530 Double. Why? 26 00:01:19,530 --> 00:01:23,470 Because I basically took that constraints and I doubling every one of the 27 00:01:23,470 --> 00:01:27,999 coefficient, okay? So instead of adding 5, I get 10, okay? 28 00:01:27,999 --> 00:01:31,830 Instead of there being 1, I get 2. Why did I do that? 29 00:01:31,830 --> 00:01:34,540 Okay? Because as soon as I do that, okay? 30 00:01:34,540 --> 00:01:38,600 So, what you can see, okay? Is that this 10 here, okay? 31 00:01:38,600 --> 00:01:42,710 Is actually greater than the coefficient in the objective function. 32 00:01:42,710 --> 00:01:46,690 This value is also greater. All the values here are greater than the 33 00:01:46,690 --> 00:01:49,780 objective function. And therefore, I'm maximizing something, 34 00:01:49,780 --> 00:01:55,245 which has to, so, so if this, is this is a value, this will have a larger value of 35 00:01:55,245 --> 00:01:58,560 inter-objective functions. As a value, this has to be greater than 36 00:01:58,560 --> 00:02:01,090 the value of the objective function by definition, okay? 37 00:02:01,090 --> 00:02:05,650 And therefore, in this particular case, I know that 110, okay? 38 00:02:05,650 --> 00:02:09,880 Has to be an upper bound, okay? I will never be able to get to, to, you 39 00:02:09,880 --> 00:02:13,540 know, to get higher than 110, okay? So that's an upper bound. 40 00:02:13,540 --> 00:02:15,300 Now this is a terrible upper bound, of course. 41 00:02:15,300 --> 00:02:16,730 But I'm going to show you better ones, okay? 42 00:02:16,730 --> 00:02:20,680 So, look at these two things here. I have two, I basically take these two 43 00:02:20,680 --> 00:02:22,910 constraints. I add them together, okay? 44 00:02:22,910 --> 00:02:27,250 If I add them together, I get this constraint that you see here, right? 45 00:02:27,250 --> 00:02:34,370 So, you basically see here 4x1, you know, plus 3x2, and so on smaller equal to 58, 46 00:02:34,370 --> 00:02:36,820 okay? So now, once again, you know, you can do 47 00:02:36,820 --> 00:02:39,530 the same reasoning. You can look at all the coefficients that 48 00:02:39,530 --> 00:02:42,580 you see there. And once again, they are always greater 49 00:02:42,580 --> 00:02:45,540 than the coefficients inside the objective function, okay? 50 00:02:45,540 --> 00:02:49,000 So, greater or equal, right? So this 4 is the 4 of the objective 51 00:02:49,000 --> 00:02:51,420 function. The next one is 3 instead of 1. 52 00:02:51,420 --> 00:02:54,870 So, I know that if I sum these two terms there, they will be smaller than the sum 53 00:02:54,870 --> 00:02:57,540 of these two terms. I continue to doing the same way, right? 54 00:02:57,540 --> 00:03:01,230 So the five in the objective function becomes six, okay? 55 00:03:01,230 --> 00:03:06,292 And the three remains three, okay? So, I know that this value is always 56 00:03:06,292 --> 00:03:08,540 going to be greater than the value of the, the objective function. 57 00:03:08,540 --> 00:03:10,510 Whatever the value that I find for the variables. 58 00:03:10,510 --> 00:03:15,920 But now, this time, the value here is 58. So, it's a much smaller value. 59 00:03:15,920 --> 00:03:20,390 So, I know that 58 in this particular case is a bound to this objective value 60 00:03:20,390 --> 00:03:22,320 already, okay? So, wow. 61 00:03:22,320 --> 00:03:24,690 Okay. So, so what I'm showing you here is that 62 00:03:24,690 --> 00:03:29,140 by combining these, these constraints. And by actually making, you know, making 63 00:03:29,140 --> 00:03:33,910 sure that this combination satisfies the basic constraints. 64 00:03:33,910 --> 00:03:36,909 They have to be greater than the coefficients of the objective function, 65 00:03:36,909 --> 00:03:39,910 okay? I can actually bound the value of this 66 00:03:39,910 --> 00:03:43,380 objective function, okay? And that's very nice, okay? 67 00:03:43,380 --> 00:03:47,740 So in a sense, yeah, yeah, yeah, but what is the relationship of the dual, okay? 68 00:03:47,740 --> 00:03:51,010 So, look. What I'm going to do is take an arbitrary 69 00:03:51,010 --> 00:03:54,530 combination, positive combination. It's called conic combination, of these 70 00:03:54,530 --> 00:03:58,286 constraints, okay? And so if I do that, I'm basically going 71 00:03:58,286 --> 00:04:02,490 to use y1, y2, and y3 to find the coefficients of the way I want to combine 72 00:04:02,490 --> 00:04:05,360 these equations, right? [laughs] Think of it, you know, why y1, 73 00:04:05,360 --> 00:04:07,180 y2, y3, does that remind you of something? 74 00:04:07,180 --> 00:04:10,246 Okay. So, I'm basically taking these y1, y2, 75 00:04:10,246 --> 00:04:13,760 y3, okay? And then, I'm basically combining, 76 00:04:13,760 --> 00:04:17,320 multiplying the, the various constraints that you have there, okay? 77 00:04:17,320 --> 00:04:22,000 And I know, okay? I know that, you know, when, when I do 78 00:04:22,000 --> 00:04:26,090 this combination, okay? So, I have to be smaller or equal to this 79 00:04:26,090 --> 00:04:30,040 particular value here, okay? Because, you know, this other right hand 80 00:04:30,040 --> 00:04:33,940 side of this constraint, okay? So, if I multiply these left hand side by 81 00:04:33,940 --> 00:04:36,510 y, I have to be smaller or equal to that, okay? 82 00:04:36,510 --> 00:04:41,640 So, I know that is I multiply this constraint by y1, y2, y3, okay? 83 00:04:41,640 --> 00:04:45,020 I have to be smaller than this expression, okay? 84 00:04:45,020 --> 00:04:49,160 Once again, you know, right inside, hey, objective function. 85 00:04:49,160 --> 00:04:53,940 So, if I minimize this, okay? I know that the value of this because of 86 00:04:53,940 --> 00:04:59,070 this combination has to be greater than the value of it's to be, it's to be 87 00:04:59,070 --> 00:05:01,140 greater. I knew that these values have, would have 88 00:05:01,140 --> 00:05:04,590 to be greater than this thing, right? But what I want to do is find the 89 00:05:04,590 --> 00:05:09,120 tightest, the tightest upper bound. So, I minimize this, okay? 90 00:05:09,120 --> 00:05:13,920 So, so I minimize, I want to find the y's that are basically minimizing the value 91 00:05:13,920 --> 00:05:17,180 of this expression. That I want to be bonding this thing by 92 00:05:17,180 --> 00:05:19,760 both, okay? Now I told you before, we have to satisfy 93 00:05:19,760 --> 00:05:22,382 some constraints, right? So, when I look at these coefficients 94 00:05:22,382 --> 00:05:27,450 there and multiply them by the y's, I have to make sure that they are greater 95 00:05:27,450 --> 00:05:31,960 than the value of the coefficient in this primal, right? 96 00:05:31,960 --> 00:05:35,680 So in a sense, what are these? Well, these are the dual constraints, 97 00:05:35,680 --> 00:05:38,200 okay? So, this is the dual objective function. 98 00:05:38,200 --> 00:05:42,450 These are the dual constraints, okay? So, the whole thing here, it's just the 99 00:05:42,450 --> 00:05:46,020 trick to actually bound the value of this primal, okay? 100 00:05:46,020 --> 00:05:48,150 So, the dual is basically bounding these values. 101 00:05:48,150 --> 00:05:51,620 And that's what I told you before, right? So the other day, you know, what we were 102 00:05:51,620 --> 00:05:55,390 doing is the primal might be minimizing, the dual was, you know, maximizing. 103 00:05:55,390 --> 00:05:59,200 And basically, the dual was always the lower bound to the value of the primal. 104 00:05:59,200 --> 00:06:02,940 Here, I'm basically maximizing. Of course, the dual is minimizing, and 105 00:06:02,940 --> 00:06:07,520 I'm always telling you hey, hey. The primal, the dual here has always to 106 00:06:07,520 --> 00:06:09,730 be an upper bound to the value of the primal, okay? 107 00:06:09,730 --> 00:06:13,030 And this is a systematic derivation of why this is true. 108 00:06:13,030 --> 00:06:16,730 Of course, once you relax, ooh, this is an interesting linear program, you can 109 00:06:16,730 --> 00:06:18,460 start whether the properties of these thing. 110 00:06:18,460 --> 00:06:21,020 And that is essentially what I have shown you last time, okay? 111 00:06:21,020 --> 00:06:25,380 That the value of the objective function of the primal at optimality is equal to 112 00:06:25,380 --> 00:06:28,220 the objective value of the dual of the optimality. 113 00:06:28,220 --> 00:06:32,460 So, this value here that you are minimizing is going to be exactly the 114 00:06:32,460 --> 00:06:36,580 optimal value of the primal, okay? That's how you actually find the 115 00:06:36,580 --> 00:06:37,860 derivation. You know what? 116 00:06:37,860 --> 00:06:39,828 Where this dual is coming from essentially, okay? 117 00:06:39,828 --> 00:06:44,338 Now, so this is, so I'm going to talk about complimentary slackness. 118 00:06:44,338 --> 00:06:49,422 And this is essentially starting to convey what these dual variables mean. 119 00:06:49,422 --> 00:06:54,506 And so in a sense, this is a topic which is, you know, a very interesting topic in 120 00:06:54,506 --> 00:06:58,190 mathematical programming. In general, this is applied to linear 121 00:06:58,190 --> 00:07:01,110 programming only, right? So what you see here, what basically 122 00:07:01,110 --> 00:07:05,000 these equations are saying, is that if you have x star and y star. 123 00:07:05,000 --> 00:07:08,990 Solutions to the primal and the dual, you have to have these conditions which are 124 00:07:08,990 --> 00:07:11,070 satisfied. And I'm going to go over, you know, over 125 00:07:11,070 --> 00:07:12,810 that. But essentially, what it means is that if 126 00:07:12,810 --> 00:07:15,280 you look at the constraints of the primal, this is the constraint of the 127 00:07:15,280 --> 00:07:17,270 primal. It's an equality, right? 128 00:07:17,270 --> 00:07:21,230 And if this, this inequality of the optimal solution is tight. 129 00:07:21,230 --> 00:07:25,970 So, so it has to be the case that either this inequality at opt, of the optimality 130 00:07:25,970 --> 00:07:29,605 has to be tight. Or the dual variable has to be zero, 131 00:07:29,605 --> 00:07:32,730 okay? So this is linking the primal val, the 132 00:07:32,730 --> 00:07:35,200 primal solutions, the primal optimal solution. 133 00:07:35,200 --> 00:07:37,140 And the dual of, you know, optimal solution. 134 00:07:37,140 --> 00:07:42,860 And basically saying oh, either that constraints in the primary state or the 135 00:07:42,860 --> 00:07:45,960 dual variable is zero. And this essentially expressing the same 136 00:07:45,960 --> 00:07:49,210 thing for the dual, right? So, all the constraints in the dual is 137 00:07:49,210 --> 00:07:53,810 tight, all the primary variable is zero. Okay, very interesting, okay? 138 00:07:53,810 --> 00:07:56,560 Very interesting ratio between these things, okay? 139 00:07:56,560 --> 00:08:00,330 So, you can guess which values are zero in the other side depending upon the way 140 00:08:00,330 --> 00:08:03,790 that the constraints are tight, okay? Now, let me give you an economic 141 00:08:03,790 --> 00:08:06,680 interpretation of this, okay? So once again, you know, I'm looking at 142 00:08:06,680 --> 00:08:08,890 this program, okay? This linear program, and we are 143 00:08:08,890 --> 00:08:12,480 maximizing so think maximizing profit. Now you have constraints, okay? 144 00:08:12,480 --> 00:08:15,170 For instance, the constraint could be production, you know, capacity 145 00:08:15,170 --> 00:08:19,430 constraints on your production, okay? So basically, this bi over there, okay? 146 00:08:19,430 --> 00:08:22,930 Is telling you oh, this is as much as you can produce, okay? 147 00:08:22,930 --> 00:08:25,450 So basically, you want to maximize your pro, profit. 148 00:08:25,450 --> 00:08:28,810 This is what you can produce, okay? But, we are limited in what you can 149 00:08:28,810 --> 00:08:32,020 produce, okay? So, look at this ti there. 150 00:08:32,020 --> 00:08:36,960 So, what I'm looking at here is ooh, assume that I can increase my capacity 151 00:08:36,960 --> 00:08:40,930 production a tiny bit, okay? What's going to happen? 152 00:08:40,930 --> 00:08:44,972 And this is essentially what this dual variables are telling you, okay? 153 00:08:44,972 --> 00:08:48,022 So, if you increase your capacity a little bit, okay? 154 00:08:48,022 --> 00:08:51,662 The value of the, the objective function is going to change tiny, you know, in a 155 00:08:51,662 --> 00:08:55,949 tiny fashion, okay? Is going to still be the, you know, still 156 00:08:55,949 --> 00:09:00,227 be at least be as good as the primal objective function that you see there is 157 00:09:00,227 --> 00:09:04,820 z star. But then, you're going to increase it 158 00:09:04,820 --> 00:09:09,039 with what, with, you know, ti times yi star, okay? 159 00:09:09,039 --> 00:09:11,626 For everyone of these dual variables. So, which basically means that, if you 160 00:09:11,626 --> 00:09:14,860 increase the capacity of these various, various constraints on the capacity, 161 00:09:14,860 --> 00:09:17,861 okay? I can, I can increase the value of the 162 00:09:17,861 --> 00:09:21,521 objective function by multiplying this increase by the value of the dual 163 00:09:21,521 --> 00:09:25,492 variables, okay? So, the dual variable is, in a sense, 164 00:09:25,492 --> 00:09:29,109 telling you a much Increasing that particular capacity. 165 00:09:29,109 --> 00:09:33,464 You know, relaxing that particular constraint, is bringing to the objective 166 00:09:33,464 --> 00:09:37,530 function, okay? Now, this is only valid when ti is 167 00:09:37,530 --> 00:09:40,840 sufficiently small, right? Because at some point, if you make this 168 00:09:40,840 --> 00:09:44,200 ti sufficiently big, you may change basis, and so on and so forth, okay? 169 00:09:44,200 --> 00:09:48,410 But this is essentially, this is essentially telling you, you may change 170 00:09:48,410 --> 00:09:51,740 fundamentally the nature of the solution. But here, when you're very close, this is 171 00:09:51,740 --> 00:09:56,787 what this is basically telling you, okay? So one last thing that I have to tell 172 00:09:56,787 --> 00:10:02,160 you, duality in the tableau, okay? So remember you know, when, when we 173 00:10:02,160 --> 00:10:05,070 presented the tableau, you always start with a basis, okay? 174 00:10:05,070 --> 00:10:09,530 So, when you start with a basis, okay? So, you know that at the end of the day, 175 00:10:09,530 --> 00:10:14,240 when you are at optimal solution. This other value of the objective 176 00:10:14,240 --> 00:10:17,490 function, okay? Now, when you look at, when you have the 177 00:10:17,490 --> 00:10:20,100 first basis, it's either the artificial variables. 178 00:10:20,100 --> 00:10:23,540 Or a basis that you found after the first phase or something like that. 179 00:10:23,540 --> 00:10:26,950 You have this basis and assume that these are, let's say artificial variables, 180 00:10:26,950 --> 00:10:29,050 okay? The cost of this things is zero in the 181 00:10:29,050 --> 00:10:31,740 objective function, okay? So, what do you know? 182 00:10:31,740 --> 00:10:36,770 You know that when you look at this formula, the cj has to be zero, okay? 183 00:10:36,770 --> 00:10:40,890 You also know that this matrix here, Aj, you know, this is the unit matrix, this 184 00:10:40,890 --> 00:10:45,140 is a unit thing, okay? So essentially, what you have here is 185 00:10:45,140 --> 00:10:50,410 that what remains of this is basically the value of these guys. 186 00:10:50,410 --> 00:10:55,520 So, cBAB minus 1 which you recognize as the simplex multiplier, right? 187 00:10:55,520 --> 00:11:00,360 So in a sense, the cost here, so what you will find in those locations are the 188 00:11:00,360 --> 00:11:04,050 simplex multipliers. Which are the dual variables, okay? 189 00:11:04,050 --> 00:11:07,890 So essentially, what you see there is that the, if you solve the primal, you 190 00:11:07,890 --> 00:11:12,285 can always look inside your tableau. And you will find the value of the dual 191 00:11:12,285 --> 00:11:14,500 variables. You will find the solution to the dual 192 00:11:14,500 --> 00:11:16,582 variables. So, not only you know that the dual is a 193 00:11:16,582 --> 00:11:20,290 particular cost, but you can actually retrieve the value of the dual variable 194 00:11:20,290 --> 00:11:24,060 to its optimality, okay? Now, why is this thing useful? 195 00:11:24,060 --> 00:11:26,260 Okay, so, so we have this beautiful theory. 196 00:11:26,260 --> 00:11:29,300 We know where it comes from. We know what it means from economic 197 00:11:29,300 --> 00:11:32,826 standpoint, for instance. But what does it correspond to? 198 00:11:32,826 --> 00:11:38,070 Okay? So, so let's look at this example, okay? 199 00:11:38,070 --> 00:11:40,520 So, we have a primary which is visible, okay? 200 00:11:41,760 --> 00:11:44,910 So, the dual is not visible until you get a optimality. 201 00:11:44,910 --> 00:11:51,850 So, you start your primary. You start minizining. 202 00:11:51,850 --> 00:11:55,410 So, because essential, so, so you have to think the primary always visible I get 203 00:11:55,410 --> 00:11:58,280 down to a point. In all these things, the dual is 204 00:11:58,280 --> 00:12:00,390 infeasible. And at some point, you get to the optimal 205 00:12:00,390 --> 00:12:02,980 solution. The dual become optimal and at the same 206 00:12:02,980 --> 00:12:07,090 time feasible, okay? So the dual, so when you do the dual 207 00:12:07,090 --> 00:12:09,790 simplex, okay? So, the dual is always feasible and the 208 00:12:09,790 --> 00:12:11,880 primal is not until you reach optimality, okay? 209 00:12:11,880 --> 00:12:16,590 So in a sense, what I'm telling you, that we can solve the primal. 210 00:12:16,590 --> 00:12:20,150 And then when, add optimality of a solution to both the primal and the dual. 211 00:12:20,150 --> 00:12:24,480 Or you can solve the dual, and then add optimality of a solution of a primal into 212 00:12:24,480 --> 00:12:27,120 the dual. So, which do you do, okay? 213 00:12:27,120 --> 00:12:30,650 Well, there is one case where it's actually very useful to use the dual, 214 00:12:30,650 --> 00:12:33,320 okay? So, assume that you optimize the primal. 215 00:12:33,320 --> 00:12:36,886 Okay, you optimize ta-ta-ta-boom, you have the objective, you have the optimal 216 00:12:36,886 --> 00:12:39,440 solution. And then somebody comes and says ooh, I 217 00:12:39,440 --> 00:12:41,740 forgot to tell you, I have this one constraint, okay? 218 00:12:41,740 --> 00:12:45,050 And obviously, the constraint is satisfied, it's not interesting. 219 00:12:45,050 --> 00:12:48,805 But assume the constraint is not satisfied, what's going to happen? 220 00:12:48,805 --> 00:12:51,000 Okay? Well, the dual, okay? 221 00:12:51,000 --> 00:12:52,070 Is going to be feasible. Why? 222 00:12:52,070 --> 00:12:54,760 Because if you look at these constraints in the dual, what is it? 223 00:12:54,760 --> 00:12:57,540 Oh, you flip, you know, and then it's the variable, okay? 224 00:12:57,540 --> 00:13:00,630 So, if you are the variable to the dual, you know, of course, you know, this, the 225 00:13:00,630 --> 00:13:02,880 dual is still feasible. You can give a zero to all these 226 00:13:02,880 --> 00:13:05,419 variables and you have the same solution, right? 227 00:13:05,419 --> 00:13:07,710 The primal is not feasible, it's constraint is violated. 228 00:13:07,710 --> 00:13:11,390 So what you can do is to say ooh, but my dual is feasible, so I can optimize the 229 00:13:11,390 --> 00:13:14,090 dual. [SOUND] I get to optimality and at that 230 00:13:14,090 --> 00:13:16,790 point, I know that the primal is going to be feasible, okay? 231 00:13:16,790 --> 00:13:20,755 So in a sense, if I'm adding a constraints to a primal algorithm, okay? 232 00:13:20,755 --> 00:13:25,440 And, and obvious this, obviously, if these constraints is, is feasible, I 233 00:13:25,440 --> 00:13:28,430 don't have a basic feasible solution to start from in the primal. 234 00:13:28,430 --> 00:13:33,330 But I have one in dual. And I can optimize the dual, get back to 235 00:13:33,330 --> 00:13:36,850 optimality, and there I know that the, the primal is, is, is going to be 236 00:13:36,850 --> 00:13:40,900 feasible and optimal, okay? So in a sense, if I have an optimal 237 00:13:40,900 --> 00:13:43,970 solution to the primal, [SOUND] I add the constraints, and that constraints is 238 00:13:43,970 --> 00:13:46,525 violated. I can optimize the dual to get back to 239 00:13:46,525 --> 00:13:49,190 optimality and feasibility by using the dual algorithm. 240 00:13:49,190 --> 00:13:53,310 Very nice, okay? You will see why this is very nice in the 241 00:13:53,310 --> 00:13:57,290 next couple of lecture when you do, when we do mixed integer programming, okay? 242 00:13:57,290 --> 00:14:00,700 Now, the other things that we can do is that actually, you know, you can do 243 00:14:00,700 --> 00:14:03,220 primal and dual on exactly the same tableau, right? 244 00:14:03,220 --> 00:14:07,080 So remember, you know, we have this primal, we have this, basically, this 245 00:14:07,080 --> 00:14:09,760 primal over there. And basically the dual is what? 246 00:14:09,760 --> 00:14:13,440 The dual is taking the objective functions of the primal, okay? 247 00:14:13,440 --> 00:14:17,670 And putting it as a right end side, okay? Where is my right end side? 248 00:14:17,670 --> 00:14:20,148 Here, right? So, we can do the same thing for the 249 00:14:20,148 --> 00:14:22,695 objective function, right? So, this is the right end side of the 250 00:14:22,695 --> 00:14:26,480 primal, it becomes the objective function of the primal, okay? 251 00:14:26,480 --> 00:14:29,700 And then, you have this big matrix, okay? The only thing that you do, [SOUND] you 252 00:14:29,700 --> 00:14:32,710 transpose it, right? And so, that's what you have here. 253 00:14:32,710 --> 00:14:35,590 These two things are the same, okay? And so, when you have the primal, assume 254 00:14:35,590 --> 00:14:39,980 that I don't have this representation of the dual, right? 255 00:14:39,980 --> 00:14:42,975 I see only the primal, right? But if I want to see the dual on the 256 00:14:42,975 --> 00:14:47,610 primal, I do this, right? And know I see the primal, right? 257 00:14:47,610 --> 00:14:51,770 So, in a, I, I see the dual, right? So, in a sense, I don't need this guy 258 00:14:51,770 --> 00:14:54,670 because it's already there, right? It's, you know, it just, you know, a 259 00:14:54,670 --> 00:14:57,890 different way of looking at it. So, now look at this. 260 00:14:57,890 --> 00:15:02,390 If I do, if I do the primal algorithm, the primal simplex, what do I do? 261 00:15:02,390 --> 00:15:06,550 I select an entering variable and then I select a leaving variable, okay? 262 00:15:06,550 --> 00:15:10,050 So, that's the primal algorithm. If I look on the other side, what does it 263 00:15:10,050 --> 00:15:12,430 mean? Ooh, it could mean in the dual, I would 264 00:15:12,430 --> 00:15:15,950 select then living variable, and then an entering variable. 265 00:15:15,950 --> 00:15:18,060 It's another way of doing it. It's fine, right? 266 00:15:18,060 --> 00:15:22,480 Because it's going to do a pivoting operation in exactly the same fashion, 267 00:15:22,480 --> 00:15:24,430 okay? And when I do the dual, right? 268 00:15:24,430 --> 00:15:28,290 If I select an entering variable in the dual and the leaving variable, and then 269 00:15:28,290 --> 00:15:30,760 the leaving variable to the dual, what does it correspond to? 270 00:15:30,760 --> 00:15:33,490 Well, the leaving variable on this guy is the entering variable on the primal and 271 00:15:33,490 --> 00:15:35,580 then vise versa. So, these things are the same, okay? 272 00:15:35,580 --> 00:15:37,960 If I pivot here, I have the same pivot here. 273 00:15:37,960 --> 00:15:40,970 If I pivot there, whoops, I have the pivot here, right? 274 00:15:40,970 --> 00:15:44,440 So when I add a new constraint and it's violated, and I'm looking at the dual, 275 00:15:44,440 --> 00:15:47,770 what do I do in the dual? I'm adding a, I'm selecting a constraint 276 00:15:47,770 --> 00:15:50,630 to enter the basis, and another constraint for leaving the basis. 277 00:15:50,630 --> 00:15:54,030 Which basically means that here, you know, I'm also selecting a variable. 278 00:15:54,030 --> 00:15:57,240 But this time, a primary variable to lead, to enter the basis, and another 279 00:15:57,240 --> 00:16:00,420 variable to leave the basis. So when I, when my constraints is 280 00:16:00,420 --> 00:16:04,110 violated in the primal and I look at the dual, the dual is basically fine. 281 00:16:04,110 --> 00:16:07,120 You know, I am basically, you know, doing a pivot operation here. 282 00:16:07,120 --> 00:16:10,280 The same thing happens here. But of course, I never have to use this. 283 00:16:10,280 --> 00:16:12,810 I can always use one of the tableau and do all of the things. 284 00:16:12,810 --> 00:16:16,210 I just have to, you know, turn my head and then it's fine, okay? 285 00:16:16,210 --> 00:16:20,060 So in a sense, that tells you, and of course, you could do some steps in the 286 00:16:20,060 --> 00:16:22,950 primal, some step in the dual. And you can do all kinds of beautiful 287 00:16:22,950 --> 00:16:26,270 things, right? So, using the same tableau, okay? 288 00:16:26,270 --> 00:16:28,558 So, this is the relationship with this primal and dual. 289 00:16:28,558 --> 00:16:31,170 And these things, you can exploit, and we will exploit them. 290 00:16:31,170 --> 00:16:34,080 And I'll, you know, you'll understand, you know, more of this when we do mixed 291 00:16:34,080 --> 00:16:36,160 integer programming. But the fact that we have these two 292 00:16:36,160 --> 00:16:41,010 things is really very useful, okay? So next time, we're going to move to 293 00:16:41,010 --> 00:16:45,060 mixed integer programming, okay? Which is going to be the, you know, the 294 00:16:45,060 --> 00:16:48,811 third big approach to combinatory optimization. 295 00:16:48,811 --> 00:16:51,700 And it will obviously rely on linear programming. 296 00:16:51,700 --> 00:16:52,550 Thank you very much.