In this video, I'll talk about how to use the big M method, which is a special case
of the simplex method, to solve LP problems with equality constraints or greater than
or equal to constraints.
In the simplex method, we need to find an initial BFS to start with.
In the previous videos, we have found initial BFS by using the slack variables as basic
variables because we only had less than or equal to constraints.
This does not work if a LP problem has = or ≥ constraints.
In such a case, the Big M method may be used to solve the problem.
Let's check this example.
It is a maximization problem with two variables.
We can use the graphical method to solve it, and the optimal point is E(0, 9), z*=18.
We have a greater than or equal to constraint.
We will use the big m method to verify this optimal solution.
The first step of the big m method is to make sure the RHS of the constraints are nonnegative.
If the RHS of a constraint is negative, we need to multiply both sides by -1 to change
it to a positive.
For this example, the RHS are both nonnegative.
So we are good.
Step 2.
Convert the LP problem into the standard canonical form by introducing a slack variable s1 and
an excess variable e2.
Step 3.
For each = or ≥ constraint, add an artificial variable.
Add sign restriction ai ≥ 0.
This example only has one ≥ constraint, so we introduce an artificial variable a2
in the second constraint and add it to the sign restriction.
In Step 4, we let M denote a very large positive number.
For each artificial variable, add Mai to R0 for the max problem.
This modification makes it extremely costly for an artificial variable to be positive.
After that, we re-write this problem in the simplex tableau.
Step 5.
Eliminate all artificial variables from R0 using EROs.
Solve the transformed problem by the simplex method.
If all artificial variables in the final solution equal zero, the solution is indeed an optimal
solution.
If any artificial variables are positive, we have a fake optimal solution, and the problem
is infeasible.
This is the original tableau.
The artificial variable has a coef of M in R0.
Now, let's subtract R0 by M times R2.
This will be gone.
Other coefs and the RHS are also updated.
In this tableau, s1 and a2 are BVs.
And others are NBVs.
Let's set NBVs to 0 and solve for BVs.
s1=9, a2=9, and z=-9M.
The entering variable will be x2, because it has the most negative coef in R0.
The ratio is the RHS divided by the coef of x2. 9/1 and 9/2.
R2 has the smallest ratio.
So it is the pivot row.
We need to change this to 1 and make it disappear from other rows using EROs.
This is the updated tableau.
x2 and s1 are BVs.
And others are NBVs.
Let's set NBVs to 0 and solve for BVs.
s1=9/2, x2=9/2, and z=9.
The entering variable will be x1, because it has the most negative coef in R0.
The ratios are 3 and 9.
R1 has the smallest ratio.
So it is the pivot row.
We need to change this to 1 and make it disappear from other rows using EROs.
This is the updated tableau.
x1 and x2 are BVs.
And others are NBVs.
Let's set NBVs to 0 and solve for BVs.
x1=3, x2=3, and z=15.
The entering variable will be e2, because it has the most negative coef in R0.
The ratio for R1 is 9 and for R2 is None because this coef is a negative value.
So R1 is the pivot row.
We need to change this to 1 and make it disappear from other rows using EROs.
This is the updated tableau.
x2 and e2 are BVs.
And others are NBVs.
Let's set NBVs to 0 and solve for BVs.
e2=9, x2=9, and z=18.
Now the coefs of all NBVs are positive.
So this tableau is optimal.
The optimal solution is x1=0, x2=9, s1=0, e2=9, a2=0.
z*=18.
Because the artificial variable a2=0, so this is a true optimal solution.
Also, this solution is the same as the one we got using the graphical method.
Now, let's check the second example.
The only difference is that this is changed from 9 to 4.
We can try the graphical method first, and we find that the feasible regions of these
two constraints have not intersection.
So the problem is infeasible.
Let's use the big m method to verify this.
For this example, the RHS are both nonnegative.
So we are good.
This is the only difference in step 2 and step 3.
This is the only difference in the initial simplex canonical form.
Now there are more changes in step 4 and along the simplex iterations.
The RHS, the BV and the ratio are all different.
As a result, the pivot row is changed to R1 because the ratio is smaller.
Let's continue, and the changes are marked in red.
Now the coefs of all NBVs are positive.
So it seems this tableau is optimal.
The optimal solution is x1=0, x2=4, s1=0, e2=0, a2=1.
z*=8-M. Because the
artificial variable a2=1 which is greater than 0, so this is a fake optimal solution.
We can also see that in the z* value.
M is a large positive number.
So z* can be infinitely small.
Therefore, we conclude this problem is infeasible.
Okay, that is how to use the big M method to solve LP problems with equality constraints
or greater than or equal to constraints.
Thanks for watching.