第2章线性规划 §2.1线性规划的基本定理 §2.2单纯形算法 §2.3线性规划的内点算法 C 2007 Fang Weiguo School of economics and management
第2章 线性规划 • §2.1 线性规划的基本定理 • §2.2 单纯形算法 • §2.3 线性规划的内点算法 © 2007 Fang Weiguo School of Economics and Management
§2.1线性规划的基本定理 21.0线性规划发展简史 21.1基本定理与标准形式 212极点的代数特征 C 2007 Fang Weiguo School of economics and management
§2.1 线性规划的基本定理 • 2.1.0 线性规划发展简史 • 2.1.1 基本定理与标准形式 • 2.1.2 极点的代数特征 © 2007 Fang Weiguo School of Economics and Management
21.0线性规划发展简史 19世纪末,康特罗维奇和F.L. Hitchcock等研究运 输问题,但其工作长期未被人们所知。由于战争的需要, TC. Koopmans重新独立研究了运输问题。 ·1947年,GB. Dantzig发表单纯形法,应用于与国 防有关的问题。该法实用而有效。单纯形法被认为是20 世纪10大算法之一(其中还有快速 Fourier变换算法等)。 ·但1972年,V.Ke和 G. Minty给出病态例子,用 单纯形法求解可能要检査遍所有的顶点才能得到最优解, 所用时间为O(2").故单纯形法为指数时间算法。 ◎2007 Fang Weiguo School of economics and management
© 2007 Fang Weiguo School of Economics and Management
21.0线性规划发展简史 1979年,前苏联数学家提出了一种求解LP的椭球 算法,计算复杂性为O(n°L2)(L为输入长度)。该算法在理 论上很重要,但计算效率远不如单纯形法有效 ·能否找到有效的多项式时间算法?在此背景下, 1984年,在美国贝尔实验室工作的印度数学家 Karmarkar 给出了一个求解线性规划的新的多项式时间算法,计算复 杂性为O(n312)。通过例题试算,收敛到较好效果,人们 希望借助这种算法解决一些领域中的大规模问题的计算。 ◎2007 Fang Weiguo School of economics and management
© 2007 Fang Weiguo School of Economics and Management
21.0线性规划发展简史 ·对于现实生活中的大多数实际问题,单纯形法仍然 有效.基于单纯形法可以方便地讨论线性规划的对偶理 论,而基于对偶理论可以设计求解LP的对偶单纯形法和 原始一对偶算法及其它算法,因此单纯形法是目前应用最 广泛的算法之 LP之所以重要有以下方面的原因: ■理论算法发展较完善 ■现实生活中许多问题可用LP近似建模 ■在非线性规划的求解中,将问题局部线性化处理 C 2007 Fang Weiguo School of economics and management
© 2007 Fang Weiguo School of Economics and Management