单纯形法(Simplex Method)

单纯形法(Simplex Method)是求解线性规划问题的经典算法,由美国数学家丹齐格于一九四七年提出。它把线性规划的可行域理解为高维空间中的凸多面体,利用最优解必在顶点取得的性质,从一个顶点出发沿多面体的棱移动到使目标函数改善的相邻顶点,反复迭代直到无法再改进,即得到最优解。

概述

线性规划研究在线性约束下最大化或最小化线性目标函数,是运筹学的核心问题。单纯形法通过把约束整理为标准型并引入松弛变量,在由基本可行解构成的顶点间跳转。它虽在人为构造的极端情形下可能遍历指数级顶点,但在几乎所有实际问题中都以近似线性的迭代次数快速收敛,是最具影响力的优化算法之一。

核心特点

• 顶点搜索:最优解必位于可行域凸多面体的某个顶点,算法只在顶点集合中搜索。
• 换基迭代:每步通过选入基变量和选出基变量,从当前顶点移动到目标更优的相邻顶点。
• 最优判定:当所有非基变量的检验数都不再能改善目标时,当前顶点即为最优解。
• 特殊处理:通过大 M 法或两阶段法解决初始可行解的寻找,并用扰动等规则避免退化引起的循环。

应用场景

单纯形法广泛应用于生产计划、资源分配、运输调度、投资组合、饮食配比与网络流建模等领域。许多商业与开源优化求解器都以单纯形法及其对偶变体作为核心引擎,它也是理解对偶理论和整数规划分支定界的基础。

常见问题

问:单纯形法最坏指数,为何仍被广泛使用?答:指数复杂度只在刻意构造的病态实例上出现,现实问题的迭代次数通常与约束数量近似成线性,配合成熟的数值实现,单纯形法在实践中极为高效稳定。

问:它与内点法有何区别?答:单纯形法沿可行域边界的顶点移动,内点法则从可行域内部逼近最优;内点法有多项式复杂度保证,大规模问题上有时更优,二者常互补使用。