Simplex Method : Entering Variable

Question

In the Simplex method, a variable that enters the basis, cannot depart the basis in the very next iteration. Please explain..why so ?

Answer 1

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.