Proof of the ratio test for dual simplex

Question

I am familiar and know the proof of the ratio test for normal simplex algorithm (with this I mean the test used to know which variables enter and leave the basis). I also know the ratio test for dual simplex but do not know how to prove it. Can anyone give me a reference or a proof of this fact? Thanks

Answer 1

Consider the following linear optimization model:

$$ \min \, z=c^Tx \\ \text{s.t.} \, Ax=b, x \ge 0$$

Let $B$ be a subset of the columns of $A$ that is invertible, i.e., it can be used to find a solution for the system $Ax=b$, which is called basic solution.

Without loss of generality assume that $A=[N, B]$ and $x^T=(x_N^T, x_B^T)$. Then, $B^{-1}b$ is a solution for $Ax=b$, defined as a basic solution, which is not necessarily a Feasible Basic Solution (FBS), which is defined as a basic solution $x$ that satisfies both conditions $Ax=b, x \ge 0$. Then, considering

$$B^{-1}Ax=B^{-1}b \Leftrightarrow B^{-1}Nx_N+x_b=B^{-1}b,$$

a general solution for $Ax=b$ is given by

$$ x_B=B^{-1}b-B^{-1}Nx_N, \\ x_N \in \mathbb {R}^{n-m}.$$

Using this and defining $c^T=(c_N^T,c_B^T)$, the objective can be rewritten as

$$c^Tx=c_B^TB^{-1}b-(c_B^TB^{-1}N-c_N^T)x_N=c_B^TB^{-1}b-\sum_{j=1}^{n-m}(z_j-cj)x_j$$

where $j$ is used for indexing non-basic variables, and where $N=(a_1,...,a_{n-m})$, $x_N^T=(x_1,...,x_{n-m})$, and $z_j=c_B^TB^{-1}a_j, j=1,...,n-m$.

In the primal simplex method, we start with a $B$ that generates an FBS, and we keep improving the objective function, while controlling the feasibility of the next basic solution.

In the dual simplex method, we start with a $B$ that generates an Optimal Basic Solution (OBS), defined as the one for which

$$z_j-c_j=c_b^TB^{-1}a_j -c_j \le 0, j=1,...,n-m.$$

Then, we continue searching for the next $B$ such that it also generates an OBS with less infeasibility. Here, we first decide which basic variable needs to leave the base and then find the entering variable; in the dual simplex, the leaving variable is the one that is already negative and has the largest absolute value among the basic variables with negative values in the vector $B^{-1}b$. For example, if $B^{-1}b=(-5,-1,2,4)^T$, we pick the first variable as the leaving variable. WLOG, let the first variable is decided to leave.

Next, we need to decide about the entering variable among $x_1,...,x_{n-m}$. This should be done in a way that after entering the new basic variable, the optimality is kept, that is, all new $z_j-c_j$ in the next round remain non-positive. For each $j$, denote the first element of $B^{-1}a_j$ by $y_{1j}$, which is the number you see in the simplex table at the cross of the first row and the column related to the variable $x_j$. If $y_{1j} \ge 0$, by entering the variable $x_j$, all the new $z_j-c_j$ remain non-positive because after pivoting they become $z_j-c_j-y_{1j}x_j$. The bottle neck is those variables $x_j$ with negative $y_{1j}$, which can potentially make $z_j-c_j-y_{1j}x_j$ positive. You can find the most problematic variable $x_j$ with negative $y_{1j}$ by assessing the inequality

$$z_j-c_j-y_{1j}x_j \le 0 \Leftrightarrow x_j \le \frac{-(z_j-c_j)}{-y_{1j}}.$$

Hence, the variable $x_j$ with negative $y_{1j}$ with minimum $$\frac{-(z_j-c_j)}{-y_{1j}} $$ is the one enters in the next iteration. This is how the ratio test works in the dual simplex.

For more details, see Section 6.4, page 280, of the 4th edition of text book.