1
$\begingroup$

Let's say you are in the middle of applying the Simplex Method to an LP problem. You've reached a tableau and by checking the sign of the objective coefficients you decided to insert a variable $a$ to the basic set in the next step and exclude a basic one $b$.

1) Is it possible that in the next step, the variable $a$ will become non-basic again ? 2) Is it possible that in the next step, the variable $b$ can become basic again?

$\endgroup$
2
$\begingroup$

Yes -- both of these can happen.

1) happens all the time -- a variable enters the basis and then leaves it later.

2) can happen if the problem is degenerate. Degeneracy means that a basic variable equals 0. So suppose $b$ is a basic variable but equals 0. So in the next iteration it will be the leaving basic variable (because it already equals 0). Suppose the entering BV is $c$. Then $c$ will equal 0 in the new basis, so the objective function value will not change, so $b$ and $c$ may both have positive coefficients in the first row of the tableau, so $b$ may be chosen as the new entering BV again, even though it has already entered and left the basis. In fact, the algorithm can cycle like this indefinitely, but in practice there are ways to break out of it.

I think that if the problem is not degenerate, then 2) can never happen -- once a BV leaves the basis, it stays non-basic for the rest of the algorithm. But maybe someone with more expertise than I on this can confirm/deny.

$\endgroup$

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.