线性规划的发展：从傅里叶到卡玛卡(2)

1、单位代码：11414学 号：2012011472题目线性规划的发展：从傅立叶到卡玛卡ka卡学院名称专业名称学生姓名指导教师起止时间： 年 月 日 至 年 月 日摘 要- III -摘 要线性规划是运筹学的一个重要分支，简称（LP）。它辅助人们进行科学管理，是国际应用数学、经济、计算机科学界所关注的重要研究领域。本文以时间为线，事件为体，从几个方面分析了线性规划问题及解法的发展过程，具体如下：123 关键词：线性规划；历史；单纯形法；椭球法；内点法- I -ABSTRACT- III -Linear programming of development： from Fourier to Karm

2、arkar ABSTRACTLinear programming is an important branch of operational research， referred to as "（LP）。 It assist people to scientific management， is the international applied mathematics， economics， computer science concerns one of the important research fields。 Key Words：Linear programming; Hi

3、story; Simplex method; Ellipsoid method; Interior-point method - III -中国石油大学（北京）本科毕业设计（论文）- 3 -目 录摘 要IABSTRACTIII前 言31. 线性规划概述32. 线性规划历史的研究现状43. 本文主要内容4第1章 线性规划问题的提出及早期研究51.1 傅里叶和瓦莱普森的工作51.1.1傅里叶简介51.1.2 傅里叶算法的线性算法的提出51.1.3 傅里叶算法的线性算法和正确性71.1.4 Fourier-Motzkin消元法及其对偶81.1.5 Fourier-Motzkin消元法整数规划问题的推

4、广101.2 康托洛维奇111.2.1 列奥尼德·康托罗维奇简介111.2.2康托罗维奇对线性规划所做贡献131.3 丹齐克和冯·洛伊曼141.3.1 丹齐克简介141.3.2 冯·洛伊曼简介151。3.3 丹齐克和冯·洛伊曼的相识16第2章 单纯形法的提出与发展182。1 图解法182.2 单纯形算法的发展202.3 单纯形算法202.4 丹齐克的单纯形法的运输问题的应用222。5 50年代后对线性规划进行大量的理论研究，一大批新的算法242.5.1 对偶单纯形法242.5.2 灵敏度分析和参数规划问题242.5.3 互补松弛定理252.5.4 分解算

5、法252.5.5 其他学科的研究25第3章 椭球法和内点法的发展263.1 Klee例子263.2 哈奇杨算法（椭球法）263.3 Smale 对单纯法提出的新观点：293.4 卡玛卡（N·Karmarkar）多项式算法（内点法）293.5 三种解法的比较31第4章 线性规划在经济分析中的应用334.1 生产和优化334.2 平衡和互补松弛364.3 线性规划的发展和经济学家的作用364.4 线性规划在经济规划的使用384.5 规划模型和信息传递404.6 均衡模型414.7 附言42结 论43参 考 文 献44前 言1. 线性规划概述线性规划主要研究有限资源最佳分配问题，即如何对有

6、限的资源进行最佳地调配和最有利地使用，以便最充分发挥资源的效能来获取最佳的经济效益。线性规划运用数学语言描述某些经济活动的过程，形成数学模型，以一定的算法对模型进行计算，为制定最优计划方案提供依据。其解决问题的关键是建立符合实际情况的数学模型，即线性规划模型。在各种经济活动中，常采用线性规划模型进行科学、定量分析，安排生产组织与计划，实现人力物力资源的最优配置，获得最佳的经济效益。目前，线性规划模型被广泛应用与经济管理、交通运输、工农业生产等领域。简单的说，线性规划是研究线性最优化的问题。一般地，线性规划的数学模型如下：其中、是维向量，是维向量，是矩阵。上式表明，线性规划就是在满足线性不等式范

7、围内，求线性函数的极值。换言之，线性规划的目的是求得一组变量特定值，使之满足各个约束条件的同时得到目标函数的最大值或者最小值。实际上这里的维向量也无需限制非负值，而的约束条件。现在普遍认为，线性规划问题是由美国斯坦福大学任教的乔治·丹齐格（G。 B。Dantzig）教授在1947年前后明确提出的。当时他担任美国空军的数学顾问，负责研发一套机械式的方法来做兵力调遣，人员训练以及后勤补给这些计划方案。由于这类问题涉及很广也很复杂，所以丹齐格博士先考虑最简单的线性结构，将有关的函数一律简化成线性形式来处理。其结果便在1948年以线性结构的规划（Programming in Linear S

