Theorem 3.3 — the simplex method terminates under Bland's rule

Consider a standard-form linear program with data $A \in \mathbb{R}^{m\times n}$, $b\in\mathbb{R}^m$, $c \in \mathbb{R}^n$, and a feasible dictionary $D_0$. Run the simplex method from $D_0$ choosing both the entering and the leaving variable by Bland's rule: among the candidates, the variable $x_k$ with the smallest index $k$ (indices $1,\dots,n$ for the decision variables and $n+1,\dots,n+m$ for the slacks). Then the simplex method always terminates:

1. there is no infinite sequence $D_0 \to D_1 \to D_2 \to \cdots$ of Bland pivots;
2. there are $T \ge 0$ and Bland pivots $D_0 \to D_1 \to \dots \to D_T$ such that the method stops at $D_T$: either

where $x_k$ is the entering variable chosen by Bland's rule in $D_T$ — that is, $D_T$ is optimal, or it shows that the problem is unbounded.

Together with Phase I, this gives a variant of the simplex method that is guaranteed to finish, the basis of the fundamental theorem of linear programming.

Formalization Note The book's statement is the termination claim; part 2 records what termination means for the method as defined on pp. 15–19 (it stops only when there is no entering candidate or no positive $\bar a_{ik}$ in the entering column), so the statement cannot hold merely because pivots fail to exist. Bland's rule compares the indices of Fin (n + m), decision variables before slacks.