证明线性规划的最优解是顶点，并通俗解释
我们来一步步证明为什么线性规划（Linear Programming, LP）的最优解总是一个顶点，不管是在二维、三维还是更高维的空间里。之后，我会用通俗的语言解释这个结论，再说明什么是凸多面体。
什么是线性规划？
线性规划是一个数学工具，用来解决优化问题。简单来说，就是在一个由线性不等式（比如 (x + y \leq 4)）围成的“可行区域”里，找到一个点，让某个线性目标函数（比如 (3x + 2y)）达到最大值或最小值。它的标准形式可以用数学写成：
- 目标：最大化或最小化 (\mathbf{c}^\top \mathbf{x})（比如 (3x_1 + 2x_2)）
- 约束：(A\mathbf{x} \leq \mathbf{b})（比如 (x_1 + x_2 \leq 4)），且 (\mathbf{x} \geq 0)（变量非负）
这里的 (\mathbf{x}) 是我们要找的点，可能是二维的 ((x_1, x_2))，也可能是更高维的 ((x_1, x_2, …, x_n))。
可行域是什么？
所有满足约束条件的 (\mathbf{x}) 组成一个区域，叫做可行域。比如在二维空间中，约束条件 (x_1 + x_2 \leq 4), (x_1 \leq 3), (x_2 \leq 2), (x_1, x_2 \geq 0) 会围出一个多边形。我们的任务就是在多边形里找一个点，让目标函数最大或最小。
为什么最优解是顶点？
要证明最优解是顶点，我们从以下几个角度来分析：
-
可行域是凸的
可行域是由线性不等式围成的，这个区域有个重要性质：它是凸的。什么叫凸的？想象一个橡皮泥球，你随便挑两个点连一条线，这条线不会跑出球外。可行域也是这样，任意两点之间的连线不会跑出区域。这种凸性保证了最优解不会“藏”在区域内部，而是倾向于出现在边界上。 -
目标函数是直线型的
目标函数（比如 (3x_1 + 2x_2)）是线性的，画出来就像二维平面上的等高线（直线）。最大化目标函数，就是让这条直线尽量往高处移动，但不能离开可行域。想象你在二维多边形上推一条直尺，直尺最后会卡在某个“角”上，这个角就是顶点。因为如果直尺卡在一条边上不动，那这条边两端的顶点也一定是最优解之一。 -
顶点的定义
在数学上，顶点是可行域的“角点”。在二维空间里，一个顶点是两条线的交点；在三维空间里，是三个平面的交点；在 (n) 维空间里，是 (n) 个线性无关约束条件（变成等式时）的交点。这些顶点是可行域的“最边缘”点。 -
直觉证明
假设最优解不在顶点，而在可行域内部或边上某个中间点。因为可行域是凸的，从这个点出发，沿着目标函数增加的方向走（比如 (3x_1 + 2x_2) 变大的方向），你总能走到边界，甚至走到一个顶点。如果目标函数在顶点处的值更大，那内部的点就不可能是最优的。如果目标函数沿着某条边不变（比如与边平行），那这条边的两个顶点也都是最优解。所以，无论如何，最优解总能找到一个顶点。
一个二维例子
考虑这个问题：
- 最大化 (3x_1 + 2x_2)
- 约束：(x_1 + x_2 \leq 4), (x_1 \leq 3), (x_2 \leq 2), (x_1, x_2 \geq 0)
画出来，可行域是一个多边形，顶点是：
- ((0, 0)): 值 = (3 \cdot 0 + 2 \cdot 0 = 0)
- ((3, 0)): 值 = (3 \cdot 3 + 2 \cdot 0 = 9)
- ((3, 1)): 值 = (3 \cdot 3 + 2 \cdot 1 = 11)
- ((1, 2)): 值 = (3 \cdot 1 + 2 \cdot 2 = 7)
- ((0, 2)): 值 = (3 \cdot 0 + 2 \cdot 2 = 4)
算下来，((3, 1)) 的值最大，是 (11)。这就是一个顶点！即使目标函数变成 (x_1 + x_2)（与边 (x_1 + x_2 = 4) 平行），最优解可能是整条边 ((3, 1)) 到 ((1, 2))，但顶点 ((3, 1)) 和 ((1, 2)) 仍然是最优解。
高维空间也一样
在三维或更高维空间，可行域变成了一个立体的凸多面体，但逻辑不变。目标函数仍然是线性的，像是推一个平面或超平面，最后还是会卡在某个顶点上。数学上，顶点由 (n) 个约束条件相交定义，线性函数的极值总出现在这些“最远”的角点。
通俗解释
想象你在山上找最高点，但山是平滑的直线坡度（因为目标函数是线性的）。山被一些直的围墙（约束条件）围住，围墙围出的形状是个凸的“多边形山”。你往高处走，最后不是被一个围墙挡住，就是走到围墙交接的“拐角”停下来。这个拐角就是顶点，也是最高点（或最低点，如果你要最小化）。
什么是凸多面体？
凸多面体是用数学定义的“形状”，它是由多个平直的“面”（线性不等式）围成的区域，而且是凸的。凸的意思是，你随便挑两个点连线，这条线不会跑出形状外。
- 二维例子：一个多边形，比如三角形、四边形。只要它不是“凹进去”的，就是凸多面体。
- 三维例子：一个立方体或四面体，表面是平面围成的，也是凸多面体。
- 高维：想象一个更高维的“立方体”，虽然我们想象不出来，但数学上它是由很多超平面围成的凸形状。
凸多面体可以是有界的（像一个封闭的盒子，叫做多胞体），也可以是无界的（像一个去掉顶的漏斗）。在线性规划里，可行域就是凸多面体，最优解在它的顶点上。
总结
不管在哪一维空间，线性规划的最优解是顶点，因为：
- 可行域是凸多面体，凸性让最优解出现在边界。
- 目标函数是线性的，它的最优值总在“最边缘”的顶点上。
- 即使最优解覆盖一条边或一个面，也总包含顶点。
用大白话说：线性规划就像在凸形“围栏”里找最高点，围栏的角（顶点）总是你最可能停下来的地方！