Bland-rule finite termination and optimal-basis existence

Every pivot in [F3] uses a negative reduced cost and a nonnegative ratio, so [F2] makes the objective nonincreasing. If a basis repeats, the deterministic rule repeats the same future pivots and produces a cycle; the objective returns to its initial value, forcing every pivot decrease to be zero. Since each entering reduced cost is strictly negative, every pivot in the cycle has $\theta =0$, so the represented feasible vector stays fixed throughout the cycle.

Let $T$ be the indices that enter in this cycle and let $q=\max T$. Because the basis returns, $q$ also leaves. Choose a tableau $P$ where $q$ enters and a tableau $Q$ where $q$ leaves. At $P$, its reduced cost $r_q^P<0$ and $r_j^P\ge 0$ for every $j<q$: a basic reduced cost is zero, and a lower-index eligible nonbasic variable would have been chosen instead. At $Q$, the entering variable $t$ is in $T$, is not the basic variable $q$, and therefore satisfies $t<q$.

At $Q$, put $d=A_{B_Q}^{-1}{a}_t$ and define the entering direction $z_t=1$, $z_{B_Q}=-d$, with other nonbasic coordinates zero. Then $Az=0$, $c^{\mathsf{T}}z=r_t^Q<0$, and $z_q<0$ because $q$ leaves through a row with positive pivot coefficient. If $r^P=c-A^{\mathsf{T}}{y}^P$ is the reduced-cost vector at $P$, then $r^P\cdot z=c^{\mathsf{T}}z<0$ since $Az=0$.

For every $j>q$, $r_j^P{z}_j=0$: if $j$ is basic at $P$ then $r_j^P=0$, while if it is nonbasic at $P$, maximality of $q$ means it never enters during the cycle and it is nonbasic at $Q$, where $z_j=0$. Also $r_q^P{z}_q>0$. Thus the negative sum $r^P\cdot z$ forces some $j<q$ with $r_j^P{z}_j<0$; because $r_j^P\ge 0$, this gives $r_j^P>0$ and $z_j<0$. Such a $j$ is nonbasic at $P$, basic at $Q$, and has $d_j>0$. Its value is zero at $P$ and stays zero during the degenerate cycle, so at $Q$ it ties with $q$ at ratio zero.

Since $j<q$ is an eligible leaving variable with the same minimum ratio as $q$, [F3] would choose $j$ to leave at $Q$, contradicting the choice of $q$. Therefore no basis repeats.

There are at most $\left(\genfrac{}{}{0px}{}{n}{m}\right)$ possible column bases, so the algorithm terminates after at most that many visited bases. At termination [F2] gives either an optimal basis or an unbounded ray. If the objective is bounded below, the ray branch is impossible. If the feasible set is nonempty, [F4] supplies a starting basis; hence a finite optimum is attained at an optimal basis found by the algorithm. The combinatorial bound does not imply polynomial-time complexity.