KNOWECON WIKI

ARTICLE

线性规划 (Linear Programming)

线性规划 (Linear Programming) 线性规划（Linear Programming, LP）是数学优化中研究最深入、应用最广泛的分支之一，研究在若干线性等式或不等式约束下，最大化或最小化一个线性目标函数的问题。线性规划诞生于二十世纪中叶——Kantorovich（1939）在计划经济背景下提出木材厂最优生产安排问题并发展了解乘数法，Dantz

浏览 0 更新 2025-10-26

线性规划 (Linear Programming)

线性规划（Linear Programming, LP）是数学优化中研究最深入、应用最广泛的分支之一，研究在若干线性等式或不等式约束下，最大化或最小化一个线性目标函数的问题。线性规划诞生于二十世纪中叶——Kantorovich（1939）在计划经济背景下提出木材厂最优生产安排问题并发展了解乘数法，Dantzig（1947）在美国空军后勤规划中独立发明了单纯形法（Simplex Method），随后Koopmans（1951）将线性规划系统性地引入经济学，三人共享 1975 年诺贝尔经济学奖——使线性规划成为运筹学和经济分析的基石工具。

标准形式与几何直觉

线性规划的标准形式分为两大类。极大化标准形式为：

max⁡cTx=c1x1+⋯+cnxns.t.Ax≤b,x≥0\begin{aligned} \max \quad & \mathbf{c}^T \mathbf{x} = c_1 x_1 + \cdots + c_n x_n \\ \text{s.t.} \quad & A\mathbf{x} \leq \mathbf{b}, \quad \mathbf{x} \geq \mathbf{0} \end{aligned}

其中 c∈Rn\mathbf{c} \in \mathbb{R}^n 为目标系数（利润或成本系数），A∈Rm×nA \in \mathbb{R}^{m \times n} 为约束矩阵，b∈Rm\mathbf{b} \in \mathbb{R}^m 为右端常数（资源禀赋），x≥0\mathbf{x} \geq \mathbf{0} 为非负约束。任意线性规划均可通过引入松弛变量、拆分自由变量或取目标函数的相反数等操作转化为标准形式。

线性规划的几何结构极富规律性。每个线性约束对应超平面（Hyperplane），非负约束界定出正象限，所有约束的交集构成可行域（Feasible Region），是一个凸多面体（Convex Polytope）。由于目标函数是线性的，其等值面为平行的超平面族，最优解必然在可行域的某个顶点（极值点）上取得——这是线性规划基本定理的核心结论。直观上，线性目标函数的梯度方向总指向多面体的边界；沿该方向移动至再也无法前进时，即抵达某个顶点。这一几何事实是单纯形法设计的理论基础。

单纯形法与内点法

单纯形法的思想简洁而强大：从可行域的一个顶点出发，沿边棱移动到目标函数值更优的相邻顶点，直至无法改进为止。每一次迭代涉及一个基交换——将一个非基变量提升为基变量、同时将一个基变量降为非基变量。单纯形法的复杂度在理论上是指数级的（Klee-Minty 反例），但在实践中表现极其高效，多数实际问题的迭代次数约为约束数量的 2–3 倍。

内点法（Interior-Point Methods）提供了一条互补路径：从可行域内部出发，沿中心路径（Central Path）以牛顿步逼近最优解。Karmarkar（1984）首次证明内点法在线性规划上具有多项式时间复杂度，自此内点法与单纯形法形成二分格局：单纯形法在中小规模问题上反应敏捷且能提供灵敏度分析所需的最优基信息，内点法在超大规模稀疏问题上更具计算优势。

对偶理论

每一个线性规划问题都天然关联一个对偶问题。若原始问题为 max⁡{cTx∣Ax≤b,x≥0}\max \{\mathbf{c}^T \mathbf{x} \mid A\mathbf{x} \leq \mathbf{b}, \mathbf{x} \geq \mathbf{0}\}，则其对偶为 min⁡{bTy∣ATy≥c,y≥0}\min \{\mathbf{b}^T \mathbf{y} \mid A^T \mathbf{y} \geq \mathbf{c}, \mathbf{y} \geq \mathbf{0}\}。对偶变量 y\mathbf{y} 的经济含义是影子价格——第 ii 种资源每增加一单位，最优目标值的边际改善量。

弱对偶定理保证：任意原始可行解的目标值不超过对偶可行解的目标值。强对偶定理进一步断言：若一方存在有限最优解，则另一方亦然，且两者最优目标值相等。互补松弛条件揭示原始变量与对偶约束之间的"一紧一松"关系：若某原始变量严格为正，则其对偶约束必须取等号；若对偶约束严格松弛，则相应原始变量必为零。这些定理不仅为单纯形法和内点法提供了终止判据，更赋予线性规划深刻的经济解释能力。

经济应用

线性规划在经济和管理中的经典应用极为丰富。饮食问题（Diet Problem, Stigler 1945）以最小成本满足营养要求，是最早被形式化的 LP 模型之一；运输问题（Transportation Problem）在 mm 个产地与 nn 个销地之间最小化总运费，其约束矩阵具有全幺模性，最优解自动取整数值；生产计划问题确定产品组合以在资源约束下最大化利润，影子价格识别出真正稀缺的瓶颈资源；数据包络分析（DEA）运用线性规划评估决策单元的相对效率；投入产出分析（Leontief）的核心求解也依赖线性规划框架。

在博弈论中，两人零和博弈的极小极大定理可通过求解一对互为对偶的线性规划来证明和计算。在金融领域，线性规划用于投资组合构建（若以绝对偏差度量风险而非方差）和信用评分。

局限性与拓展

线性规划的前提假设——目标函数和约束均为线性——在诸多经济场景中过于严格。当生产函数呈现边际报酬递减、效用函数为非线性、或约束涉及整数决策（如机器台数、人员数量）时，需要分别求助非线性规划或整数规划。后者中，变量的整数性要求使可行域失去凸性，求解难度大幅上升，分支定界法和割平面法成为主要工具。

此外，线性规划的目标系数和约束参数在实践中常受制于数据不确定性，随机规划和鲁棒优化为其提供了应对范式。线性规划的灵敏度分析通过改变目标系数和右端常数，在不需要重新求解的情况下确定最优解保持不变的参数变化范围，这在管理决策中尤为实用——管理者可以迅速回答"原材料价格波动到何种程度需改变生产计划"等日常问题。

尽管如此，线性规划以其严密的理论体系（对偶性、灵敏度分析、多项式可解性）和成熟的商业求解器（CPLEX、Gurobi），至今仍是运筹学与经济分析不可替代的基础工具。其在供应链管理、能源调度、航空机组排班等领域的日常应用规模可达数百万变量与约束，这一事实本身就是其经济价值的终极证明。