单纯形法

本文的阅读等级：中级 美国数学家丹齐格 (George Dantzig) 于1947年提出第一个有效的线性规划算法──单形法，或称单纯形法 (simplex method)，被后人誉为线性规划之父。1946年丹齐格从加州大学柏克莱分校取得博士学位，次年他以数学顾问身份为美国空军工作，经常他被要求解决一些与规划相关的问题，譬如，如何配置预算、人力、飞机，及其他资源使达到**的成本效益。因为这些问题多少与经济学有关，丹齐格跑去征询经济学家科普斯曼 (Tjalling Koopmans，1975年诺贝尔经济学奖得主)

线性规划 (LP) 涉及尽可能地减少或增加受边界、线性等式和不等式约束的目标函数。示例问题包括工程中的设计优化、生产中的利润最大化、金融业中的投资组合优化以及能源和交通行业中的调度。 线性规划是寻找将函数最小化的向量 x 的数学问题： 受线性约束： 内点法：采用原始-对偶预估-校正算法，尤其适合于具有特殊结构或可通过稀疏性矩阵定义的大规模问题