NICEFA Logo
nicefa.
Library
←Module

Proof of Finite Termination of the Simplex Algorithm (Assuming Non-Degeneracy)

Exploring the cinematic intuition of Proof of Finite Termination of the Simplex Algorithm (Assuming Non-Degeneracy).

Visualizing...

Our institutional research engineers are currently mapping the formal proof for Proof of Finite Termination of the Simplex Algorithm (Assuming Non-Degeneracy).

Apply for Institutional Early Access →

The Formal Theorem

Consider a Linear Program in standard form:\n\n\begin{align*}\n\text{maximize } & c^T x \\\n\text{subject to } & Ax = b \\\n & x \ge 0\n\end{align*}\n\nwhere A A is an m×n m \times n matrix with rank(A)=m \text{rank}(A) = m , x∈Rn x \in \mathbb{R}^n , c∈Rn c \in \mathbb{R}^n , and b∈Rm b \in \mathbb{R}^m . \n\n**Theorem:** If the Simplex Algorithm starts with an initial basic feasible solution and, at every iteration, selects an entering variable whose reduced cost is positive, and furthermore, *every basic feasible solution (BFS) encountered during the algorithm is non-degenerate*, then the algorithm terminates in a finite number of iterations, either by finding an optimal solution or by detecting that the problem is unbounded. The core mechanism is that under non-degeneracy, each pivot operation strictly increases the objective function value z z :
znew>zold z_{\text{new}} > z_{\text{old}}

Analytical Intuition.

Imagine yourself as an explorer navigating a vast, multi-dimensional geometric landscape. Each distinct vertex or 'corner' of this landscape represents a 'basic feasible solution' (BFS) x x . Your quest, guided by the 'objective function' cTx c^T x , is to find the highest possible peak. The Simplex Algorithm is your steadfast compass, always pointing towards an adjacent vertex that offers a steeper ascent. The crucial condition of 'non-degeneracy' acts as a magical wind at your back: it guarantees that *every* step you take truly moves you to a strictly higher elevation. No flat plateaus, no lingering at the same height. Since this landscape, while complex, has a *finite* number of distinct vertices (at most (nm) \binom{n}{m} ), and you're forbidden from ever visiting the same elevation twice (thanks to the strict ascent), you are mathematically destined to reach the absolute summit (an optimal solution) or discover an infinitely rising path (unboundedness) in a finite number of steps. You cannot wander forever aimlessly; every step counts, every step elevates.
CAUTION

Institutional Warning.

Students often misunderstand what 'non-degeneracy' truly implies. It means that all basic variables in a basic feasible solution are strictly positive. This is crucial because a degenerate BFS (where some basic variables are zero) can lead to a pivot that doesn't improve the objective function value, potentially causing cycling.

Academic Inquiries.

01

What happens if the non-degeneracy assumption does not hold? Can the Simplex Algorithm still terminate?

If basic feasible solutions are degenerate, the Simplex Algorithm can 'cycle' − - repeatedly visiting the same sequence of bases without improving the objective function value, thus failing to terminate. However, specific anti-cycling rules, such as Bland's Rule (the smallest index rule) or the Lexicographical Rule, have been developed to guarantee finite termination even in the presence of degeneracy.

02

Why is the number of basic feasible solutions (BFSs) finite?

For a linear program with m m equality constraints and n n variables, a basic feasible solution is defined by choosing m m basic variables out of n n total variables, with the remaining n−m n-m variables set to zero. The number of ways to choose m m variables from n n is given by the binomial coefficient (nm)=n!m!(n−m)! \binom{n}{m} = \frac{n!}{m!(n-m)!} . Since n n and m m are finite, this number is finite, providing an upper bound on the total number of distinct BFSs.

03

Does this proof guarantee that the Simplex Algorithm will find an *optimal* solution?

Yes, under the assumption of non-degeneracy, the proof guarantees finite termination. Upon termination, one of two scenarios must occur: either an optimal basic feasible solution has been found (when all reduced costs are non-positive for a maximization problem), or the algorithm has detected that the objective function can be increased indefinitely, meaning the problem is unbounded. In either case, the algorithm provides a definitive answer.

Standardized References.

  • Definitive Institutional SourceChvátal, Václav. Linear Programming. W. H. Freeman and Company, 1983.

Related Proofs Cluster.

Foundational

The Convexity of the Feasible Region of a Linear Program

Exploring the cinematic intuition of The Convexity of the Feasible Region of a Linear Program.

Intermediate

The Fundamental Theorem of Linear Programming: Existence of an Optimal Extreme Point Solution

Exploring the cinematic intuition of The Fundamental Theorem of Linear Programming: Existence of an Optimal Extreme Point Solution.

Intermediate

Equivalence of Basic Feasible Solutions and Extreme Points

Exploring the cinematic intuition of Equivalence of Basic Feasible Solutions and Extreme Points.

Advanced

Characterization of Unboundedness in Linear Programming

Exploring the cinematic intuition of Characterization of Unboundedness in Linear Programming.

Institutional Citation

Reference this proof in your academic research or publications.

NICEFA Visual Mathematics. (2026). Proof of Finite Termination of the Simplex Algorithm (Assuming Non-Degeneracy): Visual Proof & Intuition. Retrieved from https://nicefa.org/library/linear-and-integer-programming/proof-of-finite-termination-of-the-simplex-algorithm--assuming-non-degeneracy-

Dominate the Logic.

"Abstract theory is just a movement we haven't seen yet."

Subscribe for Full ProofsEarly Access