8、tructure）的标题发表。至于线性规划这个名称，则是另一位名家科普曼斯（T.C.Coopmans）和丹齐克两人于1948年夏天在美国加州圣塔莫尼卡海滩散步时拟定的。在1947到1949两年间，线性规划里的一些重要观念，包括最有名的单纯形法（Simplex method），都陆续见诸于世。而且从1947年开始，科普曼斯便指出线性规划可以做为传统经济分析的利器。还有两个小故事应该提一下，一个是线性规划这一名称的由来，因为军队调动或安排日程称为规划，丹齐克最初叫做“线性结构的规划”。1948年夏天，科普曼斯在海滩散步时对丹齐克说：“为什么不叫线性规划呢？”丹齐克说：“你说的对！”于是在当天的学术

9、报告中，他就第一次使用了这个名词。第二个故事是，丹齐克把线性规划中对偶理论的成果归结于冯·洛伊曼（Von Neumann），但是洛伊曼 在这方面并没有什么文章。1947年10月初，丹齐克到普林斯顿拜访了世界上著名的大数学家，美籍匈牙利人洛伊曼，想听听他的意见，刚说了几句，洛伊曼显得亟不可待，不耐烦的说：“讲关键的地方”。丹齐克就想：“你要快，那就看你怎样听吧！”于是用了几分钟一口气把问题的几何背景和代数形式都写到黑板上，洛伊曼站起来，竟然用了一个半小时作了一个关于线性规划理论的演讲。在那里丹齐克目瞪口呆，他第一次听到了对偶理论和Farkas引理。洛伊曼后来也给出了一个迭代的算法，但不

10、如单形法有效 马国瑜. 线性规划的发展历史J. 北京化工大学学报:自然科学版, 1985(4).。2. 线性规划历史的研究现状对线性规划发展史的研究，国内文献。国外研究。3. 本文主要内容本文主要由以下几部分组成：一，。二，。 - 5 -中国石油大学（北京）本科毕业设计（论文）第1章 线性规划问题的提出及早期研究1.1 傅里叶和瓦莱普森的工作法国数学家傅里叶（Baron Jean Baptiste Joseph Fourier，1768-1830）和瓦莱普森（C。 ？）分别于1832和1911年独立地提出线性规划的想法，但未引起注意。由于瓦莱-普森所做贡献已很难在现有文献中找到，下面着重介绍傅

11、里叶对线性规划所做的贡献。图1.1.1 让·巴普蒂斯·约瑟夫·傅立叶Fig. 1.1.1 Baron Jean Baptiste Joseph Fourier1.1.1傅里叶简介 傅立叶是法国的数学家、物理学家，1768年3月21日生于欧塞尔，1830年5月16日卒于巴黎。1817年当选为科学院院士，1822年任该院终身秘书，后又任法兰西学院终身秘书和理工科大学校务委员会主席。主要贡献是在研究热的传播和热的分析理论时创立了一套数学理论，对19世纪的数学和物理学的发展都产生了深远影响。 1.1.2 傅里叶算法的线性算法的提出 1824年傅里叶第一个提出算法求解线性算

12、法约束 J-B.J. Fourier, reported in: Analyse des travaux de lAcadamie Royale des Sciences, pendant lannee 1824, Partie mathematique, Histoire delAcademie Royale des Sciences de lInstitut de France 7 (1827) xlviilv.(Partial English translation in: D.A. Kohler, Translation of a Report by Fourier on his wo

13、rk on Linear Inequalities, Operation Research, 10 (1973) 3842.)。除了历史兴趣，这个算法具有重要的理论价值。例如， Dantzig和Eaves对此曾有评价 G.B. Dantzig & B.C. Eaves, Fourier-Motzkin Elimination and its Dual, Journal of Combinatorial Theory Ser. A, 14 (1973) 288297.：“从傅里叶的线性算法约束中我们可以轻松获得（通过简单的代数操作）基本线性规划对偶Theorem of Farkas引理，

14、各种可以选择的的定理，和著名的Motzkin运输定理。”下面我们说明傅里叶算法有一个隐藏的属性：从应用不等式我们可以立即确定方程为隐式等式，定义解决方案的仿射包集。该信息基于几何的角度。例如它允许我们确定解集的维数。正则线性算术是隐式等式计算角度的一个重要组成部分，表示数量限制和用于解决约束条件和约束增长 I. Adler, Equivalent Linear Programs, Technical Report, Department of Operations Research, University of California at Berkeley, 1976. A. Schrijve

15、r, Theory of Linear and Integer Programming, Wiley, 1986. J-L. Lassez & K.McAloon, A Canonical Form for Generalized Linear Constraints, IBM Research Report, T.J. Watson Research Center, RC 15004,1989, (preliminary version in Proceedings of FGCS88, 1988, 703710).。我们简要提及其中的一些属性和引用论文使用它们的地方。只有通过小的改

16、变对傅里叶算法的隐藏属性显式是必要的。这个修改后的傅里叶算法的正确性是建立在独立的一个定理的结果负约束 A. Schrijver, Theory of Linear and Integer Programming, Wiley, 1986.同5。我们参考此书 A. Schrijver, Theory of Linear and Integer Programming, Wiley, 1986中的概念和定义。令作为中的一组约束不等式。像往常一样，我们一起使用一组符号来表示。假设每个不等式取自其中和为实数。表示方程获得用取代了。表示每个乘以标量，也就是特别地，当为 时，可得到因此和必须遵循。的和和

