Special Cases of Linear Programming Problem-Part1:Degeneracy Condition


Hello everyone! This is Mirzaei from Cal
Poly Pomona and I’m back with a series of videos for special cases of simplex
method. In this series of lectures, first I’m going to review the four special
cases that can happen as you are solving a linear programming problem using the
simplex methods. After that, we’re going to dive deeper into each of these cases
with examples and more explanation. So, sometimes, when solving a linear
programming problem with simplex methods we run to some special conditions. These
four special conditions are the ones that are the topic of this lecture. The first
case is when there is a tie when implementing the minimum test. This
condition causes a basic variable in the next table gets the value of 0. In
the context of linear programming problem when a basic variable gets
a value of 0 we call the solution a degenerate solution. So, this is the
First special case. So, typically when you have a tie in the minimum test in
the next table one of your basic variable gets a value of 0 and this
condition is called degeneracy and the solution therefore is called a
degenerate solution. The second condition happens when there is an entering
decision variable. However, there is no exiting decision variable; because you
cannot implement the minimum test; because all the values in the pivot
column are negative or 0. So, you can think about this condition that you’re
solving a max problem and you’re looking for a most negative value in the row of
Z and you can find that value and in your pivot column now you have to
implement the minimum test. However, you’re not able to implement the minimum
test; because all the values in the pivot column are negative or 0 and you
remember that we only implement the minimum test over the positive value of
the pivot column. So, basically you have an entering decision variable to your
basis but you cannot pick anything to exit from the basis. This condition is a
sign for unbounded solution, meaning that you can increase the value of your
decision variables to infinity and satisfy all the problem constraints.
We’re going to explain this condition with more
explanation and examples later on. The third especial condition happens when
there is a non-basic decision variable that has a coefficient of zero in the
row of Z. If you remember, for all the basic variables we had the echelon form
in the simplex table meaning that their value in the row of Z have to be zero.
But that condition is true for basic variable and when you have a non-basic
variable that also has a value of zero and you are in the row of Z that’s a
sign for a special condition, that we call alternative solution. That means
that there is another alternative optimal solution to your problem. We are
going to explain this condition also with examples later. The fourth
special condition that we already explained briefly at the end of the “How
to solve a linear programming problem using the graphical method” video. There
you saw that when there is no intersection between the feasible regions
of your constraint there is no feasible solution for your problem. But how we can
identify that in a simplex table? Typically, if you have reached to the
final table of your Big M method and there is an artificial variable in your
basic variables that’s a sign for an infeasible solution. Also, if you have
reached to the optimal table of your two-phase method in the first phase, and
you have some artificial variables in the basis that their value is not 0,
then you have an infeasible solution in our definition we have to say there is
an artificial variable with positive value in the optimal table of the Big M
or the first phase of the two-phase method. Because, if your artificial
variables are basic and their value is 0, basically they have a degenerate
condition, there might be still a feasible solution to your problem. So,
this condition is called infeasibility condition, meaning that you don’t have a
feasible solution. Now [that] we are briefly familiar with the four conditions that
can happen, let’s explain each condition with further discussion and
and examples. Let’s explain the degeneracy condition with an example.
Suppose you are given a linear programming problem as shown on this
screen. Now, if I want to solve this problem using any of the simplex methods,
because all the constraints are in form of less than or equal, the regular
simplex method is appropriate for this problem. So, first I need to standardize
all the constraints by adding slack variables to them and also I have
to standardize my objective function by bringing all the variables to the
left-hand side and all the constant value to the right-hand side. If you are
not familiar with the simplex method please refer to the video posted
regarding the simplex method and how we can solve linear programming problems
using those methods. Now, first I set up this table. I have five decision
variables x1 x2 plus the slack variables for each constraints and in the initial
table of the simplex all these slack variables are my basic variables. I fill
out this table with the coefficients of decision variables in the constraints
and also I’m going to add the coefficient of objective function in the
row of Z. Now, I have created the first table of the simplex method. Now, since we
are looking at the max problem, I pick the most negative value in the row of Z
and also implement the minimum test by dividing the right-hand side by the value
of the pivot column, which they are all 1 in this case, under x2 everything is
1. We pick the second row because 2 divided by 1 is less than 3 divided by 1
and 2.5 divided by 1. So, we end up picking the second row. Again, I don’t
explain the details of the simplex method as much here because we already
covered those extensively in the videos regarding the simplex method. Now, let’s
move on to the next table by implementing the elementary row
operations. So, in the next table what I want is that this pivot value stays as
one and the rest of the value in the pivot column needs to be transformed to
0. So, let’s move on to the next table by implementing the elementary
Oh operations. OK! Now, we have created a new table. Again, I have a negative value
in the row of Z. So, I have to continue by clicking the column related
to the most negative value. Now, I have to implement the minimum test which I have
to only implement it on one and one-half because these are the only positive
value in the pivot column. So, let’s do this. The minimum test is going to
include dividing 1 by 1 which is equal to 1 and also 0.5 divided by 0.5
which is equal to 1. So, there is a tie in the minimum test when we implemented
here. Typically, when you have a tie in the minimum test is the sign that you
are going to have the degeneracy condition, meaning that we expect that
one of our basic variables in the next table gets the value of zero. Basically,
one of these value in the right hand side in the next table becomes zero. So,
when there is a tie in the minimum test which variable do we choose? There is a
rule that we have to go with the variable that has a lower index between
S1 and S3 the index of S1 is 1 and index of S3 is 3 so we have to go with
the variable that has a lower index. So, we go with S1. I explain about this rule
further in few minutes. So, we pick S1 and implement the elementary row operation
and we go to the next table. Now, in the next table as you see one of your basic
variable gets a value of zero and that is called a degenerate solution; because
when a basic variable gets a value of zero we call that condition a degenerate
solution. Typically, we don’t expect to see a basic variable with a value of 0. You
know already, that for all the variables that we don’t see in the basis here we
know that they are 0. For example, we expect our S2 and S1 to have the value
of 0, because there are non-basic. But now we have S3 that is a basic and has a
value of 0. So it’s a kind of like a special condition. Sometimes degeneracy
condition causes you get a stuck in a loop,
meaning that the same solution gets repeated over and over again. One way to
avoid that is to follow the blondes rule the one that we mentioned earlier that
we pick the variable that its row has a lowest number. Now, let’s say if I have X1 and S1 which one should I pick when I have a tie in minimum test. In this
situation you can think about S1 as the continuation. So, this is a different
notation that we have used if you had used the same notation for S’s they
actually would be X3, X4, and X5. The reason that we used S’s and not X’s is
just to understand that these S are not the main variables that we have in our
problem but between S1 and X 1 you have to pick X1 because X’s are always
before S’s. So, between X and S you always go with X’s if you have a tie and
between X’s you always go with the one with the lower index. Among the S’s
again you go with the one with the lower index. But if you have a mixed pool
of X’s and S’s you go with picking X’s in your minimum test. Like here, if I
had S1 and X2, the tie was between these two, I should have picked X2
because S1 is basically X3 you can think about it as X3 in this sense. Now,
let’s look at the graphical representation of a degenerate solution
and get a kind of understanding that what happens in a degenerate solution
and why sometimes we get a stuck in a loop when we solve a linear programming
problem with the degeneracy conditions Again, this is the problem that we have. I
pick two points for the two dimensional lines and one point for one dimensional
line that we have and plot them here. Now, what happens here in the very first
table of the simplex all the S’s are positive and X’s are non-basic variable
here. All the X’s here are 0, so basically X 1 and X 2 are 0 so we are at the
center of the coordinate system. So, in the first one I can say X1=X2=0
and this is a center of the coordinate. In the second table, we have X2 equal to 2 and X1 is a non-basic variable so X1=0. So, we have the X1 equal to 0 and X2 equal to 2. So, that’s
the second point that we are moving on in the simplex and let’s look at the
next table of the simplex where X1 is equal to 1 and X2 is equal to 2. So,
let’s show these points that we found from our table and our graph and see how
our simplex table is moving from one corner to the next one.
In the very first table, X1 and X2 are equal to 0 so we are at the center of
the coordinate. Then in the next table, we move to the point X1=0 and X2=2, which
is this point here and then in the next round
we go to this point here. But then look at this point. Do you see any specific
condition in this point here? If you look at this picture carefully, there are
three lines passing through a point in a two dimensional space. Typically, having
two lines is enough for us to find that intersection but right now we have three
ways of finding that corner point basically we have a combination of two
out of three. Because we need to lines out of the three lines to find that
intersection points. So, we have three way of finding that intersection point. That
means one of your constraint basically is extra at that point to find the
intersection point and that’s why one of your decision variables gets a value of
0. You can kind of intuitively get a sense of why sometimes you get a stuck
in a loop. Because there are 3 ways that you can find that corner point. Sometimes
your simplex table repeats all those possible combination and then therefore
you get stuck on the same corner over and over again. In general, you see that
in this case more than two lines are passing through a corner point in a two
dimensional space. So you have three lines one is extra so that causes a
degeneracy condition to happen and how we avoid getting stuck in a loop when
there is a tie in a minimum test we choose the row with the lowest numbered
variable in the basis. So, basically when you have a tie
you pick the variable with the lower index number. Between X1 and X2 for
example you pick X1 between X1 and s2 you pick X1, because you can think about
S2 here as X4 also between X2 and S1 again you pick X2. So, X’s over S’s but
if you have multiple S’s. For example, S1 and S2, you pick S1, the one
that has the lower index. In this example, the degeneracy condition happens at the
corner point that happens to be the optimal solution. However, if the
degeneracy condition happens in one of the corner point on the way of getting
to the optimal corner point. Then, we might stuck in a loop and the Bland’s
rule will be instrumental to help us to skip the loop. With this our lesson
is concluded please refer to your blackboard for your assignments. Thank
you!

30 Comments

  1. I love your videos. I don't usually leave comments but your explanations are really nice, really thorough. I've personally watched this very video over 4 or 5 times just to refresh what I've learned. Thank you so much

  2. thank you for such informative video, I would like to know if I used a software, am going to get the same results in catching the specail cases,or the soft wares are not accurate sometimes.

  3. I can imagine the amount of hard work you had put in to make these awesome lectures!!
    And that hard work should be appreciated!!
    So on that note Thank You for this awesome Linear Programming playlist. Everything about the lectures is good(pace,content, explaination etc.)

  4. Good explanation! But I have an issue with how you applied the Bland's rule and how I read it on Wikipedia (https://en.m.wikipedia.org/wiki/Bland%27s_rule). The Wikipedia version states that when choosing the column for pivoting (in the Z function), we should pick the "entering variable" with the lowest index. Sounds like in tableau 1, we should've picked -1( or X1) instead of -2( or X2). In other words we should not go by the most negative variable. Am I right or I am missing something? I would be happy if you helped get a good grasp on that one.

Leave a Reply

Your email address will not be published. Required fields are marked *