In this video, I'll talk about some special cases of LP problems and how to identify their
characteristics in the simplex tableau.
We may face the following cases of LP problems.
Case 1: Some LP problems may have a unique optimal solution.
Case 2: If a LP problem has two or more optimal extreme points, all the points that are on
the line between these two points are also optimal.
So the problem has an infinite number of optimal solutions.
Case 3: Some LP problems may be Infeasible.
Case 4: Some LP problems may be unbounded.
That means they can take arbitrarily large z-values for max problems or arbitrarily small
z-values for min problems.
Case 5: Some LP problems are degenerate, which means they have redundant constraints that
can be removed without affecting the feasible region.
When we use the simplex method to solve these LP problems, we may notice some special patterns
in the simplex tableau.
It should be noted that the examples I show in this video are all maximization problems.
For a minimization problem, we can convert it into a maximization problem by maximizing
the opposite of the objective function.
This is a LP problem with two variables, and we can solve it using the graphical method.
The optimal solution is a single point (3, 3).
The optimal z value is 15.
This is the corresponding optimal tableau.
We find that all nbvs have positive coefs in R0.
It turns out that this rule is generally applicable to all LP problems with a unique optimal solution.
If we modify the objective function, and change this coefficient from 3 to 4, then we can
find in this figure that we will have an infinite number of optimal solutions between point
(3,3) and point (4.5,0).
Now, let's check this optimal tableau.
It corresponds to this point in the figure.
We have a NBV with a coef of 0 in R0.
It is an indicator that we may have another optimal solution.
Let's proceed one more step anyway, using x2 as the entering variable.
We find that this is also an optimal solution.
It corresponds to this point.
It has the same z value.
We know that if two points are optimal, then any point on the line segment joining these
two points will also be optimal.
Therefore, we have an infinite number of optimal solutions.
A LP problem may be infeasible.
For a maximization problem, this situation does not occur when all the constraints are
≤ with non-negative right-hand side because all slack variables provide an obvious feasible
solution.
This situation occurs in the Big-M Method and the Two-Phase Method in which artificial
variable are used.
In this example, the RHS of the first constraint is 4, and the second constraint has a >= sign.
If in the optimal tableau, at least one artificial variable is positive like this, then the LP
problem is infeasible.
This is a case that the LP problem is unbounded.
The constraints are two >= constraints.
This is the feasible region and the z value can be infinitely large.
When we do the simplex iterations, at some point the entering variable has a nonpositive
coef in each constraint so we cannot proceed.
This is the indicator that the problem is unbounded.
The last case we will talk about is called degeneracy.
It is caused by one or more redundant constraints and may cost the simplex method extra iterations.
A redundant constraint is a constraint that can be removed without changing the feasible
region.
In this example, the last constraint x1<=4.5 is a redundant constraint.
We can see that from this figure, the feasible region will not change if we remove this constraint.
Formally, a LP problem with n decision variables is degenerate if at least n+1 constraints
(including the sign restrictions) are binding at an extreme point.
In this case, we have n=2 variables, and there are three constraints that are binding at
this point.
That is, it is an intersection of three lines, this one, this one, and this one.
Let's see what will happen during the simplex iterations.
This is the initial simplex tableau.
The initial BFS corresponds to this extreme point in the figure.
x1 is the entering variable because it has the most negative coef in R0.
After we calculate the ratio, we find that we have a tie.
This is an indicator that this might be a degenerate LP problem.
We break the tie arbitrarily and now we pick this row as the pivot row.
This is the updated tableau.
It corresponds to this point.
We moved from the initial extreme point here to this point.
The z-value is increased from 0 to 27/2.
Note that we have a BV equal to 0.
This is another indicator that the LP is degenerate.
x2 will be the entering variable, and this row will be the pivot row.
This is the updated tableau.
It means, we moved from this point to itself.
The z-value didn't improve.
It is still 27/2.
We still have a BV equal to 0.
Now we definitely know we have a degenerate LP problem.
Let's continue with the simplex iterations.
s3 will be the entering variable, and this row will be the pivot row.
This is the updated tableau.
It corresponds to this point.
It means, we moved from this point to this point.
The z-value is improved from 27/2 to 15.
This is the optimal tableau and we have a unique optimal solution because all the coefs
of NBVs are positive.
Therefore, degeneracy could cost the simplex method extra iterations.
If a LP problem has many degenerate BFSs, then the simplex algorithm is often very inefficient.
In this example, we are lucky and continuing the process leads to the last optimal tableau.
In some problems, degeneracy can cause the solution to cycle indefinitely, and the simplex
algorithm may fail to reach the final optimal solution.
Fortunately, some degenerate LP problems have a special structure that enables us to solve
them by methods other than the simplex.
Okay, we talked about some special cases of LP problem solutions and how to identify them
in the simplex tableau.
Thank you for watching.