Skip to content
返回搜索结果

确定性线性规划 — 具有确定性参数的经典线性规划

提出者
George B. Dantzig
年份
1947
类型
Deterministic mathematical optimization
类别
Simulation / optimization

本文为机器翻译,尚未经过审校。 阅读英文原文

字号

它有什么作用?

确定性线性规划(DLP)是线性规划的经典形式,其中所有目标函数系数、约束系数和右侧值都确定已知。它在固定的、确定的数据下,通过最大化或最小化线性目标函数并满足线性约束,来寻找最优的资源分配,提供精确且可复现的解。

方法背后的直觉

设想将固定预算分配给各个项目,每个项目都有已知的成本和回报,并受到您精确了解的资源上限的限制。确定性线性规划将其编码为一组线性不等式,并找到能从这些约束中榨取最大价值的顶点解。由于每个参数都是确定的——没有概率分布,没有歧义——求解器会返回一个单一的精确最优方案,而不是一系列结果。这种清晰性使得在数据测量良好且不确定性不是主要关注点时,DLP成为自然的首选模型。

历史学

线性规划由 George B. Dantzig 于 1947 年在为美国空军工作期间通过开发单纯形算法正式确立。Dantzig 1963 年的专著成为标准参考。当引入随机线性规划变体时(Dantzig and Beale, 1950s–1960s),“确定性”这一限定词出现,以区分原始的确定性参数模型与其概率性扩展。

何时使用

当决策问题可以用线性目标和线性约束建模,并且所有参数都已知且确定性足以将其视为固定常数时,使用确定性线性规划。理想的应用场景包括生产计划、运输和物流、饮食和混合问题,以及稳定条件下的网络流问题。当参数确实不确定且风险很重要时,请勿使用 DLP——而应优先选择随机线性规划或鲁棒线性规划。当目标或约束是非线性的、变量必须是整数(使用 MIP)时,或者必须同时平衡多个冲突目标而不能将它们聚合成一个加权和(使用多目标线性规划或目标规划)时,应避免使用 DLP。

局限与注意事项

  • 要求所有关系严格线性——无法在没有近似的情况下捕捉非线性成本曲线或收益递减。
  • 所有参数必须已知且固定;模型不提供处理不确定性或参数估计误差的原生机制。
  • 最优解可能不唯一(退化),使得报告基的选择在没有附加标准的情况下变得模糊。
  • 整数或组合要求(例如,是/否决策)需要扩展到混合整数规划,这在计算上更难。
  • 具有密集约束矩阵的大规模问题即使对于现代求解器来说也可能占用大量内存。

来源中的条件不能替代独立的科学审查或分析引擎的验证。

优势

  • 对于任何可行且有界的线性规划实例,由于凸性而保证全局最优解。
  • 高度可扩展——现代求解器能在几秒钟内处理数百万个变量和约束。
  • 对偶变量和敏感性分析提供了对影子价格和范围的丰富经济解释。
  • 透明、可审计的模型:每个假设都在约束矩阵中明确体现。
  • 成熟的软件生态系统(CPLEX、Gurobi、HiGHS、GLPK),具有可靠、经过充分测试的实现。
  • 清晰的通过/失败可行性信号:不可行性可立即揭示模型设定错误。

应用

  • 生产和制造调度,具有固定的资源容量和已知的需求。
  • 运输和物流:在网络中寻找最低成本的运输路线。
  • 饮食和混合问题:制定满足成分约束的最低成本营养或化学混合物。
  • 在具有线性回报和预算约束的金融投资组合优化。
  • 能源系统规划:具有已知成本和容量的发电单元的最优调度。
  • 供应链网络设计,当需求和提前期被视为已知常数时。

使用方式

使用方式

1

定义决策变量 x(例如,生产数量、流量),目标函数 c^T x(最小化或最大化),以及约束集 Ax <= b,其中 x >= 0。c、A 和 b 中的所有系数都被视为精确的已知常数——这就是使模型确定的原因。写出标准形式的线性规划:min c^T x,约束条件为 Ax = b,x >= 0。

