Tip:
Highlight text to annotate it
X
Before I continue with the duality theory, I just thought I will check, I think I wrote
the, so this in the last lecture when we were computing the solutions for the bounded variable
linear problem. In the second table, in a second tableau,
the top row the 0 row at this entry, I was not show you by if I had made it written it
correctly but, any way you can make this correction if it is not there it should be 3 by 5, and
this of course, we had computed finally, so I just thought I will make sure of that then
I had ask you to write down the dual of this standard formm of L P P, so the standard form
would be minimize Z equal to c transpose x, subject to A x equal to b, x greater than
or equal to 0. All constraints are equality constraints.
And I will just write down the dual, and then you can verify whichever way you want, may
be I will demonstrate to you. See the thing is that you can rewrite this as minimize Z
equal to c transpose x subject to, remember any equality constraint can always be written
as 2 inequality constraints, and that would be A x less than or equal to b and minus A
x lesser than or equal to minus b. In other words, you would write this as Ax less than
or equal to b, A x greater than or equal to b, so A x greater than or equal to b, I will
multiply by minus sign and get this, and then your x would be greater than are equal to
0; so I will give you that much hint, and now you can write down your, so your matrix
A becomes, see A minus A times x and your right hand side is b minus b, so you can now
write down the dual to this problem, using the methods I have given you and just see,
whether you get it in the right form.
Now, remember for the dual problem that I wrote down for the primal in the general form
not the very general form, but I had some inequality constraints and some equality constraints,
so I had this weak duality theorem or the Lemma which is also known as the weak duality
theorem, which said that, if x is feasible for P that means a primal problem, and y is
feasible for the dual problem, then c transpose x is greater than or equal to b transpose
y. So, this was our weak duality theorem and
this was I have proved it to you last time, we derived it from the constraints and the
definition of our dual problem. Now, just see what can you all conclude it from here,
first if x is a feasible solution to P, then the corresponding objective function value
c transpose x is an upper bound for the dual objective function, because this inequality is valid for any y feasible for
the dual and any x feasible for the primal, so here for any feasible dual solution y the
objective function value is bounded above by c transpose x.
So, that means if I can find 1 feasible solution for the primal, when I know that my dual problem
is bounded, because remember dual problem is a maximization problem. And here we are
saying that the dual objective function value cannot exceed c transpose x which is a finite
value, so there is no question of b transpose y going up to plus infinity, so this is it;
that means this implies that if P is feasible, that means I can find a feasible, and D is
also feasible then D cannot be unbounded. Now, you know for this for sure, that if the
P primal has a feasible solution and if the dual also has a feasible solution, then only
the question of unboundedness arises. Similarly, because you have this for any pair, so you
see that you can immediately make the statement, that if y is feasible for D, then the corresponding
objective function value is a lower bound for the primal objective function value. So, if I have any feasible solution for the
dual problem then provided, so then the c transpose x is greater than or equal to b
transpose y, this is the finite quantity, therefore again c transpose x that means for
the primal objective function value cannot go to minus infinity, or cannot be made as
small as we wish, because it is bounded below by a finite number, so the same statement
can be made here, that is, we will say that if D feasible and P is also feasible, then
P cannot be unbounded; so just replace P by D and D by P the same statement you can make
here that the problem is feasible. Now, the third what can be the other conclusion,
we will make some more conclusions from here, and the third conclusion is, if let us see
if I know for sure that this is unbounded, let say the primal problem is unbounded which
means that I can make that objective function value as small as I want, so it can go to
minus infinity, what is that mean, this inequality that means, if the dual was feasible then
this value would be finite, so what we would say, it would imply that something very small
is greater than some finite number, that means minus infinity is bigger than some finite
number which is not possible. So, what could we conclude if we know that the primal problem
is unbounded, then we can conclude that the dual cannot be feasible, so just with this
inequality with this all you can so many things you can conclude.
So, if P is unbounded, it would imply that D is infeasible and similarly, your fourth
statement, that if D is unbounded, it will imply that P is infeasible.
Because, again if P were feasible then this would be a finite value, but this can be made
to go to plus infinity. Since, we are saying that D is unbounded, so it is not possible,
the inequality is not possible, but we do derive this inequality for our definition
of the dual from the primal. So, that takes care of your this things and we will further
talk about, for example there would be need to talk of a converse of 3 and a converse
of 4, which I will come to a little later, but before that we want to get into the interpretation
of the dual variables, so even and before I do that, let me show you.
See, the idea here is that we started with a primal problem, and then I defined the dual
in a very natural way from the optimality conditions for a primal problem I could define
a new problem, which we call the dual problem. So, the question that needs to be asked now
is, can I now from the dual using the same process, can I define a new problem, no the
answer is no, because when I try to now look at this as a primal problem and define its
dual I will get back to P, so this is the result that we want to prove. Theorem dual
of the dual is the primal, so in other words, I will try to write down the dual of the dual using the
rules that I used for defining the dual of a primal, and then I will show you that we
get back to the same problem, and therefore the process cannot go on indefinitely, I can
only define there are 2 distinct problems that can arise in this way.
And this will further simplify the presentation of the theorems and so on, in fact you can
see that the 4 statements that I wrote would not be necessary if I had shown this but,
anyway I wanted to first look at that inequality and give you the feeling for it, and then
we go on to showing that the dual of the dual is the primal.
So, let us see I need to quickly write down, so what was my primal; the primal was minimize
z equal to sigma c j x j, j varying from 1 to n subject to, let me just verify the m
was the first equality constraints or inequality constraints, how would be writing it, I think
I was using m bar, it does not matter even if the notation is a little different subject
to, so we were saying a i x greater than or equal to b i, i belonging to m; and then a
i x where a i's are the rows, a i x equal to bi i belonging to m bar, then we said that
x j is greater than or equal to 0, j belonging to n; and x j unrestricted for j belonging
to n bar, then we wrote the dual as maximize psi equal to b i y i, i varying from 1 to
m subject to. So, this gave rise to your y i greater than
or equal to 0, this gave rise to y i unrestricted ,because equality constraints and this gave
you the condition that summation, we are not writing summation here, we are writing in
terms of rows and columns, so this gave you the condition; see this is a row here, so
column, corresponding column we will write here, so this will be A j transpose y, so
A j is a column, so transpose becomes a row, row times y is a single number; so this is
less than or equal to c j for j belonging to n; and equality constrains, so A j transpose
y equal to c j for j belonging to n bar, so this was our dual.
Now, in order to be able to write the dual of this, I have to first formulate this as
a primal problem, so what does that entail, that means I have to convert the maximization
to minimization which can be done by multiplying by minus signed objective function.
So, write the dual as a primal problem, and what would that, so I will write here minimize
minus psi which is equal to minus sigma b i y i, i varying from 1 to m, so the bi has
been replaced by minus b i.
And this of course, same conditions except that, I should have said here, i belonging
to m and here i belonging to m bar, so those remains the same. So, I let me write this
first, now here remember your constraints here are greater, so I will multiply this
by minus sign, and so this will give me minus A j transpose y greater than or equal to minus
c j, and equality constraint to maintain the uniformity, I will write this as minus A j
transpose y is minus c j, and then y i greater than or equal to 0, i belonging to m and y
i unrestricted for i belonging to m bar. So, now this problem is exactly in the same
form whose the difference dimension, but that does not matter, I know the rules for writing
down the dual of the primal when the problem is formulated in this way, so I now write
down the dual, so what would be the dual, and please remember; see, here this was a
row a i, now in this case what is my corresponding matrix here, this A j is a column I take that
transpose, so that becomes the row. So, that means this is actually the row of the transpose.
If, I take the matrix A; see, if I write the matrix A as a 1, a m then what would be n,
so then A transpose would be a 1 transpose a 2 transpose, see these rows will become
the columns. And here I need the row, because a i x greater than or equal to b i, so what
I am saying is that for this problem your matrix is A transpose actually, so the A transpose
matrix the columns become, so if you write this you can also write as A 1, A n; so when
you take the transpose it will become A1 transpose, A 2 transpose, A n transpose and that is what
happening, so here essentially the matrix is minus of A transpose this is the thing,
so these are the rows now, so when you take the transpose you get these kind of rows,
because this is the transpose of the column, so when I transpose again, I will get the
row in the row form.
So, that dual would be maximize psi or let me write some other thing here, Z bar equal
to, so the right hand side the b is came into your objective function here, so this will
be maximize minus C j and let me write Z j, j varying from 1 to n, then for this remember,
so this was for all j belonging to N, for all j belonging to N bar, so correspondingly
if you just follow this rule I am doing that only, and it will say that Z j is greater
than or equal to 0 for j belonging to n, Z j is unrestricted for j belonging to N bar.
And then, corresponding to this thing here, corresponding to y i greater than or equal
to 0, what is that you have from here, greater than or equal to 0, you had this thing here,
it just that your matrix is changed here, so this will be minus a i z, and then we will
have, what is it; see, I am writing the dual, so my dual is right now in this form, so for
non-negative here I have this less than or equal to 0, see here this is the less than
or equal to cj, so corresponding A j this is less than or equal to minus b i, i belonging
to M. Because, you have here y i non-negative for
i and M, so the corresponding thing here would be this constraint, for non-negativity there
I had this constraint, remember this that came from the optimality criteria, so i belonging
to M, so this I have this and for n minus a i z equal to minus b i, i belonging to M
bar; so then I can rewrite these 2 as a i z greater than or equal to b i, i belonging
to M and a i z equal to b i, i belonging to M bar.
So, if you look at this problem and here this is maximization of this, so I take the minus
side outside this objective function can be written as minimize, you can write Z here.
I can replace minus z bar by z which is c j z j , so it just that the variable instead
of the x variable I am writing the z variable does not matter, but your primal problem this
together with this is the same. So, if I try to write the dual of the dual
I get back the primal problem, and so now that means whatever results I have said so
are where I said for the pair p d is also valid for d p, that means I can replace p
by d and d by p, so nice symmetric relationship and it simplifies lot of things. Once we have
this established, now I want to give you a little more feeling for the for the dual problem
in terms of the economic interpretation of the dual problem, the dual variables, and
so I need to define the diet problem, so the dual of the dual is the primal once we have
this.
So, let us consider the diet problem, a housewife's diet problem; idea is very simple and the
problem may look a little over simplified, but I think it brings out the concepts of
linear programming and the dual problem, so just let look at it, suppose housewife has
to choose from n different foods1, 2 to n, so n different foods are there, she has to choose
different foods from here in different quantities to come up with a diet.
Now, what are the features of, so actually she would like to have a adequate diet, so
for an adequate diet which sort of gives you the required nutrition's. For an adequate
diet 1, 2 to m different nutrients are required and b 1 to b 2 b m are the minimum requirements
for the respective nutrients, that means for the first nutrition which may be protein then
you are saying that at least b 1 among must be there, then carbohydrates; second nutrients
carbohydrate and you must have at least b 2 units, whatever your unit of measure gram
or whatever, this you must have this and so on.
So of course, one can say that may be if fat a nutrient, then you should not actually have
a lower bound for the fat, but it should of an upper bound, but any way then you can multiply
your minus sign and whatever it is; I am just taking as I said, a simple version of the
problem, so you may have constraints of the kind greater than also, because if you have
fat or sugar, then you do not want to have lot of these things in the diet, there must
be on upper bound. Anyway, so b 1, b 2, b m are the minimum requirements
for the respective nutrients. Now, the thing is that the different foods so for example,
a i j will tell you the amount of ith nutrient present in jth food you have this, and then
you have c j as the cost of a unit of jth food, so with data what is she wanting to do, the first of all say you look at the
constraint a 1 1 x 1 plus a 1 2 x 2 and so on, plus a 1 n x n, so my decision variables
x 1 to x n are the decision variables, that means x 1 will tell me the amount of first food that I am going
to include in the diet, x 2 will be amount of second food I have in the diet and so on.
So, with these decision variables if x 1 x 2 x n, you see this will tell me, remember
I am assuming linearity and so on an additivity axioms of linearity, so then this tells me
the first nutrient which is present in the first food, so then this will be the total
amount of first nutrient that my first food gives me, then this will be the amount of
first nutrient that the second food gives me, when I take x 2 amount of it.
So, this total is the is my diet is made up of x 1 x 2 x n, then this will give me the
total amount of first nutrient which is present in my food, and this must be greater than
or equal to b 1. So similarly, you can have a 2 1, x 1 plus
a 2 2, x 2 the second nutrient a 2 n, x n greater than or equal to b 2 and finally,
you have a m 1, x 1 so on plus a m n, x n greater than or equal to b m; so these are
your constraints which make sure that the diet you finally choose of the housewife chooses
is adequate, it meets the nutrition requirements and of course, this is very natural, because
either you will choose the food or you will not choose it, so there is no question of
negative amount of food being chosen. So, all variables must be non-negative, and
she wants to, obviously a housewife has this problem of wanting to choose a diet which
is economical also, it is adequate but economical, so minimize Z equal to c 1 x 1 plus c n x
n; so this is 1 formulation of the diet problem, the housewife's diet problem. And in a matrix
notation we can write this and this known as minimize z equal to c transpose x subject
to A x greater than or equal to b, x greater than or equal to 0, and this form is known
as the economical form; economical form of an L P P, so minimizing the cost subject to
the conditions that your diet is adequate and this is it, so this is your housewife's
problem. Now, let us write down the dual to this, and remember here in this case the constraints
are all greater, there is no equality constraint, and then so that means your m bar is missing
and n bar is missing,
So, write down the dual of the diet problem, so this would be maximize psi equal to b transpose
y subject to; so it simply takes the transpose A transpose y, this is on non-negative, so
this will become less than or equal to C remember, because you do not have the m bar and n bar
inequality constraint, so you have y greater than or equal to 0; actually the economical
form is very easy to remember the dual, because for minimization the constraints have to be
greater than or equal to the sign non-negativity if you have, then this would imply that all
your dual variables are non-negative, and this would imply that the constraints are
less than are equal to And if you can remember very well that; see
for this minimization problem the optimality criteria would be of the kind c j minus z
j is non-negative, so you can remember, so there are many ways in which you can remember
how to write down the dual and everybody can have one's own formula the way you interpret
them. So, this is your dual of the diet problem. Now, there is an interesting side to it, suppose
there is a manufacturer who wants to manufacture different pills for the different nutrients,
so a pill maker or a pill manufacturer, and then he wants to suggest to the housewife,
it will hypercritical he wants to suggest to the housewife, that instead of you know
cooking up with diet I will provide you with pills or different nutrients, so that they
together will give you an adequate diet. But, then how can the pill manufacturer attract
the housewife in what way; so let us say, just see the dual problem is the maximization
problem, so the manufacturer prices the ith nutrient pill as y i units, that means y i
rupees you can say, now look at the first constraint, so this is the A transpose; so remember your
A is a 1 1, a 1 2, a 1 n, so when you write A transpose the first row of A transpose is
the first column here, so what will it be, so the first dual constraint is, so let us
interpret it is a 1 1, y 1 plus a 2 1, y 2. And then a m 1 y m less than or equal to c
1, but you look at this now, the price of 1 unit of the ith nutrient is y i rupees and
a 1 1 amount of first nutrient is present in the first food. So, a 1 1 into y 1 will
be the value of the first nutrient in terms of the manufacturer, because he is pricing
the ith nutrient as y i rupees, so this is the total worth of the ith nutrient to the
manufacturer, then a 2 1, y 2 this is the second nutrient; the first index refers to
the nutrient, so a 2 1, y 2; so that means for the first food, the nutrient present in
the second nutrient present in the first food is a 2 1 per unit of the first food, the second
nutrient; so this is the total worth, so this the left hand side tells you the worth of
the first food in terms of its nutrients. Corresponding to the prices that the manufacturer
is putting to these different nutrients, so the for the manufacturer, these are the values
of the prices of the different nutrients and a 1 1, a 2 1, a m 1 are different nutrients
present in the first food, so the total worth of the first food is this much, and obviously
this cannot exceed C 1 the price of the first food in the market, because if it exceeds
C 1 then why would the housewife be interested in you know going for the pills rather than
the food. This is the kind of argument that you are making it, just to help you to look
at the other side of the Linear Programming Problem.
And so this gives you C 1 and similarly, the other constraints; so the second constraint
will tell you, that the worth of the second food in terms of its nutrients it contains,
and therefore the value that is being accorded to these different nutrients by somebody else;
by the manufacturer, so the total worth of the second food should be less than or equal
to C 2 and this would be your second constraint. So therefore, the dual constraints give you
a nice way of looking at the constraints here, and it says that you are comparing the actual
price of the food in the market to the worth of the food in terms of the nutrients it contains,
it can be other scenario and therefore, it can be some other interpretation, but this
is a kind of thing one will do. And then of course, the manufacturer also has to know
as to what would be the prices for these different nutrients, so that his proposal to the housewife
becomes attractive. So but, he would want to maximize his pricing,
he would want to maximize, because he wants to maximizes gain subject to this constraint,
because the moment he violates this, his proposal is not attractive. Therefore, this is the
dual problem and so y i in other words the dual variables here are in a sense, you have
this primal problem, you have the right hand side quantities; so the dual variables are
in a way prices for the other person what would be the worth of these items of these
nutrients to the other person, who wants to come up with an alternative way of making
of this diet, that means in terms of pills. So, this is 1 interpretation of this thing.
And now, you can look at the weak duality theorem also, which says that the c transpose
x, the cost of the adequate diet should be always be more than the worth of the food
to the manufacturer in terms of the pills; so c transpose x is always greater than or
equal to b transpose y and we will come back to the reputations of the dual variable some
more at optimality what does it say.
Now, let me come to the fundamental theorem of duality, we have already and there are 2 ways of stating this. I will
make the statement first, so let me now give you the fundamental theorem of duality, which
says that if x bar is optimal for P, then the dual problem D is feasible, then D also
has an optimal solution y bar and the 2 objective function values are equal, that is c transpose
x bar is b transpose y bar. So, let us prove this and then proof. So,
if x is optimal there is a basis b, so proof since x bar is an optimal solution for P,
there exist a basis B such that, and this we have shown while I was defining dual problem,
such that y bar equal to C B, B inverse, I think I used that the y bar transpose C B,
B inverse is a dual feasible solution, the way we define the dual problem I showed you
that if B is a optimal basis, then the optimality criteria will be satisfied and that means
that y bar given by C B, B inverse is dual feasible.
So, if you just go back to the definition of the dual you will recall this, so this
is dual feasible solution and by definition c transpose x bar which has nothing, but C
B, B inverse B, because your basic feasible solution C B, B inverse B, C B is the profession
part and then this this and this is equal to B inverse B transpose C B, B inverse; so
you can write the transpose and same thing, because it is a single number, so I take the
transpose. So, the 2 objective function values are equals, therefore I have shown you that
D also has an optimal solution and the 2 objective function values are equal.
So, the proof is simple, because the way I constructed the dual, there is nothing much
to do, but the implications are many and we will show. Now, of course one can also state
the fundamental theorem as saying. I hope there is no confusion, see sometimes I may
not write the transpose and so on, but it is all evident from the context whatever.
So, another alternate statement could be what, alternate statement
of the theorem would be if x baris feasible for P and y bar is feasible for D and c transpose
x bar is b transpose y bar, then x bar is optimal for P and y bar is optimal for D.
Now, again there is not much different, because remember if x bar is feasible for P and y
bar is feasible from your weak duality theorem what did we say, that if x is feasible and
D is also feasible, then D cannot be unbounded and similarly, if D is feasible P is feasible
then P cannot be unbounded, so once we know that both the problems are not unbounded,
because both have a feasible solution therefore, both will have finite optimal solutions. And
this, because you have given this that c transpose x bar is b transpose y bar, so you will should
be able to show byexactly following this proof.
Because, now you have come here, so if x is optimal for D and D is also has an optimal
solution y bar and that 2 objective function values are equal, now we will say that; see
the statement that is x is feasible and D is feasible, then x has an optimal solution,
because P cannot be unbounded and therefore, the rest of the proof follows.
I would like you to just sit down and write the proof for this using that, because you
just have to bring it from here, you conclude that P has a finite optimal solution, and
because the 2 objective function values are equal you will be able to show that y bar
is optimal for here, may be you can say that the proof is not complete, because I have
shown you that the 2 objective function values are equal, I have shown you that this is b
transpose y bar but, then y is bar optimal for D, so maybe I can complete the proof here,
so we come back here and we say that, I have shown you that the exists of feasible y bar
for the dual problem; such that the objective function values are equal.
Let, y be any dual
feasible solution, then x bar y is a primal dual pair of feasible solution and from the
weak duality theorem
c transpose x bar is greater than or equal to b transpose y, because x bar is feasible
for the primal, y is feasible for the dual; so c transpose x bar is greater than or equal
to b transpose y, but b transpose y bar is equal to c transpose x bar and therefore,
this is greater than b transpose y, where y is any dual feasible solution.
So therefore, this implies that b transpose y bar is greater than or equal to b transpose
y for any feasible y, so this implies that y bar is optimal for D. So, I should have
completed the proof there, so this shows that this is called a constructive proof, given
optimal solution for the primal I can actually construct an optimal solution for the dual,
and so that alternate statement you can also do the same thing, because you have this equality
and this will only happen when y bar is equal to C B, B inverse for B an optimal basis for
the primal. So, this is this.
Now, you can immediately see that, from the weak duality theorem I had the statement 3
from
the weak duality theorem, statement 3 was what was your statement 3, statement 3 was
that, if the primal is unbounded it implies dual is infeasible, so let me just look at
this one and then you can similarly, write the converse of statement 4, so P is unbounded
implies D is unfeasible, what would be the converse; so converse would be, if D is infeasible,
does it imply question mark P is unbounded, so this would be the converse.
Now, actually the converse would be that if D is infeasible the primal can be unbounded
or infeasible, so because we said that the dual of the dual is the primal, so and this
part we have already set, that if P is unbounded D is infeasible; so you can replace P by D
and D by P, so you say that if D is unbounded P is infeasible; so here D is infeasible you
want to conclude, whether P will always be unbounded which is not true, because I can
now take a quickly example here to show you that both can be infeasible at the same time.
So, let us take this example, minimize z equal to x 1 plus x 2 subject to x 1 minus x2 less
than or equal to minus 1 and minus x 1 plus x 2 less than or equal to minus 1, x 1, x
2 greater than or equal to 0; you can immediately see that the problem is obviously, because
x 1 minus x 2 less than minus 1 and minus of that is also less than minus 1, so you
can draw the thing if you put this equal to 0, you have a this thing here and you have
a this here, so the feasible region is this side, because 0 lies on the other side.
Similarly, here when you put this equal to 0, you have this parallel line and then this
is minus 1, so you have this and this thing is this. So, problem is infeasible; quickly
write the dual. Now, writing the dual and of course, you can see this is minimization,
you can either make it greater and then add slack or you can add slack variables and get
the standard form and then write the dual, but treat this as an exercise and try to write
the dual, this would be the dual. So, here y 1, y 2 are less than or equal to 0.
Because see here the constraints are not greater kind, anyway; so this is the dual and when
you plot it here, it turns out that this is the feasible region and this will be unbounded,
because y 1 y 2 are less than or equal to 0, and if you look at these 2 constraints,
then they are represented by these 2parallel lines and then this is the region.
So, in this case the dual is unbounded, so primal infeasibility can imply dual unboundedness.
This is one case I wanted to look at and then the second situation is if you take this L
P P, minimize z equal to x 1 subject to x 1 plus x 2 greater than or equal to 1, and
in the same constraint again greater than or equal to 1 and x 1 x 2 are unrestricted.
So, in this case you see obviously it is infeasible, because the same quantity and the minus of
that is greater than 1 not possible, so and if you plot it you see that 1 constraint represents
this side and the other one this; so the primal is infeasible, because x 1 x 2 are unconstraint,
so its spreads on both side.
Now, again here you can write the dual this is in the economical form, and because the
variables are unrestricted, therefore the constraints would be equality kind and you
can immediately see that y 1 minus y 2 equal to 1 and y 1 minus y 2 equal to 0; so this
is infeasible. In this case, I have shown you, given you an example, that if the dual
or whichever way problem you look at is infeasible, then the other will also be infeasible, can
be infeasible. And here the unboundedness comes, because the dual problem is feasible,
the primal is infeasible, the dual is feasible, and therefore it will be unbounded.
So, both cases are possible, therefore the converse statement would be, let it D is infeasible
then P is unbounded, if P is feasible, so we will write that P is unbounded if P is
feasible, otherwise P is infeasible this is the thing. So, since we have already said
that the dual of the dual is the primal, so you can interchange the statement P and D.
So, what essentially we are saying or we establishing through examples is that if 1 of the problems
is infeasible, the other problem would either be infeasible and if it is feasible it will
be unbounded. So, this is the proper converse of the statement 3 and through examples I
just thought, I will give you an idea.
And now, I can quickly give you this chart for the fundamental theorem, which we will
talk about in the next lecture also. So, you have P, you have D, then you have optimal
solution, then you have infeasibility and you have unboundedness and here you have optimality
infeasibility and then unboundedness. So, your chart will look like this,
And now when we have said that, when one is optimal the other is also optimal from your
fundamental theorem of duality, and then if this is optimal, this is not possible; the
dual problem cannot be infeasible or unbounded. Similarly, if P is infeasible, if this is
the infeasible then this is not possible, remember we just not said that if P is infeasible,
then the dual cannot have an optimal solution, it can be infeasible or unbounded, because
I gave you an example that if one is infeasible the other can be infeasible or it can be unbounded.
Now, when this is unbounded the dual cannot have a finite optimal solution, because it
will imply that P also has finite optimal solution, unboundedness this is true and this
is not true. So, the chart is complete and one can use these results in many ways, we
will show you, and in fact this will give rise to the fundamental theorem of duality
also gives rise to the complementary slackness conditions, which we will discuss next time
and also alternate ways of solving a Linear Programming Problem.