KNOWECON WIKI

ARTICLE

Linear Programming

线性规划 (Linear Programming) 线性规划 (Linear Programming, LP) 是数学优化中最基础也是最重要的分支之一，研究在由一组线性不等式或等式定义的约束条件下，最大化或最小化一个线性目标函数的问题。线性规划的结构简洁、理论完备且算法高效，使其在经济学、运筹学、工程学、供应链管理、资源分配等诸多领域得到广泛应用。 标准形式

浏览 0 更新 2026-05-25

线性规划 (Linear Programming)

线性规划 (Linear Programming, LP) 是数学优化中最基础也是最重要的分支之一，研究在由一组线性不等式或等式定义的约束条件下，最大化或最小化一个线性目标函数的问题。线性规划的结构简洁、理论完备且算法高效，使其在经济学、运筹学、工程学、供应链管理、资源分配等诸多领域得到广泛应用。

标准形式

线性规划问题的标准形式通常写作：

min⁡xc⊤xs.t.Ax≥b,x≥0\begin{aligned} \min_{\mathbf{x}} \quad & \mathbf{c}^\top \mathbf{x} \\ \text{s.t.} \quad & A\mathbf{x} \geq \mathbf{b}, \quad \mathbf{x} \geq \mathbf{0} \end{aligned}

其中 x∈Rn \mathbf{x} \in \mathbb{R}^n 是决策变量向量，c∈Rn \mathbf{c} \in \mathbb{R}^n 是目标函数系数向量，A∈Rm×n A \in \mathbb{R}^{m \times n} 是约束系数矩阵，b∈Rm \mathbf{b} \in \mathbb{R}^m 是约束右端项向量。根据问题的具体需求，也可将目标函数写为最大化形式，约束条件可表示为等于号或小于等于号。通过引入松弛变量 (slack variables) 和剩余变量 (surplus variables)，任意形式的线性约束均可转化为标准形式。

可行域与基本可行解

线性规划中，所有满足约束条件的点 x \mathbf{x} 构成一个凸多面体 (convex polyhedron)，称为可行域。可行域具有以下关键性质：

  • 可行域是一个凸集：若 x1 \mathbf{x}_1 和 x2 \mathbf{x}_2 均为可行解，则其凸组合 λx1+(1−λ)x2 \lambda \mathbf{x}_1 + (1-\lambda)\mathbf{x}_2 （0≤λ≤1 0 \leq \lambda \leq 1 ）也是可行解。
  • 目标函数是线性的，因此既是凸函数也是凹函数。这意味着局部最优解一定是全局最优解。
  • 若最优解存在，则至少有一个最优解出现在可行域的顶点 (vertex) 或极点 (extreme point) 上。

这一极点性质是单纯形法 (Simplex Method) 的理论基础：算法通过沿着可行域的边在极点之间移动，逐步改进目标函数值，直至达到最优。

几何直观

对于一个二维线性规划问题，可行域的每个约束对应一条直线（半平面），所有半平面的交集构成一个凸多边形。目标函数在该多边形上的等值线是一族平行线。沿梯度方向移动等值线，直到与可行域恰好相切于某个顶点时，该顶点对应的目标函数值即为最优值。

在三维空间中，可行域是一个凸多面体，极点是多面体的角点。在 n n 维空间中，极点是 n n 个约束条件的交点在可行域内的点。

对偶理论

对偶理论 (Duality Theory) 是线性规划最深刻的理论支柱之一。每个原问题 (primal problem) 都对应一个对偶问题 (dual problem)：

max⁡yb⊤ys.t.A⊤y≤c,y≥0\begin{aligned} \max_{\mathbf{y}} \quad & \mathbf{b}^\top \mathbf{y} \\ \text{s.t.} \quad & A^\top \mathbf{y} \leq \mathbf{c}, \quad \mathbf{y} \geq \mathbf{0} \end{aligned}

对偶理论的核心结论包括：

  1. 弱对偶定理 (Weak Duality)：任意原问题可行解的目标函数值 c⊤x \mathbf{c}^\top \mathbf{x} 不小于任意对偶问题可行解的目标函数值 b⊤y \mathbf{b}^\top \mathbf{y} 。
  2. 强对偶定理 (Strong Duality)：若原问题存在最优解，则对偶问题也存在最优解，且两者的最优目标函数值相等：c⊤x∗=b⊤y∗ \mathbf{c}^\top \mathbf{x}^* = \mathbf{b}^\top \mathbf{y}^* 。
  3. 互补松弛性 (Complementary Slackness)：在最优点处，若某个原问题约束是紧的（取等号），则对应的对偶变量可取正值；若某个原问题约束是松的（严格不等式），则对应的对偶变量必须为零；反之亦然。

对偶变量 y \mathbf{y} 的经济学解释极为重要：每个对偶变量 yi y_i 衡量了相应约束资源 bi b_i 的边际贡献，即影子价格 (shadow price)。影子价格告诉决策者，若放宽一单位该约束条件（如增加一单位某种资源的可用量），最优目标函数值将改善多少。

单纯形法

