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