Tip:
Highlight text to annotate it
X
So, let me now defined another entity that we need to consider various kinds of structures
that a polyhedron can have. Now, here let me defined a direction of..., and I am doing
it for a polyhedron direction of the polyhedron; and here I will do it for this particular
one, so I will take it for the..., I will take up the polyhedron that corresponds to
the feasible region of a linear programming problem that we defined in 3 which I have
been calling as LPP 3. So, here you have Ax equal to b, x greater
than or equal to 0, and of course, x belongs to R n, so this is my polyhedron in dimension;
and we say that a vector d belonging to R n is said to be a direction of the above polyhedron;
if Ad is equal to 0, Ax equal to b, so Ad must be 0, and d non-negative, all components
of d are non-negative, and d satisfies the condition that Ad is 0, fine now you see what
do we mean by this, the idea is the direction, the idea is that if I take any.... So, let
x naught belongs to F, remember I am calling the feasible region, that means, all x which
satisfies this condition and a non-negative condition, the they are the collection of
all these feasible solutions, I am referring to as F.
So, if x naught belongs to F, then x naught plus lambda d belongs to F for all lambda
non-negative, because if you take A of x naught plus lambda d, then A of x naught plus lambda
Ad, but Ad is 0, so Ax naught will be equal to C, and since all components of d are non-negative
lambda is something positive non-negative, all the components here also non-negative;
that means, for any lambda positive, this is also feasible solution; and so, that means,
that I can continue proceeding in the feasible region, because as lambda goes becomes higher
and higher this vector also becomes of your length higher and higher, and so I continue
to remain in the feasible region; and no matter what the value of lambda is, as long as it
is non-negative, it is a positive number; so, this is the idea, that means, you can
move in the feasible region along it direction. Now, of course, you can have your description
of the polyhedron as less than or equal to b or greater than equal to b, or then this
I will leave as an exercise for you to sit down; and of course, I will demonstrate through
this particular example to show you the concept of direction and how do you go about a locating
it fine. Now, see for example, if you have this polyhedron, so and then another thing
is that if a polyhedron has a direction, then we it cannot be bounded.
So, what I am said trying to say is that, may be presence of a direction in a polyhedron
implies that the search is not bounded, because I will not be able to find, since no m greater
than 0 exists such that x naught plus lambda d norm is less than M for all lambda greater
than 0, because you give me a M, I will choose a value of lambda higher then what it is now
and then violate this inequality. So, this set is not bounded, so the presence
of directions implies that your feasible region or your polyhedral is not bounded. So, let
us look at this example here; now, since I do not have all equalities, of course, I could
convert it to standard from, and then talk about..., but I want to demonstrate that how
you can modify this definition and even you have when all the constraints are not inequality
or of the quality type.
So, here that means, to find a direction for the given polyhedron d has to d which is d
1, d 2, d 3, remember I will write it as a row vector does not matter, but I understand
it is a three tuple. So, d is given to find a direction for this, this should satisfy...;
so, here it will be, for example, minus d 1 plus d 2 equal to 4, after this one it have
to be d 1 minus 2d 2 plus d 3 less than are equal to 0, sorry I am sorry this is 0, because
obviously since I want this constraint to be satisfied for all values of lambda is less.
So, if it is less than are equal to 0, this condition this can will remain feasible; so,
just check it out for yourself, and then here it will be that d 3 is greater than are equal
to 0, and of course d 1, d 2, d 3 are greater than 0. So I would like you to sit down and
just make sure that this these conditions are enough to define a direction, that means,
what you because I am assuming non-negativity, so all you need to verify is that.
For all values of lambda such a point for all values of non-negative values of lambda,
this point will remain feasible, so please do this exercise for yourself; now, here you
want to look at this and let see what will be the...
So, if you want me to let me draw the thing for you; so, this is 1, this 2, and this is
2, third axis when you have d in this this implies that d 2 is d 1; and so, here that
gives you this thing here, this is the line d 2 equal to d 1; now, add these two, fine,
because this one has given me d 1 is equal to d 2, I should have done it this way, no
I do not need to write this yes so from here d 1 equal to d 2.
So, if you if you put d 1 as d 2, this gives you minus d 2 plus d 3 is less than or equal
to 0 right; so, this says that, d 3, this implies, d 3 is less than or equal to d 2;
so, the set of directions that we have finally obtained is all d 1, d 2, d 3, where these
components are non-negative, and d 1 is equal to d 2, and d 2 together are greater than
or equal to d 3, so this is the set. And you see that I have marked with the arrow,
the region in which any direction would satisfy this condition, and therefore this becomes
a cone, you see it is a cone of all the directions with any vector lying in the direction in
that arrow region would be direction for the set. And now, I am also talking about extreme
directions just like we have the concept of the extreme points; so, here you see 1 1,
0 upon root would be unidirectional, it is also a direction, because see here d 3 becomes
0, and d 1 and d 2 both are 1, similarly because you can have d 2 and d 1 both greater than
or equal to d 2. So, you can also have the direction 1, 1,
1 divided by root 3, and so I have marked those two directions; so, then any direction
that they form the two sides, the extreme sides of the cone and any direction in this
cone would be then near direction of the feasible region right; and so, I have shown you that
you take a non-negative combination, and C 1 proceed 2, C 1 plus C 2, C 2 and this would
be because C 1 C 2 are non-negative; so, these can satisfy the condition that, d 1, the first
component and the second component are the same, and they are greater than or equal to
third component; therefore, you see that the feasible region that we were considering is
not bounded, because they are directions in the feasible region
So, now, let us continue with some more results of the of the simple for the simplex algorithm,
that means, I am trying to develop the theory; the thing is that, we have so far...; let
me now say something about the geometry and the algebra that is running parallel; see
I first define for the for the LPP 3 that I am calling, I had the problem as minimize
c transpose x subject to Ax equal to b x greater than or equal to 0 right; so, I have defined
your feasible region F as x belongs to R n implies that Ax is equal to b x greater than
or equal to 0 and I call this this set of feasible regions; then I showed you that if
f is non-empty, then it will always..., and then of course we define the concept of a
basic feasible solution; and I showed you that if f is non-empty, it means if f has
a feasible solution, and it always have a basic feasible solution.
So, this basic feasible solution came through the idea of selecting m linearly independent
columns here, then we will call that as a basis, and then I put the remaining variables
as 0, and I solve the reduced system, and I got A so this was a completely algebraic
concept. Then I have also been looking at F as polyhedron F as a polyhedron, because
F is being described as intersection of finite number of hyper planes and finite number of
half spaces, so this becomes a polyhedron; and then I have defined an extreme point of
F also, because F is a polyhedron. So, what I am trying to say is that, on one
hand we talked of basic feasible solutions that form part of the feasible solutions which
are collected in F, and then I have also looked upon F as a polyhedron, and then we have the
notion of an extreme point of F. Now, in the result that we are going to prove shortly;
I want to show you that these two notions even though they have been defined separately
are actually one and the same, that means, a basic let me write down this theorem here,
I am not going into the technicalities of you know, because if you define a polyhedron,
then you talk of a dimension, so here of course since these are all equalities, so the dimension
of this polyhedron particular is n minus m, because I am assuming that rank A is m.
So, therefore, the dimension of f is as a polyhedron is n minus m, and so what one can
have a representation for F in which you only require n minus m variables, but we are not
discussing that here; my basic idea is that, you want to show you that this concept of
basic feasible solution and an extreme point are one and the same, so theorem is that,
a corresponding to basic feasible solution x bar belonging to F there is an extreme point.
Now, actually, again I should not be saying that, there is an extreme point, a basic feasible
solution is an extreme point, and vice-versa, basically this what you want to show; so,
corresponding to a basic feasible solution x bar belonging to f, there is an extreme
point. So, when I see there is an extreme point,
that means, when I am looking upon F is a polyhedron may be in a smaller dimension,
the corresponding dimension of F, so corresponding to a basic feasible solution x bar belonging
to F, there is an extreme point, and vice- versa; maybe I should rewrite the theorem.
Essentially, what I want to say is that, if and only if it is an extreme point, so maybe
you will allow me to rewrite the theorem, I will just erase this x bar belonging to F is a basic feasible solution
of F, if and only if it is an extreme point, it is an extreme point of F.
This is a better way of what I going to say, what I said earlier is also correct, but then
we would have to be more technical, so I want to just give you the basic result here, that
is x bar is a basic feasible solution of F, if and only of it is an extreme point of F;
start moving the theorem I will of course take the definitions here, if you look at
the proof.
So, x bar is a basic feasible solution; so, I consider x bar belonging to F is basic feasible
solution, this and this implies that, Ax bar is equal to b, x bar greater than or equal
to 0; and sigma A i X i bar i varying from 1 to r is equal to b, where after where after
renumbering the columns of A I have made the first r variables as the positive ones.
So, x bar is a basic feasible solution, it may be degenerate, I do not know; but so,
what we are saying is that, if the r components of x bar are positive, then I renumber my
columns as I have been saying it earlier, I renumber the columns, and the first r columns
when correspond to the positive components of x bar; suppose, x bar is not an extreme
point, this implies, there exist x 1 and x 2 belonging to F, such that, x bar can be
written as lambda x 1 plus 1 minus lambda x 2 for 0 less than or equal to lambda less
than or equal to 1. See, my definition of an extreme point is
that, it cannot be expressed as a convex combination of any other two points of the set, so I start
with the basic feasible solution, then I am saying that suppose it is not an extreme point,
then I must able to find two points x 1 and x 2 in F, such that, x bar can be expressed
as a convex combination of these two points right fine.
Now, the thing is that x i bar is 0 for i varying from r plus 1 to n; remember, I have
renumbered the columns and the variables, so my first r components of x bar are positive,
the remaining and n minus r are 0s, which means that x bar i is 0 for i varying from
r plus 1 to n. Now, since lambda is greater than or equal to 0, x 1 and x 2 are also non-negative,
what do you get from this equation; you see this is 0 here for a for any component of
x bar, which is after from r plus 1 to n, for any such component here if you become
this component wise sum. So, here everything is non-negative. So, when
can this equation be satisfied, this will be satisfied, this implies that, x 1 i equal
to x 2 i are 0 for i for i varying from r plus 1 to n, that means, the last n minus
r components of x 1 and x 2 must also be 0, otherwise this equation will not be satisfied.
We are starting with the assumption that x bar is not an extreme point, so I can find
x 1 and x 2 such that x bar is expressible as a convex combination of these two points;
but then since the last n minus r components of x bar i are 0, it implies that the last
n minus r components of x 1 and x 2 must also be 0 right; therefore, B x bar B - we are
referring to the first r components - is equal to B x 1 B is equal to B x to b is equal to
b, because both x 1 and x 2 are solutions to your..., they are in the feasible region,
so they must be satisfying this these equations, the last n minus r components of x 1 and x
2 are 0. So, this system reduces to B x B bar, where
B is the basis, where b is the..., there is a little problem here in the sense that B
I am assuming only r components positive, so let say that we have extended the basis,
where B is the extended basis is the extended basis for x bar. I have explain this concept
also to you that if you have a set of linear independent columns which is less than the
basis size, then you can always add few more columns to it, that it so that it becomes
a basis; so, b is the extended basis; so, then I have this equation which implies that
x B 1 is equal to B inverse b is x B 2, and this is equal to x B bar right; and since
the last n minus r components of the three vectors are the same.
So, this implies is that, x 1 equal to x 2 is equal to x bar, and so our assumption that
x bar is not an extreme point fails right, because I have shown you that if you start
with this assumption, then you have no choice but to say that it, but to conclude that x
1 and x 2 to have to be x bar, so therefore x bar cannot be an extreme point; so, I stated
with the basic feasible solution, and I have shown you that x bar also has to be an extreme
point.
So, now, we have do the other way which I started writing earlier; now, the if part,
that is if x bar is an extreme point of maybe I draw a line here an extreme point of F, it is also a basic feasible solution.
Now, here we will say that x bar is an extreme point, and I will again say the same thing
that..., so x bar is an extreme point, and it is in F, therefore Ax bar is b x bar is
greater than or equal to 0. And suppose, x bar is not a basic feasible
solution, and remember our definition of a basic feasible solution is that the columns
corresponding to the positive variables in a feasible solution, if they are linearly
independent, then I can always call it a basic feasible solution. So, suppose, x bar is not
a basic feasible solution, this implies that, summation y i A i i varying from 1 to r is
0. So, here again I am assuming that, I have
renumbered the column just as there; so, the first r columns correspond to the positive
components of x bar, and so the corresponding column are linearly dependent right, this
all y i(s) are 0; let me sum, then I do the same trick, I multiply this by theta and add
here.
So, if you write this in expanded form it will be A 1 x 1 bar and so on; so, without
working out the details, so I will say that 1, and this is 2, so 1 plus theta into 2 imply
that summation x i bar plus theta y i A i i varying from 1 to r is equal to b; see I
am trying to show you I am trying to..., so here the idea would be abstracted with the
assumption that x bar is an extreme point; and now, I want to show that it is an basic
feasible solution. So, I will try to show you that, if x bar
is an extreme point, then x bar has to be a basic feasible solution; and since, I am
starting with the assumption that, x bar is not a basic feasible solution, therefore I
will have this. So, using this I will try to contradict the fact that x bar is an extreme
point, and so since I have assume this I am this is given to me, that means, I should
be then able to say that x bar has to be a basic feasible solution, so this will be the
idea behind the proof by contradiction, as you say I am proving the result by contradiction.
So, this is this. Now, let us see why I can be positive negative are 0s right, now if
and I am taking theta, here I should have said for theta positive, let me take or no
nothing I am not saying anything yes, so in the second part. So, this is I have this mark
here. Now, consider all y i(s) greater than 0, so for all y i(s) then I should my theta
there will be limit on theta, because I want x i bar plus theta y i greater than are equal
to 0. So, that means, what we are saying..., this
is non-negative, this is positive, this is positive; so, if theta is positive then no
problem, but I am trying to find out how far can theta can go as a negative number; so,
this is this; this implies theta has to be greater than or equal to minus x i bar upon
y i which is a negative number, because this is positive, this is positive, so this is
the negative number. So, let me take theta to be this thing as
max of minus x i bar upon y i, because i if I take this as max y i greater than 0, so
among all y i(s) which are positive, I am taking this corresponding ratio here, and
then choosing the maximum. So, if theta bar, so if theta is bigger than this theta bar,
then you see the corresponding numbers here will all remain non-negative if my theta is
bigger than theta bar, then it will satisfy all these inequalities, and so the corresponding
number here will remain nonnegative, and this is what I want to ensure.
So, let us continue with this proof here, so theta bar you see if I choose theta greater
than this, then I am because these numbers will not become negative; similarly, for all
y i less than 0 x i bar plus theta y i greater than or equal to 0 will imply that theta see
here y i is negative. So, when I write the inequality theta y i
greater than minus x i bar, and then when I divide y i it is a negative number, so the
inequality will reverse implies theta should be less than or equal to minus x i bar upon
y i; for all y i negative in order that this number remains non-negative, I should have
theta satisfy the condition, which means that if I choose theta bar as the number which
is minimum of minus x i bar on y i less than 0.
Again now this is the positive number, and once my theta if my theta is greater than
see this is less than or equal to..., so if theta is less than theta upper bar, then all
these numbers will remain non-negative, so here theta bar we decided we selected theta
bar as this, and your theta lower bar was max minus x i bar y i with y i greater than
0. So, we choose this, and then the idea here
is you see if I draw this line here this number theta lower bar because y i is positive x
i is also positive, so this number will be negative, so your theta lower bar, therefore
this number is 0 here, and this is theta lower bar, and theta upper bar is somewhere here,
because theta bar is a positive number, y i less than 0.
Now, the thing is that I want to satisfy both the conditions, because for whatever the value
of y i positive or negative my components here it should be non-negative fine; therefore,
for example, if theta bar is less than theta upper bar theta lower bar, then I will choose
this interval right, and I will call it therefore; and if theta bar upper bar is smaller, than
this then I will accordingly choose an interval around 0, so that this interval is a subset
of the interval theta lower bar theta upper bar the whole idea is to...
So, therefore, what I am saying is, let us select, so, let theta naught as minimum of
if so then for and you can now verify, because of this diagram, it is an existent for 0 less
than or equal to theta less than theta naught, the two since vectors x bar plus theta y and
x bar minus theta y are feasible, so your LPP 3 that is what we have been discussing,
and they are both in F. So, now, if I choose a theta which is in this interval, then x
bar plus theta y and or it may be just to be safe, we will take into be strictly less
than theta naught, it does not matter; so, then these two solutions are feasible right
and x bar can be written as half x bar plus theta y plus half x bar minus theta y.
So, that means, I started with the assumption that x bar is an extreme point of F, and then
I have been able to construct; and then with the assumption that x bar is not a basic feasible
solution I could construct two feasible solutions such that their convex combination is your
point x bar, which contradicts the fact that x bar is because we started in the assumption
that x bar is a base is a an extreme point, so this contradicts the fact that x bar is an extreme point F.
Therefore, our assumption that the columns corresponding to positive components x bar
are linearly dependent is not correct fine; and so, the columns corresponding to positive
components of x bar are linearly independent, and if they are m in number fine, because
then x bar is a basic feasible solution.
Otherwise, we will extend; so, if necessary, extend this set of columns set of linearly
dependent columns to form a basis B. So, we have seen in this process, so many times that
in case you have a feasible solution and the corresponding and the columns corresponding
to positive components are linearly dependent; and we can always say that, it is a basic
feasible solution, because we can extend the set of linearly dependent columns to form
a basis, and then it becomes a basic feasible solution by our have definition.
So, this is what, therefore, the theorem is complete now, because I have now shown you
that there is one one correspondence between a basic feasible solution; well, one one in
the sense that, if a feasible solution is there which is a basic feasible solution,
then I can show that it must be an extreme point and vice versa. But we have also no
seen that when you have degenerate basic feasible solutions or a degenerate extreme point, then
you they can be more than one basic feasible solution corresponding to the same extreme
point; so, this is what...; and now, let me in continuation of this only show you discuss
one of the pathological cases. So, before that I will like to..., so a pathological
case, let me just to say this, so here so far we have defined it for a equality constraints
with non-negative variables, remember our definition of the basic feasible solution.
Now, suppose consider the system of constraints, what shall I say Dx plus Ey equal to b where
and where x is it this is greater than or equal to 0, and what we are saying is that
D is m by n 1 and E is m by n 2 n 1 plus n 2 is equal to n. So, the total number of variables
are n, but you have first n 1 variables satisfying the non-negativity constraints, second set
of variables, the n 2 variable this are not are free.
So, now, obviously the definition of a basic feasible solution will change; though again
you can..., and what I am going to do will tell how to always reduce system, I have also
discussed it earlier with you that, if you have unrestricted variables, you can always
convert them the system to a restricted except that the dimension goes up anyway, so here
I will just straight away define the this thing.
So, a basic feasible solution, so you say that x y is a basic feasible solution of 1
if the set of columns set of columns D j said that x j greater than 0 union all columns
E i i varying from 1 to n 1, this all columns, this are linearly independent; that means,
for the unrestricted variables the corresponding columns all must be linearly independent,
and here for the positive for components of x or the corresponding columns, so all these
called together should be linearly independent, this is the definition.
Now, if we look at the..., now look at the equation or the constraint x 1 minus x 2 equal
to 1, let us say, x 1 x 2 belonging to r 2 fine; consider this feasible region; consider
this feasible region. Now, you could draw it in the r 2 plane, this is x 1 x 2, when
this is passing through the point 1 0 and 0 minus 1, and this line exceed the feasible
region is this line which is extending to both the direction to infinity in both the
directions; so, no extreme point right. So, you can see it from geometry, but if you
apply this definition or not it is no but; and if you apply this definition, this gets
verified, because here remember you are in r 2, there is only one constraint, so what
are the columns, and they are known no x j variables in the sense that no non-negativity
constraints variables are here, both the variables are free to take any value; and so, in this
case, your columns are 1 and minus 1, these are the two columns, its one-dimensional,
so your n is 1, therefore this is 1 column in this; so, these are linearly dependent,
because one can be written as one this can be written as minus time this.
So, these two columns are linearly dependent; therefore, there will be no extreme point
to this feasible region as we have can be verified by the definition of zone; so, I
will transform this region, which is a straight line extending to both sides, and hence therefore
has no extreme points by this transformation; so, x 1 gets replaced by x 1 plus minus x
1 minus, x 2 get replaced by x 2 plus minus x 2 minus, and all them all these four variables
are non-negative. So, this is the new constraint now; so, I
have embedded this two-dimensional thing in to a four-dimensional region; now, you see
since a single constraints of the rank of the coefficient matrixes again 1, so I will
again have a basic feasible solution corresponding to 1 column, and a single turn non 0 vector
is linearly independent vector, that is what I am using here, I should said this set is
linearly independent, that is.., so then column a one corresponding to this if I choose and
I will put all these three equal to 0 and my solution would be 1 0 0 0.
So, this is the basic visible solution; similarly, here because of non-negativity I cannot choose
these, so I will choose this one; so, if I choose A 4 as my basic column, then I will
put the first three variables to 0, and then that will give me x 2 minus as equal to 1,
so this would be the corresponding basic feasible solution; they are distinct basic feasible
solutions, and hence they are two extreme points to this system.
So, you see by the non-negativity constraints on the variables are necessary for the theorem
to be valid; the theorem that I was still talking to you about correspondence between
a basic feasible solutions of an extreme point. So, here you have a..., because of non-negativity
of the variables, you could then compute find out two basic feasible solutions and hence
there are two extreme points, so this was the thing.
Now, another word of caution that is needed here is that, the correspondence is not 1
1, that means, the theorem or the lemma that I wrote in the beginning that by proof to
you showing correspondence between basic feasible solutions and extreme points; so, here you
see if degenerate basic feasible solution is there, then you can have more than one
bases corresponding to this same degenerate basic feasible solution. So, to think that
you have..., and therefore there may be more than one bases which is giving you the same
basic feasible solution, and hence the same extreme point right; therefore, this is I
want to..., I thought I will through an example I would show you this.
So, look at this example; and here you have five variables all are non-negative, not non-negativity
constraints are there; now, I wrote out the this thing column here, and I choose the basis
B 1 as A 1, A 2, and A 3 are may be I did the row operations here, and finally I reduce
the matrix this form; so, you see, you can read from here, I could have made 0s here
also, but that would not make a difference to the basic visible solution, because this
is 0. So, when I subtract this from here, and twice
this from here, this these numbers will not change, so that is why I did not do that arithmetic;
so, here, we can read from here anyway; so, this is a set of linearly independent columns,
three independent columns, and so they form a basis, and the corresponding basic feasible
solution is 5 1 0 0 0, and so there is an extreme point also; corresponding extreme
point and r 5 which will be given by this; but then you see from here from this tableau
that if I can remove a drop a three from my basis and then I can take A 5, because A 4
again is linearly dependent on A 1 and A 2, because there is A 0 here.
So, therefore, A 5 is the other column, which together with A 1 and A 2 will make a linearly
independent set, and so this forms a basis; and see, because there is a 0 here, so even
when you pivot on this, you see if you pivot on this, you will divide by minus 2, so it
becomes a 1, this will not change, and again when you make 0s here, these numbers will
also not change. So, trying show you that, when you have a
degenerate basic feasible solution, there is not a unique basis which corresponds to
the basic feasible solution; therefore, B 1 and B 2 give you the same basic feasible
solution, and hence the extreme point will also not change, because your basic feasible
solution has not change, the corresponding basis have changed.
So, in the lemma I have said that corresponding to a basic feasible solution, there will be
extreme point, but then when you talk of a basic feasible solution you have a concept
of a basis corresponding to it; so, essentially what I am saying here is that, they can be
more than one basis corresponding to the same extreme point under degenerousy; so, the correspondence
will be 1 1 only if you have non-degenerate basic feasible solution, and they corresponding
extreme point will also be non-degenerate, and therefore that correspondence will be
1 1.
So, essentially, I had told you that there is a upper bound on the this would be n c
m, out of that means, if you if you rank of the matrix A is m, then you choose m columns
for forming a basis, and so the number of a basic feasible solutions that you have the
number bound will be n c m, because out of the n columns you want to choose m columns
and hopefully I mean if they are linearly independent then of course they form a basis;
but then again having a basis may not always lead you to a basic feasible solution, I have
gone through all this with you; but in any case, this is an upper bound on the number
of basic feasible solution or the number of basis that you can have.
And therefore, this is also an upper bound, and the number of basic feasible solutions
you can have; and therefore, we also said that this is also a upper bound and the number
of extreme points that you can have; so, this is the kind of count, and I was just wanted
to caution you that the correspondence we have to understand what we mean by this correspondence;
and essentially, I am trying to say that under degenerousy they can be more than one basis
which will correspond to the same extreme point.