13
$\begingroup$

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:

enter image description here

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?

$\endgroup$
5
  • 1
    $\begingroup$ If there is a non basic variable $x_r$ such that $z_r-c_r=0$ (and all others are $< 0$) and point 3 (the one about the min ratio) is satsified 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. $\endgroup$ Commented May 7, 2016 at 10:55
  • 2
    $\begingroup$ I am not clear why you are insisting that the $q$th row will have all but one entries $0$. $\endgroup$ Commented May 7, 2016 at 10:56
  • $\begingroup$ @Shahab 1 thanks! ^-^ post as answer? 2 re 'I am not clear why you are insisting that the $q$th row will have all but one entries $0$.' --> 'Suppose the s-th row of some current simplex tableau has 1 in the column of $x_q$ and 0's everywhere else.' ? I mean that's in the problem. You mean you don't think it's relevant? $\endgroup$ Commented May 7, 2016 at 11:15
  • $\begingroup$ @Shahab Did you mean 'and all others are $\color{red}{\ge}0$'? Or $<0$ but for $c_r - z_r$ rather than $z_r - c_r$? $\endgroup$ Commented May 7, 2016 at 11:40
  • 2
    $\begingroup$ Yes I meant all other $z_r-c_r\ge 0$ (assuming the problem is a max problem), And yes, I see no reason why the $q$th row should be what you say. $\endgroup$ Commented May 7, 2016 at 16:32

3 Answers 3

Reset to default
3
+200
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Thanks a million fredq! ^-^ Any idea how this is related to the Big M Method? Or artificial variables? $\endgroup$ Commented May 18, 2016 at 18:00
  • 1
    $\begingroup$ no idea. As I said, the situation described corresponds to a constraint $x_q = b_s$ so the variable can be removed from the problem. It may help if you provide more details on the context. Why do you think big M and artificial variables are important? $\endgroup$ Commented May 18, 2016 at 18:19
  • $\begingroup$ Hey actually I just realised. Big M Method can be used when an LP problem has an equality constraint and no slack variables right? The problem is from chapter 2 here $\endgroup$ Commented May 20, 2016 at 19:10
  • $\begingroup$ Wait you said column of $x_q$. You mean row of $x_q$? I mean if $x_q$ never leaves the basis then the column of $x_q$ of course never changes? $\endgroup$ Commented May 20, 2016 at 19:11
2
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ Thanks Shahab. ^-^ This doesn't answer everything, but I guess it's better than nothing $\endgroup$ Commented May 7, 2016 at 16:43
  • $\begingroup$ I edited my post... $\endgroup$ Commented May 13, 2016 at 16:43
  • $\begingroup$ @BCLC: It would be good if you tell the detailed source of these questions. $\endgroup$ Commented May 14, 2016 at 1:29
  • $\begingroup$ Shahab, what do you think about new answer? Also here $\endgroup$ Commented May 18, 2016 at 18:10
1
+100
$\begingroup$

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$
$\endgroup$
3
  • $\begingroup$ Oh thanks Kuifje. Wasnt notified. You mean maximisation? You mean nonpositive reduced cost? $\endgroup$ Commented May 11, 2016 at 22:57
  • $\begingroup$ I edited my post... $\endgroup$ Commented May 13, 2016 at 16:43
  • $\begingroup$ Kuifje, what do you think about new answer? $\endgroup$ Commented May 18, 2016 at 18:09

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.