Simplex algorithm : Which variable will go out of the basis?

Question

I want to use the simplex algorithm.

At the first step we want to determine which variable will enter the basis. To do that we pick the smallest negative number of the last row of the simplex table.

Then we want to determine which variable will go out of the basis. For that we have to compute the last column of the simplex table, which is the column of the right side divided by the elements of the column that we picked in the previous step. We chose that the smallest positive element of that column. If there are also zero elements, is then that one the element that we pick or do we compare only the elements $>0$ ?

Answer 1

Suppose $a_{ij^*} \ \forall\ i$ are the elements of the chosen pivot column. And $b_{i} \ \forall\ i$ are the corresponding values of the RHS. As you said you calculate the minimum of the fractions. $b_{i}$ has to be greater or equal $0$. This is always the case if you apply the simplex algorithm correctly. And $a_{ij^*}$ has to be greater $0$. The short notation is

$\min\bigg\{\frac{b_i}{a_{ij^*}}|a_{ij^*}>0\bigg\} $

Since $b_{i}\geq 0$ it follows that $\frac{b_i}{a_{ij^*}}\geq 0$

Answer 2

If you are tired of reading the OP, just read this answer.

Easy-to-read illustration of the question

Let's first recap the steps in the question body by a sample simplex tableau.

\begin{align*} \begin{array}{c|ccc|cc} \small\text{basic var} & * & x_j & * & \overbrace{\small\text{RHS}}^{\text{current BFS: } \\ (y_{10},\dots,\color{blue}{y_{r0}},\dots,y_{n0})} & \small\text{ratio} \\ \hline * & * & * & * & * & * \\ x_{s} & * & y_{sj} & * & y_{s0} & y_{s0}/y_{sj} \\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots \\ x_{t} & * & y_{tj} & * & y_{t0} & y_{t0}/y_{tj} \\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots \\ \color{blue}{x_r} & \color{blue}{*} & \color{blue}{y_{rj}} & \color{blue}{*} & \color{blue}{y_{r0}} & \color{blue}{\underbrace{y_{r0}/y_{rj}}_{\text{2. pick } least\ nonnegative\ ratio \\ x_r\ will \text{ be the leaving variable}}}\\ * & * & * & * & * & * \\ \hline \small\text{obj fct row} & * & y_{0j} & * & \underbrace{y_{00}}_{\small\text{current obj fct val}} \\ & & \small{\text{1. pick } most\ negative \text{ number } y_{0j} \text{ here} \\ x_j\ will \text{ be the entering variable}} \end{array} \end{align*}

N.B. OP says that, in step 2, "the smallest positive element of that [the rightmost] column" is chosen. We are going to see that this is incorrect.

OP's problem

In step $\color{blue}{two}$, if there's a $\color{blue}{ratio\ y_{r0}/y_{rj} = 0}$, should we pick $\color{blue}{x_r}$ as the leaving variable? Or should we only pick $\color{blue}{postive\ ratios}$?

Answer

We should always choose the least nonnegative $\color{blue}{ratio}$, so if there's a row such that its $\color{blue}{ratio\ y_{r0}/y_{rj} = 0}$, we should pick it (or any other row of ratio 0).

Concrete example

This example is taken from an online LP notes.

\begin{array}{r|rrrrr|rr} & x_1 & x_2 & x_3 & x_4 & x_5 & & \text{ratio} \\ \hline x_3 & 0 & \bbox[border:1px solid]{2} & 1 & -1 & 0 & 4 & 2 \\ x_1 & 1 & 1/4 & 0 & 1/4 & 0 & 2 & 8 \\ x_5 & 0 & 1 & 0 & -1 & 1 & 0 & 0 \\ \hline & 0 & -1/2 & 0 & 1/2 & 0 & 4 & \end{array}

If we follow the steps in the questions body, we will choose "the smallest positive element" 2 instead of 0 at the ratio column. After one pivot operation, we'll break the feasibility.

\begin{array}{r|rrrrr|rr} & x_1 & x_2 & x_3 & x_4 & x_5 & \\ \hline x_2 & 0 & 1 & 1/2 & -1/2 & 0 & 2 \\ x_1 & 1 & 0 & -1/8 & 3/8 & 0 & 3/2 \\ x_5 & 0 & 0 & -1/2 & -1/2 & 1 & -2 \\ \hline & 0 & 0 & 1/4 & 1/4 & 0 & 5 \end{array}

So we have to choose the least nonnegative ratio in order to get an optimal solution.

\begin{array}{r|rrrrr|rr} & x_1 & x_2 & x_3 & x_4 & x_5 & \\ \hline x_3 & 0 & 0 & 1 & 1 & -2 & 4 \\ x_1 & 1 & 0 & 0 & 1/2 & -1/4 & 2 \\ x_2 & 0 & 1 & 0 & -1 & 1 & 0 \\ \hline & 0 & 0 & 0 & 0 & 1/2 & 4 \end{array}

Theoretical justification

To justify this choice of ratio, first note that in the RHS $y_{i0} \ge 0 \forall i \in \{1,\dots,n\}$ since the current basic feasible solution (BFS) is nonnegative.

To describe the properties of a leaving variable, we denote $x_r$ as the leaving variable for the rest of this solution.

Before calculating the $\color{blue}{ratio\ y_{r0}/y_{rj}}$, we have to make sure that it's defined. Therefore, the ratio is calculated only when $y_{rj} > 0$ or $y_{r0} = 0$ with $y_{rj} \ne 0$. (If the pivot $y_{rj} < 0$, then the new BFS will have $y_{r0}/y_{rj} \le 0$ at one of its components. Unless $y_{r0} = 0$, we'll get a contradiction.)

We then proceed to the calculations for the new BFS. If $\color{blue}{y_{rj}}$ is chosen as a pivot, it's clear from the above tableau that the new RHS are $$(\dots, y_{s0} - \frac{y_{sj}}{\color{blue}{y_{rj}}}\color{blue}{y_{r0}},\dots, y_{t0} - \frac{y_{tj}}{\color{blue}{y_{rj}}}\color{blue}{y_{r0}},\dots, \color{blue}{\frac{y_{r0}}{y_{rj}}},\dots )$$

Each component above is nonnegative due to feasibility. For any current non-leaving basic variable $x_s$

$$ y_{s0} - \frac{y_{sj}}{\color{blue}{y_{rj}}}\color{blue}{y_{r0}} \ge 0 \iff \frac{y_{s0}}{y_{sj}} \ge \frac{y_{r0}}{y_{rj}}\stackrel{(*)}\ge0.$$

Hence we should choose the least nonnegative ratio.

Note: (*) is true due to our choice of pivot element $y_{rj}$.