17、不等式与化为不等式：。由一个非负的线性组合不等式，我们指的是一个不等式也就是，其中，k=1，2，m。当每个严格为正的时候， 是一个独立的正的线性组合。F为解决一个实数分配变量满足的一个公式，这个F的结果P（记为）。如果每个P是一个解决方案的解决方案。很明显，后面的一系列不平等的非负线性组合下封闭。如果P是一个隐式方程平等 C是P中的不等式。我们有时候称C为一个平等隐式。让P是一组的不平等，的方程结合，其中i = 1;2，：;n对于每一个i，让为不等式中的取代=，取代。在书 J-L. Lassez & K.McAloon, A Canonical Form for Generalized

18、 Linear Constraints, IBM Research Report, T.J. Watson Research Center, RC 15004, 同6中有以下结果。定理1：（独立负约束）解决了每一个未确定的i，同样也决定了。在本文中，我们使用一个双重的版本定理1。推论2：对于一些i。下面的命题显示了如何获取隐含的等式约束的线性组合：命题3 ：如果（k=1，2，m）和然后是一个隐式平等式其中j=1，2，m。证明：因此：然后P在非负线性组合下封闭，。显然和（j=1，2，m）。 1.1.3 傅里叶算法的线性算法和正确性我们下面说明傅里叶算法。我们做一个小小的修改，让每个不等式从它的原

19、始不平等所派生出来。让P为一组不等式，让x是一个变量。让作为P 中的一个负系数的不等式在x中记为，为P中一个正系数的不等式在x中记为。然后是一个不包含x的不等式。（在我们修改后我们可以联想到这个不等式集合，其中集和相关于）。对于所有这些不平等，以及P中不包含x的不等式，就是傅里叶讲x从P中迭代消元的结果。如果x在P中没有任何负的系数或者没有任何正的系数，然后傅里叶是将x从P的所有不等式中迭代消元消除其中也包含x 。我们称这种方法为傅里叶迭代消元法。如果是P经过傅里叶迭代消元的结果，我们记为。傅里叶算法反复运用傅里叶迭代消元法直到得到一组矛盾的不等式，c是负的，或者全部的变量被消掉然后就没有矛盾

20、的不等式。在第一种情况下我们可以推断出原式没有满足的不等式的解，在第二种情况下我们可以推断出其可满足性。在我们修改中我们初始化设置与每个原不等式中的关联然后应用傅里叶算法，修改的方法如上所述。为简便起见，我们也将修改后的算法称为傅里叶算法。如果包含在S与一个不等式相关的集合S，然后我们说由C得到了。修改用于检测隐式平等的方法在以下说明：扩展中使用的所有约束条件推断是隐式平等的集合。很简单，每个不等式C和关联的集合S中计算过程中产生的傅里叶算法是一个正的线性组合的不等式。这句话和命题3，修改后的算法是合理的。我们现在解决这个问题的完整性。让P是一组的不等式，让x是一个变量。这是方便安排一个稍微不

21、同的形式的不等式。通过简单的代数运算的不等式可以转化为等价的不等式：其中，每个不包含于，原始的设置是不等式，并推导了相应的不等式。第一个不等式与不等式x有负的系数，第二个q的不等式对应x有一个正的不等式系数，和其余的S不等式对应的现象是x不会产生的现象。傅里叶迭代消元x是不等式的转化方法：不等式将联系起来和每个将联系起来。一个傅里叶迭代一小步是如果p = 0或q = 0。傅里叶消元算法重复下列程序，直到所有变量或找到矛盾的不等式：选择一个变量消除;适当形式的不等式;应用傅里叶迭代消除所选择的变量。 1.1.4 Fourier-Motzkin消元法及其对偶在1947年以前，研究线性不等式问题仅仅

22、由几个孤立的研究者来努力钻研。一个典型的方法就是减少方程组中变量的数量。在傅里叶 J. B. J. FOURIER, Solution dune question particulkre du calcul des inbgalitks, (1826), （extracts from “Histoire de IAcadbmie” (1823, 1824), Oeuvres II, 317-328 (French Academy of Sciences)）.，戴勒斯（Dines） L. L. DINES, Systems of Linear Inequalities, Ann. of Math

23、. 20 (1918-1919).，和摩兹清（Motzkin） T. S. MOTZKIN, Beitrage zur theorie der linearen Ungleichungen, Doctoral Thesis, University of Base, 1936.工作中可以找到其描述的方法。不幸的是它不同于模拟方程组的方程中的每个步骤消元可以大大增加在剩下的变量中不等式的数量。多年以来此方法被称为Motzkin消元法。然而，由于提出或研究此方法的文献不断被发现，此方法现被称为Fourier-Motzkin消元法，也许最终会被称为Fourier-Dines-Motzkin消元方法。给

