线性规划

1939 年，苏联数学家 Leonid Kantorovich 在研究苏联工业生产调度时（其著作《生产组织与计划的数学方法》），提出了一类特殊的数学优化问题：目标函数和约束都是线性的。他的工作后来为他赢得了 1975 年诺贝尔经济学奖（与 Tjalling Koopmans 共享）。

1947 年，在美国空军资助下，George Dantzig 独立发展了线性规划理论，并提出了求解这类问题的单纯形法（Simplex Method）。二战期间的军事后勤调度需求，直接推动了这一理论的诞生。

线性规划（Linear Programming，LP）是优化理论中最成熟、应用最广的分支，是运筹学的核心工具，也是整数规划、凸优化等更一般框架的基础。

标准形式#

一个线性规划问题的标准形式：

$$\text{最大化 } \mathbf{c}^T \mathbf{x}$$

$$\text{满足 } A\mathbf{x} \leq \mathbf{b},\ \mathbf{x} \geq \mathbf{0}$$

其中： - $\mathbf{x} \in \mathbb{R}^n$：决策变量（如生产数量、资源分配量） - $\mathbf{c} \in \mathbb{R}^n$：目标函数系数（如单位利润） - $A \in \mathbb{R}^{m \times n}$：约束矩阵（如资源消耗系数） - $\mathbf{b} \in \mathbb{R}^m$：约束右端（如资源总量）

一个直觉例子：工厂生产两种产品，各有不同的利润和资源消耗，资源总量有限，如何安排生产使总利润最大？这就是最简单的 LP。

可行域：多面体的几何#

LP 的约束定义了一个多面体（Polyhedron）——若干线性不等式的交集。在二维情况下是凸多边形，三维是凸多面体，高维类似。

关键定理（基本可行解定理）：若 LP 有最优解，则一定存在一个多面体的顶点（Vertex/Extreme Point）也是最优解。

直觉：线性目标函数在凸多面体上的最大值，一定在顶点取到（或在一条边/面上取到，但总有顶点也是最优的）。

这一观察是单纯形法的几何基础。

单纯形法：沿边游走#

单纯形法（Simplex Method，Dantzig 1947）：

1. 从多面体的一个顶点（基本可行解）开始
2. 检查所有相邻顶点（沿一条边移动可达）
3. 若有相邻顶点使目标函数值更大，移动过去
4. 重复直到没有更好的相邻顶点——已到达局部（也是全局）最优

由于 LP 是凸问题，局部最优即全局最优。

代数实现：用单纯形表（Simplex Tableau）表示当前顶点和约束，每次"主元变换（Pivot）"对应从一个顶点沿边移动到相邻顶点。

为什么沿边走就有效：站在某个顶点上，目标函数的"改进方向"可以分解到从该点出发的各条边上——每条边对应一个检验数（reduced cost，即让对应非基变量增加一单位所带来的目标值变化）。只要存在检验数为正的边，沿它走就严格改进；所有检验数都非正，说明每个可行方向都在恶化目标值，当前点即最优。凸性保证了"四周无更好"就是"全局无更好"，无须回头复查。

退化与循环：实际中常出现退化顶点——穿过该点的约束面多于必要个数，同一个顶点对应多组基。此时主元变换可能换了基却没挪动位置（目标值原地踏步），理论上甚至可能绕回之前的一组基，陷入无限循环。1977 年，Robert Bland 给出一条简单的Bland 规则（每次在候选变量中固定选下标最小者进基、离基），证明它能彻底杜绝循环——这是"算法正确性依赖一个看似琐碎的平局裁决规则"的经典例子。

实践性能：单纯形法在实际中极快——典型地在 $O(m)$ 到 $O(3m)$ 次迭代收敛（$m$ 为约束数），每次迭代 $O(mn)$。尽管理论最坏情况是指数级的（Klee-Minty 立方体，1972 年），但病态实例在实际问题中极罕见。

Klee-Minty 问题与多项式算法#

1972 年，Klee 和 Minty 构造了使单纯形法需要指数步骤的实例，引发了一个问题：LP 有多项式时间算法吗？

Khachian 椭球法（1979）：Leonid Khachian 证明 LP 可以在多项式时间内求解——但实践中极慢。思路与单纯形法完全不同：用一个椭球包住可行域的某一部分，检查椭球中心；若不可行，就用被违反的约束把椭球切成两半，再造一个更小的椭球包住含解的那一半。体积每步按比例缩小，有限步内要么找到可行点，要么体积小到足以断言无解。

