Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
what is the pivot rule? –  tulasi Jun 14 '12 at 16:00
    
with danzig rule thanks! –  iassael Jun 15 '12 at 14:38

1 Answer 1

up vote 1 down vote accepted

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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