24、出一个方程组的线性不等式：找到，例如：， （1）根据的系数是否是正的，负的，或零可以划分成三组不等式，这里将公式（1）重新定义： （2）其中是的线性函数。首先减少方程组或许可以解决：找到使其满足 （3）然后找到一个，使其满足 （4）其中一直满足（3）。证明？：给出任何（，）满足（2），很明显，（3）和（4）必须满足。相反，给出任何满足（3），然后在中我总能找到一个满意（4）;因此（，）满足（1）。方程组（3）就是将方程组（2）“消元”的结果。如果p + q 4，减少的方程组包含一个变量，没有更多的不等式。如果p > 2，q > 2，r = 0，然而，消元的过程将大大增加不等式的数量

25、。这是为什么它不能作为一个实用的解决方案的方法给出的主要原因。然而，值得注意的是，（3）有特殊的结构，这可以用它的优势发展成一个实际的计算方法。1.1.5 Fourier-Motzkin消元法整数规划问题的推广以上我们描述了Fourier-Motzkin如何消元的方法，它可用于解决线性规划问题，也可以扩展到处理整数规划问题。扩展源自一个已知的决策过程的一个片段的形式理论算术不包括乘法。下面的目的是展示Fourier-Motzkin消元法如何求解联立线性不等式，特别是线性规划问题，可以自然地扩展处理整数规划（IP）的问题。Fourier- Motzkin消元的描述是由Dantzig（3） G.

26、B. DANTZIG, “Linear Programming and Extensions,” Princeton Univ. Press, Princeton, New Jersey, 1963.。没有人意识到在这之前Fourier-Motzkin消元法是和兰福德（Langford） C. ET. LANGFORD, Some theorems on deducibility, AWL of Muth. I, 28 (1927): 459-471.的决策过程的形式逻辑理论密度线性顺序一样的。一个相当类似但更复杂的决策理论是由Presburger M. Presburger, “Uber d

27、ie Vollstindigkeit eines gewissen Systems der rilhmelilc ganzer Zahlen in w&hem die Addition als einzige Operatiorl hervortritt, C:.R. I Coizgres dcs Math. tkes Pays S!atc.r, Wflrmw (193Q), 92- 101,的片段算术理论决定的，但是其中不包括乘法。通过Lee R. D. LEE, An application of mathematical logic to the integer linear p

28、rogramming problem, Notre Dame /. Formal Logic 23, No. 2 (1972).的工作Presburger的过程已经被应用到IP问题。此节的目的是给出Presburger分析Fourier-Motzkin消元的过程作为一个推广，以期统一理解线性规划和整数规划之间的关系，以及提高数学的意识方法逻辑上的一些结果。之前描述的详细方程组应该指出是由Fourier-Motzkin消元法一直在扩展其他方法来处理整数规划问题。布拉德利（Bradley） G. H. BRADLEY, An algorithm for integer linear program

29、ming: A combined algebraic and enumeration approach, Operations Research 21 No. 1, 1973.适用于Fourier-Motzkin消元法简单的整数规划问题，而卡博特（Cabot） A. V. CABOT, An enumeration algorithm for knapsack problems, Operations Res. 18 No. 2 (1970).将Fourier-Motzkin消元法适用于渐缩问题的解决方法。而应用Fourier-Motzkin消元法求解整数规划问题的方法是应用线性规划问题相关的

30、对偶理论，这可能由Dantzig和Eaves G. B, DANTZIG AND B. C. EAVES, Fourier-Motzkin elimination and its dual, J. Combinatorial Theory 14 No. 3 (1973), 288-297.最早提出。一般整数规划问题可以被视为一个最大化或最小化线性函数服从线性等式。在随后描述非负的不等式将被认为是显式。还需要考虑优化的问题作为一个新的单变量与等式约束。1.2 康托洛维奇1.2.1 列奥尼德·康托罗维奇简介图1.2.2 列奥尼德·康托罗维奇Fig. 1.2.2 Leonid V

