# In the simplex algorithm, when might some a variable leave a basis?

 -1 In the simplex algorithm in linear programming, what are conditions for a variable to leave a basis (not necessarily basis for the/an optimal solution)? I'm supposed to list as many sufficient and necessary conditions as possible for some basic variable $$x_q$$ which could be slack, artificial or non-slack and non-artificial. Let $$x_q$$ be the s-th basic variable. Suppose the s-th row of some current simplex tableau has 1 in the column of $$x_q$$ and 0's everywhere else. Under what circumstances, if any, might $$x_q$$ leave the basis? Can any of the values in the s-th row of the tableau ever change? Well since it's a basic variable, I'm guessing the $x_q$ column already has 0's everywhere except in the s-th row. Now, the $x_q$ row has 0's everywhere in the column of $x_q$ like: This is in the context of the Big M Method and artificial variables. I'm not quite sure what the relationship is exactly, though. What I tried: $$x_q$$ leaves if there is some non-basic variable $$x_r$$ that enters because $$z_r - c_r < 0$$ $$z_r - c_r = \min_j (z_j - c_j)$$ $$\frac{b_q'}{a_{qr}'} = \min_i \{\frac{b_i'}{a_{ir}'} | a_{ir}' > 0 \}$$ Is that right? Any other sufficient or necessary conditions? What is the relevance of the 0's in the row? Also, how do I approach the last question? I have no clue. asked 07 May '16, 07:21 BCLC 8●3●12 accept rate: 0%
Be the first one to answer this question!
 toggle preview community wiki

### Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "Title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported

Tags:

Asked: 07 May '16, 07:21

Seen: 7,564 times

Last updated: 07 May '16, 07:21

### Related questions

OR-Exchange! Your site for questions, answers, and announcements about operations research.