Skip to content
返回搜索结果

单纯形法

提出者
George Dantzig
年份
1947
类型
algorithm
类别
Optimization

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

字号

它有什么作用?

单纯形法由乔治·丹齐格于1947年开发,是求解线性规划问题的基础算法。它系统地探索可行域的顶点,以在满足线性约束的条件下找到目标函数最大化或最小化的最优解。

方法背后的直觉

该方法通过从由线性约束定义的可行域的某个顶点开始,然后移动到能改善目标函数值的相邻顶点来工作。它持续进行,直到达到一个没有相邻顶点能提供进一步改进的顶点,从而保证最优性。该算法利用了线性规划的最优解位于约束多面体顶点的几何性质。

历史学

乔治·丹齐格于1947年引入了单纯形法,彻底改变了运筹学,并成为几十年来线性规划的标准算法。克利和明蒂(1972年)证明了其最坏情况下的指数时间复杂度,但经验上该方法仍然很快。20世纪80年代,内点法作为替代方法得到发展,但由于其鲁棒性和现代实现的复杂性,单纯形法在许多实际应用中仍然占主导地位。

何时使用

在求解具有有界可行域和线性目标函数的线性规划问题时应用单纯形法。它对于具有数百或数千个变量和约束的问题特别有效。如果问题是非线性的或无界的,则应避免使用它。对于非常大规模的问题,内点法可能更受青睐。

局限与注意事项

  • 指数级的最坏情况时间复杂度(尽管在实践中很少见)
  • 在高度退化的问题上表现可能不佳
  • 在非常大规模的问题上不如内点法有竞争力
  • 要求问题处于标准形式,并显式处理约束

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

优势

  • 保证在线性规划问题中有限时间内找到最优解
  • 在仔细实现和处理退化的情况下,实践中效率很高
  • 已广泛实现并得到成熟优化库的支持
  • 理解更高级优化算法的基础

应用

  • 生产计划:优化生产数量以最小化成本,同时满足需求约束
  • 运输与物流:确定仓库和配送中心之间最优的运输路线和数量
  • 投资组合优化:在风险和预算约束下,将资本分配到不同资产以最大化回报
  • 资源分配:分配劳动力和材料等有限资源以最大化组织产出
  • 混合问题:以最优比例混合原材料,以满足质量规格并最小化成本
  • 劳动力排班:为班次分配工人以最小化劳动力成本,同时满足需求

使用方式

使用方式

1

将线性规划转换为具有松弛变量的标准形式,并确定一个初始的基本可行解(如果可行,通常是原点)。

2

在单纯形表上执行主元操作:选择一个具有负约简成本的进基变量,通过最小比率检验确定出基变量,并更新基。

3

使用约简成本检查最优性条件;对于最大化问题,如果所有约简成本均非负,则当前解是最优的;否则返回主元步骤。

常见陷阱

  • 未能正确处理退化基引起的循环(使用布兰德规则或扰动法)
  • 不正确的主元选择或单纯形表更新中的算术错误导致数值不稳定
  • 在开始算法之前未检查无界性或不可行性

常见问题

为什么单纯形法被称为‘单纯形’?

“单纯形”一词指的是多面体在任何给定维度下的最简单形式。该算法通过沿着约束定义的该多面体的边和顶点移动来工作。

单纯形法与内点法有什么区别?

单纯形法停留在可行域的边界顶点上,而内点法则穿越可行域的内部。内点法具有更优的最坏情况复杂度,但对于中等规模的问题,单纯形法在实践中通常更快。

如何处理不可行性或无界性?

使用两阶段单纯形法:第一阶段求解一个辅助问题,以找到一个基本可行解或确定不可行性;第二阶段将标准单纯形法应用于原始问题。

什么是退化,为什么它很重要?

当一个基本可行解具有多个基表示时,就会发生退化,这可能导致循环。使用布兰德规则(按索引顺序选择变量)或扰动法来处理它。

相关方法

参考文献

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

    打开 DOI 文献
    已复制。
  2. Vanderbei, R. J. (2014). Linear Programming: Foundations and Extensions (4th ed.). Springer.

    打开 DOI 文献
    已复制。