31、. Kantorovich 列奥尼德·康托罗维奇（(Leonid V. Kantorovich,1912-1986），前苏联著名经济学家、科学院院士、国家科学技术委员会国民经济管理研究所经济问题研究主任。1912年1月19日，康托罗维奇出生在在圣彼得堡一个性病学家家族（1月6日，根据旧的俄罗斯日历）。奇怪的是，许多参考书给另一个日期（也就是前三天）。康托罗维奇不停地笑着解释，他记得自己是1912年1月19日。当他小的时候男孩的天赋就被发现了。1926年，14岁时，他进入圣彼得堡（当时列宁格勒）州立大学（SPSU）。很快他开始参与G。M。Fikhtengolts为学生和描述性的功能理论

32、研讨会。是很自然的，早期的学术年成立了他的第一个环境：D 。 K 。法捷耶夫，I。P 。Natanson，S。 L 。Sobolev，S 。G 。 Mikhlin和其他几个人一起康托罗维奇很友好在一生也参与Fikhtengolts的研讨会。这些天以来。旧的亲信叫他“Lenechka”。1930年从SPSU毕业后 康托罗维奇开始教学，结合强化科学研究。在1932年，他已经成为一个完整的列宁格勒土木工程学院的教授、SPSU的副教授。从1934年康托罗维奇在他的母校成为一个真正的教授。康托罗维奇最主要的数学成就在属于“列宁格勒”时期的生活。在1930年代他的许多论文发表为纯数学而1940年代致力于计

33、算数学，作为一个科学家，他在这个国家很快获得领导者的欣赏。院士N. N. Luzin在1934年4月29日的一封信中写到，在康托罗维奇的个人档案发现了其几年前准备出版的文章 On the occasion of the centenary of the birth of L. V. Kantorovich.。1935年康托罗维奇提出了重要的数学概念，康托罗维奇空间，即矢量的每个非空的集合有限子集的上确界和下确界。康托罗维奇空间提供了自然发展中线性不等式的理论框架是一个几乎未知的研究领域。不等式的概念显然是相关的近似计算，而我们总是感兴趣的各种估计结果的准确性。另一个挑战的兴趣来源于经济学问题中

34、关于股票的线性不等式。最后，线性不等式的概念是离不开一个凸集的关键理念。泛函分析表明非平凡的存在连续线性泛函空间考虑，尽管存在这种类型的功能相当于存在非空的适当开放凸子集的环境空间。此外，每个凸集一般同线性不等式的解集在一个适当的系统。在1940年代末康托罗维奇制定和解释应用数学之间相互依存的论文功能分析：“现在有一个传统的查看功能分析作为一个纯粹的理论学科远离直接应用不能解决实际问题。本文试图打破这一传统，至少在一定程度上，揭示功能分析之间的关系和应用数学的问题。“出于经济的新的优化问题他区分了三种方法：柯西方法也叫做最优函数，有限维近似法和拉格朗日方法。康托罗维奇基于他的研究巴拿赫空间版本

35、的牛顿法的最优一般命令为向量空间。有限维近似无限维的空间和运营商的类似物，离散化，必须考虑和计算数学的奇妙的普遍理解的科学有限近似一般（不一定是可度量）紧密的 This revolutionary definition was given in the joint talk by S. L. Sobolev, L. A. Lyusternik, and L. V. Kantorovich at the Third All-Union Mathematical Congress in 1956; cp. 4, pp. 443444.。新奇的极值问题在社会科学与多维的存在矛盾的效用函数。这就提出了

36、一个重大问题效应相互冲突的目标，相应的技术可能被视为一个数值实例向量值的目标。从1930年代末康托罗维奇获得新特性的研究在他的大胆突破经济学。康托罗维奇小册子的数学方法在生产组织和计划出现在1939年的物证线性规划的诞生。线性规划技术最大化一个线性函数的正解线性不等式的一个系统。难怪线性规划的发现后立即成为康托罗维奇空间理论的基础。在1940年代康托罗维奇几乎不可见的工作在经济学表面游走。但经济是他的创作研究的问题。在第二次世界大战期间，他完成了他的第一个版本最好的书最佳资源利用的经济计算，在1975年他诺贝尔奖授予他和T。C。Koopmans由于在经济学做出的贡献。1948年苏联部长会议发表

37、了一份绝密指令编号1990 - 774 ss / op3，下令“在两周内组织15位小组计算员工，在列宁格勒的数学研究所的苏联科学院的康托罗维奇任命教授组的负责人。” 这是康托罗维奇是如何加入了苏联制造核武器的军队的项目 This was the Soviet project “Enormous,” transliterated in Russian like “´Enormoz.” The code name was used in the operative correspondence of the intelligence services of the USSR.。1957年

38、康托罗维奇接受了西伯利亚部门的邀请参加新成立的苏联科学院。他搬到新西伯利亚，在西伯利亚的第一次选举他很快成为经济学的相应部门的成员。从那时起，他的代表作是致力于经济学除了著名的功能分析，“康托罗维奇和Akilov”在学生的术语。这很难想象，更不用说一个才华横溢的科学家康托罗维奇和他的学生在提出一个科学方法出租车计量利率。这个国家的年长一代的人记住，在1960年代，出租车计率是现代化的根本：出现价格搭乘出租车结合少每公里的成本。这使得出租车停车场立即提高效率以及盈利能力的短出租车驱动器。这种经济衡量的结果是数学建模的出租车停车场效率是通过康托罗维奇和一群年轻的数学家和数学调查发表在俄罗斯著名的数

39、学期刊。1960年代成为他被认可的十年。1964年，他被选为正式成员的数学系苏联科学院，1965年，他被授予列宁奖。在这些年中，他积极提出和维护自己的观点之间相互作用的数学和经济学和施加努力灌输现代科学的理念和方法进入前苏联的经济管理，这几乎是徒劳的。1970年代初康托罗维奇离开新西伯利亚莫斯科，他深深地从事经济分析，没有停止他的努力影响日常国民经济经济实践和决策。他的活动主要是这个国家的管理者浪费时间和精力的误解和障碍。1986年4月7日，癌症终止他的科学路径。他被葬在莫斯科新圣女公墓。1.2.2康托罗维奇对线性规划所做贡献苏联的数学家和经济学家康托洛维奇1938年到1939年，发表了一系列

40、文章，其中生产组织与计划中的数学方法（1939年）是最主要的著作。这部著作产生的实际背景是当时苏联正处在第三个五年计划时期。在完成这个这个任务时，苏共中央提出“要广泛的开展运用最新技术及科学的生产组织的工作”，而康托洛维奇正好碰到了属于生产组织的一系列问题，列如最好地给机床或机器分配工作，尽量减少残料，最好的利用原料、当地材料、燃料及运输能力等问题，而这些问题都可以归结为同一极值问题，可是又不能用原有的数学方法求解。针对这一问题康托洛维奇提出“解乘子法”，在19401941年以及19481949年期间康托洛维奇的工作主要在两个方面，一方面在应用中有进一步深化，列如下料问题在很多工厂实际应用，并

41、且在1951年写了工业材料合理下料计算一书；另一方面，在计算方法及经济意义解释上作了进一步工作。值得指出的是，康托洛维奇1943年曾在莫斯科经济研究所工作过，解乘数后来发展成为客观约束估值，赋予了很多经济意义，但遗憾的是，四十年代到五十年代美国独立的，但飞快地发展出“线性规划”这一分支，在苏联未受到重视，一直到五十年代末期，康托洛维奇才写了一本更为完整的重要著作：最佳资源利用的经济计算（1960），后来康托洛维奇由此获得了诺贝尔奖。1.3 丹齐克和冯·洛伊曼1.3.1 丹齐克简介美国数学家，美国全国科学院院士，线性规划的奠基人。1914年11月8日生于美国俄勒冈州波特兰市。在马里兰大

42、学获数学和物理学学士学位。在密歇根大学获数学硕士学位。1946年在伯克利加利福尼亚大学数学系获哲学博士学位。1974年丹齐克在总结前人工作的基础上创立了线性规划，确定了这一学科的范围，并提出了解决线性规划问题的单纯形法。19371939年任美国劳工统计局统计员，19411952年任美国空军司令部数学顾问、战斗分析部和统计管理部主任。19521960年任美国兰德公司数学研究员，19601966年任伯克利加利福尼亚大学教授和运筹学中心主任。1966年后任斯坦福大学运筹学和计算机科学教授。1971年当选为美国全国科学院院士。1975年获美国科学奖章和诺伊曼理论奖金。丹齐克还获马里兰大学、耶鲁大学、瑞

43、典林雪平大学的以色列理工学院的名誉博士学位。丹齐克是美国运筹学会和国际运筹学会联合会 （IFORS）的主席和美国数学规划学会的创始人。他发表过100多篇关于数学规划及其应用方面的论文，1963年出版专著线性规划及其范围，这本著作至今仍是线性规划方面的标准参考书。1.3.2 冯·洛伊曼简介（冯·诺依曼）冯·诺依曼（John von Neumann，1903-1957），20世纪最重要的数学家之一，在现代计算机、博弈论、核武器和生化武器等诸多领域内有杰出建树的最伟大的科学全才之一，被后人称为“计算机之父”和“博弈论之父”诺曼·麦克雷 范秀华 朱朝晖天才的拓荒

44、者冯·诺依曼传，上海科技教育出版社，2008.。原籍匈牙利。布达佩斯大学数学博士。先后执教于柏林大学和汉堡大学。1930年前往美国，后入美国籍。历任普林斯顿大学、普林斯顿高级研究所教授，美国原子能委员会会员。美国全国科学院院士。早期以算子理论、共振论、量子理论、集合论等方面的研究闻名，开创了冯·诺依曼代数。第二次世界大战期间为第一颗原子弹的研制作出了贡献。为研制电子数字计算机提供了基础性的方案。1944年与摩根斯特恩（Oskar Morgenstern）合著博弈论与经济行为，是博弈论学科的奠基性著作。晚年，研究自动机理论，著有对人脑和计算机系统进行精确分析的著作计算机与人脑

45、。1.3.3 丹齐克和冯·洛伊曼的相识提出“线性规划”是在1947年，当时与美国的空军军事规划有关，在第二次世界大战期间，英国和美国的军事小组遇到了广泛的与军事有关的各种各样的线性规划问题。（当时并不这样认为）二次世界大战后不久，美国空军召集一批科学家研究把数学技术运用到军事规划的预算和计划中去的可能性。广泛的军事后勤问题受到重视。乔治·丹齐格就是这个研究小组的成员，他最早提出一个大组织的活动之间的相互关系，可以看做一个线性规划的模型。而最优规划是根据将一个线性目标函数（单目标）最小化来确定的。这个观点导致了美国空军组织一个研究小组的产生。命名为SCOOP（scientif

46、ic Computation of optimum Programs最优规划的科学计算）。SOOP计划开始于1947年6月，同年夏末，丹齐克和他的同事们建立了线性规划的一般模型，很可惜，当时没有现成的解法，于是丹齐克自己研究找到了一种解法，由于这种解法中用了特殊的几何空间形式，这种几何空间的维数同规划问题中列的维数一致，而不是同行的维数，这种几何形式即为单纯形。对于这种单纯形为背景的方法，后来即称为单纯形算法，但是开始对它的威力以及进一步的理论基础并不是一下子认识的很清楚。丹齐克带着这个解法拜访了当时的大数学家冯·洛伊曼，他讲了不到一分钟，而洛伊曼接着讲了一个半小时，其中讲到了线性规

47、划的数学理论。事实上前不久，洛伊曼正好写了一本竞赛论与经济行为，里面提到的基本理论正好和线性规划的基本理论是等价的。洛伊曼还答应进一步考虑别的解法，后来果然提出了一种新解法。1952年单纯形法和Motgkin 的方法由Hoham 在美国国家标准局里试用过，结果表明还是单纯形法最好 李银兴. 线性规划发展的几个时期J. 宝鸡文理学院学报:自然科学版, 1993(2):68-72.。然而，如果我们仔细观察很容易发现冯·洛伊曼的博弈论与经济行为中的博弈论和经济均衡理论均与线性规划的对偶模型有紧密的联系。冯·洛伊曼的著名极小极大定理和经济均衡理论中的鞍点和公式就是丹齐克线性规划理论

48、中的对偶规划模型的前身。这就是冯·洛伊曼对线性规划的贡献。冯·洛伊曼对数学规划的另一个贡献就是证明线性不等式的“选择矩阵定理”。这个著名的定理证明将极大极小定理、经济均衡理论和输入-输出模型联系起来了。- 49 -第2章 单纯形法的提出与发展2.1 图解法线性规划可以在一定条件下合理安排人力、 物力等资源，使经济效果达到最好。一般来说，求线性目标函数在线性约束条件下的最大值或最小值的问题，统称为线性规划问题。满足线性约束条件的解叫做可行解，由所有可行解组成的集合叫做可行域。决策变量、 约束条件、 目标函数是线性规划的三要素。然而图解法不适合解大规模的线性规划的问题，局限性比

49、较大。但对于只有两个或者三个变量的线性规划问题，可以用图解法求最优解，也就是作出约束条件的可行域，利用图解的方法求出最优解，其特点是过程简洁、图形清晰，简单易懂。下面仅做只有两个变量的线性规划问题。只含两个变量的线性规划问题，可以通过在平面上作图的方法求解，步骤如下：（1）以变量x1为横坐标轴，x2为纵坐标轴，适当选取单位坐标长度建立平面坐标直角坐标系。由变量的非负性约束性可知，满足该约束条件的解均在第一象限内。（2）图示约束条件，找出可行域（所有约束条件共同构成的图形）。（3）画出目标函数等值线，并确定函数增大（或减小）的方向。（4）可行域中使目标函数达到最优的点即为最优解。下面举出一个实例

50、来说明：例1某木器厂生产圆桌和衣柜两种产品，现有两种木料，第一种有72，第二种有56，假设生产每种产品都需要用两种木料，生产一张圆桌和一个衣柜分别所需木料如下表所示。每生产一张圆桌可获利60元，生产一个衣柜可获利100元。木器厂在现有木料条件下，圆桌和衣柜各生产多少，才使获得利润最多?产 品木料（单位）第 一 种第 二 种圆 桌0.180.08衣 柜0.090.28解：设生产圆桌张，生产衣柜个，利润总额为元，则由已知条件得到的线性规划模型为： ， 72， 这是二维线性规划，可用图解法解，如图2-1。图2-1先在坐标平面上作出满足约束条件的平面区域，即可行域，如上图所示。再作直线，即，把直线平移

51、至的位置时，直线经过可行域上点，且与原点距离最远，此时取最大值，为了得到M点坐标解方程组，得？、于是知点坐标为（350，100），从而得到使利润总额最大的生产计划，即生产圆桌350张，生产衣柜100个，能使利润总额达到最大值31000元。这表明，当资源数量已知，经过合理制定生产计划，可使效益最好，这就是用图解法解线性规划来解决生产计划安排的问题之一。2.2 单纯形算法的发展 丹齐格的单纯形法开始时曾做一个假设非退化，当时他认为这是合理的，因为三维空间中四个平面交于一点的概率为零，另外他所遇到的实例也确实没有发生过，但是科普曼斯还是希望他进一步做些工作，以后他和他的工作者曾提出用对右端项做摄动的

52、办法，并用字典序方法等采用了避免退化的程序，在实际求解中是否要加上解决退化的程序，至今还有争论，到1981年发现即使退化现象不产生，接近退化的概率的仍然很大，这就提示我们在选择转轴元素的准则时，应该避免退化或接近退化的基本可行解的方向，去寻找可行解，这样可以减少总的迭代次数。 从单纯形法问世到现在已有很长的历史，尽管中间有种种修改，但始终是解线性规划问题的重要方法。虽然也提出过种种方法，大多数不如单纯形法有效，除过针对一些特殊情况而设计的算法。2.3 单纯形算法给定一个线性规划问题（P）： （P） 定义可行解集合：，则下述两定理成立：定理1：若，则F至少含有一个顶点。定理2：若，而且（P）的最

53、优解值不为无限大，那么F至少有一个顶点会是（P）的最优解。值得注意的是一般而言，时，它可能为一个有界的多面体，也可能是一个无界的多面集合。但是不论无界还是有界，F都是一个含有有限个顶点的凸集合。至于定理2则指出当线性规划问题有解时，它的最优解可能朝着无界的极值方向发生而使得最优解值变得无限小。如果不是这种情况，那么F的某个顶点一定会是最优解之一。根据定理1和定理2，我们知道当时而且（P）的最优解值不为负无限大时，F虽然可能含有非顶点的最优解，但至少有一个顶点是最优解之一。单形法的基本概念很简单明了，既然是一个线性规划的最优解可能出现在F的一个顶点之上，那我们就由某一个容易求得的顶点开始，再检查

54、所有在F中与它相连接的邻近顶点。如果有任何一个邻近顶点的函数值要求来得更小，那么我们便移动到这个邻近顶点。接着便以此新的顶点为准再检查与它相连接的邻近顶点来决定向何处移动。因为F的顶点个数个数有限，最后我们终于会找到一个顶点使他的函数值要比所有邻近顶点都来得低或至少相当，或者我们可以发现到此顶点有一个极值方向会使函数值降到无限小。据此便可以判断出现有的顶点为（P）的最优解或者（P）的最优解值为无限大。我们可以将单行法的重要步骤勾勒如下：步骤一：找一个F的顶点，使得。如果找不到，则表示而且（P）无解。设定指标k=1。步骤二：决定由现有顶点通往邻近顶点或极值的各个方向。（i）方向走，均会增加目标函

55、数值，则已是（P）的最优解。（ii）若沿着某一个方向走，会减少目标函数值，则做下一步骤。步骤三：测试沿着方向走能远而不离开（F）（亦即步长）。（i）若步长可为无限大，则通往极值方向，而且（P）的最优解值为负无限大。（ii）若步长有其上限，则沿通往较之邻近顶点：重新设定指标，转步骤二。 上述的三个步骤仅是个概述，至于细节则需要参考其他资料。一般而言，步骤一中常用Big-M法或者Two-Phase法来找第一个顶点。步骤二中的可能移动方向则由所谓的基矩阵（Fundamental Matrix）来决定。至于步骤三中的步长则由最小比例测试（Minimum Ratio Test）来决定。由图2-2可以看出

56、“单纯行法”沿着可行解集合F的边界由一个顶点移动到另一个顶点的情形，也就是因为这个原因，单纯形法被归类于“边界邻近法”。图2-2 单纯行法搜索路径Fig 2.2 整体而言，单形法的表现相当不错。对于一个有个变数以及个约束条件的线性规划问题，平均起来，单形法只需要移动经过大约这么多个顶点，便能求得最优解。但是G·Minty和V·Klee 两位学者在1971年提出实例来验证单形法在最差情况下的表现非常不好，对于一个维空间里的特殊线性规划问题，单形法要移动经过个顶点才能达到最优解。因为这个数目随着的增长而做指数形式成长，所以成长速度非常快，要用单纯形法来解决超大型的线性规划问题确实有值得考虑的地方。大家可以想象便知道有多大。也就是因为这个隐患，所以学者专家们一直希望能找出一个解法不需要经过那么多次计算便能达到最优解。最好是随着与的增长，总共的计算量仅做多项式函数的增加，而非指数式增加。这也就是一般所谓在“多项式时间”（polynomial-time）内解线性规划问题。2.4 丹齐克的单纯形法的运输问题的应用几年前美国空军在Leontief的工作下，使其适用于高度动态的情况下，Hitchoeck和K