Tip:
Highlight text to annotate it
X
Let me recall from the last lecture I had defined a linear programming problem in its
standard form, and we said that it will be minimize c transpose x subject to A x equal
to b x greater than or equal to 0, and then, I told, I discussed situations under which,
this system of equations will have a solution. So, we said that the rank of matrix A should
be equal to rank of the augmented matrix A b and I add another column to the matrix A,
that become the augmented matrix. The two ranks must be the same, and it is very easy
to understand why this condition is required, because when we say that rank here is the
same as this, that means, b can be expressed as a linear combination of the columns of
A and this is what we are looking for. Here, when we say that this system has a solution,
then you can rewrite the system as if I write, if I address the columns of A by A 1. So,
this will be A 1 x 1 A 2 x 2, this is a second column and so on. So, this will be A n x n
is equal to b. So, we are looking for numbers scalars x 1
x 2 x n so that this linear combination of the columns of A this equal to your right
hand side vector b. This is what we mean when we say that the system has a solution, and
then, we will also want to not only have a solution to this system, but we want to have
a solution where all the components, that is, x 1 x 2 x n or all non-negative. So, that
will be my feasible solution to the constraints for this linear programming problem in its
standard form. Now, let me further develop some more theory
here so that we can then describe the simplex algorithm analyze its complexity and so on.
So, here, I will make the assumptions. So, let me just say that assumption, I will make
this assumption and, that is, rank A is equal to m; that means its full row rank. I am assuming
that a matrix A is m by n. So, by saying that rank a is m, I am assuming that all the rows
of the matrix A are linearly independent, and later on, we will see that this condition
would not be necessary of the time, because the algorithm that we develop for solving
this linear programming problem, we will also be able to detect the redundant constraints;
that means if some rows are not linearly, if all the rows are not linearly independent,
it will be able to detect the dependent rows, and then, we can drop those rows from the
matrix A, and so, what we get after dropping out the redundant rows would be again matrix
which is fully row rank. The reduce matrix will again have all the
rows which are linearly independent. So, therefore, this is not loss of generality. We will see
that the algorithm will be able to detect whether the matrix A is full rank or not and
then drop out the constraints which are not really needed.
So, I have start with the rank A equal to m, and now, let me make a few definitions.
So, here, I am going to define a basic solution first, a basic solution, and this to, to,
system of equations, a basic solution we always refer to a system of equations. So, this is
my system of equations, and I have assume that rank A is m. So, what we will do is choose
B a collection of columns of A which are linearly independent and m in number. Since I am assuming
that a rank is m, the maximum number of linearly independent columns or rows that A can have
is m. So, let me choose some, there may be more
than one set of m columns of a which are linearly independent let me choose one set and I call
it B. B is called a basis and what we mean by that is since all the other columns of A are dependent
on the columns of B. Therefore, I can express any other columns which is not in b as a linear,
as a columns of b. So, this is what I mean when we say that B is called a basis. So,
I can use the term column space of A some of you who are familiar with this concept.
When we say that if you take a subspace which is generated by all the columns of A, then
since the rank of the or the dimension of that subspaces m and B is a set of m linearly
independent columns. Therefore, every other column of A is expressible as a linear combination
of the columns of B; B is called a basis. Now, put all x j equal to 0 for which A j
does not belong to B. So, since we start with the assumption, that A is an m by n matrix.
So, there are n columns, and as I mention in my earlier lecture, that we will always
we dealing with under determine systems. So, n is much larger than m. Therefore, here,
since we are taking only m columns, so, the reaming n minus m columns are not present
in B and we put all the variables x j corresponding to A j which are not in B equal to 0. Then,
I have reduced system. So, the reduced system is B x B equal to b.
So, let me say that, see, here, I have put x j equal to 0 corresponding to the A j which
is not in B. So then, the remaining variables I will call them as x B, because they correspond
to this basis B, and so, I have this reduce system; this is a square system and this is
because the matrix B is non-singular. It is a collection of linearly independent columns.
So, system is this and determinant B is not 0. This implies that x B equal to B inverse
b is the unique solution to A x equal to b where we have put certain variables equal to 0, because this system
is equal to this system, and since here my matrix B has determinant non-zero, non-singular,
it has an inverse. Therefore, x B equal to B inverse b is the unique solution.
Now, here, when I mention this, see you may have a matrix A, where you have these columns,
and I have just, I have picked up may be say some separate column which are not really
1 2 3 and so on. So, it could be any number, and therefore, the, when I pick up this column,
the corresponding variable is x 1; when I pick up this column, the corresponding variable
is x 3 and so on. So, therefore, x b will always be the set of variables which corresponds
to the column, which makes up my basis matrix b.
So, therefore, this is now a unique solution, and I call this a basic solution; this is
a basic solution, and in case, if all components of x B are non-negative, x B is a basic feasible
solution. So, this is x B is the basic feasible solution and that is what we are looking for,
because we want solutions to the system A x equal to b which are non-negative, and here,
I have taken a particular kind of a solution to this system A x equal to b x non-negative,
where I have put certain variables equal to 0. I am solving a reduce system. I get another
a feasible solution but I call it a basic feasible solution.
One this thing, when I am talking of the numbering, say for example, if you take this column 1
0 0 0 1 0 0 3 1 0 1 1 1 0 0 0 0 1 0 0, I have this set of, there may be there are four constraints
and the number of variables may be whatever. This is my B; this is a basis matrix. What
I want to show you that the ordering also matters here in the sense that when I want
to reduce this to, you see, I can, by row operations, I can reduce this to the form
0 0 0 1. Now, you are all familiar with elementary row operations, and when you solving system
of equations, the elementary row operations do not change the set of solutions to the
system of equations. So, I can do the row operations here and I
will get this matrix 0 0 1 0 1 0 0 0 and 0 1 0 0. So, by elementary row operation, so,
therefore, what I want to point out here is that this is actually the first basic variable
of the first basic column and the corresponding variable. So, if these variables are, if these
columns are A 2 A 3 A 4 A 5, suppose I selected these columns out of whatever number of columns
the matrix a had, and this is my basis. This can be check that this is the determinant
of this matrix is non-zero. Then, when I reduce it to this form, see after all to solve this
system of equations, I would have to do row operations, and once I reduce it to this form,
I can immediately read my solution, because there no other variables present here. So,
therefore, this is equal to whatever the right hand side number; this will be equal to the
second one and so on. So, what I want to says that even though I
write my B as whatever the columns A 2 A 3 A 4 A 5, this corresponds to the first basis
column; this corresponds to the second basic column and this to the third and this to the
fourth.
So, this will also be needed a times. I just want to it, because if the matter of notation,
I want to you to be familiar with this, and then, let me now begin with take up an example
and go through all the concepts that we have so far introduced. So, I begin with how you
can get different kinds of basic feasible solutions and maybe I will just point out
one more thing here and, that is, it is possible. You see, I obtain a basic feasible solution
by putting the variables which do not correspond to the columns in B to 0. So, when I say that
x j is 0, where A j does not belong to B, then x j is
called a non-basic variables, and your x B, the components of x B are the basic variables.
This is all corresponding to the fix basis. I start with, I select a basis, then I get
a basis feasible solution. The variables that I have put to 0 are called non-basic variables,
and the basic variables are the ones which corresponds to my, this is basic variable
and this non-basic variable. It is possible, see, I put these two 0.
Now, it is possible that some x B i may be 0. Therefore, you may have more than n minus
m variables equal to 0 in a basic feasible solution, but there will always be at least
n minus m zeros in a basic feasible solution, and again, here, as I told you that if the
system A x equal to b, you can write as A 1 x 1 plus A 2 x 2 plus A n x n is equal to
b. So, if I in a, this expressions in this is
just summing up. If I renumber this column and I also renumber the variable correspondingly,
then the system does not change; I mean this system of equations will not change if I renumber
my columns and the corresponding variables also. Therefore, just for is of notation,
I will refer to a basic feasible solution. So, this will be my basic feasible solution,
where these refer to the basic variables and these refer to the non-basic variables. So,
it helps to have a notation specified.
Now, let me just start with this example and try to cover up whatever concepts we have
introduced. So, this is minimize z equal to minus x 1 minus 3 x 2 subject to the constraints
x 1 plus x 2 less than or equal to 6; minus x 1 plus 2 x 2 less than or equal to 8; x
1 x 2 greater than or equal to 0. So, as I told you, this is minus minimization of this
which I can write as maximize. See, here, if you want to write the same z, then this
is maximize minus z which will become x 1 plus 3 x 2.
So, I had in my first lecture told you that we can refer to a linear programming problem
as a minimization problem or a maximization problem, does not matter, because it is a
question of just multiplying the objective function by minus sign, and now, here, I need
to add slack variables, because all the constraints are less than or equal to So, this can be
to the standard. I am reducing this problem to this standard form. So, that gives me x
1 plus x 2 plus x 3 equal to 6; so, I will drop the s suffix, because we treat them anyway
as regular variables with the understanding that the objective function value of the slack
variables will be 0. So, I will write them as a x 3, and then, the second constraint
is minus x 1 plus 2 x 2 x 4 is equal to 8, and then, you have all the variables x 1 x
2 x 3 x 4. This is the standard form and it always it is easier to handle equality constraints.
So, now, let us just choose some basis here. Say for example, I choose my B 1 to be 1 minus
1 1 2, so, I choose the first two columns - first and the second column, and I guide,
so, if this is the determinant, you can see is non-zero. Therefore, this lead to me a
basic solution. So, here, I will solve the reduce system. So, corresponding to this basis,
I will solve the system x 1 plus x 2 equal to 6 and minus x 1 plus 2 x 2 equal to 8.
So, if you add up the two equations, you get this implies that 3 x 2 is 14. Therefore,
x 2 is 14 by 3 and that gives me x 1 as 6 minus 14 by 3 which is 4 by 3 18 4 by 3.
So, therefore, if you want to write the basic feasible solution and it is full form. So,
this is because both the components are non-negative, this is a basic feasible solution and my basic
feasible solution corresponding to this basis is 4 by 3 14 by 3 0 0, because I choose the
first two columns. Therefore, x 3 and x 4 now become non-basic variables; these are
the basic variables. So, this is one equation.
If I choose another basis, for example, B 2 as 1 2 0 1, now, this time, I have chosen
the columns was the second column here and the fourth column. So, this is my basis with
corresponding reduce system will be what? So, I will put x 1 and x 3 to 0. So, that
will give me x 2 equal to 6. The first constraint will reduce to x 1 and x 3 are 0. So, x 2
is 6, and then, I have 2 x 2 plus x 4 is equal to 8. So, if x 2 is 6, this implies that x
4 will be minus 4 which is less than 0. So, this is a basic solution; that means the solution
that have got is x 1 is 0; x 2 is 6; x 3 is 0; x 4 is minus 4 is the basic solution but not a basic feasible solution where you
see the difference.
So, therefore, given say for example, here and this is what I will be coming to next
that if you have the system of equations, you have four variables, two equation. So,
therefore, the possible number of bases that you can choose; that means it is an upper
boundary, because it is not necessary that any two columns here would be linearly independent,
but the upper bound on the number of basic solutions will be what? The upper bound would
be here 4 c 2; that means, out of four columns, I have been choose two. So, this 4 c 2 would
be the upper bound on the number of basic solutions I can have for this system.
Now, let me also demonstrate the situation. Then you can have degenerate basic feasible
solutions. Hence, what we mean by, because these are terms which will be we using very
often. So, let me just system of inequalities. Consider these systems of inequalities, system
of inequalities are assuming you. This is x 1 plus x 2 plus less than or equal to 6
x 2 less than or equal to 3 x 1 plus 2 x 2 less than or equal to 9 and x 1 x 2 greater
than or equal to 0. So, again, we it reduce slack variables and
this will by introducing, we obtained. So, it will be the system of equalities is x 1
plus x 2 plus x 3 is equal to 6; x 2 plus x 4 is equal to 3; x 1 plus 2 x 2 plus x 5
is equal to 9, and we have the non-negativity constraints x 1 x 2 x 3 x 4 x 5. So, choose
here a basis. So, you want to just show you that in case, you, let me just choose my b
to be, so, the rank here is 3, yes, may be you can answer that question yourself, because
I have three columns here which form the identity, which form the columns of the identity matrix.
So, the rank of this matrix is 3. Therefore, I will choose a basis of size three; which
means I have I want to choose pickup three columns form here which are linearly independent,
and just for ready reference, because I have it written down here. You can chose by b to
b 1 0 1 1 1 2 and take this is as 0 1 0. So, if I choose this as my basis, that means this
is first column; this is second column; this is A 1 A 2 and this is fourth column. So,
that means, I will put x 3 equal to x 5 equal to 0 and solve the reduce system.
So, my reduce system would be x 3 and x 5 was 0. So, this is x 1 plus x 2 equal to 6.
Then x 2 plus x 4 is equal to 3 and x 1 plus 2 x 2 is equal to 9, because x 5 is 0 x 3
is 0. Now, if you subtract this from here, x 1 will cancel out and this will give you.
So, these two together will give you x 2 is equal to 3; so, x 2 this implies that x 4
is 0 and x 1 is 3. You see one of the basic variables is 0, and so, my basic feasible
solution is 3 3 0 0 0. So, only two of the variables are positive, whereas a basic feasible
solution is supposed to have at least. So, 3 x 3 and x 5 they have to be 0, but one of
the basic variables is also become 0.
And here, again, another point which has to be noticed is that since a solution is degenerate,
they can be more than one basis which will correspond to the same degenerate basic feasible
solution, and this will also be very important later on, because when we want to talk about
how the complexity of the simplex algorithm, which is the algorithm that we are going to
design for solving a linear programming problem. So then, with, these concepts are very important
and I can show you, say for example, if you take your B to be, to take the basis to be
1 0 1, 1 1 2 and 1 0 0; that means, now I have selected the columns as A 1 A 2 and A
3, and if you quickly look at this thing here, because then I am putting x 4 and x 5 as 0.
A 1 A 2 A 3 is the set of basis columns. So then, this will immediately give me x 2 equal
to 3. Once I have x 2 equal to 3, since this is 0, I will get x 1 as 3 and then x 3 will
be 0.
So, it just that in the earlier case, because my basis contained A 4 as a basic column.
Therefore, this was the basic variable and it was 0. This was the non-basic column. So,
it is only the status of the variable has change, because my basis has change but the
solution remains the same. So, B also, this basis also corresponds to the degenerate basic
feasible solution 3 3 0 0 0. So, this is a another thing to be noted, whereas for a non-degenerate
basic feasible solution, for a non-degenerate basic feasible solution means that only, so,
maybe I can write it down here. For a non-degenerate basic feasible solution, the number of 0 variables
is exactly n minus m. And remember, here, we are starting with the
assumption that the rank of the matrix is m, and therefore, everything is reference
to that, and when the retardant constraints get dropped, the m will change and in everything
will follow exactly. So, for a non-degenerate basic feasible solution, the number of zero
variables is exactly n minus m, and both degenerate and non-degenerate basic feasible solutions
play very important role when we analyze the algorithm.
Now, as I mentioned earlier, you see if you look at linear programming problem, and we
want to, here, we are looking at the basic feasible solutions and that maybe in the next
lecture will be clear why we are putting so much stress on the basic feasible solutions
that look on, but before I go to that, let me just show you, you can also, even though,
see we can put a bound on the number of an upper bound. So, an upper bound on the number
of basic feasible solutions and that is very simple as I pointed out to you earlier, because
out of n columns, we want to select m linearly independent columns. Therefore, the possible basis can be n choose m or n combination of
the objects or n columns. You want to select m and the number of ways you can do it is
n C m. So, therefore, your basic solution, the number of basic solutions is less than
or equal to n C m, because for every basis leads to a basic feasible solution, and of
course, as we have seen that more than one basis may lead to the same basic feasible
solution, but even we are computing the upper bound, we just want to say that may be the
case is there that, every bases leads to different basic feasible solutions.
So, whatever it is, the total number cannot exceed n C m and this is number of basic solutions.
Therefore, number of basic feasible solutions is also bounded by n C m, because every basic
solution may not be a basic feasible solution. So, this is the number that you are obtain,
and so, now, the idea is that if you can say that your search for a optimal solution for
a linear programming problem can be limited to a basic feasible solution. Then, you see,
what we are saying is that solving a linear programming problem reduces to actually examining
all possible basic feasible solutions and then choosing the best, but let me let me
just warn you that even though this number is finite, this can be very big and it can
take years to solve. Say for example, just to given idea how large this number can be
and let me also tell you that people have designed linear programming problems for which
this bound can be attained; that means every set of m linearly independent columns is a
leads to a basic feasible solution, and therefore, this number can be attained.
Now, it, in case n is 100 and let say m is 40, the number 100 C 40 is of order 10 raise
to 28, and this with the fastest machine, we take years to actually examine all possible
basic feasible solutions. So, you will compute the value of the objective function C transpose
x, for example, at each of these basic feasible solutions and then select the one which is
the smallest in case of minimization problem, but then, this is not a small number; this
can become very big number, and therefore, it can take a lot of time to compare it. Therefore,
this is not certainly a very satisfactory way of solving a linear programming problem
even though the number of feasible solutions is the finite, and therefore, algorithm has
to be design and this is what we will a do now here.
So, now, let me make a few more definitions. We will say that feasible region I will just
it makes the notation simples of feasible region. We say that F will be all x belonging
to R n such that A x equal to b x greater than 0. So, I will always refer to now, because
I will always be referring to the standard form of the linear programming problem, and
when I refer to F, that means it is all feasible solutions to the standard version of the linear
programming problem. Simple lemma: if F is non-empty, if F is non-empty,
then it has a basic feasible solution. Let me explain what we are saying is that if the
system, remember, I told you the condition when the system will have a solution, and
then, of course, that solution should be also having all components non-negative; that would
be a feasible solution. So, when I say f is non-empty, what I mean is that I have an x
which satisfies both the constraints, both the set of constraint. Then, what we are saying
is that because basic feasible solutions are special kind of feasible solutions. So, it
is, if I am going to deal with basic feasible solutions, I have to be sure that if my region,
if my feasible set, the set of feasible solution is non-empty, then it must also have a basic
feasible solution, because I cannot be talking in the air; I must know that basic feasible
solutions exist.
So, this is the whole idea and let me give you proof here. This, now, because start becoming
technical and we have to be careful. So, the lemma F, if F is non-empty, then F has a basic
feasible solution. So, let me give you the proof, and as I explain just two minutes ago
that what we mean is that there is a x here, which satisfies that constraints A x equal
to b and all components non-negative. Then, I want to demonstrate to you that there must
be a basic feasible solution. So, since F is non-empty, x belongs to F. Now, define, let I x be the
index set of all those x j which are positive. So, I have a feasible solution in F because
F is non-empty. Let me just collect the all the for which the corresponding x j is positive.
Now, see, two things can happen - either the columns A j such that j belongs to I x. So,
either the columns these are linearly independent or linearly dependent, took their two possibilities.
The columns which correspond to the positive components of the feasible solution in F are
either linearly independent or linearly dependent.
Now, this is another phenomena that I want to explain to you, that is, if the set A j
such that j belongs to I x is linearly independent, then it can be augmented by adding columns
from A such that the new set, that the augmented set is linearly independent. Those of you who
have some background of linear algebra know this, that if you have a set of linearly independent
columns, and if you know that, the certain number of the basis contains the number basis
columns can be more than what the columns here are. When you can always augment a set
of linearly independent columns by some more columns so that the new set is forming a basis
and that is what so we do that.
And the thing is that when I augmented set, my solution remains the same, because my solution
was A x equal to b x greater than or equal to 0. So, I x gave me the variables which
are positive. So, here, when I augment the set of columns here to form a basis, then
the corresponding variables are 0, but I can now say, because after augmenting, x becomes
a solution; x is a basic feasible solution. So then, this is implies that x is a basic
feasible solution. I will try to put it again in more few words. What we are saying is that
our requirement for calling a basic feasible solution is that it should correspond to,
that means the non-zero components must correspond to the columns which are linearly independent
and they form a basis. Now, here, I have started with the solution
and I know that certain columns are there which correspond to the positive components
of that solution and which are linearly independent, but this number is not equal to the number
of columns, that should be there in a basis. So, I augment, I augment, my solution does
not change, it remains the same, because the augmented columns the corresponding variable
here is 0. So, the same solution is valid. It just that I now say that x is a basic feasible.
I am allowed to claim that x is a basic feasible solution.
So then, the lemma gets proved in case this set is linearly independent. Now, I have to
handle the case when this is set is not linearly independent. So, the second cases in if the
set A j such that j belongs to I x is linearly dependent, so, linearly dependent means that
there is a linear combination of the columns A j which is equal to 0. If this is re read,
and this implies there exist scalars y j j belonging to I x such that sigma y j A j j
belonging to I x is 0. If is set of columns is linearly dependent, you can always finds
scalars not all zero such that this set is this linear combinations equal to 0. I also
have and the other equation, because the x is a solution here. So, I also have that a
summation x j A j j belonging to I x is equal to b. So, I have these two equations. So,
the columns Aa j are the same columns. Now, multiply this by theta and add to this.
So, this gives me that summation x j plus theta y j A j j belonging to I x this equal
to b, because there is the right hand side is 0. So, this what I get, and you see that
because the remaining components are 0, this again that means I have been able to construct
another solution to my system A x equal to b. I am not calling it feasible, because I
am not sure depending on what my theta and y js are, whether these components are non-negative,
but at least I have a solution to this system of equations, and then I want to, so, here,
if you see that x j is a component of a feasible solution, so, this is a non-negative theta.
I can choose to be positive; x j's are non-negative. So, now, if y j's are also non-negative, if
y j's are non-negative, then this is a feasible solution. If now two cases are possible - suppose
all y js are greater than or equal to 0, then I do not have to, so, what I will do is y
j's are all non-negative. In this equation, it does not matter. Then multiply the, let
me number this equation as, let say 1. Then, consider multiply 1 by minus i.
So then, I will get summation minus y j A j j belonging to I x equal to 0, because it
is a right hand side 0. It does not matter whether I multiply the whole equation by minus
sign or So, in that case, what will happen to my equation? So then, in that case, I will
get the equation as summation x j minus theta y j A j is equal to b j belonging to i x.
So, in this case, I could have said it here. The possibility was that I need not have,
what I am saying is that in case all y j's are positive or non-negative, then I can multiply
by minus sign and get the y j's as negative.
So, in any case, I need the bother about multiplying by minus sign, because so, in other words,
I can say that there will always be at least 1 y j which is negative, because if there
is no none y j which is negative, then I can multiply the whole equation or minus sign.
It does not matter. Let just take this case. So, now, you see that if y j is positive now,
because have a minus sign, then it is possible that this component can become negative and
I am trying to a matter basic feasible solution. I am trying to construct a basic feasible
solution from the given feasible solution. So, what I will do is - choose theta equal
to minimum of, see, remember, I want this to be non-negative. So, I will choose when
I write say that this is greater than or equal to zero, I will get theta as minimum of x
j upon y j y j is greater than 0. So, among for all y j's which are positive, I will take
this ratio and then choose theta is the minimum, because that theta is greater than this number,
then some expression here can become negative. Therefore, if I choose my theta to with this,
and at least since we have said that at least there is one y j which is positive, because
all y js cannot be 0. Remember, this set is linearly dependent. So, I told you that the
scalars y j non-zero exist so that this linear combination is 0. So, that is not possible.
So, at least some y j is there which is positive, and so, this ratio exists and theta can be
chosen like this. In that case, let say that this is equal to x k upon y k
So, for some k, this happens. Then, the corresponding x k minus theta y k is 0 and all x j minus
theta y j are non-negative. So, I have been able to construct a feasible solution. From
the given feasible solution x, in which, at least one component has become 0; that means
the new feasible solution that I have has one component less than that the new feasible
solution has one component more which is 0, one component more which is 0.
So, the new solution now you will find out. So, let me call it. What do you want to call
it? So, x prime is the new feasible solution. Now, if i x prime is such that the corresponding
set of columns is linearly independent, then I have a basic feasible solution as I explain
to you that once I get for the new solution, I have the index set of positive components.
The corresponding columns are linearly independent. Then, I can always augment that set two a
basis, and therefore, this will constitute a basic feasible solution.
In case the columns here are not linearly independent, then I will continue with the
same process. Reduce the number of positive components to with they will be at least one
component which will become 0, and this process can go until I end up with set of linearly
independent columns corresponding to the positive components of the feasible solution, that
I have finally get, and then, that will be a basic feasible solution.
So, by this method of... So, actually, I like this proof, because it shows you actually
how you can lead from any feasible solution to a basic feasible solution. So, this will
be very help full in designing the algorithm and in trying to analyze it. So, as usual
let me give you an example here again. Let me just show you actually how we go about
doing this. Example: this is x 1 plus x 2 plus x 3 is equal to 6. So, I will take a
system of equations start with the feasible solution, and then, show you how the reduction
process works to get to a basic feasible solution. So, this will be x 2 plus x 4 equal to 3.
This is the same system that we took earlier to demonstrate to you degenerate basic feasible
solutions x 1 plus 2 x 2 plus x 5 is equal to 9 and your x j greater than or equal to
0 for all j. So, this is your system, and now, let me start with the feasible solution
here.
So, consider the feasible solution 1, 3, 2, 0, 2. Then, quickly verify that this satisfies
of these constraints as a quality.
So, the columns... So, you are your I x here is 1, 2, 3 and 5. This is your index set corresponding
to, that means these set of columns, and obviously, a number columns here is 4, and the rank of
the matrix this, this is a 3 by 5 matrix. So, the rank cannot be more than 3, and it
is actually three because you have these three linearly independent columns here. So, therefore,
the columns are linearly dependent; I x is this. Since cardinality of I x is 4 which
is more than 3, the corresponding columns are linearly dependent.
So, let us find the y j's, the scalars which will be used in the linear combination to
show that this is 0, and again, just by inspection, you can see that A 1 plus 0 into A 2 minus
A 3 minus A 5 is 0. So, this is the combination of the columns linear combinations; that means
my y 1 is 1; y 2 is 0; y 3 is minus 1 and y 5 is minus 1, and also, I have this equation
is, since that is the equation, so, I have A 1 plus 3 A 2 plus 2 A 3 plus 0 A 4 plus
2 A 5 is equal to your right hand side which is 6 3 and 9.
So, we multiply this by theta; add to this equation to obtain this will be 1 plus theta
a 1 plus theta A 1 plus 3 A 2 this is 0 here plus 2 minus theta A 3. This is 0; I do not
need the A 4 plus 2 minus theta A 5, and this is also equal to your right hand side by 6
3 9, and remember, so, we had to look at the negative y's and take this ratio number. So,
in this case, because there is a minus sign, so, I took the positive y j. Now, here, whatever
it is, because you see that a theta positive does not bother this variable, this component
because this will be remain non-negative. Here, there is no theta. So, it is only the
value of theta here which can, if becomes more than 2 for example, this particular component
will become negative and we are looking for a feasible solution.
So, here, you can immediately see that theta has to be less than or equal to 2 but I will
choose theta equal to 2 since I want to reduce the number of positive components from 4 to
3 or 2 whatever is possible. So, I choose theta equal to 2 which is in this case minimum,
because both the values are 2, The theta one corresponding to negative y here or you can
treat y as 1 here or as minus 1 does not matter, it is a matter of notation. So, any case,
theta has to be 2. If I choose theta to be 2, the new reduced solution is 3 3 0 0 0 0.
So, in this case, what happened is that the two components became 0. My choice of theta
was such, but at least one will always become 0, two became 0, and therefore, I got a, so,
this is a basic feasible solution but it is degenerate. So, the, in a product has the
distribute property also by which why we mean that if you take the dot product between the
vector x and c y plus z - where c is a any real number, then you can, when you, you can
open up the brackets and you will have c x dot y bar plus x dot plus z bar and this is
two for all x y z in R n and all see in R.
So, the distributive property is there. Then, with the help of the inner product, we can
defined the norm or the length of a vector and it is done by taking the inner product
of the vector by itself and then the under root. So, the norm or the length of vector
x is given by this number and you can show immediately, because you have real numbers
sum of squares of real numbers if it is 0, then each number must be 0; so, that means
norm x 0 if and only if this stands for, if and only if short form i f f, if and only
if x bar is 0. If the vector is 0, the norm is 0, and if the norm is 0, the vector must
be 0. Now, you can easily show using this definition
that if you take the norm of the vector c x c is a real number, then this come out as
absolute value of c; that means the positive part, because remember, I should have said
here also that this is greater than or equal to 0, because you talking of real numbers
and then taking the under root. So, that must be non-negative number. So, here, this has
to be absolute value of c times the norm of x.
And then, this is the triangle in equality which also you can sit down and proof by yourself
that norm of x plus y will be less than or equal to norm x plus norm y; that means if
you take a triangle, if you take two directions with the vectors x and y and length norm of
x and norm of y, then you can show that the third side must be less than or equal to the
sum of the two sides, the length of the third side. Then, we can also have a concept of
an angle here, and that all I need to now show you is that for a linear programming
problem, it is more than enough to just worry about or just bother with the basic feasible
solutions and try to find the best among all the basic feasible solutions.