第二章线性规划

第一节线性规划概述

线性规划(linear programming，LP)是运筹学中研究较早、发展较快、应用广泛、方法较成熟的一个重要分支，它是辅助人们进行科学管理的一种数学方法，通常用来解决资源的最优利用、设备的最佳运行等问题，以提高经济效果。在经济管理、交通运输、工农业生产等经济活动中，提高经济效果一般通过两种途径：一是技术方面的改进，例如改善生产工艺，使用新设备和新型原材料；二是生产组织与计划的改进，即合理安排资源。线性规划所研究的是：(1)当一项任务确定后，如何统筹安排尽量做到以最少的人力、物力、财力等资源去完成；(2)已知一定数量的人力、物力、财力等资源，如何安排使用它们使完成的任务(创造的价值或实现的利润等)最多。一般地，求线性目标函数在线性约束条件下的最大值或最小值的问题，统称为线性规划问题。满足线性约束条件的解叫做可行解，由所有可行解组成的集合叫做可行域。决策变量、约束条件、目标函数是线性规划的三要素。

在20世纪30年代后期，前苏联数学家、诺贝尔经济学奖获得者(1975年)利奥尼德·康托洛维奇(L.V.Kantorovich)研究工业生产组织中的机器负荷分配和原材料的合理利用等问题时，把资源最优利用这一传统的经济学问题，由定性研究和一般的定量分析推进到现实计量阶段，对于在企业范围内如何科学地组织生产和在国民经济范围内怎样最优地利用资源等问题做出了独创性的研究。他于1939年发表论文《生产组织和计划中的数学方法》，提出了类似线性规划的模型，并给出了“解乘数法”的求解方法，但当时并未受到重视。

1946年，时任美国空军数学顾问的乔治·伯纳德·丹兹格(G.B.Dantzig)，面临解决如何使规划过程机械化的问题。具体任务是：寻找一个方法能更快地计算出分时间段的调度、训练和后勤供给的方案。当时计算这些问题，都是依靠经验总结出的优先准则，而不是当成一个大系统来考虑，也没有一个明确的目标函数。丹兹格深入研究了这个问题以后，于1947年正式提出“线性规划”的概念，并提出了单纯形求解方法。这个方法在线性规划领域沿用多年，至今还在发挥作用，丹兹格因此被评为“线性规划之父”。

丹兹格认为关于线性规划的理论是受到冯·诺伊曼(Von Neumann)帮助，后者在1947年提出了对偶理论，开创了线性规划许多新的研究领域，扩大了它的应用范围和解题能力。线性规划提出后很快受到经济学家的重视，如在第二次世界大战中从事运输模型研究的美国经济学家库普曼斯(T.C.Koopmans)很快看到了线性规划在经济领域中的应用，并于1951年出版《生产与配置的活动分析》一书，他本人也因在发展线性规划方法以及革新、推广和发展资源最优利用理论方面所做出的杰出贡献，与康托洛维奇一起分享1975年度诺贝尔经济学奖。

20世纪50年代，对线性规划进行大量的理论研究，并涌现出一大批新的算法。例如，1954年莱姆基提出对偶单纯形法；1954年S.加斯和T.萨迪等人解决了线性规划的灵敏度分析和参数规划问题；1956年A.塔克提出互补松弛定理；1960年丹兹格与沃尔夫(P.Wolfe)建立大规模线性规划问题的分解算法。同时，线性规划的研究成果还直接推动了其他数学规划问题包括整数规划、随机规划和非线性规划的算法研究。由于计算机科学的蓬勃发展，出现了许多线性规划软件，如MPSX，OPHEIE，UMPIRE等，可以很方便地求解几千个变量的线性规划问题。

1978年苏联数学家哈奇扬(L.G.Khachian)提出解线性规划问题的椭球算法，并从理论上证明线性规划属于多项式型问题。1984年美国贝尔电话实验室的印度数学家N.卡马卡提出解线性规划问题新的多项式时间算法。用这种方法求解线性规划问题在变量个数为5000时只要单纯形法所用时间的1/50。经过80年代以来多人的努力，现已形成线性规划多项式算法理论，由此形成的内点算法在超大型线性规划问题方面的解题速度要快于单纯形法。