Variable leaving basis in linear programming - when does it happen?

Question

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

1. $$z_r - c_r < 0$$

2. $$z_r - c_r = \min_j (z_j - c_j)$$

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

Answer 1

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

1. $$z_r - c_r < 0$$

2. $$z_r - c_r = \min_j (z_j - c_j)$$

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

Answer 2

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

Answer 3

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

1. There is another variable with a negative reduced cost (or positive if we are maximizing)
2. $\min_i\{\frac{b_i'}{a_{ir}'}|a_{ir}'>0\}=\frac{b_q}{a_{qr}'}=b_q$