In this video, we'll talk about how to solve the dual LP problem directly using the dual
simplex method.
In the previous videos, we talked about how to solve the dual if we already know the optimal
solution to the primal.
We can use three methods.
Method 1, we can use this formula to calculate the optimal solution to the dual.
Method 2, we can identify the optimal solution to the dual by observing the optimal primal
tableau.
Method 3, we can use complementary slackness to find the optimal solution to the dual.
What if we don't know the optimal solution to the primal?
In that case, we cannot use these three methods.
We can use another method called the dual simplex method to directly solve the dual
problem in the standard form.
The dual simplex method has three steps.
In Step 1, we need to reformulate the dual problem so it will be a maximization problem,
with non-negative Row 0, and non-positive right hand side (RHS).
In step 2, we need to choose the most negative BV as the leaving variable and the row will
be the pivot row.
Then, compute the ratio for each NBV that has a negative coefficient in the pivot row.
The ratio is the coefficient of a NBV in R0 over the coefficient of that NBV in the pivot
row.
After that, we choose the variable with the smallest absolute ratio as the entering variable.
We use Elementary Row Operations (or EROs) to make the entering variable a BV in the
pivot row.
In the dual simplex method, we determine the leaving variable first then the entering variable,
which is different from the regular or primal simplex method.
In Step 3, If there is any constraint with a negative RHS and each variable has a non-negative
coefficient, then the dual LP problem is infeasible, and stop
If the RHS of each constraint is non-negative, then an optimal solution is found and stop.
Otherwise, return to Step 2.
Let's illustrate the dual simplex method using this example.
This is a dual problem in the standard form.
It is a minimization problem.
All the constraints are ≥ the RHS.
All the variables are ≥ 0.
The first step of the dual simplex method is to reformulate the dual problem.
We change this problem to a max problem by taking the opposite of the objective function
and give it to v. In the canonical form, each variable has a
non-negative coefficient in Row 0.
We need to introduce two excess variables, e1 and e2 to make these two equality constraints.
Now, the RHS of both constraints are positive, we need to make them non-positive by multiplying
-1 for both sides.
This is the updated canonical form.
Let's write this in a tableau.
Now, let's find the BVs.
They are the variables with a coefficient 1 and appear only in one row and not other
rows.
So the BVs are e1 and e2.
Remember, v is not a BV.
It represents the objective function value.
But by convention, we just put it in this column.
All other variables are NBVs.
Let's set the NBVs to 0 and solve for the BVs.
This is what we get.
Now, we need to check if this tableau is optimal or not by checking if the RHS of each constraint
is non-negative.
We find that the RHS of both constraints are negative.
So it's not optimal yet.
We need to choose the most negative BV as the leaving variable, which is e2, and this
row will be the pivot row.
Let's compute the ratio for each NBV that has a negative coefficient in the pivot row.
The ratio is the coefficient of a NBV in R0 over the coefficient of that NBV in the pivot
row.
1 divided by -2 is -1/2, 2 divided by -1 is -2.
After that, we choose the variable with the smallest absolute ratio as the entering variable,
which is u1.
We use EROs to make this entering variable have a coefficient 1 in the pivot row and
make it disappear in all other rows.
This is the new tableau.
Let's solve for the BVs.
They are e1 and u1.
Now, we need to check if this tableau is optimal or not by checking if the RHS of each constraint
is non-negative.
We find that the RHS of this constraint is still negative.
So it's not optimal yet.
We need to choose the most negative BV as the leaving variable, which is e1, and this
row will be the pivot row.
Let's compute the ratio for each NBV that has a negative coefficient in the pivot row.
The ratio is the coefficient of a NBV in R0 over the coefficient of that NBV in the pivot
row.
1/2 divided by -3/2 is -1/3.
1/2 divided by -1/2 is -1.
After that, we choose the variable with the smallest absolute ratio as the entering variable,
which is u3.
We use EROs to make this entering variable have a coefficient 1 in the pivot row and
make it disappear in all other rows.
This is the new tableau.
Now, let's solve for the BVs.
They are u3 and u1.
Now, we need to check if this tableau is optimal or not by checking if the RHS of each constraint
is non-negative.
They are both positive.
So, this tableau is optimal.
The optimal solution to the dual problem is w=-v=10/3, u1=10/3, u3=2/3, u2, e1, and e2
are 0.
Now, we know that each LP problem can be formulated from two perspectives, primal and dual.
We can solve the primal using the primal simplex method, and solve the dual using the dual
simplex method.
The question is, when should we solve the primal and when should we solve the dual?
For a LP problem, if the number of basic variables is much smaller than the number of constraints,
the problem is highly likely degenerate.
Therefore, the answer to the question is, if the primal is degenerate, it's better to
solve the dual problem, and vice versa.
Okay, thanks for watching.