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?