Theorem 4.2.3 — optimal solutions exist and can be taken basic

Let $A$ be a real $m\times n$ matrix of rank $m$ (so $n\ge m$), let $b\in\mathbb{R}^m$ and $c\in\mathbb{R}^n$, and consider the linear program in equational form

1. If there is at least one feasible solution and the objective function $c^{T}x$ is bounded from above on the set of all feasible solutions, then there exists an optimal solution.
2. If an optimal solution exists, then there is a basic feasible solution that is optimal.

Part 1 says that optimal solutions fail to exist only when the program is infeasible or unbounded. Part 2 reduces the search for an optimum to the finitely many basic feasible solutions, which is the principle behind the simplex method.

Formalization Note The standing assumption of §4.2 (p. 44), $n\ge m$ and $\operatorname{rank}A=m$, is a hypothesis. "Optimal" means feasible with $c^{T}y\le c^{T}x$ for every feasible $y$, and "bounded from above" means $c^{T}x\le M$ for some real $M$ and all feasible $x$; no supremum is used. Both parts are stated as one conjunction, as in the book.