4
$\begingroup$

How can I prove that in the simplex method, a variable that has just left the basis cannot re-enter the basis on the very next iteration? The pivoting rule is Dantzig's.

  • 0
    what is the pivot rule?2012-06-14
  • 0
    with danzig rule thanks!2012-06-15

1 Answers 1

4

Assume the problem to be a minimization problem. Then we choose an entering variable only if the coefficient in the objective row of that variable is negative so as to reduce the objective value by increasing the value of the variable (from it's current value).

When a variable leaves the basis, the coefficient in the objective row of that variable becomes non-negative. In the next iteration of simplex, only variables with a negative coefficient can enter the basis. Hence the variable that just left cannot re-enter the basis in the very next iteration.

  • 0
    so the [solution here](https://books.google.com.ph/books?id=Q_Y_ZsuDcoMC&pg=PA127&lpg=PA127&dq=prove+cannot+enter+next+iteration&source=bl&ots=_rtr7ik1zb&sig=csa5MNTeno6A4sy7QW-81VPv8pg&hl=en&sa=X&ved=0ahUKEwibrP_utK_LAhUD7GMKHWkfDocQ6AEIODAF#v=onepage&q=prove%20cannot%20enter%20next%20iteration&f=false) is unnecessarily complicated? the only difference between what you wrote and what i would submit to my professor is symbols. i honestly don't think the proof gets more complicated than that. oh wait, do you think myb we might need to prove2016-03-07
  • 0
    that the variable's $z_j - c_j$ becomes nonnegative in the next iteration?2016-03-07