Variable leaving basis in linear programming - when does it happen? 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.
Edit: It looks like one of the constraints is the original (maximisation?) problem has something like
$$x_2 = 10$$
or
$$x_4 = 0$$
I guess the relationship would be Big M Method applies for equality constraint?
But I think an equality constraint like for example
$$x_4 = 0$$
would lead to
$$x_4 + x_5 = 0$$
with $z$ being replaced with $z' = z - Mx_5$
So
$$x_4 + x_5 = 0$$
doesn't exactly lead to a row of all but one zero entry? There are two non-zero entries?

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?

Edit:
I guess an example would be something like
\begin{bmatrix}
2 & 0 & 10\\ 
0 & 1 & 0\\ 
5 & 0 & 6
\end{bmatrix}
If $x_q$ leaves and then $x_r$ enters where $x_q$'s column is the second column, and then $x_r$ is, say, the first column. What would be the EROs?
$$\color{red}{\frac{1}{2}R_1 + R_2 \to R_2}$$
$$-2R_2 + R_1 \to R_1$$
$$-5R_2 + R_3 \to R_3$$
I have never had to make $\color{red}{\text{a zero entry to a non-zero number}}$ in the simplex method.
I find this suspicious. Should I not?
Perhaps the elements in the row can never change because $x_q$ can never leave?
Or $x_q$ can never leave because row can never change?
 A: 1. Lets show $x_q$ can't leave the basis
Intuitively
If the row $s$ contains all zeros except in the column of $x_q$, it means the problem contains a constraint of the type
$$x_q = b_s$$
In that case, only solutions with $x_q = b_s$ are feasible, so the variable $x_q$ never leaves the basis.
Mathematically

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

It is true, assuming the problem is about maximization.
Now, lets apply this to the case where the row corresponding to $x_q$ contains only zeros except in the column corresponding to $x_q$. You have 
$$z_q = 1\times c_q = c_q$$ 
So $z_q- c_q = 0$, which is normal since $x_q$ is a basic variable.
Now, let $x_r$ be the entering variable. From the asumptions of the problem, we know that $a'_{qr} = 0$. This implies  
$$\min_i \{\frac{b_i'}{a_{ir}'} | a_{ir}' > 0 \} \neq \frac{b_q'}{a_{qr}'}$$
This means the variable $x_q$ never leaves the basis.

2. Let's show row $s$ can't change
Intuitively
Lets call $x_r$ the entering variable, and $x_t$ the exiting variable.
Now lets see how the pivot will affect the column of $x_q$. We have 
Line $i$ of the new tableau is a linear combinaison of lines $i$ and $t$ of the old tableau. Since these value are 0 for the column of $x_q$, the column of $x_q$ will never change. The reduced cost of variable $x_q$ will always be 0 and $x_q$ will never leave the basis.
Mathematically
Lets call $x_r$ the entering variable, and $x_t$ the exiting variable.
When making the pivot for row $s$, the formulae is (assuming $a'_{ij}$ is the new value in the tableau and $a_{ij}$ is the old value.
$$a'_{si} = a_{si} - \frac{a_{qr}}{a_{tr}} a_{ti}$$
Since $a_{qr} = 0$, the row $s$ stays unchanged.
A: If there is a non basic variable $x_r$ such that $z_r−c_r=0$ (and all others are $\ge 0$) and point 3 (the one about the min ratio) is satisfied one can still force $x_q$ to leave and $x_r$ to enter. This will not improve the optimal value but give an alternative solution
A: Assume we are dealing with a minimization problem. Any variable $x_r$ with negative ($\le 0$) reduced cost can enter the basis. Once this is done, another variable has to leave the basis. You can choose any variable $x_i$ such that 
$$
\frac{b_i'}{a_{ir}'} \ge 0,
$$
i.e. any variable such that if $x_r$ replaces $x_i$, the solution remains feasible. Typically we choose the variable that minimizes $\frac{b_i'}{a_{ir}'}|a_{ir}'>0$, because it gives you the best possible value for the entering variable, before the solution becomes infeasible.
So in this particular case, $x_q$ will leave the basis if and only if 


*

*There is another variable with a negative reduced cost (or positive if we are maximizing)

*$\min_i\{\frac{b_i'}{a_{ir}'}|a_{ir}'>0\}=\frac{b_q}{a_{qr}'}=b_q$

