[proofplan] We first prove the finite active-set fact that every nonempty pointed polyhedron has a vertex. The argument starts at an arbitrary feasible point and, unless the active equality and inequality normals already determine a single point, moves along a nonzero direction preserving the currently active constraints until a new inequality becomes active. Since only finitely many active sets exist and pointedness forbids a two-sided line, this process reaches a vertex. We then apply this fact to the exposed optimal face and show that a vertex of that face is also a vertex of the original polyhedron. In standard form, vertices are exactly basic feasible solutions, so the first part gives the final assertion. [/proofplan] [step:Prove that every nonempty pointed polyhedron has a vertex] Let $Q \subset \mathbb{R}^n$ be a nonempty pointed polyhedron. Choose a representation \begin{align*} Q = \{x \in \mathbb{R}^n : Mx \leq r,\ Nx = s\}, \end{align*} where $M \in \mathbb{R}^{p \times n}$, $r \in \mathbb{R}^p$, $N \in \mathbb{R}^{q \times n}$, and $s \in \mathbb{R}^q$. For $x \in Q$, define the active inequality index set \begin{align*} I(x) := \{i \in \{1,\dots,p\} : M_i x = r_i\}, \end{align*} where $M_i \in \mathbb{R}^{1 \times n}$ denotes the $i$th row of $M$. Define the active normal space at $x$ by \begin{align*} V(x) := \operatorname{span}\{M_i^\top : i \in I(x)\} + \operatorname{span}\{N_j^\top : j \in \{1,\dots,q\}\} \subset \mathbb{R}^n, \end{align*} where $N_j \in \mathbb{R}^{1 \times n}$ denotes the $j$th row of $N$. We claim that there exists $x_* \in Q$ with $V(x_*) = \mathbb{R}^n$. Start with any $x_0 \in Q$. If $V(x_0) = \mathbb{R}^n$, stop. Otherwise choose a nonzero vector $d_0 \in \mathbb{R}^n$ orthogonal to $V(x_0)$. Equivalently, \begin{align*} Nd_0 = 0 \end{align*} and \begin{align*} M_i d_0 = 0 \quad \text{for every } i \in I(x_0). \end{align*} Consider the feasible parameter set \begin{align*} T_0 := \{t \in \mathbb{R} : x_0 + t d_0 \in Q\}. \end{align*} The set $T_0$ is a closed interval containing $0$. It is not all of $\mathbb{R}$, because otherwise $\{x_0 + t d_0 : t \in \mathbb{R}\}$ would be an affine line contained in $Q$, contradicting pointedness. Hence at least one of its two endpoints is finite. Replacing $d_0$ by $-d_0$ if necessary, let \begin{align*} \tau_0 := \sup\{t \geq 0 : x_0 + t d_0 \in Q\} < \infty. \end{align*} Set $x_1 := x_0 + \tau_0 d_0$. Since $T_0$ is closed, $x_1 \in Q$. The constraints active at $x_0$ remain active at $x_1$, because $M_i d_0 = 0$ for $i \in I(x_0)$ and $Nd_0 = 0$. Since $\tau_0$ is a finite endpoint, at least one inequality inactive at $x_0$ becomes active at $x_1$. Therefore \begin{align*} I(x_0) \subsetneq I(x_1). \end{align*} Repeating this construction strictly increases the active set whenever $V(x_k) \neq \mathbb{R}^n$. Since there are only finitely many subsets of $\{1,\dots,p\}$, the process terminates at some $x_* \in Q$ satisfying $V(x_*) = \mathbb{R}^n$. We now show that this $x_*$ is a vertex of $Q$. Suppose $y,z \in Q$ and \begin{align*} x_* = \frac{1}{2}y + \frac{1}{2}z. \end{align*} For every $i \in I(x_*)$, the inequalities $M_i y \leq r_i$ and $M_i z \leq r_i$ hold, while \begin{align*} r_i = M_i x_* = \frac{1}{2}M_i y + \frac{1}{2}M_i z. \end{align*} Thus $M_i y = r_i$ and $M_i z = r_i$ for every $i \in I(x_*)$. Also $Ny = s$, $Nz = s$, and $Nx_* = s$. Hence $y - x_*$ and $z - x_*$ are orthogonal to every vector in $V(x_*)$. Since $V(x_*) = \mathbb{R}^n$, this gives $y - x_* = 0$ and $z - x_* = 0$. Therefore $x_*$ is a vertex of $Q$. [guided] The goal is to prove a structural fact about pointed polyhedra: a nonempty pointed polyhedron cannot be made entirely out of positive-dimensional flat pieces; at least one zero-dimensional face must occur. Write the polyhedron as \begin{align*} Q = \{x \in \mathbb{R}^n : Mx \leq r,\ Nx = s\}, \end{align*} where $M \in \mathbb{R}^{p \times n}$, $r \in \mathbb{R}^p$, $N \in \mathbb{R}^{q \times n}$, and $s \in \mathbb{R}^q$. For a point $x \in Q$, define \begin{align*} I(x) := \{i \in \{1,\dots,p\} : M_i x = r_i\}. \end{align*} These are exactly the inequalities that are tight at $x$. Also define \begin{align*} V(x) := \operatorname{span}\{M_i^\top : i \in I(x)\} + \operatorname{span}\{N_j^\top : j \in \{1,\dots,q\}\}. \end{align*} This is the span of all equality normals together with the normals of the inequalities active at $x$. Why is the condition $V(x) = \mathbb{R}^n$ the right one? If these normals span all directions, then the active constraints pin the point down. If they do not span all directions, there is a nonzero direction $d \in \mathbb{R}^n$ invisible to all currently active constraints. Formally, if $V(x) \neq \mathbb{R}^n$, choose $d \neq 0$ orthogonal to $V(x)$. Then \begin{align*} Nd = 0 \end{align*} and \begin{align*} M_i d = 0 \quad \text{for every } i \in I(x). \end{align*} Thus moving from $x$ to $x + td$ preserves all equality constraints and all inequalities that are currently active. Start with any $x_0 \in Q$. If $V(x_0) = \mathbb{R}^n$, we are already at the desired kind of point. Otherwise choose a nonzero direction $d_0$ satisfying \begin{align*} Nd_0 = 0 \end{align*} and \begin{align*} M_i d_0 = 0 \quad \text{for every } i \in I(x_0). \end{align*} Define the set of feasible parameters \begin{align*} T_0 := \{t \in \mathbb{R} : x_0 + t d_0 \in Q\}. \end{align*} Because the constraints defining $Q$ are finitely many closed linear equalities and inequalities, $T_0$ is a closed interval containing $0$. It cannot be all of $\mathbb{R}$: if it were, then the full affine line \begin{align*} \{x_0 + t d_0 : t \in \mathbb{R}\} \end{align*} would lie in $Q$, contradicting the assumption that $Q$ is pointed. Therefore at least one endpoint of $T_0$ is finite. After replacing $d_0$ by $-d_0$ if the finite endpoint is on the negative side, define \begin{align*} \tau_0 := \sup\{t \geq 0 : x_0 + t d_0 \in Q\} < \infty. \end{align*} Set $x_1 := x_0 + \tau_0 d_0$. Since $T_0$ is closed, $x_1 \in Q$. The old active inequalities stay active at $x_1$. Indeed, if $i \in I(x_0)$, then \begin{align*} M_i x_1 = M_i x_0 + \tau_0 M_i d_0 = r_i. \end{align*} At least one new inequality becomes active at $x_1$. If no new inequality became active, then every inequality inactive at $x_0$ would remain strict at $x_1$. By openness of strict inequalities, we could move a little beyond $\tau_0$ and remain feasible, contradicting the definition of $\tau_0$ as the endpoint. Hence \begin{align*} I(x_0) \subsetneq I(x_1). \end{align*} Repeat the same construction from $x_1$, then from $x_2$, and so on. Every time the active normal span is not all of $\mathbb{R}^n$, the active inequality set strictly increases. There are only finitely many possible active inequality sets, because there are only finitely many inequalities. Therefore the procedure must stop at a point $x_* \in Q$ such that \begin{align*} V(x_*) = \mathbb{R}^n. \end{align*} It remains to prove that this spanning condition makes $x_*$ a vertex. Suppose \begin{align*} x_* = \frac{1}{2}y + \frac{1}{2}z \end{align*} with $y,z \in Q$. For each $i \in I(x_*)$, we have $M_i y \leq r_i$ and $M_i z \leq r_i$, while \begin{align*} r_i = M_i x_* = \frac{1}{2}M_i y + \frac{1}{2}M_i z. \end{align*} The average of two numbers each at most $r_i$ equals $r_i$ only if both numbers equal $r_i$. Hence \begin{align*} M_i y = r_i \end{align*} and \begin{align*} M_i z = r_i \end{align*} for every $i \in I(x_*)$. Also the equality constraints give \begin{align*} Ny = s, \quad Nz = s, \quad Nx_* = s. \end{align*} Thus $y - x_*$ and $z - x_*$ are orthogonal to all active inequality normals and all equality normals. In other words, they are orthogonal to every vector in $V(x_*)$. Since $V(x_*) = \mathbb{R}^n$, the only vector orthogonal to all of $V(x_*)$ is $0$. Therefore \begin{align*} y = x_* \quad \text{and} \quad z = x_*. \end{align*} This is exactly the definition that $x_*$ is a vertex of $Q$. [/guided] [/step] [step:Identify the optimal solution set as a nonempty pointed exposed face] Define the linear functional $\ell: \mathbb{R}^n \to \mathbb{R}$ by $\ell(x) := c^\top x$. Let \begin{align*} \alpha := \min_{x \in P} \ell(x). \end{align*} By hypothesis, $\alpha \in \mathbb{R}$ and there exists $x_0 \in P$ such that $\ell(x_0) = \alpha$. Define the optimal solution set \begin{align*} F := \{x \in P : \ell(x) = \alpha\}. \end{align*} Then $F$ is nonempty because $x_0 \in F$. Since $P$ is a polyhedron, choose a finite linear description \begin{align*} P = \{x \in \mathbb{R}^n : Mx \leq r,\, Nx = s\}, \end{align*} with $M \in \mathbb{R}^{p \times n}$, $r \in \mathbb{R}^p$, $N \in \mathbb{R}^{q \times n}$, and $s \in \mathbb{R}^q$. Then \begin{align*} F = \{x \in \mathbb{R}^n : Mx \leq r,\ Nx = s,\ \ell(x) = \alpha\}, \end{align*} so $F$ is a polyhedron. It is pointed: if $F$ contained an affine line $\{a + td : t \in \mathbb{R}\}$ with $d \neq 0$, then the same affine line would be contained in $P$, contradicting that $P$ is pointed. [/step] [step:Apply the pointed polyhedron lemma to obtain an optimal vertex of the face] By the previous step, $F$ is a nonempty pointed polyhedron. Applying the result proved in the first step to $Q := F$, there exists a vertex $v$ of $F$. Since $F \subset P$ and every point $x \in F$ satisfies $\ell(x) = \alpha$, the point $v$ is an optimal solution of the original linear program. [/step] [step:Show that a vertex of the optimal face is a vertex of the original polyhedron] We prove that $v$ is a vertex of $P$. Suppose $y,z \in P$ and \begin{align*} v = \frac{1}{2}y + \frac{1}{2}z. \end{align*} Since $\alpha$ is the minimum of $c^\top x$ over $P$, we have \begin{align*} c^\top y \geq \alpha \end{align*} and \begin{align*} c^\top z \geq \alpha. \end{align*} Using $\ell(v) = \alpha$ and linearity of the map $\ell: \mathbb{R}^n \to \mathbb{R}$ gives \begin{align*} \alpha = \ell(v) = \frac{1}{2}\ell(y) + \frac{1}{2}\ell(z). \end{align*} The average of two [real numbers](/page/Real%20Numbers) each at least $\alpha$ equals $\alpha$ only if both equal $\alpha$. Hence $\ell(y) = \alpha$ and $\ell(z) = \alpha$, so $y,z \in F$. Since $v$ is a vertex of $F$, the equality \begin{align*} v = \frac{1}{2}y + \frac{1}{2}z \end{align*} forces $y = v$ and $z = v$. Therefore $v$ is a vertex of $P$. Thus the optimal solution set contains a vertex of $P$. [/step] [step:Translate vertices into basic feasible solutions in standard form] Now assume \begin{align*} P = \{x \in \mathbb{R}^n : Ax = b,\ x_i \geq 0 \text{ for every } i \in \{1,\dots,n\}\}, \end{align*} where $A \in \mathbb{R}^{m \times n}$ has full row rank. This standard-form polyhedron is pointed: if it contained an affine line $\{a + td : t \in \mathbb{R}\}$ with $d \neq 0$, then for each coordinate $i \in \{1,\dots,n\}$ the inequalities $a_i + td_i \geq 0$ for all $t \in \mathbb{R}$ would force $d_i = 0$, so $d = 0$, a contradiction. A feasible point $x \in P$ is a basic feasible solution precisely when the columns of $A$ indexed by \begin{align*} B(x) := \{i \in \{1,\dots,n\} : x_i > 0\} \end{align*} are linearly independent, equivalently when $x$ is a vertex of this standard-form polyhedron. Because $A$ has full row rank, any linearly independent support column set can be extended to a full basis of $m$ columns, which is the usual textbook formulation of a basic feasible solution. For completeness, we verify the equivalence. If the columns indexed by $B(x)$ are linearly dependent, choose a nonzero vector $h \in \mathbb{R}^n$ supported in $B(x)$ such that $Ah = 0$. Since $x_i > 0$ for every $i \in B(x)$ and $h_i = 0$ for $i \notin B(x)$, there exists $\varepsilon > 0$ such that $x + th \geq 0$ for every $t \in [-\varepsilon,\varepsilon]$. Also $A(x + th) = b$ for every such $t$. Hence $x$ lies in a nontrivial line segment contained in $P$, so $x$ is not a vertex. Conversely, if the columns indexed by $B(x)$ are linearly independent and \begin{align*} x = \frac{1}{2}y + \frac{1}{2}z \end{align*} with $y,z \in P$, then for every $i \notin B(x)$ we have $x_i = 0$ and $y_i,z_i \geq 0$, so $y_i = z_i = 0$. Thus $y - x$ and $z - x$ are supported in $B(x)$, and \begin{align*} A(y - x) = 0 \end{align*} and \begin{align*} A(z - x) = 0. \end{align*} The [linear independence](/page/Linear%20Independence) of the columns indexed by $B(x)$ implies $y - x = 0$ and $z - x = 0$. Hence $x$ is a vertex. By the previous steps, if the standard-form linear program has a finite attained optimum, then an optimal vertex $v$ of $P$ exists. By the equivalence just proved, $v$ is a basic feasible solution. Therefore some basic feasible solution is optimal. [/step]