Skip to content
返回搜索结果

线性规划 — 线性目标在约束下的最优化

提出者
George B. Dantzig
年份
1947
类型
Mathematical programming / continuous optimization

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

字号

它有什么作用?

线性规划(LP)由乔治·B·丹齐格(George B. Dantzig)于1947年开创,是一种数学方法,用于在满足一组线性的不等式和等式约束的条件下,找到线性目标函数(如最低成本或最高利润)的最佳值。它是运筹学的基本技术,是生产计划、资源分配、物流、饮食问题以及工程、经济学和自然科学中无数其他决策场景的基础。

方法背后的直觉

设想您经营一家生产两种产品的小工厂。每种产品都能为您带来一定的利润,但生产它会消耗有限的原材料和机器时间。线性规划可以找到一种精确的产品组合,在不违反任何物理或合同限制的情况下,从您的固定资源中榨取最大的利润。“线性”意味着利润和资源消耗与您生产的数量成直线关系。可行选择构成一个多边形(在二维空间中)或一个多面体(在高维空间中),而最优解始终位于其顶点之一。

历史学

线性规划的系统性发展始于1947年,当时乔治·B·丹齐格(George Dantzig)在美国空军工作,发明了单纯形算法来自动化军事后勤规划。丹齐格在他的1963年专著中发表了基础理论,该专著至今仍是标准参考。苏联的列昂尼德·坎托罗维奇(Leonid Kantorovich)独立且并行地工作(1939年),使用类似的数学思想解决了生产计划问题,坎托罗维奇因这项贡献于1975年获得诺贝尔经济学奖。多项式时间可解性的理论问题由卡恰恩(Khachian)的椭球方法(1979年)和后来的卡尔马卡(Karmarkar)的内点法(1984年)解决,后者被证明对大规模问题非常有效。如今,商业和开源LP求解器已嵌入全球的企业资源规划、航空调度和能源系统中。

何时使用

只要您需要优化一个数量,该数量线性地依赖于一组决策变量,并且所有约束也是线性的,线性规划就是适用的。它不需要任何分布假设,也不需要最小样本量——它是一个确定性的数学模型,而不是统计估计量。当决策变量是连续的时(分数是有意义的),该方法适用;如果变量必须是整数或二进制,则需要整数规划。

局限与注意事项

  • 线性要求:如果目标函数或任何约束是非线性的,LP模型就会被错误设定,解可能不正确或不可行。
  • 仅限连续变量:当决策变量必须取整数或二进制值时,LP松弛给出了下界,但不是有效解;必须使用整数规划。
  • 确定性:LP不模拟参数中的不确定性;当数据不确定时,需要随机规划或鲁棒优化。
  • 退化和循环:在罕见情况下,单纯形法可能会在退化基之间循环而不收敛,尽管反循环规则(例如,Bland规则)可以解决这个问题。

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

优势

  • 保证全局最优:由于可行区域是一个凸多面体,任何局部最优解也是全局最优解,不存在陷入次优解的风险。
  • 高度可扩展:现代求解器(HiGHS、Gurobi、CPLEX)可以在几秒钟内处理包含数百万个变量和约束的模型。
  • 丰富的后验解信息:影子价格和敏感性范围提供了关于资源价值和解的鲁棒性的可操作见解,而无需额外的运行。
  • 无分布假设:LP是一个纯粹的代数模型,因此不需要正态性或数据的任何统计特性。

应用

  • 生产计划:在尊重机器产能和原材料限制的同时,找到最大化利润的最优产品组合。
  • 供应链和运输物流:最小化仓库和客户网络之间的运输成本。
  • 饮食和混合问题:选择满足营养需求的配料数量,同时最小化成本。
  • 金融投资组合优化:在风险和监管约束下,将资本分配到不同资产以最大化预期回报。
  • 能源调度和电网规划:在满足电力需求和发电机容量限制的同时,最小化燃料成本。
  • 人员和劳动力调度:以最低的劳动力成本分配班次给工人以满足需求。

