Theorem 3.2 — the simplex method terminates under the lexicographic 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$ with any entering candidate at each step and the leaving variable selected by the lexicographic rule: the right-hand sides of $D_0$ are perturbed by symbols $0 < \epsilon_m \ll \dots \ll \epsilon_1 \ll$ all data, and the leaving variable minimizes the perturbed ratio. Then the method terminates: there is no infinite sequence

of such pivots.

The lexicographic rule is the first of the two anticycling rules of the chapter; it fixes the leaving variable and leaves the entering variable free.

Formalization Note The symbolic perturbation is encoded by the coefficient vectors $(\bar b_i, r_{i1},\dots,r_{im})$ compared lexicographically (see the definition PivotRules); no real value of $\epsilon$ is fixed. The $p$-th symbol is attached in $D_0$ to the row of its $p$-th basic variable in increasing index order.