椭球法真正的遗产不是算法本身，而是它揭示的原理：求解 LP 不需要显式列出全部约束，只需要一个"分离预言机"——给定任意点，回答它是否可行；若不可行，给出一条被违反的约束。这意味着即使约束多到指数级（例如旅行商问题的子环游消除约束），只要能快速找出被违反的那一条，仍可多项式时间求解。Grötschel、Lovász 与 Schrijver 沿这条路建立了"分离与优化等价"的一般理论，成为组合优化的理论支柱。

Karmarkar 内点法（1984）：N. Karmarkar 提出的内点法（Interior Point Method）不沿边游走，而是穿过多面体内部，理论复杂度 $O(n^{3.5}L)$（$L$ 为输入编码长度），实践中也快于单纯形法（对某些大规模问题）。机制上，现代内点法用障碍函数把约束"软化"进目标：给目标函数加上一项在靠近边界时趋于无穷的惩罚项，使无约束化的优化路径（中心路径）始终悬在多面体内部，再用牛顿法沿这条路径逐步逼近边界上的最优顶点。穿内部而行的代价是每步要解一个稠密线性方程组，但步数远少于单纯形法——问题越大，这个交换越划算。

为什么实际很快：平滑分析。最坏情况指数、实际却飞快——这个鸿沟长期没有理论解释。2001 年，Daniel Spielman 与滕尚华提出平滑分析（smoothed analysis，STOC 2001）：对任意输入做微小随机扰动，单纯形法的期望运行时间是多项式的。直觉是，Klee-Minty 式的病态实例依赖约束面之间极端精细的角度安排，任何一点扰动都会破坏这种排列——病态实例在输入空间中"测度极小"。平滑分析介于最坏情况与平均情况之间，被认为是解释"算法实践表现"最有说服力的框架之一。

现代 LP 求解器（Gurobi、CPLEX、HiGHS）同时实现了单纯形法和内点法，根据问题规模和结构自动选择： - 单纯形法：更适合需要温起动（Warm Start）的序列求解（如整数规划中的 LP 松弛序列） - 内点法：更适合大规模稠密 LP

对偶理论：LP 最深刻的结论#

每个 LP 问题（原问题，Primal）都有一个对应的对偶问题（Dual）：

$$\text{原问题：最大化 } \mathbf{c}^T\mathbf{x},\ A\mathbf{x} \leq \mathbf{b},\ \mathbf{x} \geq 0$$

$$\text{对偶：最小化 } \mathbf{b}^T\mathbf{y},\ A^T\mathbf{y} \geq \mathbf{c},\ \mathbf{y} \geq 0$$

弱对偶定理：对偶可行解的值 $\geq$ 原始可行解的值（提供上界）。

强对偶定理（Strong Duality）：若原问题有最优解，则对偶问题也有最优解，且两者最优值相等。

这是 LP 理论最深刻的结论：一个极大化问题和一个极小化问题，居然有相同的最优值。

经济解释：原问题的对偶变量 $\mathbf{y}$（"影子价格，Shadow Price"）表示每单位约束松弛对最优值的边际贡献——约束的经济价值。

互补松弛（Complementary Slackness）把对偶落到实处：在最优解处，每个约束要么被用满（等号成立），要么其对偶变量为零——两者必居其一。用经济语言说：没有用完的资源，影子价格必为零（多给它一分也不会改善最优值）；影子价格为正的资源，必定被用得一点不剩。这条定理是灵敏度分析的基础——它告诉决策者哪些约束是真正的瓶颈，放松哪些约束纯属浪费。

与最大流-最小割的关系：最大流-最小割定理是对偶定理的组合版本——最大流 LP 的对偶正是最小割问题，两者的强对偶等价于 Max-Flow = Min-Cut。

整数线性规划（ILP）#

若决策变量必须是整数（如生产件数不能是 0.7 件），则为整数线性规划（Integer Linear Programming，ILP）。

ILP 是 NP-hard 问题——它比 LP 困难得多。标准求解方法是分支定界法（Branch and Bound）：