单纯形法 (Simplex Method) 由 George Dantzig 于1947年提出，是求解线性规划问题最经典且在实际中极其有效的算法。算法的基本思想如下：

  1. 从一个初始基本可行解（即可行域的一个极点）出发。
  2. 检验当前解是否最优。若非最优，则沿一条改进方向移动至相邻的极点。
  3. 重复上述过程，直至无法进一步改进，此时达到最优解。

单纯形法中涉及的关键概念包括：

  • 基变量与非基变量：n n 个变量中选出 m m 个基变量，其余 n−m n-m 个非基变量设置为零。
  • 进基与离基：通过比值检验 (ratio test) 确定哪个非基变量进入基、哪个基变量离开基。
  • 退化 (Degeneracy)：当多个约束在同一极点处相交时，可能出现基变量取零值的情况，导致算法可能循环。Bland 规则 (Bland's Rule) 或字典序规则可防止循环。

尽管单纯形法在最坏情况下具有指数时间复杂度，但它在实际大规模问题中通常表现出多项式时间性能（平均情形下的效率极高）。

内点法

1984 年，Narendra Karmarkar 提出了投影尺度算法 (projection scaling method)，开辟了线性规划内点法 (Interior Point Methods, IPM) 的研究方向。与单纯形法沿可行域边界移动不同，内点法从可行域内部出发，沿着由障碍函数 (barrier function) 确定的路径——即中心路径 (central path)——逐步逼近最优解。

内点法的主要特点包括：

  • 每次迭代的步长较大，且理论上的迭代次数由多项式时间界保证。
  • 在处理大规模稀疏问题时，内点法往往比单纯形法更具竞争力。
  • 原始-对偶内点法 (primal-dual interior point method) 是当前最主流的内点法变体。

线性规划的变体与扩展

  • 整数线性规划 (Integer Linear Programming)：要求部分或全部决策变量取整数值。虽然整数规划是 NP-Hard 问题，但可通过分支定界法 (Branch and Bound) 和割平面法 (Cutting Plane Method) 求解。
  • 混合整数线性规划 (Mixed-Integer Linear Programming, MILP)：同时包含连续变量和整数变量的线性规划。
  • 随机线性规划 (Stochastic Linear Programming)：约束中的某些参数具有不确定性，通常通过场景树 (scenario tree) 建模处理。
  • 目标规划 (Goal Programming)：将多个冲突目标纳入线性规划框架，通过添加偏离变量实现。

线性规划的经济学应用

线性规划在经济学中有着极其广泛的应用：

  1. 投入产出分析：Leontief 投入产出模型可以用线性规划框架表示为在最终需求约束下最小化总投入的问题。
  2. 资源配置：厂商在资本和劳动约束下选择最优生产组合以实现利润最大化或成本最小化。
  3. 运输问题 (Transportation Problem)：在满足各目的地需求和各起运地供给约束下最小化运输成本，是线性规划的一个经典特例。
  4. 膳食问题 (Diet Problem)：在满足营养需求的前提下最小化饮食成本，是最早的线性规划应用之一（Stigler, 1945）。
  5. 一般均衡的理论基础：福利经济学第二定理在理性化 (rationalizing) 意义下与线性规划的对偶性密切相关。

线性规划的局限性

尽管线性规划强大而优雅，但它也存在一些内在局限：

  • 线性假设：现实世界中许多关系和目标函数都是非线性的。当使用线性近似时，可能会丢失重要的经济机制。
  • 确定性假设：标准线性规划假设所有参数是已知且确定的，无法直接处理不确定性。随机规划或鲁棒优化可以部分弥补这一不足。
  • 可分割性：线性规划允许决策变量取任意实数值，但在很多实际问题（如雇用员工数量、购买设备台数）中，变量必须为整数。
  • 规模问题：极大规模的线性规划问题（如变量数达数百万）虽然可用内点法或列生成法 (column generation) 处理，但对计算资源的要求依然很高。

历史回顾

线性规划的发展史是数学、经济学和计算科学交叉融合的缩影：

  • 1939 年：苏联数学家 Leonid Kantorovich 提出线性规划的雏形，用于解决生产计划问题，但他的工作在苏联之外长期不为人知。
  • 1947 年：George Dantzig 独立发现线性规划并发明单纯形法，被誉为"线性规划之父"。
  • 1947 年：John von Neumann 在 Dantzig 的一次演讲后立即提出了对偶理论的基本框架。
  • 1975 年：Kantorovich 和 Tjalling Koopmans 因将线性规划应用于资源配置理论获得诺贝尔经济学奖。
  • 1979 年：Leonid Khachiyan 提出椭球法 (Ellipsoid Method)，证明线性规划属于 P 类问题。
  • 1984 年：Karmarkar 提出内点法，为大规模线性规划提供了理论保证与高效实现。

总结

线性规划是优化理论中最完整的框架之一：它的全局最优性由凸性保证，对偶性提供了深刻的经济洞察，单纯形法和内点法确保了实际计算的高效性。无论是在微观经济学中的消费者选择与厂商决策，还是在宏观经济学中的最优增长路径，乃至在数据科学中的支持向量机 (SVM) 训练问题，线性规划的思想和方法都在持续发挥着基础而不可替代的作用。