线性规划 学术论文

第二章 线性规划理论简述

2.1 理论的渊源及演进过程

（1）线性规划理论发展的萌芽期

法国数学家J.- B.- J.傅里叶和C.瓦莱－普森分别于1832和1911年独立地提可解的问题会有一个简单多边形的可行域出线性规划的想法，但未引起注意。二十几年后，1939年苏联数学家Л.В.康托罗维奇在《生产组织与计划中的数学方法》一书中提出线性规划问题，也未引起重视。此后的十几年中，线性规划只是作为一个还不成形的思想并未引起世界的重视。

（2）线性规划理论发展的成长期

1947年美国数学家G.B.Dantzing提出求解线性规划的单纯形法，为这门学科奠定了基础。同年，1947年美国数学家J.von诺伊曼提出对偶理论,开创了线性规划的许多新的研究领域，扩大了它的应用范围和解题能力。1951年美国经济学家T.C.库普曼斯把线性规划应用到经济领域，为此与康托罗维奇一起获1975年诺贝尔经济学奖。

（3）线性规划理论发展的成熟期

50年代后对线性规划进行大量的理论研究，并涌现出一大批新的算法。例如，1954年C.莱姆基提出对偶单纯形法，1954年S.加斯和T.萨迪等人解决了线性规划的灵敏度分析和参数规划问题，1956年A.塔克提出互补松弛定理，1960年G.B.丹齐克和P.沃尔夫提出分解算法等。线性规划的研究成果还直接推动了其他数学规划问题包括整数规划、随机规划和非线性规划的算法研究。由于数字电子计算机的发展，出现了许多线性规划软件，如MPSX，OPHEIE，UMPIRE等，可以很方便地求解几千个变量的线性规划问题。1979年苏联数学家L.G.Khachian提出解线性规划问题的椭球算法，并证明它是多项式时间算法。1984年美国贝尔电话实验室的印度数学家N.卡马卡提出解线性规划问题的新的多项式时间算法。用这种方法求解线性规划问题在变量个数为5000时只要单纯形法所用时间的1/50。现已形成线性规划多项式算法理论。

由于单纯形法是求解线性规划模型的常用方法，并且其在求解线性规划模型上使用相当广泛，因此国内外对于单纯形法的研究成果可体现国内外对线性规划在数学建模中的研究进程。

2.2国外有关研究的综述

1983年，S.Smale再次给出了Borgwardt在1982年证明的单纯形法平均多项式时间复杂类似的结果，这些结果都表明此算法虽然在最坏情况下是“差”算法，但是，它的平均复杂性是“好”的。

1992年，J.J.Forrest和D.Goldfarb给出了steepest.edge规则的若干变形和与之相应的递推公式，数值实验结果表明单纯形法与当时正处于发展势头强劲之际的内点法确实存在不分高低和难分伯仲的竞争状态。

2002年，R.E.Bixby在“Solving real-world linear programs:a decade and more of progress”文章中总结了对偶单纯形法从20世界90年代以后的新进展，并指出它已经成为最有效的求解线性规划问题的方法之一【1】。

2.3国内研究的综述

国内有关学者们对于单纯形法的各方面研究成果也不计其数，依照目前已经公开发表的资料来看：

郭秀英在“线性规划单纯形法迭代法则的改进”【2】文章中提出一种当进、出变量唯一不变时的可减少迭代次数的判断进、出变量的新法则，并验证了其有