Okay, so discrete optimization, part six, last part, okay? And, so what I am going to talk about today is where these, this dual coming from and why it is useful, okay? So, we saw that it was beautiful, okay? We have no idea, you know, where magically it came from, okay? And so, that's what I want to talk about, you know, in this, in this lecture. And then, I want to also tell you a little bit what it means. How you can understand these things, okay? What is the meaning of these dual variables, and then I want to talk about, you know, what it's useful for. Okay, so this is, you know, the mod, you know, understanding where it came from, okay? So this is an example that I took from [UNKNOWN] book. If you have to read two books on linear programming, this, this has to be one of them, okay? So, what you see there is basically linear programming. I'm maximizing my profit here, I'm maximizing this objective function, you know, subject to these constraints. Okay? And the, the question is that, you know, I'm asking, you know, the question, you know, can I bound this maximum? Is there an optimistic evaluation of that maximum? Okay? And so what I'm showing you here is one of them. I'm basically telling you here, okay? That the maximum value that is objective function in everything is 110, okay? Why? Okay? So, look at this constraints and look at this one. Look at these two constraints, okay? So, this is 55, this is 110, okay? Double. Why? Because I basically took that constraints and I doubling every one of the coefficient, okay? So instead of adding 5, I get 10, okay? Instead of there being 1, I get 2. Why did I do that? Okay? Because as soon as I do that, okay? So, what you can see, okay? Is that this 10 here, okay? Is actually greater than the coefficient in the objective function. This value is also greater. All the values here are greater than the objective function. And therefore, I'm maximizing something, which has to, so, so if this, is this is a value, this will have a larger value of inter-objective functions. As a value, this has to be greater than the value of the objective function by definition, okay? And therefore, in this particular case, I know that 110, okay? Has to be an upper bound, okay? I will never be able to get to, to, you know, to get higher than 110, okay? So that's an upper bound. Now this is a terrible upper bound, of course. But I'm going to show you better ones, okay? So, look at these two things here. I have two, I basically take these two constraints. I add them together, okay? If I add them together, I get this constraint that you see here, right? So, you basically see here 4x1, you know, plus 3x2, and so on smaller equal to 58, okay? So now, once again, you know, you can do the same reasoning. You can look at all the coefficients that you see there. And once again, they are always greater than the coefficients inside the objective function, okay? So, greater or equal, right? So this 4 is the 4 of the objective function. The next one is 3 instead of 1. So, I know that if I sum these two terms there, they will be smaller than the sum of these two terms. I continue to doing the same way, right? So the five in the objective function becomes six, okay? And the three remains three, okay? So, I know that this value is always going to be greater than the value of the, the objective function. Whatever the value that I find for the variables. But now, this time, the value here is 58. So, it's a much smaller value. So, I know that 58 in this particular case is a bound to this objective value already, okay? So, wow. Okay. So, so what I'm showing you here is that by combining these, these constraints. And by actually making, you know, making sure that this combination satisfies the basic constraints. They have to be greater than the coefficients of the objective function, okay? I can actually bound the value of this objective function, okay? And that's very nice, okay? So in a sense, yeah, yeah, yeah, but what is the relationship of the dual, okay? So, look. What I'm going to do is take an arbitrary combination, positive combination. It's called conic combination, of these constraints, okay? And so if I do that, I'm basically going to use y1, y2, and y3 to find the coefficients of the way I want to combine these equations, right? [laughs] Think of it, you know, why y1, y2, y3, does that remind you of something? Okay. So, I'm basically taking these y1, y2, y3, okay? And then, I'm basically combining, multiplying the, the various constraints that you have there, okay? And I know, okay? I know that, you know, when, when I do this combination, okay? So, I have to be smaller or equal to this particular value here, okay? Because, you know, this other right hand side of this constraint, okay? So, if I multiply these left hand side by y, I have to be smaller or equal to that, okay? So, I know that is I multiply this constraint by y1, y2, y3, okay? I have to be smaller than this expression, okay? Once again, you know, right inside, hey, objective function. So, if I minimize this, okay? I know that the value of this because of this combination has to be greater than the value of it's to be, it's to be greater. I knew that these values have, would have to be greater than this thing, right? But what I want to do is find the tightest, the tightest upper bound. So, I minimize this, okay? So, so I minimize, I want to find the y's that are basically minimizing the value of this expression. That I want to be bonding this thing by both, okay? Now I told you before, we have to satisfy some constraints, right? So, when I look at these coefficients there and multiply them by the y's, I have to make sure that they are greater than the value of the coefficient in this primal, right? So in a sense, what are these? Well, these are the dual constraints, okay? So, this is the dual objective function. These are the dual constraints, okay? So, the whole thing here, it's just the trick to actually bound the value of this primal, okay? So, the dual is basically bounding these values. And that's what I told you before, right? So the other day, you know, what we were doing is the primal might be minimizing, the dual was, you know, maximizing. And basically, the dual was always the lower bound to the value of the primal. Here, I'm basically maximizing. Of course, the dual is minimizing, and I'm always telling you hey, hey. The primal, the dual here has always to be an upper bound to the value of the primal, okay? And this is a systematic derivation of why this is true. Of course, once you relax, ooh, this is an interesting linear program, you can start whether the properties of these thing. And that is essentially what I have shown you last time, okay? That the value of the objective function of the primal at optimality is equal to the objective value of the dual of the optimality. So, this value here that you are minimizing is going to be exactly the optimal value of the primal, okay? That's how you actually find the derivation. You know what? Where this dual is coming from essentially, okay? Now, so this is, so I'm going to talk about complimentary slackness. And this is essentially starting to convey what these dual variables mean. And so in a sense, this is a topic which is, you know, a very interesting topic in mathematical programming. In general, this is applied to linear programming only, right? So what you see here, what basically these equations are saying, is that if you have x star and y star. Solutions to the primal and the dual, you have to have these conditions which are satisfied. And I'm going to go over, you know, over that. But essentially, what it means is that if you look at the constraints of the primal, this is the constraint of the primal. It's an equality, right? And if this, this inequality of the optimal solution is tight. So, so it has to be the case that either this inequality at opt, of the optimality has to be tight. Or the dual variable has to be zero, okay? So this is linking the primal val, the primal solutions, the primal optimal solution. And the dual of, you know, optimal solution. And basically saying oh, either that constraints in the primary state or the dual variable is zero. And this essentially expressing the same thing for the dual, right? So, all the constraints in the dual is tight, all the primary variable is zero. Okay, very interesting, okay? Very interesting ratio between these things, okay? So, you can guess which values are zero in the other side depending upon the way that the constraints are tight, okay? Now, let me give you an economic interpretation of this, okay? So once again, you know, I'm looking at this program, okay? This linear program, and we are maximizing so think maximizing profit. Now you have constraints, okay? For instance, the constraint could be production, you know, capacity constraints on your production, okay? So basically, this bi over there, okay? Is telling you oh, this is as much as you can produce, okay? So basically, you want to maximize your pro, profit. This is what you can produce, okay? But, we are limited in what you can produce, okay? So, look at this ti there. So, what I'm looking at here is ooh, assume that I can increase my capacity production a tiny bit, okay? What's going to happen? And this is essentially what this dual variables are telling you, okay? So, if you increase your capacity a little bit, okay? The value of the, the objective function is going to change tiny, you know, in a tiny fashion, okay? Is going to still be the, you know, still be at least be as good as the primal objective function that you see there is z star. But then, you're going to increase it with what, with, you know, ti times yi star, okay? For everyone of these dual variables. So, which basically means that, if you increase the capacity of these various, various constraints on the capacity, okay? I can, I can increase the value of the objective function by multiplying this increase by the value of the dual variables, okay? So, the dual variable is, in a sense, telling you a much Increasing that particular capacity. You know, relaxing that particular constraint, is bringing to the objective function, okay? Now, this is only valid when ti is sufficiently small, right? Because at some point, if you make this ti sufficiently big, you may change basis, and so on and so forth, okay? But this is essentially, this is essentially telling you, you may change fundamentally the nature of the solution. But here, when you're very close, this is what this is basically telling you, okay? So one last thing that I have to tell you, duality in the tableau, okay? So remember you know, when, when we presented the tableau, you always start with a basis, okay? So, when you start with a basis, okay? So, you know that at the end of the day, when you are at optimal solution. This other value of the objective function, okay? Now, when you look at, when you have the first basis, it's either the artificial variables. Or a basis that you found after the first phase or something like that. You have this basis and assume that these are, let's say artificial variables, okay? The cost of this things is zero in the objective function, okay? So, what do you know? You know that when you look at this formula, the cj has to be zero, okay? You also know that this matrix here, Aj, you know, this is the unit matrix, this is a unit thing, okay? So essentially, what you have here is that what remains of this is basically the value of these guys. So, cBAB minus 1 which you recognize as the simplex multiplier, right? So in a sense, the cost here, so what you will find in those locations are the simplex multipliers. Which are the dual variables, okay? So essentially, what you see there is that the, if you solve the primal, you can always look inside your tableau. And you will find the value of the dual variables. You will find the solution to the dual variables. So, not only you know that the dual is a particular cost, but you can actually retrieve the value of the dual variable to its optimality, okay? Now, why is this thing useful? Okay, so, so we have this beautiful theory. We know where it comes from. We know what it means from economic standpoint, for instance. But what does it correspond to? Okay? So, so let's look at this example, okay? So, we have a primary which is visible, okay? So, the dual is not visible until you get a optimality. So, you start your primary. You start minizining. So, because essential, so, so you have to think the primary always visible I get down to a point. In all these things, the dual is infeasible. And at some point, you get to the optimal solution. The dual become optimal and at the same time feasible, okay? So the dual, so when you do the dual simplex, okay? So, the dual is always feasible and the primal is not until you reach optimality, okay? So in a sense, what I'm telling you, that we can solve the primal. And then when, add optimality of a solution to both the primal and the dual. Or you can solve the dual, and then add optimality of a solution of a primal into the dual. So, which do you do, okay? Well, there is one case where it's actually very useful to use the dual, okay? So, assume that you optimize the primal. Okay, you optimize ta-ta-ta-boom, you have the objective, you have the optimal solution. And then somebody comes and says ooh, I forgot to tell you, I have this one constraint, okay? And obviously, the constraint is satisfied, it's not interesting. But assume the constraint is not satisfied, what's going to happen? Okay? Well, the dual, okay? Is going to be feasible. Why? Because if you look at these constraints in the dual, what is it? Oh, you flip, you know, and then it's the variable, okay? So, if you are the variable to the dual, you know, of course, you know, this, the dual is still feasible. You can give a zero to all these variables and you have the same solution, right? The primal is not feasible, it's constraint is violated. So what you can do is to say ooh, but my dual is feasible, so I can optimize the dual. [SOUND] I get to optimality and at that point, I know that the primal is going to be feasible, okay? So in a sense, if I'm adding a constraints to a primal algorithm, okay? And, and obvious this, obviously, if these constraints is, is feasible, I don't have a basic feasible solution to start from in the primal. But I have one in dual. And I can optimize the dual, get back to optimality, and there I know that the, the primal is, is, is going to be feasible and optimal, okay? So in a sense, if I have an optimal solution to the primal, [SOUND] I add the constraints, and that constraints is violated. I can optimize the dual to get back to optimality and feasibility by using the dual algorithm. Very nice, okay? You will see why this is very nice in the next couple of lecture when you do, when we do mixed integer programming, okay? Now, the other things that we can do is that actually, you know, you can do primal and dual on exactly the same tableau, right? So remember, you know, we have this primal, we have this, basically, this primal over there. And basically the dual is what? The dual is taking the objective functions of the primal, okay? And putting it as a right end side, okay? Where is my right end side? Here, right? So, we can do the same thing for the objective function, right? So, this is the right end side of the primal, it becomes the objective function of the primal, okay? And then, you have this big matrix, okay? The only thing that you do, [SOUND] you transpose it, right? And so, that's what you have here. These two things are the same, okay? And so, when you have the primal, assume that I don't have this representation of the dual, right? I see only the primal, right? But if I want to see the dual on the primal, I do this, right? And know I see the primal, right? So, in a, I, I see the dual, right? So, in a sense, I don't need this guy because it's already there, right? It's, you know, it just, you know, a different way of looking at it. So, now look at this. If I do, if I do the primal algorithm, the primal simplex, what do I do? I select an entering variable and then I select a leaving variable, okay? So, that's the primal algorithm. If I look on the other side, what does it mean? Ooh, it could mean in the dual, I would select then living variable, and then an entering variable. It's another way of doing it. It's fine, right? Because it's going to do a pivoting operation in exactly the same fashion, okay? And when I do the dual, right? If I select an entering variable in the dual and the leaving variable, and then the leaving variable to the dual, what does it correspond to? Well, the leaving variable on this guy is the entering variable on the primal and then vise versa. So, these things are the same, okay? If I pivot here, I have the same pivot here. If I pivot there, whoops, I have the pivot here, right? So when I add a new constraint and it's violated, and I'm looking at the dual, what do I do in the dual? I'm adding a, I'm selecting a constraint to enter the basis, and another constraint for leaving the basis. Which basically means that here, you know, I'm also selecting a variable. But this time, a primary variable to lead, to enter the basis, and another variable to leave the basis. So when I, when my constraints is violated in the primal and I look at the dual, the dual is basically fine. You know, I am basically, you know, doing a pivot operation here. The same thing happens here. But of course, I never have to use this. I can always use one of the tableau and do all of the things. I just have to, you know, turn my head and then it's fine, okay? So in a sense, that tells you, and of course, you could do some steps in the primal, some step in the dual. And you can do all kinds of beautiful things, right? So, using the same tableau, okay? So, this is the relationship with this primal and dual. And these things, you can exploit, and we will exploit them. And I'll, you know, you'll understand, you know, more of this when we do mixed integer programming. But the fact that we have these two things is really very useful, okay? So next time, we're going to move to mixed integer programming, okay? Which is going to be the, you know, the third big approach to combinatory optimization. And it will obviously rely on linear programming. Thank you very much.