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!

That was excellent..i have studied from your videos.

You explained very well !!!!! Beauty with brains 🙂

your videos are excellent, keep sharing them thanks a lot

Thank you! Helped for my exam.

you're amazing

really helpful.. thanks a lot

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

all Z values would be all zero and Cj-Zj value would be 1, 2 how ur Z value come to be -1 and -2???

very clear explaination

Can you please explain the types of degeneracies with examples

keep doing your videos are awesome

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.

Thanks to be done

Thanks, lifesaver

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.)

What happens when an artificial variable is in tie?

can you please become my prof. ! 😭❤️thank you very much !!

Thank you so much

Thank you .your lecture was my perfect search i got.

which software do you use ?

can we solve such problems by any other methods?

Nice work, I come to understand the concept very clearly!!

really great teaching many new things i have learnt from here

it's bland rules the substitute show "blonde" lol

Thanks

Oh great, finally I understand the degeneracy.. Great work!! Many thanks.

<3

You're a lifesaver.

Very well explain and demonstrated! Thank you!

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.