线性规划与单纯形法：沿着顶点爬
是什么：目标函数和约束都线性的最优化。生活比喻：可行域是个多面体（3D 是宝石形），目标函数是斜放的屋顶，最高利润一定在宝石的某个角上。
因标准形式与顶点
标准型：min cᵀx s.t. Ax = b, x ≥ 0。m 个等式约束把可行域切成 (n−m) 维多面体。
顶点：基可行解。n 个变量中 m 个为基变量（非零），n−m 个非基变量为 0。顶点个数 C(n,m)，指数级。
单纯形法：从一个顶点出发，选一个能让目标函数改善的非基变量入基，再让一个基变量出基，跳到相邻顶点。重复直到没有改善。
路考点心法：看到「线性规划与单纯形法：沿着顶点爬」先想什么
• 直觉优先：研究生数学从具体到抽象——先用生活直觉类比理解，再看严格定义
• 反例思维：对任意定理，先想一个反例看看它到底在保证什么条件
• 历史脉络：每门抽象数学都有几十年的酝酿——知道为什么需要它才能真正懂
完整解法：工厂利润顶点枚举
物流调度、航空公司排班、网络流、投资组合，全是线性规划；单纯形法 1947 年由 Dantzig 发明，是运筹学开山之作；Karmarkar 内点法后来把最坏复杂度压到多项式。
坑：单纯形法一定快。最坏情况下（Klee-Minty 立方体）单纯形法要遍历所有顶点 O(2ⁿ)，指数慢。实际平均快，理论最坏差。内点法（Khachiyan 椭球法、Karmarkar）才保证多项式。
① 线性规划最优解在顶点；单纯形沿棱爬。
② 实际快、最坏指数；内点法保证多项式。
证线性规划与单纯形法：沿着顶点爬的关键定理与公式
推导思路：① 可行域是多面体，线性目标在最优点必在某顶点取到（极值原理）；② 对偶构造：拉格朗日 $L=c^Tx+y^T(b-Ax)$ 对 $x$ 取下确界给出对偶上界；③ 单纯形法沿棱从一个顶点走到更优顶点直到最优。
直觉把握：线性规划是"在多边形里找最便宜的顶点"——运输排班、投资组合、网络流全是它；对偶给出"影子价格"，解释每单位资源的边际价值。
④ 用途与案例
工程：线性规划与单纯形法：沿着顶点爬
在工程、物理、计算机、金融等领域，线性规划与单纯形法：沿着顶点爬是基础工具——理解"使用场景"比死记公式重要。
日常：你见过但没注意的线性规划与单纯形法：沿着顶点爬
生活中处处有线性规划与单纯形法：沿着顶点爬——价格波动、几何造型、统计图表、游戏设计——只不过没人告诉你这就是数学。
练习与答案
1.【基础】 为什么线性规划的最优解一定在某个顶点取到？
思路与解答
线性目标在凸多面体上的极值必在极点或边界达到，而多面体的极点就是顶点，因此只需在顶点中搜索最优。2.【进阶】 写出原问题 $\min c^Tx$ s.t. $Ax=b,\ x\ge0$ 的对偶，并说明互补松弛的经济含义。
思路与解答
对偶为 $\max b^Ty$ s.t. $A^Ty\le c$；$x_i>0$ 时对应对偶约束取等号，给出该资源的"影子价格"——增量一单位资源带来的目标增量。3.【挑战】 单纯形法最坏情况为什么可能指数慢（Klee-Minty）？内点法为什么能保证多项式复杂度？