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 𝒂 basic one 𝒃.

a. Is it possible that in the next step, the variable 𝒂 will become non-basic again?

b. Is it possible that in the next step, the variable 𝒃 can become basic again?

$\endgroup$
0
$\begingroup$

The answer to (a) is yes. Consider the LP in the image below, whose feasible region is the triangle ABC. The decision variables are $x$ and $y$, and the slack/surplus variables are $s_1$ and $s_2$. 2Dlinear program The simplex method starts at A and (after pivoting an artificial variable out of the basis) has $x$ and $s_2$ as the basic variables. Since the rate of increase of $f$ is faster along edge AB than along edge AC, the next pivot moves from A to B, removing $s_2$ from the basis and adding $y$. The final pivot moves from B to the optimal vertex C, removing $y$ from the basis and adding $s_1$.

The answer to (b) is trickier. I don't think this can happen at a degenerate corner, and it cannot happen at a nondegenerate corner. I'll just give a hint to the proof in the absence of degeneracy: if it did happen, you would be moving along an edge of the feasible region that contained three distinct vertices, which contradicts the definition of a vertex.

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