使用方式

使用方式

1

现实世界的决策问题被转化为数学符号。您需要确定决策变量(您可以控制的数量),将目标函数(您想要最大化或最小化的内容)写成这些变量的线性组合,并将每个约束(资源限制、产能上限、需求要求)写成线性不等式或等式。一个格式良好的LP模型具有明确的目标、显式的变量界限以及所有结构性约束都以线性的方式表达。

2

模型被转换为求解器可以处理的标准形式或规范形式。通过引入非负的松弛变量或剩余变量,将不等式转化为等式,并且任何无约束变量都被两个非负变量的差所取代。这个机械步骤会产生算法作用的表或矩阵表示,它不会改变问题本身,只是为了计算而重塑它。

3

求解器在可行多面体内搜索最优顶点。经典的单纯形法(Simplex method)从一个顶点沿着多面体的边移动到另一个顶点,始终改进(或保持)目标函数,直到没有可以改进的邻近顶点为止。内点法(Interior-point methods)则沿着中心路径穿越可行区域的内部,这对于非常大的模型尤其有效。当最优解存在时,这两种方法都能保证找到全局最优解,因为可行区域是凸的。

4

求解器返回决策变量的最优值和最优目标值,以及对偶变量(影子价格)和敏感性范围。影子价格量化了如果一个约束的右侧值放松一个单位,目标函数会改善多少——直接告诉决策者在哪里增加资源最有价值。敏感性分析确定了成本系数或右侧值在当前基数不再最优之前可以改变多少。

常见陷阱

  • 在线性约束或目标函数非线性时应用LP——解将是错误的,或者求解器将拒绝该模型。
  • 忽略整数要求:将连续LP解四舍五入为整数通常不能得到可行或最优的整数解;应使用整数规划。
  • 不可行或无界模型:如果可行区域为空(约束冲突)或目标函数无界(缺少界限约束),求解器将报告失败——在运行前务必检查模型结构。
  • 将LP输出视为没有敏感性分析的建议:一个技术上最优的解可能处于一个非常狭窄的范围内,数据的微小变化就会改变建议——应始终检查敏感性范围。

常见问题

什么使得一个问题在LP的意义上是“线性的”?

目标函数和每个约束都必须是线性的——这意味着每个项是常数乘以单个决策变量,没有变量的乘积,没有指数,也没有非线性函数。即使一个约束或目标函数涉及例如x乘以y或x的平方,标准的LP也不再适用,需要非线性或二次规划求解器。

为什么最优解总是在可行区域的顶点上?

由线性约束定义的可行区域是一个凸多面体(或多胞体)。线性目标函数本身就是线性的,因此它不能被“拉向”凸集的内部——它总是在边界上达到其极值,特别是达到一个顶点(角点)。这是单纯形法逐顶点策略的几何洞察。

我应该何时使用整数规划而不是LP?

当一个或多个决策变量必须取整数或二进制(0/1)值时——例如,是否开设一个工厂(是/否),调度多少辆卡车(整数),或者选择包含哪些项目。简单地求解LP并将连续解四舍五入通常是不可靠的:四舍五入的解可能是不可行的或远离最优解。整数规划能正确处理整数性,但计算成本更高。

影子价格告诉我什么?

绑定约束的影子价格(对偶变量)表示在保持其他所有条件不变的情况下,如果该约束的右侧值放松一个单位,最优目标值会提高多少。例如,劳动小时约束的影子价格为3,意味着增加一个小时的劳动将使目标值提高3个单位。不绑定的约束影子价格为零——它们没有限制当前的最优值。

相关方法

参考文献

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

    ISBN:9780691059136
    已复制。
  2. Vanderbei, R.J. (2014). Linear Programming: Foundations and Extensions. Springer.

    打开 DOI 文献
    已复制。