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


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.

  • 2
    $\begingroup$ Perhaps 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. $\endgroup$ – Mike Spivey Sep 23 '11 at 15:55
  • $\begingroup$ @ 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." $\endgroup$ – Tav Sep 23 '11 at 16:22
  • 1
    $\begingroup$ @Tav: So the question is really about characterizing when a variable that enters the basis leaves it in the next iteration? $\endgroup$ – Mike Spivey Sep 23 '11 at 16:55
  • $\begingroup$ Yes, 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. $\endgroup$ – Tav Sep 23 '11 at 17:39
  • 1
    $\begingroup$ @Tav: I suspect it may be hard to characterize in a clean way. Could you give the book and page number for your reference? $\endgroup$ – Mike Spivey Sep 23 '11 at 20:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.