How to Solve a Linear Programming Problem Using the Big M Method


Hello everyone this is Mirzaei from Cal Poly
Pomona and in this lesson we are going to learn how to solve a linear programming problem
using the big M method. Big M method is used when there are constraints with>=or=signs
in a linear programming problem. Before solving a problem using the big M method, we need
to learn the concept of excess and artificial variables. The concept of excess variable
is very similar to the slack variables in the simplex method. Let’s understand this
concept by an example. Suppose we have a maximization problem which is subject to three constraints
with=. The first step before solving this problem is to standardize
it. For the constraints with=sign. Let’s see how we can treat this constraint. Consider
a feasible solution to this problem. For example, x1=x2=100, is a feasible solution to this
problem. Because, if you replace x1 an x2 in the first constraint, you see that it satisfies
the first constraint. Because you get 300=150. So, the constraint is satisfied. That’s why we call this solution a feasible
solution to the problem. Now, if I replace this feasible solution in the last constraint
of this problem which has a>=sign you’ll see that the left hand side will be 300. despite
the constraints with=or=sing
to generate that basic variable that we are looking for to start the problem. In this
example, if I add an artificial variable to the left hand side of this problem, I can
generate that decision variable that has a coefficient of 1 in one constraint and all
the other coefficients of a4 are zero. You don’t see a4 in any of the previous constraints
that we have. So, now we can start the Simplex using this initial solution. But, a4 doesn’t
actually exist. It’s an artificial variable that helps solving the problem. It’s a sort
of auxiliary type of decision variable. So, we have to get rid of a4 along the way as
we solve the problem. Since we are looking at a maximization problem, if I add this a4
with a very big negative coefficient in the objective function, then my optimization problem
tries to minimize a4; because it has a very big negative coefficient. So, its contribution
to the objective functions is negative and is really big. If a4 for example gets a value
of 1 and let’s say its coefficient is -1 million, So -1 million it is a really big amount that
will be deducted from my objective function. So, what the objective function tries to do
is to eliminate the impact of a4, and then we can get rid of artificial variables along
the way, because In the first place it doesn’t exist. So, what I do, I add a4 with a very
big number with a negative sign to the objective function of maximization. Along the way, to
maximize this problem I reduce the value of a4 as much as I can and hopefully I will reduce
a4 to zero. This way, I can eliminate the impact a4 from the objective function. Again,
we have to standardize this problem so we take all the decision variables to the left
hand side and make the equation equal to zero. Now, the thing that you have to pay attention
is to adjust your objective function before you standardize it. If you standardize, and
then add -Ma4 , you will actually try to increase the value of a4, which we are not looking
for . If you define auxiliary decision variable a4 for your problem, then your objective function
have to reduce that impact. So, if you are looking at a maximization problem we add a
very big number with minus sign to the objective function, whereas if I am looking to a minimization
problem, I will add a4 with a very big coefficient to the objective function. So, the sign of
M, here, depends to the direction of objective function. For maximization is negative and
for minimization is positive. But, the logic is the same. Alright, we have set up the initial
table of Simplex and we are good to start. Again, all the steps are very similar to regular
simplex method where we are looking for the most negative value in the row of Z, and then
we are trying to run the minimum test to find the exiting decision variable. However, before
we start solving the problem, we have to do some manipulation in the row of Z. If you
look at this table, a4 is a basic variable and has a coefficient of M in the objective
function. Whereas, according to the definition, we should have 0 and anything besides this
value, in this column, should be zero. So now, we have to some manipulation in this
row to make that change happen, to change that M to 0. To be able to do this, we have
to again use elementary row operations. The telemetry row operation that we introduce
in this step is -M multiplied by the 4th row of the table plus the row of Z. Why I choose
the forth row of this table? Because if I multiply this row by -M and then add it with
the row of Z, I am able to generate that zero, whereas if I use any of the other rows that
we have, it doesn’t change anything; because the coefficients, here, are zero. So, anything
I multiply by these rows doesn’t have any impact. So, the only option that we have is
the 4th row, and I use this row to manipulate the row of Z. Here, you are able to see the
new row of Z. Now, we can start the Simplex method very similar to what we have done for
the regular Simplex. So, if I look at the most negative value in the row of Z, this
is the most negative number. M is a very huge number. You can always replace that M with
a big number. Let’s say 10^6, if that makes it easier for you to understand. To find what
is the decision variable that will exit the basis in the next table, we have to run the
minimum test. If I do the minimum test, which is dividing the right hand side of your problem
by the positive value of the pivot column, you see that the minimum number is related
to the 4th row of this table. So, the pivot row will be the 4th row, and the intersection
of the pivot column and the pivot row gives you the pivot value which is 2, and in the
next table we have to change that value to 1, and also in the next table x2 will replace
a4. So, the decision variable related to the pivot column will replace the decision variable
related to the pivot row. So, x2 replaces a4 in the next table. But, all the other decision
variables are the same. Now, the elementary row operation to change the [pivot value]
in the pivot row to 1 is dividing the pivot row by 2. So, R4/2 is the elementary row operation
we need to do. Now, we have to use this row to manipulate the other three rows to value
of 0 in the pivot column. By the elementary row operation of -R4+R1 we are able to generate
0, in the first row [of the pivot column]. If you have forgotten about the elementary
row operations, please refer to the lesson related to the elementary row operations.
If I multiply the 4th row of this table by -1 and adding it with this row, the first
row here, we are able to generate the value of 0, here. Now, let’s do this operation and
see how the first row will change. As you see we are able to generate the value of 0,
here. The ERO to change the second element of the pivot column to 0 is negative R4 in
the new table or our new pivot row, plus the second row in the old table. Similarly, to
change the third row of the pivot column to 0, the elementary row operation will be -2
multiplied by the 4th row of the old table plus the 3th row in the old table. Now, remember
that we have to always have a pivot row used in our elementary operations row operations.
It doesn’t matter whether we are using the pivot row in the new or in the old table.
So, in this example instead of multiplying this row by -4, I decided to multiply this
row by -2. We can use either one, Pivot row in the new table or the pivot row in the old
table to set up your elementary row operation. Make sure you always multiply a pivot row
by some amount and then add it with the row that you want to see the change in it. By
doing this, I get the new 3rd row of simplex table. Now, the last part is to define the
elementary row operation for changing the element of the Z-row in the pivot column to
0. The elementary row operations will be 2M+4 Multiplied by the new pivot row plus the row
of z. Again, as you see I defined some coefficient for the pivot row in the new table and add
it with the row that I want to see the change in it. So, if you pay attention to these EROs
you see what is in common between all of them. You see that this is the row that we are changing
every time, this part, and the first part is the pivot row multiplied by some number.
So, every time you are trying to find what should be the coefficient of pivot row so
that when you add it with the row that you want to see the change in it, you are able
to see that change. Now, if I implement this ERO, I am able to see the new row of Z which
has a value of 0 under x2, which is our new basic variable. Now, x2 has become a basic
variable in this table, and if I look at the column related to x2 I see 1 for x2 and x2
and all the other elements are zero in this column. So, that confirms that I was able
to make x2 a basic variable. For all the basic variables you should see the same pattern.
If I look at S2 column, I should only see 1 in one row and all the other elements should
be equal to 0. Now, you have to check for optimality condition to decide whether I have
to continue or stop the Simplex. For maximization problem, optimality condition is when all
the coefficients in the row of z are positive [or zero]. But, here, we see two negative
values which are -1 and -2. So, you have to continue the table of Simplex. Again, I have
to find the most negative value, here, and implement the minimum test. As you know, we
only implement the minimum test on the positive values of the pivot column, which are 1/2
1/2 and 2. By implementing the minimum test, we see the min value is related to the second
row of this matrix. So, we have to change 1/2 to 2 in the next table, because e4 is
going to replace s4 in the next table. So, if I do this replacement the elementary row
operation to change 1/2 to 1 is to multiply this row by a value of 2, and this is the
new row that we get. Now, we have to use this row to manipulate other elements of the pivot
column to become 0. To change the first row element in the pivot column to 0, if I multiply
this row by -1 and then add it with the first row, here, I am able to see the value of 0
that I was looking for. So, that’s what I am going to implement in here which is -R2
the old table plus R1 in the old table. To change the third row of pivot column to 0,
we multiply the 2nd row of the new table, which is our pivot row by -2, and then add
it with the third row in our old table. So, implementing this step gives us the new third
row in the next table. Now, since this one is -1/2 and our pivot row has 1/2. By implementing
this step, we are going to get the new 4th row, which gives us a value of 1 for e4, and
all the other values are zero in this column. Now, we have to also manipulate the row of
Z to have the value of 0 in this element here. So, if I multiply the second row, which is
our pivot here, by 2 and then add with the row of z, I am able to generate the value
of 0, here. Let’s do this operation and see how it works. So, 2 multiplied by the second
row of the new table, which is my pivot row, plus the row of z, it will give me the new
row of z. Now again, if I look at the pattern, as you see, every time I multiply something
with the pivot row, and then add it with the row that I want to see the change in it. Now,
I have to check for optimality condition here to see whether I have to stop, I am at the
optimal table, or I have to continue. As you see, all the elements here are positive [or
zero]. So, for maximization when we have everything positive [or zero] we are at the optimal table
of the simplex. So, Do I have a final solution to this problem? Before deciding about the
final solution of this problem we have to check whether you see an artificial variable
in the basis of your table or not. If you see an artificial variable, here, your optimization
problem doesn’t have a feasible solution. Because we know that the artificial variable
doesn’t exit. We want that artificial variable to become 0. But, here, since we don’t see
any artificial variable, we are at the optimal solution. So, in the optimal table the artificial
variable is not a basic variable. Thus, the optimum solution is a feasible solution. Otherwise
we couldn’t conclude that we have a feasible solution to this problem. And not only we
have we have a feasible solution, but also we have optimal feasible solution, because
we reached the final table where all the values are positive [or zero] in the row of z. Your
final z value is 900. All the other decision variables that I don’t see in the basis are
equal to zero, and the decision variables that I don’t see here are x1, s2 and a4. So,
the value related to them is 0. With this our lesson in big M method has concluded please
refer to the backboard for your assignments.

Leave a Reply

Your email address will not be published. Required fields are marked *