1. 先求 LP 松弛（忽略整数约束）
2. 若解已是整数，则完成
3. 若某变量取非整数值 $x^* = 3.7$，分支为两个子问题：$x \leq 3$ 和 $x \geq 4$
4. 递归求解每个子问题，用 LP 界剪枝

现代 ILP 求解器还结合割平面（Cutting Planes）、启发式等技术。分支定界之所以可行，全靠 LP 松弛提供的界足够紧：界越紧，剪枝越早，搜索树越小——ILP 求解器的大部分功力，其实花在"加固这个界"上（预处理、割平面、约束传播），而不是花在搜索本身。

0-1 背包、旅行商问题、调度问题等都可以建模为 ILP。

现实应用#

航空调度：航空公司每天用 LP/ILP 解决机组人员排班（Crew Scheduling）、飞机轮转（Aircraft Rotation）——这些问题有数十万变量，现代求解器在分钟内给出最优解。

电力调度：电网单位承诺问题（Unit Commitment）——哪些发电机开/关，以最小成本满足需求——是每天实时运行的大规模 ILP。

供应链优化：全球供应链的仓储、运输、生产配置决策，通常建模为多目标线性规划。

金融投资组合：Markowitz 均值-方差优化模型的计算核心是 QP（二次规划），是 LP 的直接推广。

机器学习（SVM）：支持向量机的训练在数学上是一个二次规划（QP）问题，是 LP 的推广。

跨域连接#

• 线性代数：约束定义一个凸多面体，线性目标的最优值必在顶点取到——顶点对应一组基变量，单纯形法的每次主元变换就是换基。这把几何直觉与矩阵运算对上了：沿一条边移动等于换掉基里的一个向量，而"没有更好的相邻顶点"这个终止条件就是检验数非负。退化与循环的麻烦也出自这里：同一个顶点可以对应多组基。
• 一般均衡：对偶变量就是影子价格，表示每放松一单位约束能带来多少最优值增量。互补松弛给出一条可检验的关系：没有用满的资源影子价格必为零，价格为正的资源必定用满。这也是把优化模型接入经济解释的接口——影子价格与市场价长期背离，说明该资源的配置存在改进空间。
• 网络流：最大流写成线性规划后，它的对偶恰是最小割，强对偶定理因此就是最大流最小割定理的一般形式。流问题特殊在约束矩阵全单模，保证顶点解自动是整数，割才具有组合意义。多数整数规划没有这个性质，这正是"哪些组合问题好解"的分水岭之一。
• 营养科学：最早的应用之一是用最低成本满足全部营养约束的食谱问题，数学上最优的解却几乎无法下咽。这不是模型算错，而是目标函数漏了"可接受性"这一维。教训在今天的配餐与饲料配方里依然成立：真实做法必须加上口味、多样性与食材上下限约束，而这些约束的多少直接决定最优成本被抬高多少。
• 碳预算与净零：把总排放上限写成一条约束、最小化减排总成本，这条约束的影子价格就是边际减排成本，也就是理论上的最优碳价。由此推出几条后果：约束越紧价格越高；一项技术只有在成本低于影子价格时才进入最优解；各部门若被分别设限，整体成本必然高于统一定价——因为多条约束的影子价格不再相等。

参考文献#

• Dantzig, G.B. Linear Programming and Extensions. Princeton University Press, 1963.
• Khachian, L. G. A Polynomial Algorithm in Linear Programming. Soviet Mathematics Doklady 20 (1979): 191–194.
• Bland, R. G. New Finite Pivoting Rules for the Simplex Method. Mathematics of Operations Research 2(2) (1977): 103–107.
• Karmarkar, N. "A New Polynomial-Time Algorithm for Linear Programming." Combinatorica 4(4), 1984.
• Grötschel, M., Lovász, L. & Schrijver, A. Geometric Algorithms and Combinatorial Optimization. Springer, 1988. （分离与优化等价的系统理论）
• Spielman, D. A. & Teng, S.-H. Smoothed Analysis of Algorithms: Why the Simplex Algorithm Usually Takes Polynomial Time. STOC 2001: 296–305（完整版见 JACM 51(3), 2004）.
• Vanderbei, R.J. Linear Programming: Foundations and Extensions. 4th ed. Springer, 2014.
• Bertsimas, D. & Tsitsiklis, J. Introduction to Linear Optimization. Athena Scientific, 1997.