In the Simplex method, a variable that enters the basis, cannot depart the basis in the very next iteration. Please explain..why so ?
simplex method : Entering Variable
1 Answers
This isn't true. For a counterexample, consider $$\max \text{ } Z = x_1 + 2x_2$$ subject to $$x_1 + 3x_2 + s = 3,$$ $$x_1, x_2, s \geq 0.$$ where $s$ is the slack variable.
The initial basis is $\{s\}$. Using Dantzig's rule for selecting the entering basic variable, we would pick $x_2$, as it gives the largest per-unit increase. Since $x_2$ enters, $s$ must leave. Our new dictionary looks like $$Z = 2 + \frac{1}{3}x_1 - \frac{2}{3}s, $$ $$x_2 = 1 - \frac{1}{3} x_1 - \frac{1}{3} s.$$ Thus we can increase $Z$ by increasing $x_1$. Let $x_1$ enter the basis; then $x_2$ must leave, yielding the optimal dictionary: $$Z = 3 - x_2 - s,$$ $$x_1 = 3 - 3x_2 - s.$$ The point is that $x_2$ entered the basis in the first iteration and left in the second, providing a counterexample to your statement.
-
2Perhaps you meant "In the Simplex method, a variable that *leaves* the basis, cannot *enter* the basis in the very next iteration"? That is true. If so, maybe that should be a separate question. – 2011-09-23
-
0@ Mike Spivey: Thanks for your reply. I guess the question is correct. A variable once inserted into the basis cannot be removed in the next iteration. Further the question says " When can this occur and when is this impossible." – 2011-09-23
-
1@Tav: So the question is really about characterizing when a variable that enters the basis leaves it in the next iteration? – 2011-09-23
-
0Yes, you are right. I guess it has something to do with the criteria which departs the variable from the basis if it has the minimum ratio. Or alternatively, as in the example above, if we start increasing a non basic variable from 0 to a positive level, the first basic variable that becomes zero ( leaves the basis) is the one which has the smallest coefficient. I am confused how do we characterize this. – 2011-09-23
-
1@Tav: I suspect it may be hard to characterize in a clean way. Could you give the book and page number for your reference? – 2011-09-23
-
0Thanks a lot for your help. This is an exercise problem in the book "Linear Programming and Network Flows, Bazaara, Jarvis and Sherali. Page 131, Ex 3.38. – 2011-09-23