什么是LP问题

线性规划（LP）问题：定义与求解方法

线性规划（Linear Programming，简称 LP）是运筹学中研究较早、应用广泛的优化模型，核心是在一组线性约束条件下，求解线性目标函数的最大值或最小值。它在资源分配、生产计划、物流优化等领域有重要应用。

LP 问题的核心构成

一个标准的 LP 问题包含三个要素：

1. 决策变量：需要优化的未知量（通常记为x₁, x₂, ..., xₙ），代表实际问题中的可调整参数（如生产数量、运输量等）。
2. 目标函数：关于决策变量的线性函数，需最大化（max）或最小化（min）。
   形式：max/min z = c₁x₁ + c₂x₂ + ... + cₙxₙ（cᵢ为系数，代表各变量对目标的贡献）。
3. 约束条件：关于决策变量的线性等式或不等式，描述问题的限制（如资源总量、生产能力等）。
   形式：
   • 不等式约束：aᵢ₁x₁ + aᵢ₂x₂ + ... + aᵢₙxₙ ≤ bᵢ 或 ≥ bᵢ（i=1,2,...,m）
   • 等式约束：aᵢ₁x₁ + ... + aᵢₙxₙ = bᵢ
   • 非负约束：xᵢ ≥ 0（通常默认决策变量非负）

示例：简单 LP 问题

某工厂生产 A、B 两种产品，A 每件利润 3 元，B 每件利润 5 元。生产 1 件 A 需 2 小时工时，生产 1 件 B 需 3 小时工时，总工时不超过 12 小时。求最大利润。

• 决策变量：x₁（A 的产量），x₂（B 的产量）。
• 目标函数：max z = 3x₁ + 5x₂（最大化利润）。
• 约束条件：
  2x₁ + 3x₂ ≤ 12（工时约束），
  x₁ ≥ 0, x₂ ≥ 0（非负约束）。

LP 问题的求解方法

LP 问题的求解方法需利用 “线性” 特性，核心是在可行域（约束条件构成的区域） 中找到目标函数的最优解（线性函数的最优解必在可行域的顶点处取得）。常见方法包括：

1. 单纯形法（Simplex Method）

核心思想

从可行域的一个顶点（基可行解）出发，通过迭代移动到 “更优” 的顶点，直至找到目标函数的最大值或最小值。

步骤

1. 标准化：将约束条件转化为等式（引入松弛变量、剩余变量），确定初始基可行解（可行域的一个顶点）。
2. 检验最优性：通过检验数判断当前顶点是否为最优解（若所有检验数≤0，对最大化问题为最优）。
3. 迭代改进：若未达最优，选择 “进基变量”（使目标函数增长最快的变量）和 “出基变量”（保持解的可行性），通过初等行变换移动到新顶点。
4. 终止：重复步骤 2-3，直至找到最优解或判断无界。

特点

• 适用于大多数 LP 问题，效率高，是工业界的主流方法。
• 最坏情况下时间复杂度较高，但实际应用中表现优异。

2. 障碍函数法（Barrier Method）

核心思想

属于内点法的一种，通过在目标函数中加入 “障碍项”（惩罚函数），将约束条件转化为目标函数的一部分，使优化过程始终在可行域内部进行，最终逼近原问题的最优解。

步骤

1. 构造障碍函数：对不等式约束（如gᵢ(x) ≤ 0），引入障碍项（如-μΣln(-gᵢ(x))，μ>0为障碍参数），将原问题转化为无约束优化问题：
   min f(x) + μ·B(x)（B(x)为障碍项，f(x)为原目标函数）。
2. 参数控制：通过逐步减小μ（如μ → 0），使障碍项影响减弱，目标函数的最优解逐渐逼近原 LP 问题的最优解。
3. 无约束优化：对每个μ，用梯度下降等方法求解障碍函数的最优解，作为下一次迭代的初始点。

特点

• 从可行域内部迭代，适合大规模 LP 问题（如金融、工程中的高维优化）。
• 收敛速度快，数值稳定性好。

3. 原始对偶法（Primal-Dual Method）

核心思想

同时处理 LP 问题的原始问题和对偶问题，通过构造 “互补松弛条件”，迭代调整原始解和对偶解，直至两者都满足最优性条件。

步骤

1. 建立对偶问题：根据原始问题的约束和目标，写出对偶问题（变量和约束存在对应关系：原始的约束对应对偶的变量，原始的变量对应对偶的约束）。
2. 初始化：给定原始问题的可行解和对偶问题的可行解。
3. 迭代优化：通过 “对偶间隙”（原始目标与对偶目标的差值）判断是否最优，若未最优，调整原始变量和对偶变量，使间隙减小。
4. 终止：当对偶间隙趋近于 0 时，得到原始问题的最优解。

特点

• 无需处理人工变量，对某些问题（如网络流、整数规划松弛问题）效率高于单纯形法。
• 能同时提供原始解和对偶解，便于敏感性分析（如资源影子价格的求解）。

LP 问题的应用场景

• 资源分配：如在有限的人力、物力下，最大化生产收益。
• 生产计划：确定产品产量，满足需求约束并最小化成本。
• 物流优化：设计运输路线，最小化运输成本（如车辆调度、仓库选址）。
• 金融投资：在风险约束下，最大化投资组合收益。

总结

线性规划（LP）问题是在 linear 约束下求解 linear 目标函数极值的优化问题，其核心是利用可行域的顶点特性寻找最优解。单纯形法、障碍函数法、原始对偶法是三类经典求解方法，分别适用于不同场景：单纯形法适合常规问题，障碍函数法适合大规模问题，原始对偶法适合需同时分析原始与对偶解的场景