Linear programming

The objective is linear, so its level sets are parallel hyperplanes; sliding such a hyperplane across a convex polyhedron, the last point it touches before leaving the region is always a corner, never a point in the interior of a face, because interior points can always be pushed further in the direction that improves the objective.

Since $P$ is a bounded polyhedron defined by finitely many linear inequalities, it has finitely many vertices $v_1,\ldots,v_k$, and a classical fact about polytopes (Minkowski's theorem) states that every point of $P$ is a convex combination of these vertices: $x=\sum_{i=1}^{k}\lambda_i v_i$, where $\lambda_i\ge 0$ and $\sum_i \lambda_i=1$.

Because the objective $c^{\mathsf{T}}x$ is linear, evaluating it on such a convex combination gives $c^{\mathsf{T}}x=\sum_i \lambda_i\left(c^{\mathsf{T}}v_i\right)\le \left(\max_i c^{\mathsf{T}}v_i\right)\sum_i\lambda_i=\max_i c^{\mathsf{T}}v_i$, since each $\lambda_i\ge 0$ and they sum to $1$.

This shows every feasible $x$ has objective value no larger than the best vertex value $\max_i c^{\mathsf{T}}v_i$. But that best vertex, call it $v_{i^*}$, is itself a feasible point of $P$, so it actually attains this upper bound: $c^{\mathsf{T}}v_{i^*}=\max_{x\in P} c^{\mathsf{T}}x$. Hence the optimum of the linear program is achieved at the vertex $v_{i^*}$, proving the claim.

Duality says the primal maximization and the dual minimization are two views of the same number: the dual variables $y$ act as prices on the resources, and weak duality says no feasible production plan can ever earn more than the value of the resources it uses at any valid pricing, while strong duality says that at the optimum, the best production plan and the cheapest valid pricing agree exactly.

(Weak duality.) Let $x$ be any primal-feasible point ($Ax\le b$, $x\ge 0$) and $y$ any dual-feasible point ($A^{\mathsf{T}}y\ge c$, $y\ge 0$). Since $x\ge 0$ and $A^{\mathsf{T}}y\ge c$, multiplying the inequality by the nonnegative vector $x$ preserves it: $c^{\mathsf{T}}x\le \left(A^{\mathsf{T}}y\right)^{\mathsf{T}}x=y^{\mathsf{T}}Ax$. Since $y\ge 0$ and $Ax\le b$, the same argument gives $y^{\mathsf{T}}Ax\le y^{\mathsf{T}}b=b^{\mathsf{T}}y$. Chaining the two inequalities, $c^{\mathsf{T}}x\le b^{\mathsf{T}}y$ for every feasible pair, which is weak duality.

(Strong duality.) Run the simplex method on the primal until it terminates at an optimal basic feasible solution $x^{*}$ with optimal basis matrix $B$, so that $x^{*}_B=B^{-1}b$ and the reduced costs of every non-basic variable are non-negative — this termination condition is equivalent to defining $y^{*\mathsf{T}}=c_B^{\mathsf{T}}B^{-1}$, which one can check satisfies $A^{\mathsf{T}}y^{*}\ge c$ and $y^{*}\ge 0$, i.e. $y^{*}$ is dual-feasible.

Substituting, the primal optimal value is $c^{\mathsf{T}}x^{*}=c_B^{\mathsf{T}}x^{*}_B=c_B^{\mathsf{T}}B^{-1}b=y^{*\mathsf{T}}b=b^{\mathsf{T}}y^{*}$. Combined with weak duality ($c^{\mathsf{T}}x^{*}\le b^{\mathsf{T}}y^{*}$ always), equality here forces $y^{*}$ to be dual-optimal as well, so $c^{\mathsf{T}}x^{*}=b^{\mathsf{T}}y^{*}$, proving strong duality.