Simplex Algorithm: Why must the optimal value of the LP lie on the face or vertex of a polyhedron?
Suppose $P = \lbrace x: Ax \leq b \rbrace$ is the polyhedra, where $x \in \mathbb{R}^n$. Further assume $P$ is full dimensional, then let $x_0$ be some interior point in P. Let $c \in \mathbb{R}^n$ (and $c \neq 0$) be the objective function you are interested to minimize (say). Then since $x_0 \in int(P)$, there exists a ball $B$ centered at $x_0$ with radius $\epsilon &gt; 0$ s.t. $B \in int(P)$. Now consider any unit vector say $u \in \mathbb{R}^n$ s.t. $c^t u \neq 0$ (notice that it is always possible to select such a $u$), then both ($x_0 + \epsilon * u$) and ($x_0 - \epsilon * u$) are in  $B$, so by extension also in $P$. Now evaluate the function at 3 points, namely $x_0, x_0 + \epsilon * u, x_0 - \epsilon * u$. The objective you would get are-:
$c^T x_0 , c^T  x_0 + \epsilon (c^T  u) ,  c^T  x_0 - \epsilon (c^T  u) $. Clearly if since $c^T  u \neq 0 $, one of $c^T  x_0 + \epsilon (c^T  u) ,  c^T  x_0 - \epsilon (c^T  u)$ must be lower than $c^T x_0$. This illustrates that the objective at $x_0$ is greater than some other point on the ball, hence $x_0$ cannot be optimum. You can repeat this argument for every other interior point and claim that such an interior point cannot give the optimum. Hopefully this gave you the intuition. More generally, suppose a point $x \in P$, can be represented as convex combination of 2 other points $y, z \in P$, we can repeat the same type of argument and say that the objective at $x$ cannot be strictly lesser than the objectives at both $y$ and $z$. A vertex is an example of a point that cannot be represented as convex combination of 2 other points from the same polyhedron.