Questions about the Simplex algorithm

[aymane]

Hello everyone, I have three questions about the simplex algorithm if you have any idea:

1. Why do we choose the smallest ratio while choosing the leaving variable?
2. Why the pivot can not be negative?
3. How do we know there is more than one optimal solution?

 

[Deleted member 4993]

Hello everyone, I have three questions about the simplex algorithm if you have any idea:

1. Why do we choose the smallest ratio while choosing the leaving variable?
2. Why the pivot can not be negative?
3. How do we know there is more than one optimal solution?

These are questions that require YOUR thoughts.

What does your textbook say? In the absence of that:

Have you tried to use Google to investigate the question? What did you find? We will join in - but you need to lay the foundation! For example, how would you define a "leaving variable"?

 

[aymane]

These are questions that require YOUR thoughts.

What does your textbook say? In the absence of that:

Have you tried to use Google to investigate the question? What did you find? We will join in - but you need to lay the foundation! For example, how would you define a "leaving variable"?

Hi, thank you for your answer. I actually was searching the web for the past week about these questions and I sent my professor an email and he didn't respond. These are just my questions they are not a homework, I truly wanna understand this, I know we'll choose the smallest positive ration, but why?
For the third one my textbook says it's when we can't find a valid candidat to leave the base, but I couldn't understand the explanation as why is that.

For your question, the leaving variable is a variable that will be equal 0 after it leaves and will be replaced by the entering one, I am thinking that this will have something to do with why do we choose the minimum but I'm not sure what it is. If you have a lesson that I can read and figure it myself it'd be much appreciated!

Hi

 

[Steven G]

Instead of searching online try to figure this out yourself. See what happens when you don't obey these rules. Why did it not help? Why doing the way your textbook shows is better. Experiment, experiment and then experiment some more. The more you do on your own the better you'll understand things.

 

[Cubist]

I've seen the Simplex algorithm given to students (my own two children!) without an explanation of how it works. It's fairly easy to learn the required steps without knowing how it works. (Many people can drive a car without knowing how an engine works.) I suspect that you, @aymane , are in this very position. Perhaps your professor is reluctant to give you extra material that will never appear on your exams. It's also possible that your prof doesn't actually know how it works, they might just know how to perform the algorithm themselves!

I very much like that you're interested to know how it works. IMO this shows that you'll have a good future in maths!

I used to have a good understanding of its functionality but I've forgotten. I suspect it wouldn't take me too long to re-learn it. However I'd recommend that you follow the tips from @Subhotosh Khan and @Jomo to see if you can work it out for yourself (as a hobby, since it probably isn't required for your course). If you're stuck then tell us the name of your textbook, and have a go at explaining it yourself.

 

[aymane]

Instead of searching online try to figure this out yourself. See what happens when you don't obey these rules. Why did it not help? Why doing the way your textbook shows is better. Experiment, experiment and then experiment some more. The more you do on your own the better you'll understand things.

Well, tomorrow is my exam so I really didn't have much time to try to figure it myself haha. But I think I eventually did.

1. This one was the hardest one to figure out, it's because the ratio is actually the "future" value of the entering variable, when the entering variable is equal to the ratio the leaving variable will be equal to 0. The ratio is also the maximum value that the entering variable can take before it stops respecting the constraint, so if the entering variable > the corresponding ratio, then the sorting variable candidate will be negative which can't be true. that's why we choose the smallest one because this assures us that all of the constraints will be respected.

2. Pivot can't be negative because it'll cause us to obtain a negative ratio, as I said the ratio is the "future" value of the entering variable, and all variables are nonnegative.

3. "Under Simplex Method, the existence of multiple optimal solutions is indicated by a situation under which a non-basic variable in the final simplex table showing optimal solution to a problem, has a net zero contribution." This one is just copy pasted from the internet, but I understand it.

 

[aymane]

I've seen the Simplex algorithm given to students (my own two children!) without an explanation of how it works. It's fairly easy to learn the required steps without knowing how it works. (Many people can drive a car without knowing how an engine works.) I suspect that you, @aymane , are in this very position. Perhaps your professor is reluctant to give you extra material that will never appear on your exams. It's also possible that your prof doesn't actually know how it works, they might just know how to perform the algorithm themselves!

I very much like that you're interested to know how it works. IMO this shows that you'll have a good future in maths!

I used to have a good understanding of its functionality but I've forgotten. I suspect it wouldn't take me too long to re-learn it. However I'd recommend that you follow the tips from @Subhotosh Khan and @Jomo to see if you can work it out for yourself (as a hobby, since it probably isn't required for your course). If you're stuck then tell us the name of your textbook, and have a go at explaining it yourself.

Thank you! I eventually I got it. I think my professor understands it pretty well haha and it's surely required for my course because after looking at his past exams it seems that he asks similar questions, I didn't know this before asking him tho, It was just out of curiosity, so I think he didn't wanna answer me to make me search more on my own.