Simplex Method

定义 Definition

单纯形法（simplex method）：一种用于求解线性规划（linear programming）问题的经典算法，通过在可行域的“顶点”（基本可行解）之间迭代移动，逐步改进目标函数值，直到达到最优解（或判定无界/无可行解）。常见形式包括表格法（tableau）与修正单纯形法（revised simplex）。（线性规划之外也有更广义的“单纯形”概念，但此处主要指线性规划算法。）

发音 Pronunciation (IPA)

/ˈsɪm.plɛks ˈmɛθ.əd/

例句 Examples

We used the simplex method to solve the linear programming problem.
我们用单纯形法来求解这个线性规划问题。

After converting the constraints into standard form, the analyst applied the simplex method and performed several pivots until the objective value could no longer be improved.
在把约束条件转成标准形式后，分析师使用单纯形法并进行了多次主元变换，直到目标函数值无法再提升为止。

词源 Etymology

simplex 源自拉丁语 simplex，意为“单一的、简单的”（sim- “一” + -plex “折叠/层”相关）。在数学里，“单纯形（simplex）”指高维空间中由若干点构成的最简单多面体（如三角形、四面体）。单纯形法由 George Dantzig 在 20 世纪中期提出，用来在多面体可行域的顶点之间高效搜索最优解，因此得名。

相关词 Related Words

• Linear Programming
• Optimization
• Constraint
• Objective Function
• Feasible Solution
• Pivot
• Tableau
• Duality
• Revised Simplex
• Interior-Point Method

文学与著作 Literary Works

• George B. Dantzig — Linear Programming and Extensions（线性规划与扩展）
• Hamdy A. Taha — Operations Research: An Introduction（运筹学导论）
• Frederick S. Hillier & Gerald J. Lieberman — Introduction to Operations Research（运筹学导论）
• Mokhtar S. Bazaraa, John J. Jarvis & Hanif D. Sherali — Linear Programming and Network Flows（线性规划与网络流）
• Vašek Chvátal — Linear Programming（线性规划）