Exercise 3.10*

Suppose towards a contradiction that some pivoting rule generates a cycle. Without loss of generality, let’s assume the tableau looks like below at the beginning of the cycle.

Also, suppose $c_{m+1}<0$ and the pivoting rule select $x_l$ as the entering variable. Then $l\in r_1=\{i|1\le i\le m,u_{i,1}>0\}$. After this iteration, the tableau becomes

For simplicity, we still notify the updated last column with the same variable names. As the reduced cost of the basic direction $x_l$ is $-\frac{c_{m+1}}{u_{l,1}}<0$, we must have $c_{m+2}<0$ otherwise the simplex algorithm will terminate. Suppose the exiting variable is $x_j$, we will show 1)$j\ne l$ and 2)$j\in r_1$. First notice that, after this iteration, we will have two nonbasic variables $x_j$ and $x_l$. Since $x_j$ just exits the basis, it cannot reenter the basis in the very next iteration. Hence $x_l$ must be the entering variables in the next iteration. It implies the reduced cost $\overline{c_l}$ in the next iteration must be negative. If $j=l$, then the reduced cost $\overline{c_l}=-\frac{c_{m+1}}{u_{l,1}}+(-\frac{c_{m+2}}{u_{l,2}})\cdot \frac{1}{u_{l,1}}>0$ as $c_{m+1},c_{m+2}<0$ and $u_{l,1},u_{l,2}>0$. Therefore $j\ne l$. To prove 2), suppose that $j\notin r_1$. Then $u_{j,1}\le 0$. The reduced cost $\overline{c_l}$ in the next iteration would be $\overline{c_l}=-\frac{c_{m+1}}{u_{l,1}}+(-\frac{c_{m+2}}{u_{j,2}})\cdot (-\frac{u_{j,1}}{u_{l,1}})>0$. Hence 2) must be true.

From 1) and 2), we conclude that $j$ must belong the the set $r_2=\{i|u_{i,2}>0,i\in r_1,i\ne l\}$. As $\left|r_1\right|\le m$, we have $\left|r_2\right|\le m-1$. If we continue this process, we will have $\left|r_{m+1}\right|\le 0$. Hence the simplex must terminate after m iterations and therefore it cannot cycle, we reach a contradiction here. As a corollary, we conclude if $n-m=2$, then the simplex algorithm will terminate after at most $m$ iterations.