In this video, I'll show you how to use the simplex method to solve a LP problem.
You will see an example first.
At the end of the video, I will summarize the steps of the method.
The key concepts such as entering variable, leaving variable, ratio test, and pivoting
will be introduced.
This is a LP problem.
It's a maximization problem with two variables.
We need to covert it into the standard form by introducing two slack variables s1 and
s2 to make these equality constraints.
All the variables are greater than or equal to 0.
After we get the standard LP form, we re-write the objective function and move the RHS to
the left and make it equal to 0.
The objective function is changed to this and it is marked as Row 0.
The two constraints are marked as R1 and R2.
This is called the simplex canonical form.
It is a system of linear equations in which each equation has a variable with a coefficient
of 1 in that equation, and a zero coefficient in all other equations.
We can put this canonical form in a table.
These are the variables, z, x1, x2, s1, s2, and the RHS.
We write the values of the parameters in the corresponding cells in the table.
For example, the coefs of the variables in R0 are 1 for z, -3 for x1, -2 for x2, 0 for
s1, 0 for s2, and the RHS is 0.
We do that for R1 and R2 as well.
Finally, this is called a simplex tableau.
If we do not count z, we have n=4 variables, x1, x2, and s1, s2.
We have m=2 constraints.
Therefore, we can set n-m=2 NBVs to 0, and solve for the remaining m=2 BVs.
We can pick the variables that appear with a coefficient of 1 in a single equation and
not in all other equations as BVs.
For example, s1 has a coef of 1 in R1 and it's not in other rows.
It is a BV.
So is s2.
The other two variables x1 and x2 are NBVs.
Let's set x1 and x2 to 0 and solve for s1 and s2.
This part will be gone.
We have s1=9 and s2=9.
In R0, we have z=0.
As a general rule, a slack variable can be used as a BV if the RHS of the constraint
is nonnegative.
If the RHS is negative, then you cannot use the slack variable as a BV because it will
violate these sign restrictions.
Let's write out this BFS: s1=9, s2=9, x1=x2=0, and z=0 for this BFS.
Here is a question: Can the objective function z, which is equal to 3x1 + 2x2, be improved
by increasing some NBV from its current value of 0 while holding all other NBVs at 0?
Right now, the two NBVs are x1 and x2.
They are both 0.
If we increase x1 from 0 to 1, the z-value will increase from 0 to 3.
If we increase x2 from 0 to 1, the z-value will increase from 0 to 2.
So, increasing either NBV will improve z.
The current BFS is not optimal yet.
Increasing x1 will cause a greater rate of increase of z.
Let's check the tableau.
x1 has the most negative coefficient in R0.
If we increase x1 from 0 to a positive number, it will become a BV.
Because it is entering the set of BVs, we called x1 the entering variable.
Now we need to determine the largest we can make x1 so that all BVs are still nonnegative.
For that purpose, we need to compute a ratio for every constraint in which the entering
variable has a positive coefficient.
This ratio is the RHS of each constraint row over the coef of the entering variable x1
in that constraint row.
The constraint with the smallest ratio is called the winner of the ratio test.
Let me show you what it actually means.
For R1, if x1 is no longer 0, we have to write out this item, 2*x1.
x2 is still a NBV, so its value is 0.
s1 is a BV, so we put it here.
We don't have s2 in this equation because the coef is 0.
The right hand side is 9.
We re-write this equation by moving 2x1 to the RHS.
We have s1=9-2x1.
Due to the sign restriction, s1 is >=0.
So, x1<=4.5, which is the RHS in this row divided by the coef of x1.
For R2, if x1 is no longer 0, we have to write out this item, 1*x1.
x2 is still a NBV, so its value is 0.
s1 has a coef of 0, so we don't have it in this equation.
s2 is a BV, so we put it here.
The right hand side is 9.
We re-write this equation by moving x1 to the RHS.
We have s2=9-x1.
Due to the sign restriction, s2 is >=0.
So, x1<=9, which is the RHS in this row divided by the coef of x1.
Now we have two upper bounds, 4.5 and 9.
To satisfy all the sign restrictions, we have to select a smaller value, which means the
largest value we can increase x1 to is 4.5.
This is the actual meaning of the ratio test.
So, R1 wins the ratio test.
We need to make x1 a BV in this row.
It means, we should use Elementary Row Operations (or EROs) to make x1 have a coef of 1 in R1
and a coefficient of 0 in all other rows.
This procedure is called pivoting on R1; and R1 is called the pivot row.
x1 will replace s1 as the BV for R1.
s1 is called the leaving variable because it leaves the set of BVs and becomes a NBV.
I'll show you how to do the EROs step by step.
We change this coef to 1 by dividing 2 for both sides.
This new row is called R1'. 2 divided by 2, we get 1.
1 divided by 2, we get 1/2.
9 divided by 2, we get 9/2.
Then, we remove this coef in R0 by adding 3 times R1' to R0.
It is called R0'.
This will be gone.
This will be changed to -1/2, this 3/2, and the RHS is now 27/2.
Now, we remove this coef in R2 by subtracting R1' from R2.
It is called R2'.
This will be gone.
This will be changed to 3/2, this -1/2, this is 1, and the RHS is now 9/2.
In this tableau, the coef of x1 in R1' is 1, and the coefs in other rows are 0.
So we are done with the EROs and pivoting.
This is a new tableau.
Now the BVs are x1 and s2, and NBVs are x2 and s1.
We set NBVs to 0 and solve for BVs.
The BVs are x1=s2=9/2.
The z value is 27/2.
What actually happened was that we used the pivoting procedure to go from one BFS to a
better adjacent BFS with the largest z value.
This is called an iteration Let's write out this BFS: x1=9/2, s2=9/2,
s1=x2=0, and z=27/2 for this BFS.
Here is the question again: Can the objective function z, which is equal to 27/2 + x2/2
- 3s1/2, be improved by increasing some NBV from its current value of 0 while holding
all other NBVs at 0?
Yes, if we increase x2, the z-value will increase.
So, the current BFS is not optimal yet.
Let's check the tableau.
x2 has the most negative coefficient in R0'.
So, x2 is the entering variable.
Now we need to do the ratio test to find out which row will be the pivot row.
We find out that R2' has the smallest ratio.
So it will be the pivot row.
We need to make x2 a BV in this row.
It means, we should use EROs to make x2 have a coef of 1 in R2' and a coefficient of 0
in all other rows.
This time, you can try it yourself.
I'll just quickly show the results.
We replace R2' by two thirds of R2'.
Now add a half of R2'' to R0'.
Subtract a half of R2'' from R1'.
Finally, this is the updated tableau.
Now the BVs are x1 and x2, and NBVs are s1 and s2.
We set NBVs to 0 and solve for BVs.
The BVs are x1=x2=3.
The z value is 15.
So we used the pivoting procedure to go from one BFS to a better adjacent BFS with the
largest z value.
This is the second iteration.
Let's write out this BFS: x1=3, x2=3, s1=s2=0, and z=15 for this BFS.
Increasing s1 or s2 will not improve z.
So, the current BFS is optimal.
As a general rule, a canonical simplex tableau is optimal (for a max problem) if each NBV
has a nonnegative coefficient in R0.
To sum up, we can use the following steps to solve a maximization LP problem.
Step 0: Convert a LP into a canonical Simplex tableau.
Step 1: Obtain an initial BFS from the Simplex tableau.
Step 2: Determine if the current BFS is optimal by checking if all NBVs have nonnegative coef
in R0.
Step 3: If not, determine the entering variable and which row to pivot on.
The entering variable has the most negative coef in R0.
The pivot row is the row that wins the ratio test.
Step 4: Use EROs to find a new BFS with a better objective value.
Then go back to Step 3 For a minimization problem, we can convert
it to a maximization problem by maximizing the opposite of the objective function.
Okay, that is the simplex method for solving LP problems.
Thanks for watching.