Tip:
Highlight text to annotate it
X
Good morning and welcome to this the lecture number 11 of the course Water Resource Systems
Modeling Techniques and Analysis. Now, we have been discussing the simplex algorithm
and specifically in the previous lecture, I discussed about how we solve a problem,
L P problem with simplex method. A simple problem we took, where the constraints were
of the type less than or equal to, and then we added corresponding to each of the constraints,
we added one slack variable to make the problem in the standard form, to express the problem
in the standard form and then we could find an initial basic feasible solution and therefore,
we progressed from iteration to iteration and then, arrived at the optimal solution.
So, if you recall the simplex algorithm, which is the algebraic approach for L P solutions,
we first express the problem in a standard form.
So, given an L P problem, that is linear programming problem, we express it in a standard form,
what do I mean by standard form? A standard form that we are adapting in this course is
a standard form consists of the objective function expressed as maximization type. So,
the objective function is maximization type, all the constraints are of equality type and
all the variables, decision variables x 1 x 2 etcetera x n are all non-negative, so
the standard form consists of such a structure of the L P problem. We know how to express
a given problem in a standard form, if your objective function is minimization type, you
express a objective function as maximization by taking the negative of that, recall that
maximize f of x is also equal to minimize minus f of x.
Similarly, if your constraints are of the type less than or equal to you add a slack
variable to each of such constraints to make them equality constraints, if they are of
greater than or equal to you deduct a surplus variable to make them equality constraints,
and if you have unrestricted variables, that is variables that are unrestricted in sign,
then you express each of such unrestricted variables as difference of two non-negative
variables to make them unrestricted. Therefore, given L P problem we should able to express
in a standard form. Then, we went onto formulate the algebraic
method of solution, we start with an initial basic feasible solution, recall that a basic
solution is a solution, which is obtained by setting n minus m variables to 0 and then
obtaining the solutions for the remaining m variables, where m is the number of constraints
and n is a number of variables. After you have expressed the problem in the standard
form, because you would have added slack variables surplus variables and so on, after you have
expressed it in the standard form, the number of constraints is m and the number of variables
will be n. And you set n minus m variables to 0 and solve
for the remaining m variables and these m variables for which you obtain the solution
are called as the basic variables. And the n minus 1 variable, which you initiate or
which you set to 0 are called as the non-basic variables. So, you start with an initial basic
feasible solution and then from iteration to iteration, every time identifying whether,
the solution is optimal, if the solution is not optimal, you identify exactly one entering
variable, which will enter the basis. And then, I will identify exactly one exiting
or departing variable, which will depart the variable to make way for the entering variable.
So, every time you change the basis for exactly replacing one variable by replacing exactly
one variable, one variable comes in one variable goes out, like this from iteration to iteration
you proceed until you hit the optimal solution. How do we decide whether the solution is optimal?
You look at the coefficients in the Z-row or the zeroth row, if all the coefficients
are non negative, it means, that the solution is optimal, that optimal solution cannot be
further improved and therefore, you terminate the solution at that point.
So, this is what we did in the simplex algorithm, so we solved a simple problem to demonstrate,
how the simplex algorithm works. Then, towards the end of the previous lecture, I also introduce
the concept of multiple solutions in the simplex algorithm, we have seen of course, what are
the what are the multiple solutions in the graphical method, how to capture the multiple
solutions and so on and what are the implications of the multiple solutions.
But in the simplex algorithm, in the final tableau as I just mention, the optimality
criteria is that all the coefficients in the Z-row should be non-negative. Let us say that,
one of the currently non basic variables has a coefficient of 0 there, it means that that
variable can be brought into the basis, it was the non basic variable, but it has the
0 coefficient in the zeroth row or the Z-row and that can be brought into the basis, without
gaining the solutions, which means you get another alternate solution; optimal another
alternate optimal solution, which means that there are multiple solutions possible to this
and if you have two solutions there are infinite number of solutions. We will see an example
of multiple solutions, but before that some features of the final tableau you must be
aware of.
Recall that, we solve this example maximize Z is equal to 3x 1 plus 5x 2 subject to x1
less than or equal to 4, 2x 2 less than or equal to 12, 3x 1 plus 2x 2 less than or equal
to 18, x 1 greater than or equal to 0, x 2 greater than or equal to 0. This is the solution
this is the problem for which we obtained solution, through simplex method in the previous
lecture. And this is the final tableau, that is the optimal solution that is the tableau
corresponding to the optimal solution. Now, x1 x2 x3 are in the basis, see here the
coefficients of these basic variables x1 x2 x3 in the zeroth row or the Z-row are all
0. This is in general true that means, all the basic variables will have a coefficient
of 0 in the Z-row not only in the final solution, but also in any solution in any intermediate
iteration also, the coefficients of the basic variables will always be 0 in the Z-row. The
solution is write to the all of solution itself will be write as Z is equal to 36, the b i
column columns gives the solution, Z is equal to 36, x3 is equal to 2, x2 is equal to 6
and x1 is equal to 2. So, this is how we obtain the solution, this
is how we read the solution from the final simplex tableau. Now, x4 and x5 are the non
basic variables in the final tableau, when the optimality criteria are met, the non basic
variables are x4 and x5. See here in this Z row, the optimality criterion is met, because
these coefficients are all non-negative. And therefore, we say that the solution can not
be further improved and therefore, we will terminate the competitions at this point,
x4 and x5 are the non basic variables, they have non-negative coefficients in the Z row
indicating that, if you bring anyone of them into the basis, then the Z value will decreased,
it will not increased for the maximization problem, it will decrease and therefore, that
is the penalty if you bring any of the non basic variables into the basis here.
Let us say that, one of these non basic variables had a coefficient of 0 in the final solution
in that optimal solution, let us say instead of 3 by 2 this was 0, what does that mean?
That means, that this is a non basic variable, but this can be brought into the basis by
identifying one of the departing variables, without changing the optimal value of the
objective function, which in this case is Z is equal to 36 and that is how we identify
the multiple solutions.
We will see an example now, for the multiple solutions. Let us say, you look at this example,
maximize Z is equal to 40x 1 plus 100x 2, subject to 10x 1 plus 5x 2 less than or equal
to 2500, that is 2500, 4x 1 plus 10x 2 less than equal to 2000, 2x 1 plus 3x 2 less than
equal to 900. I encourage you to solve this problem by the graphical method, there are
only two variables, so the you should be able to solve it by graphical method, you do solve
it by graphical method and then look, at what kind of solutions you get whether there are
multiple solutions possible and so on, and of course, these are the non-negative.
Remember there is an objective function, which is the linear function of that is an variable
x1 and x2, there are constraints set of constraints all of which are linear constraints of x1
and x2 and there is a non-negativity of decision variables. We first express this in the standard
form, to express this in the standard form first look at the objective function; objective
function must be of maximization type in the standard form that we are using.
So, in this case it is in fact, in the standard form, that objective function is in the standard
form, so will not touch the objective function. Look at all these constraints, they are all
of less than or equal to type, anytime you have a less than or equal to type, you add
a slack variable, so I add a slack variable here, I add a slack variable here, slack variable
here, and the decision variables are anyway non-negative therefore, we keep them as it
is. So, how do we write it in the standard form,
we write the constraints 10x 1 plus 5x 2 less than or equal to 2500, as 10x 1 plus 5x 2
plus x 3 is equal to 2500, x 3 is the slack variable. Similarly, x 4 is the slack variable
here and x 5 is the slack variable and all these variables x 1 x 2 x 3 x 4 x 5 are all
non-negative, because you added the slack variables, you add also add them also in the
objective function by taking a coefficient of 0, 0x 3 0x 4 0x 5. So, now you have express
this problem in the standard L P problem L P form, where the objective function is of
maximization type, all the constraints are of equality type, all the variables set are
involved in the problem, are all non-negative. Then, you look at the number of variables
and number of constraints, there are x 1 x 2 x 3 x 4 x 5, variables 1 2 3, three equality
constraint, so three numbers of equations. So, 5 number of variables and three number
of constraints or three number of equations. We start with an initial basic feasible solution
as that said, in most problems of this type where you have maximization and then you have
all less than or equal to constraints and you have exactly one slack variable associated
with each of the constraints, in such situations by setting the original decision variables
in this particular case x 1 and x 2 by setting the original decision variables as non basic
variables, you always obtain a initial basic feasible solution.
So, our basis will consist of x 3 x 4 and x 5. So, our non basic variables are x 1 and
x 2, you are setting them to 0 and like we did in the last class, you are write also
Z as one of the row, so we are writing it as Z minus 40x 1 minus 100x 2 minus 0x 3 minus
0 x 4 minus 0x 5 is equal to 0, that is the Z row, so that is how you write Z row. Then
corresponding to each of these rows, that is row number one is this, row number one,
you write the coefficients of the associated variables x 1 x 2 x 3, so 10x 1 plus 5x 2
plus x 3, that is this constraint is equal to 2500, both the other variables will be
0. Then similarly, for other rows that is row
number two you write the coefficients, row number three you are write the coefficients.
Now, you recall what we did in the previous lecture for solving this problem by the simplex
method, first we ask the question is the solution optimal, the solution is optimal only if all
the coefficients here in the Z row are non-negative, because there are some negative coefficients
here, this the solution is not optimal. And once you identify that the solution is not
optimal, the second step is which is the currently non basic variable that can enter into the
basis and the answer to that is, that the variable which has the highest negative coefficient
in the Z row will enter the basis, because that is the one, which will increase the objective
function value the fastest and we are interested in the maximization problem and therefore,
we would like to increase the objective function value the fastest.
And therefore, the coefficient the particular variable, which has the highest negative coefficient
in the Z-row will be the entering variable therefore, we identify in this particular
case, the variable x 2 as the entering variable. Then we identify this as the pivotal column
obtain b i by a i j, if it is non-negative. So, this you do not compute 2500 by 5, that
is 500, 2000 by 10, that is 200, 900 by 3 that is 300, so you obtain the b i by a i
j. The departing variable is the one which has
the lowest b i by a i j ratio, so 200, so this is the departing variable. So, in the
next basis x 4 goes out x 2 comes in, so the how do I write x 3 x 2 x 5. So, when you go
to the next tableau you rewrite the basis first then divide all the pivotal row elements
with the pivot, this is the pivot point. So, that is the first transformation you do.
So, when you go to the next tableau, first rewrite the basis x 3 x 2 x 5, the x 4 went
x 4 variable went out of the basis and x 2 variable came into the basis. Then, you wrote
the pivotal row first by dividing all of these elements by 10 which is the pivotal element.
So, 4 by 10, 1 0, 1 by 10, 0 200, that is what you have got here, up to b i column.
Remember b i by a i j is a only a computed for identifying the departing variable, you
should not divide this also by 10, b i by a i j is this column is always computed corresponding
to an iteration after you have done all the transformation to obtain the new tableau.
So, we write now the iteration two tableau. So, the first row that you transform is this,
then each of these other values you transform using you are earlier formula, that we had
used, let me show how we do this, let us say that you want to transform this value 0, that
is the right hand side value, how do we transform this? This should be 0 minus, minus 100 into
2000 divided by the pivotal element. So, this will be you will have 20000, plus
20000. So, that is how you get plus 20000. Similarly, you look at this value 2500, 2500
which is the old value minus 5 into 2000 divided by 10 that is how you get 15000. That is 2500
minus this value 5 into this value 2000 here divided by the pivot. So, this will be 1000
2500 minus 1000, that is how you get 1500 and similarly, you transform all these variables,
all these numbers except the pivotal row pivotal row you have already transform.
So, except the pivotal row you transform all other numbers here and this is what you get
I would encourage all of you to solve several problems using the simplex method, so that
you will be able to do it mechanically almost mechanically you should able to do. And also
those have a programming capability, you write the program this a very simple algorithm,
write the program may be in C or FORTRAN or some such things and test this examples. Now,
anytime you write the tableau completely for that particular iteration, what is the question
you will ask? You will ask whether this particular solution is optimal, and that is a question
we will ask, is the solution optimal to answer that, you look at the coefficients in the
Z-row of all the variables. If all the coefficients are non-negative, then the current solution
is optimal. In this particular case, all the solutions,
all the coefficients and sorry all the coefficients are in fact, non-negative and therefore, this
present solution becomes optimal, what is the optimal solution? The optimal solution
is Z is equal to 20000, x 3 is equal to 15000, x 2 is equal to 200 and x 5 is equal to 300.
And of course, x 1 will be equal to 0 and x 4 is equal to 0, which are non non basic
variables. So, this is the solution that you obtain. Once you obtain the optimal solution,
you should also look for alternate or multiple solutions for which you look at the currently
non basic variables, the currently non basic variables are x 1 and x 4.
Then you look at the coefficients of these non basic variables in the Z-row, x 1 has
the solution the coefficient of 0, x 4 has the coefficient of 10. If any currently non
basic variables have a coefficient of 0 in the Z-row in the last iteration, this is the
last iteration because you have it the optimal solution, then it indicates that multiple
solutions are possible, which means what its says that you by bringing in x 1 into the
basis, you are not making any change in the objective function value, because it has a
coefficient of 0. And therefore, you can afford to bring x 1 into the basis, without changing
the solution which is Z is equal to 20000 without changing the objective function value,
optimal objective function value and yet to generating another set of solution, why I
say another set of solution? Look here x 3 x 2 and x 5 in the basis and therefore, the
solution was x 3 is equal to 1500, x 2 is equal to 200, x 5 is equal to 300.
Now, I bring in x 1 into the basis by identify one of these variables to go out make way
for x 1 and therefore, I can generate another solution by adapting the same methodology
of identifying exiting variable or the departing variable from the basis.
So, what we are saying now is since, all the coefficient in the Z-row are non-negative,
this is the optimal solution. And the optimal solution is Z is equal to 20000, that is what
we are reading here Z is equal to 20000, x 1 is equal to 0, because it is a non basic
variable, x 2 is equal to 200, then x 3 is equal to 1500, x 3 is equal to 1500 and 4
is equal to 0, because its a non basic variable, x 4 is 0 and x 5 is equal to 300, so this
is the solution that you obtain. Then, you say that because x 1 has a coefficient of
0 here, this can be brought into the basis and therefore, generate another set of solutions.
So, we are saying that coefficient of x 1, which is the non basic variable in the final
tableau in the objective in the optimal solution, because the coefficient is 0, you can bring
it into the basis and you also say therefore, that multiple solutions exist, so the requirement
for the multiple solutions in the simplex algorithm is that, the coefficient of that
particular non basic variable of a particular non basic variable must be 0 in the Z-row.
So, this is how you are say that there are multiple solutions, then we need to get the
multiple solution said if there are two solutions possible to the L P problem, there are infinite
number of solutions, if you recall in the graphical method what did we do, if the Z-value
when as it is increasing the last point of the Z-value coincides with one of the edges
of the feasible space, then it means that there are multiple solutions and any point
on that particular edge, edge of the the feasible space in the in your graphical method. Any
point on that edge is in fact, an optimal solution and therefore, there are infinitely
many solutions and what we are getting through this simplex algorithm is the corner points.
Remember, we are going from one basic solutions to another basic solutions, so we are going
from one corner point to another corner point, let us say that, you identify this as the
solution objective function value, this as the optimal solution and then here you said
that, there are multiple solutions possible because the one of the non basic variables
has the 0 coefficient in the Z-row and therefore, you identify that this is a non basic, this
is the case where multiple solutions exist, but you were at this point. Then you generate
another basic solution basic feasible solution in fact, and therefore, you go from this corner
point to this corner point in your feasible space, let us said the feasible point was
something like this. So, you hit the optimal point here optimal
point here and you came to know that this is in fact, the the optimal solution and therefore,
from here you go to the next optimal solution, which should be here. And any point joining
these two optimal solutions on the feasible space, any point on this line is also an optimal
solution, giving you the same Z-value and therefore, you can obtain infinitely many
many solutions for this particular problem, which means that if you can identify two solutions,
you can identify infinitely many numbers of solutions. Let us see, how we obtain it for
the next solution, so these are the tableau here and therefore, said that multiple solutions
exist and therefore, I again bring in x 1, so let us try bringing x 1.
So, we identify that particular non basic variable, which has a coefficient of 0 in
the Z-row as the entering variable. So, we identify this particular case x 1 as the entering
variable, this was the non basic variable because it was not in the basis. So, we identify
x 1 as the entering variable and then apply our same criteria. So, you have you obtain
b i by a i j. Remember, once you identify the entering variable, you have to calculate
b i by a i j to identify which is the departing variable.
So, we have compute the b i by a i j only if it is non-negative, so this you do not
compute 1500 by 8, 200 by 4 by 10 which will be 500 and 300 by 8 by 10 which will be 375
and 1500 by 8 will be the smallest value and therefore, the departing variable will be
x 3, so corresponding to the entering variable x 1, you identified a departing variable x
3. So, you write one more iteration now, starting with this, we write one more iteration we
rewrite the basis, we we transform the pivotal row and then transform all the other elements
as we did earlier. So, when we write the next iteration, the
basis will get transform form Z x 3 x 2 x 5 to Z x 1 x 2 x 5, x 3 goes out and x 1 comes
in, but the objective function value still remains the same. Look at this 20000 and this
is your pivotal column and this is your pivotal row. So, if I have to transform this value
what happens 20000 minus 0 into 1500 divided by 8, because 1of them is 0 this remains the
same, so this becomes 20000. Like this, you obtain all other values here, then you will
get the solution as Z is equal to 20000, x 1 is equal to 1500 by 8, x 2 is equal to 125,
x 5 is equal to 150 and the currently non basic variables x 3 is equal to 0 and x 4
is equal to 0. The point to be noted is that, the objective function value remains the same,
although your solution is different why I say solution is different, it is because x
1 is equal to 1500 by 8 here, what are the x 1 value x 1value was 0 here, because it
is a non basic variable. So, you get another set of solutions x 2 was 500 here, x 2 becomes
125, x 5 was 150 here, x 5 becomes sorry x x 5 was 375 here, x 5 becomes 150 and therefore,
you get a different solution in terms of x 1 x 2 x 3 etcetera, but the Z value still
remains the same and therefore, this is an alternate solution.
So, you got 2 solutions now one solution from here, namely x 3 is equal to 1500 by 8 sorry
x 3 is equal to 1500, x 2 is equal to 200, x 5 is equal to 300, x 1 is equal to 0, x
4 is equal to 0, this is one solution, which give Z is equal to 20000. The next solution
is x 1 is equal to 1500 by 8, x 2 is equal to 125, x 5 is equal to 150 and of course,
other non basic variables namely x 4 is equal to 0 and x 3 is equal to 0. So, this is an
alternate solution that you obtain corresponding to the previous solution, which we said you
got two sets of solutions now, we will call them as x 1 and x 2, so that two solutions
are x 1, which is this is the value of x 1 here small x 1, so this is x 1, this is x
2 x 3 x 4 and x 5.
Similarly, these are the x 1 x 2 x 3 x 4 x 5. So, these are the two sets of solutions,
that you obtained, we will call them as x 1 and x 2 they are vector sum, now form these
two solutions, you must be able to generate infinitely many solutions, how do we do that?
We can formulate another solution let us say x star as a linear combination of these two
solutions, let us say alpha x 1 plus 1 minus alpha x 2, so you can take a linear combination
of these two and then write another set of solutions.
So, we will write this as X star is equal to alpha X 1 plus 1 minus alpha X 2 for alpha
being in the range 0 to 1. So, this is also an optimal solution, it gives you the same
Z value and it gives you a different point altogether. So, I can write X star as alpha
X 1 your X star X 1 star was this, so small x 1 is 0, so alpha X 1 plus 1 minus alpha
into X 2 here 1500 by 8, so that will be 1 minus alpha 1500 by 8. Similarly this was
200, so 200 alpha plus 125 into 1 minus alpha, so 200 alpha 1 minus alpha into 125, like
this you write write you will get a different solution 1 minus alpha 1500 by 8, 125 plus
25 alpha 1500 alpha, this becomes 0 itself and then 150 plus 150 alpha.
By choosing alpha appropriately in this range, you can generate one solution you said alpha
is equal to 0.3 you get one solution, alpha is equal to 0.4 you get another solution and
so on. So, you can generate an infinitely many solutions from this, corresponding to
each of the solutions your Z value remains the same.
So, they are all alternate solutions let, us say that we put alpha is equal to 0.5 here,
so you if you put alpha is equal to 0.5 you will get a solution like this, x 1 is equal
to 93.75, x2 is equal to 162.75 and so on. So, when you put these values in your Z expression
you will get Z is equal to 20000 still, which is the same value that you obtained as the
optimal solution here. So, corresponding to any of the solution set you are generating
you are so, generating the objective function values still remains to be 2000 Z is equal
to 20000.
So, these are called as multiple solutions, then we have an another situation, now where
we need to introduce what are called as the artificial variables. Let us, look at a background
why we need to introduce artificial variables, the simplex tableau requires that, you start
with an initial basic feasible solution, remember we start the process with an identification
of initial basic feasible solution. How did we do this, let us say that you had a constraint
x 1 is less than or equal to 4 in the example, that we solved earlier and let us say there
were two constraints.
So, corresponding to this, what we do we do? we added a variable for a two variable problem,
we put this as x 3, x 1 is plus x 3 is equal to 4. And therefore, when I set x 1 as a non
basic variable which means x 1 is equal to 0 I get x 3 is equal to 4, which is the feasible
solution, because I am getting a non-negative value for x 3 and therefore, I am state away
getting a feasible solution there.
Lets say that, you had a constraint of the type greater than or equal to, instead of
x 1 less than equal to 4 let us say I had x 1 greater than or equal to 4, then what
I will do I will deduct a surplus variable, let us say x 1minus x 5, we will call it is
equal to 4, where this is a surplus variable. And when I put x 1 is equal to 0, what happens
x 5 will be equal to minus 4. So, I get x 5 is equal to minus 4, which is not feasible
for x 1 is equal to 0. So, if instead of x 1 less than or equal to 4, if you had x 1
greater than or equal to 4 here in this particular case, because your put a surplus variable
with a negative sign, by setting x 1 as the non basic variable you would get a infeasible
solution, so x 5 is equal to minus 4 is not a feasible solution, so you cannot start with
a initial basic feasible solution by setting your original decision variables to 0.
Similarly, you take a condition where you had x 1 plus 2 x 2 is equal to let us say
18, this also constraint and you were setting x 1 is equal to 0, x 2 is equal to 0, these
are the original constraints a original variables, so you wanted to start the simplex algorithm
by setting the original decision variables to 0 therefore, you would have put x 1 as
non basic variable x 2 as non basic variable, which means they will take value of 0, then
this becomes infeasible, because of this constraint, that is you had in equality constraint.
And therefore, when you have either a greater than or equal to constraint or a equality
constraint by setting the original decision variables to 0, which means by setting the
original decision variables as non basic variables in the first iteration, you will not be able
to get a initial basic feasible solution to start the competitions you have to do something
else. There is one more aspect that you must remember is that, when I said that you start
with an initial basic feasible solution always you write let us say, that a 1 x 1 plus a
2 x 2 is equal to b i let us, say you write it as b 1 let us say this the one of the constraints.
You must look at this sign, this must be positive only then you will get the initial basics
feasible solution or I will say non-negative, we will call it as non-negative. If this is
negative then, what will happen that you would not get a initial basic feasible solution,
so when you write the constraints are the equality constraints make sure that the right
hand side is non-negative, if it is not then what to do, multiplied by minus 1, let us
say this was negative multiplied by minus 1, so that you will get a non-negative value
on the right hand side. So, there are conditions where you will not
be able to state away get an initial basic feasible solution, to start the simplex algorithm.
In such situations, when you have a greater than or equal to constraint are a equality
constraint in such situations you are add what are called as artificial variables, for
greater than or equal to or equality constraints. We add the artificial variables to get an
initial basic feasible solution, that is the whole purpose of getting an artificial variable,
the variables were not existing in the original problem, the variables did not exist then
we converted into standard form by adding the slack variable by or subtracting the surplus
variable etcetera, these variables did not exist, after convert it into the standard
form you then see that, the initial basic feasible solution is not available, in an
initial basic feasible solution is not available and therefore, you add artificial variable,
these variables are artificially added, there were they were not existing in the original
problem. Let us see what we do for the artificial variables and these are typically denoted
as a 1 a 2 and so on. So, you add one artificial variable corresponding
to each of the greater than or equal to and equality constraints, let us say that you
had 2 greater than or equal to constraint and one equality constraint, you add corresponded
to the first one you add a 1 corresponded to second greater than or equal to you add
a 2 corresponded to the equality constraint you add a 3, like this you add one artificial
variable associated with each of the greater than or equal to and equal equality constraints.
This is after, this is we do this just before we standardize, let us see what we do in this
particular case, how do we add the artificial variables. So, we add the artificial variables
to each of the constraints, so if you have a equality constraint or if you have a greater
than or equal to constraint, you add one artificial variable with each of them. Now, your objective
function is maximization type and now you are adding an a artificial variable, you do
not want the artificial variables to appear in the final solution. And therefore, what
we have to do, let us say, that you add maximizing 3 x 1 plus 5x 2, x 1 being greater than or
equal to 0, x 2 being greater than or equal to 0, subject to several constraints.
You would like to increase the objective function value from iteration to iteration, now by
adding artificial variables, it is possible that if you put a 0 into a 1 like we did for
the slack variables and the surplus variables in the objective function, we are as coefficients
in the objective function value it is possible that, your artificial variables still remain
in the basis and therefore, you need to penalize the artificial variables in the objective
function. So, we penalize the objective function for even a small value of artificial variable
in the final tableau therefore, we would like to get rid of the artificial variables as
early as soon as possible. What I mean by that is let us say that, you
have an artificial variable, let us say you had Z is equal to 3 x 1 plus 5x 2 and you
were maximizing this and you have put some artificial variables here some constraint
and a artificial variable and then that equal to 0.
Because, you do not want the artificial variables in the final solution, what we will do is
we penalize this with a negative sign and put a large coefficient, this is the big coefficient
and that is why this method is called as Big M method, and say minus M into A 1, which
means even if you put a very small value to this artificial variable in the iterations,
then this whole function becomes highly negative value and therefore, there is a penalty associated
with this, you would like to increase the value 3 x 1 plus 5x 2, you would like to increase
the value of Z, by putting this penalty you are actually pulling down the value of Z and
therefore, there is no incentive for the algorithm to put any value other than 0 here.
And that is what we do by penalizing the objective function, so we penalize the objective function
by a Big M method. So, this is a Big M, which means the value of m is larger in fact much
larger compare to any of the coefficients any of the values that you get in the iteration
in the simplex tableau. So, Big M is so large, that it is much larger than any of the value
that you are getting in the iterations. So, this is how we penalize the objective function.
So, we add artificial variables to each of the constraints and then penalize the artificial
variable in the objective function, by penalizing I mean if it is a, because where dealing with
the maximization problem, you deduct a very high value of the artificial variable, that
is minus M into a 1, so even if a 1 takes on a very little value the objective function
value is pull down to a great extend and therefore, there is no incentive to put any value to
the artificial variable in the iterations that is what we do, and then what we do is,
that the zeroth row now that means, the Z row you have put minus M into a 1 minus M
M 1 into a 1 minus M 1 2 into a 2 and so on, typically we will use the same m coefficient
minus M into a 1, minus M into a 2 and so on.
This zeroth row now, we transform we transform using the artificial variable, remember you
have associated an artificial variable to a constraint, so a particular row has a artificial
variable, take that row along with the zeroth row and then transform the zeroth row by taking
the particular row as the pivotal row itself, I demonstrate that and then transform all
the elements in the zeroth row by using our transformation method, that is the new element
is equal to old element minus R, which is the element in the pivotal row and this C
is the element in the pivotal column divided by the pivotal itself, so you take just those
two rows namely the Z row and the row correspond row containing the artificial variable, only
just take 2 of them and transform the Z row. If there are more number of constraints containing
artificial variables do this transformation one by one, what I mean by that is take one
row containing the artificial variable transform the Z Z-row using this expression, then on
this transform row Z-row you add another row containing another artificial variable, again
retransform the Z-row like this one by one you keep on using the rows of the rows containing
the artificial variables and then keep transforming the Z-row.
I will demonstrate this with a simple example, let us say that, you know this is the same
problem that we solved using the graphical method, this same problem that we solved in
the first simplex example, first example using the simplex method in the previous lecture.
So, we will take the same example except that, this constraint which was the less than or
equal to constraint earlier, which is 3 x 1 plus 2 x 2 was less than or equal to 18
will make it as equality constraint, which means that we do not accept any solutions
less less than 18, earlier problem had 3 x 1 plus 2 x 2 less than or equal to 18, we
remove the less than, we say that it has to be exactly equal to 18.
Now, look at what we would done to this problem earlier, we would have said x 1 plus x three
is equal to 4 and 2 x 2 plus x 4 is equal to 12 and 3 x 1 plus 2 x 2 in the earlier
case we put plus x 5 is equal to 18, because this for less or equal to constraint. Now,
because this is equality constraint we will let us say that, we put it as equal to 18
as it is, because we have satisfied all the conditions for the standard form.
If we do this then what happens, I am setting x 1 is equal to 0, x 2 is equal to 0, because
we want the original decision variables to be non basic, then what would happen x 3 is
equal to 4, x 4 is equal to 12, but this becomes infeasible, I am putting 0 here 0 here equal
to 18 therefore, this becomes infeasible and therefore, I do not have an any initial basic
feasible solution to to overcome this situation and to obtain an initial basic feasible solution,
what I will now do is only for this constraint I will say 3 x 1 plus 2 x 2 plus a 1 is equal
to 18. So, I am setting an artificial variable here, then what happens you set x 1 is equal
to 0 x 2 is equal to 0 therefore, x 3 is equal to 4, x 4 is equal to 12 and because these
2 are 0 we will get a 1 is equal to 18 and that we will give you an initial basic feasible
solution to start the computations, because you put a 1 here, which is an of artificial
variable, you need to penalize the objective function.
So, I will put minus M into a 1, so this is a Big M, so this is very large for example,
in the case of 3 and 5 etcetera, when you are looking at such numbers it can be 10 to
the power 5, 10 to the power 6 etcetera, anyway we will not associated any dimensions here,
any particular magnitudes here, simply assume that this M is way to large compared to any
of the other numbers that you get, even if you get 20000, 50000, 10 to the power 6 etcetera,
M is still larger than that. So, you are penalizing the objective function, so this is what you
do by introducing the artificial variables. Once you introduce the artificial variables,
then you will write the Z as Z row or the zeroth row as Z minus 3 x 1, you would have
written the Z-row as Z minus 3 x 1 minus 5x 2 plus M into a 1, of course, the other slack
variables will have a coefficient of 0. So, that is what you write as the Z-row and using
that Z-row, you and using this particular row in which, you have introduce the artificial
variables, you transform the Z-row, I will explain what we do that. So, first you convert
the problem into a standard L P form x 1 plus x 3 is equal to 4, you added a slack variable
here, added a slack variable here this you written as it is, then you saw that number
variables is 4 number of constraints is equal to 2 and then you are add an artificial variables.
So, we added an artificial variable 3 x 1 plus 2 x 2 plus a 1 is equal to 18, this is
a artificial variable you are adding and like I said, you will penalize the objective function
and therefore, you will write the zeroth row or the Z-row as Z-minus 3 x 1minus 5x 2, I
am rewriting this Z minus 3 x 1 minus 5 x 2 plus m into a 1, because you would have
put minus m into a 1 here for a maximization problem, we would like to penalize with the
big penalty and therefore, you would have written minus m into a 1 and therefore, here
it becomes plus m into a 1 is equal to 0 this is your row 0.
And you take this along with the constraint in which, you added the artificial variable.
So, it is here that you have added the artificial variable 3 x 1 plus 2 x 2 plus a 1 is equal
to 18. These two constraints together you take and then make the particular column containing
the artificial variable as the pivotal column, I will demonstrate what I mean. So, we are
now writing the transformation for Z, you added the penalty minus m a 1 in the zeroth
row and then you considered the constraint containing the artificial variable. Now, together
we will use to transform the Z row, we are not doing anything to this row we will only
transform the Z row, let us see what we do.
So, we write the Z row this is Z minus 3 x 1 minus 5x 2 plus M a 1 minus 3 x 1 minus
5x 2 x 3 x 4 have 0 coefficients plus M and right hand side is 0. So, you take b i as
0 and you write 3 x 1 plus 2 x 2 plus a 1 is equal to 18 3 x 1 plus 2 x 2 plus a 1 is
equal to 18. Make this as the pivotal column, remember this transformation you are doing
one artificial variable at a time, so if you had three constraints containing artificial
variables you will do this one by one. So, always take only one artificial variable.
So, this is the row containing the artificial variable and you make this particular column,
which corresponds to the artificial variable as the pivotal column, and then use our usual
method of transformation and then transform each of the elements. So, this becomes the
pivot, this is the pivotal column this becomes the pivotal row say for example, you want
to transform this how do you transform that this is I will write 0 minus M into 18 divided
by 1. So, this is what you write as minus 18 M.
Similarly, if you want to write let us say this number, this will be minus 5 minus m
into 2 divided by 1. So, minus 2 M minus 5 that is what you get here similarly, here
minus 3 let us say I want to write this that will be minus 3 minus M into 3 divided by
1. So, minus 3 M minus 3 this is what you get here like this you transform the Z row,
you do this transformation only on the row you get minus 3 M minus 5 minus 3 M minus
3 minus 2 M minus 5 0 0 0 minus 18 M. So, this is how you do the transformation
on the Z-row whenever you introduce artificial variables, then to start the simplex algorithm,
simplex method for this particular problem, we use the transformed Z-row in the first
iteration, we use the transform Z-row and do the competitions as we did did in the previous
examples. So, in we will see this example, will continue this example in the next lecture
and then see, how we deal with the artificial variables in the simplex tableau.
So, in this today lecture, what we started with what is the multiple solutions, how to
capture the multiple solutions in the simplex tableau, in the optimal solution or in the
final simplex tableau, if you have the coefficient of one of the non basic variables one or more
of the non basic variables as 0 in the Z-row or in the zeroth row it means that multiple
solutions exist; that means, you can bring that particular non basic variable into the
basis without changing the objective function value and therefore, you can generate one
more set of solutions and if you can generate two sets of solutions you can generate infinitely
many sets of solutions by taking linear transform linear transformation of these two sets of
solutions. We have seen, how to obtain these infinitely
many solutions x star is equal to alpha x 1plus 1 minus alpha x 2, where alpha you can
choose any value any convenient value between 0 and 1 and therefore, you know how to obtain
multiple solutions, then we went onto introduce the artificial variables in case is where
an initial basic feasible solution is not possible and when is this not possible, whenever
you have a greater than or equal to constraint or an equality constraint in the original
problem, because for the greater than or equal to constraint, you would have a subtracted
a surplus variable to make it equality and for the equality constraint, you would not
add an anything and therefore, you you will written the equality constraints as it is
and therefore, by setting your initial basic, initial variables of the problem as non basic
variables, you will still not get a initial basic feasible solution.
Because, you have a variable, a slack variable or may it may be surplus variable in the greater
than or equal to constraint the surplus variable comes with the negative sign and therefore,
you may not have an initial basic feasible solution. Just to ensure that you get an initial
basic feasible solution, the artificial variables are introduced, the artificial variables we
typically in introduce for greater than or equal to and equal to constraint in fact we
introduce exactly one artificial variable associated with each of the greater than or
equal to and equal to constraints and because we introduce the artificial variables, we
penalize the objective function, because we are dealing with the maximization of objective
function, we deduct minus m into a 1, that is we introduce a term minus m into a 1, where
m is the large coefficient and this is called as a Big M method the big m method, where
m is so, large compare to any of the other variables that there is a penalty associated
with even a small increase in value of a 1. And then we looked at the transformation of
the Z-row corresponding to the artificial variable we will continue that discussion
on how we use this transformed variable transformed Z-row in the simplex method to obtain optimal
solution, we will continue the discussion in the next lecture, Thank you for your attention.