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.