公式
\min_{x} \; c^\top x \quad \text{s.t.} \quad Ax \leq b, \; x \geq 0
2

在优化之前,验证可行域非空(约束集至少有一个解)并且目标有界。如果可行域为空,则问题不可行;如果目标无界,则模型设定错误。这些检查由求解器自动执行,但分析师应进行解释以捕获模型错误。

3

使用单纯形算法(沿着凸多面体的边向最优顶点进行旋转操作)或内点法(沿着可行域内部的路径进行搜索)来求解线性规划。这两种方法都利用了可行集和目标函数的凸性与线性度,保证了任何局部最优解都是全局最优解。现代求解器(CPLEX、Gurobi、HiGHS)能高效处理数百万个变量和约束。

4

求解器返回最优决策向量 x* 和最优目标值 c^T x*。由于可行域是凸多面体且目标函数是线性的,最优解总是在一个顶点(基本可行解)处达到。记录 x* 并验证它满足所有约束,然后将其翻译回管理术语(例如,要生产的单位、要使用的路线)。

公式
x^* = \arg\min \{ c^\top x : Ax \leq b,\; x \geq 0 \}
5

在获得 x* 后,进行敏感性(最优后)分析,以确定 c 或 b 中的每个系数在当前基(以及最优解)发生变化之前可以变化的幅度。影子价格(对偶变量)量化了放宽每个约束的边际价值。尽管模型是确定性的,敏感性分析仍能在不放弃确定性框架的情况下,揭示解对参数估计误差的稳健性。

常见陷阱

  • 将不确定参数视为固定点估计而不进行后续敏感性分析,可能会产生纸面上最优但在实践中脆弱的解。
  • 忘记包含非负约束或逻辑边界可能产生数学上最优但操作上不可行的解(例如,负生产数量)。
  • 误解影子价格为超出范围分析中确定的有效范围的保证边际价值。
  • 在真实问题具有整数结构(例如,卡车数量)时使用 DLP,然后对 LP 解进行四舍五入——这可能会违反约束或错过真正的整数最优解。
  • 将多个目标过度聚合为单一加权和,而未经验证权重是否准确反映了利益相关者的偏好,从而隐藏了重要的权衡。

常见问题

是什么使线性规划成为“确定性”的,而不是“随机性”的?

在确定性线性规划中,目标函数、约束矩阵和右侧向量中的每个系数都是已知的常数。相比之下,随机线性规划将其中一些或所有系数视为具有概率分布的随机变量,寻求在期望值或高概率下表现良好的解。

单纯形算法总是高效的吗?

在实践中是的——单纯形方法能极快地解决几乎所有现实世界的线性规划问题。理论上,在最坏情况下(Klee–Minty 示例)可能需要指数时间,但内点法(例如,Karmarkar 算法)在多项式时间内运行,并且对于非常大的实例具有竞争力。

如果我的一些决策变量必须是整数,我能使用 DLP 吗?

不能。如果变量必须是整数(例如,要购买的机器数量),则模型将成为混合整数或纯整数规划。求解 LP 松弛并进行四舍五入可能会违反约束或错过真正的整数最优解;请改用专用的 MIP 求解器。

求解后,影子价格如何提供帮助?

约束的影子价格(对偶变量)告诉您,在有效范围允许的情况下,如果该约束的右侧放宽一个单位,目标值将提高多少。这有助于指导在哪里投资以最经济有效地扩大产能。

何时应从 DLP 升级到鲁棒或随机线性规划?

当参数不确定性非同小可,并且在实际参数值下出现不可行或糟糕解的成本很高时进行升级。如果一个关键系数的 10-20% 的偏差会改变首选解或导致约束违反,那么确定性线性规划的确定性假设就过于强烈了。

相关方法

参考文献

  1. Dantzig, G. B. (1963). Linear Programming and Extensions. Princeton University Press, Princeton, NJ.

    ISBN:9780691059136
    已复制。
  2. Linear programming. Wikipedia.

    打开出版物文献
    已复制。