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?