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.