《线性规划的发展：从傅里叶到卡玛卡(2).docx》由会员分享，可在线阅读，更多相关《线性规划的发展：从傅里叶到卡玛卡(2).docx（61页珍藏版）》请在三一办公上搜索。
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; History;
3、 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消元法整数规划问题的推广101.2
4、 康托洛维奇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 分解算法252.5.5 其他学科的研究25第3章 椭球法和内点法的
5、发展263.1 Klee例子263.2 哈奇杨算法（椭球法）263.3 Smale 对单纯法提出的新观点：293.4 卡玛卡（NKarmarkar）多项式算法（内点法）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 Structure）的标题发表。至于线性规划这个名称，则是另一位名家科普曼斯（T.C.
8、Coopmans）和丹齐克两人于1948年夏天在美国加州圣塔莫尼卡海滩散步时拟定的。在1947到1949两年间，线性规划里的一些重要观念，包括最有名的单纯形法（Simplex method），都陆续见诸于世。而且从1947年开始，科普曼斯便指出线性规划可以做为传统经济分析的利器。还有两个小故事应该提一下，一个是线性规划这一名称的由来，因为军队调动或安排日程称为规划，丹齐克最初叫做“线性结构的规划”。1948年夏天，科普曼斯在海滩散步时对丹齐克说：“为什么不叫线性规划呢？”丹齐克说：“你说的对！”于是在当天的学术报告中，他就第一次使用了这个名词。第二个故事是，丹齐克把线性规划中对偶理论的成果归结
9、于冯洛伊曼（Von Neumann），但是洛伊曼 在这方面并没有什么文章。1947年10月初，丹齐克到普林斯顿拜访了世界上著名的大数学家，美籍匈牙利人洛伊曼，想听听他的意见，刚说了几句，洛伊曼显得亟不可待，不耐烦的说：“讲关键的地方”。丹齐克就想：“你要快，那就看你怎样听吧！”于是用了几分钟一口气把问题的几何背景和代数形式都写到黑板上，洛伊曼站起来，竟然用了一个半小时作了一个关于线性规划理论的演讲。在那里丹齐克目瞪口呆，他第一次听到了对偶理论和Farkas引理。洛伊曼后来也给出了一个迭代的算法，但不如单形法有效 马国瑜. 线性规划的发展历史J. 北京化工大学学报:自然科学版, 1985(4).
10、。2. 线性规划历史的研究现状对线性规划发展史的研究，国内文献。国外研究。3. 本文主要内容本文主要由以下几部分组成：一，。二，。 - 5 -中国石油大学（北京）本科毕业设计（论文）第1章 线性规划问题的提出及早期研究1.1 傅里叶和瓦莱普森的工作法国数学家傅里叶（Baron Jean Baptiste Joseph Fourier，1768-1830）和瓦莱普森（C。 ？）分别于1832和1911年独立地提出线性规划的想法，但未引起注意。由于瓦莱-普森所做贡献已很难在现有文献中找到，下面着重介绍傅里叶对线性规划所做的贡献。图1.1.1 让巴普蒂斯约瑟夫傅立叶Fig. 1.1.1 Baron
11、Jean Baptiste Joseph Fourier1.1.1傅里叶简介 傅立叶是法国的数学家、物理学家，1768年3月21日生于欧塞尔，1830年5月16日卒于巴黎。1817年当选为科学院院士，1822年任该院终身秘书，后又任法兰西学院终身秘书和理工科大学校务委员会主席。主要贡献是在研究热的传播和热的分析理论时创立了一套数学理论，对19世纪的数学和物理学的发展都产生了深远影响。 1.1.2 傅里叶算法的线性算法的提出 1824年傅里叶第一个提出算法求解线性算法约束 J-B.J. Fourier, reported in: Analyse des travaux de lAcadamie
12、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 work on Linear Inequalities, Operation Research, 10 (1973) 3842.)。除了
13、历史兴趣，这个算法具有重要的理论价值。例如， 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引理，各种可以选择的的定理，和著名的Motzkin运输定理。”下面我们说明傅里叶算法有一个隐藏的属性：从应用不等式我们可以立即确定方程为隐式等式，
14、定义解决方案的仿射包集。该信息基于几何的角度。例如它允许我们确定解集的维数。正则线性算术是隐式等式计算角度的一个重要组成部分，表示数量限制和用于解决约束条件和约束增长 I. Adler, Equivalent Linear Programs, Technical Report, Department of Operations Research, University of California at Berkeley, 1976. A. Schrijver, Theory of Linear and Integer Programming, Wiley, 1986. J-L. Lassez
15、& 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).。我们简要提及其中的一些属性和引用论文使用它们的地方。只有通过小的改变对傅里叶算法的隐藏属性显式是必要的。这个修改后的傅里叶算法的正确性是建立在独立的一个定理的结果负约束 A. Schrijver, Theory o
16、f Linear and Integer Programming, Wiley, 1986.同5。我们参考此书 A. Schrijver, Theory of Linear and Integer Programming, Wiley, 1986中的概念和定义。令作为中的一组约束不等式。像往常一样，我们一起使用一组符号来表示。假设每个不等式取自其中和为实数。表示方程获得用取代了。表示每个乘以标量，也就是特别地，当为 时，可得到因此和必须遵循。的和和不等式与化为不等式：。由一个非负的线性组合不等式，我们指的是一个不等式也就是，其中，k=1，2，m。当每个严格为正的时候， 是一个独立的正的线性组合
17、。F为解决一个实数分配变量满足的一个公式，这个F的结果P（记为）。如果每个P是一个解决方案的解决方案。很明显，后面的一系列不平等的非负线性组合下封闭。如果P是一个隐式方程平等 C是P中的不等式。我们有时候称C为一个平等隐式。让P是一组的不平等，的方程结合，其中i = 1;2，：;n对于每一个i，让为不等式中的取代=，取代。在书 J-L. Lassez & K.McAloon, A Canonical Form for Generalized Linear Constraints, IBM Research Report, T.J. Watson Research Center, RC 1500
18、4, 同6中有以下结果。定理1：（独立负约束）解决了每一个未确定的i，同样也决定了。在本文中，我们使用一个双重的版本定理1。推论2：对于一些i。下面的命题显示了如何获取隐含的等式约束的线性组合：命题3 ：如果（k=1，2，m）和然后是一个隐式平等式其中j=1，2，m。证明：因此：然后P在非负线性组合下封闭，。显然和（j=1，2，m）。 1.1.3 傅里叶算法的线性算法和正确性我们下面说明傅里叶算法。我们做一个小小的修改，让每个不等式从它的原始不平等所派生出来。让P为一组不等式，让x是一个变量。让作为P 中的一个负系数的不等式在x中记为，为P中一个正系数的不等式在x中记为。然后是一个不包含x的不
19、等式。（在我们修改后我们可以联想到这个不等式集合，其中集和相关于）。对于所有这些不平等，以及P中不包含x的不等式，就是傅里叶讲x从P中迭代消元的结果。如果x在P中没有任何负的系数或者没有任何正的系数，然后傅里叶是将x从P的所有不等式中迭代消元消除其中也包含x 。我们称这种方法为傅里叶迭代消元法。如果是P经过傅里叶迭代消元的结果，我们记为。傅里叶算法反复运用傅里叶迭代消元法直到得到一组矛盾的不等式，c是负的，或者全部的变量被消掉然后就没有矛盾的不等式。在第一种情况下我们可以推断出原式没有满足的不等式的解，在第二种情况下我们可以推断出其可满足性。在我们修改中我们初始化设置与每个原不等式中的关联然后
20、应用傅里叶算法，修改的方法如上所述。为简便起见，我们也将修改后的算法称为傅里叶算法。如果包含在S与一个不等式相关的集合S，然后我们说由C得到了。修改用于检测隐式平等的方法在以下说明：扩展中使用的所有约束条件推断是隐式平等的集合。很简单，每个不等式C和关联的集合S中计算过程中产生的傅里叶算法是一个正的线性组合的不等式。这句话和命题3，修改后的算法是合理的。我们现在解决这个问题的完整性。让P是一组的不等式，让x是一个变量。这是方便安排一个稍微不同的形式的不等式。通过简单的代数运算的不等式可以转化为等价的不等式：其中，每个不包含于，原始的设置是不等式，并推导了相应的不等式。第一个不等式与不等式x有负
21、的系数，第二个q的不等式对应x有一个正的不等式系数，和其余的S不等式对应的现象是x不会产生的现象。傅里叶迭代消元x是不等式的转化方法：不等式将联系起来和每个将联系起来。一个傅里叶迭代一小步是如果p = 0或q = 0。傅里叶消元算法重复下列程序，直到所有变量或找到矛盾的不等式：选择一个变量消除;适当形式的不等式;应用傅里叶迭代消除所选择的变量。 1.1.4 Fourier-Motzkin消元法及其对偶在1947年以前，研究线性不等式问题仅仅由几个孤立的研究者来努力钻研。一个典型的方法就是减少方程组中变量的数量。在傅里叶 J. B. J. FOURIER, Solution dune quest
22、ion 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. 20 (1918-1919).，和摩兹清（Motzkin） T. S. MOTZKIN, Beitrage zur theorie der linear
23、en Ungleichungen, Doctoral Thesis, University of Base, 1936.工作中可以找到其描述的方法。不幸的是它不同于模拟方程组的方程中的每个步骤消元可以大大增加在剩下的变量中不等式的数量。多年以来此方法被称为Motzkin消元法。然而，由于提出或研究此方法的文献不断被发现，此方法现被称为Fourier-Motzkin消元法，也许最终会被称为Fourier-Dines-Motzkin消元方法。给出一个方程组的线性不等式：找到，例如：， （1）根据的系数是否是正的，负的，或零可以划分成三组不等式，这里将公式（1）重新定义： （2）其中是的线性函数。首
24、先减少方程组或许可以解决：找到使其满足 （3）然后找到一个，使其满足 （4）其中一直满足（3）。证明？：给出任何（，）满足（2），很明显，（3）和（4）必须满足。相反，给出任何满足（3），然后在中我总能找到一个满意（4）;因此（，）满足（1）。方程组（3）就是将方程组（2）“消元”的结果。如果p + q 4，减少的方程组包含一个变量，没有更多的不等式。如果p 2，q 2，r = 0，然而，消元的过程将大大增加不等式的数量。这是为什么它不能作为一个实用的解决方案的方法给出的主要原因。然而，值得注意的是，（3）有特殊的结构，这可以用它的优势发展成一个实际的计算方法。1.1.5 Fourier-Mo
25、tzkin消元法整数规划问题的推广以上我们描述了Fourier-Motzkin如何消元的方法，它可用于解决线性规划问题，也可以扩展到处理整数规划问题。扩展源自一个已知的决策过程的一个片段的形式理论算术不包括乘法。下面的目的是展示Fourier-Motzkin消元法如何求解联立线性不等式，特别是线性规划问题，可以自然地扩展处理整数规划（IP）的问题。Fourier- Motzkin消元的描述是由Dantzig（3） G. B. DANTZIG, “Linear Programming and Extensions,” Princeton Univ. Press, Princeton, New J
26、ersey, 1963.。没有人意识到在这之前Fourier-Motzkin消元法是和兰福德（Langford） C. ET. LANGFORD, Some theorems on deducibility, AWL of Muth. I, 28 (1927): 459-471.的决策过程的形式逻辑理论密度线性顺序一样的。一个相当类似但更复杂的决策理论是由Presburger M. Presburger, “Uber die Vollstindigkeit eines gewissen Systems der rilhmelilc ganzer Zahlen in w&hem die Addi
27、tion 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 programming problem, Notre Dame /. Formal Logic 23, No. 2 (1972).的工作Presburger的过程已经被应用到IP问题。此
28、节的目的是给出Presburger分析Fourier-Motzkin消元的过程作为一个推广，以期统一理解线性规划和整数规划之间的关系，以及提高数学的意识方法逻辑上的一些结果。之前描述的详细方程组应该指出是由Fourier-Motzkin消元法一直在扩展其他方法来处理整数规划问题。布拉德利（Bradley） G. H. BRADLEY, An algorithm for integer linear programming: A combined algebraic and enumeration approach, Operations Research 21 No. 1, 1973.适用于F
29、ourier-Motzkin消元法简单的整数规划问题，而卡博特（Cabot） A. V. CABOT, An enumeration algorithm for knapsack problems, Operations Res. 18 No. 2 (1970).将Fourier-Motzkin消元法适用于渐缩问题的解决方法。而应用Fourier-Motzkin消元法求解整数规划问题的方法是应用线性规划问题相关的对偶理论，这可能由Dantzig和Eaves G. B, DANTZIG AND B. C. EAVES, Fourier-Motzkin elimination and its du
30、al, J. Combinatorial Theory 14 No. 3 (1973), 288-297.最早提出。一般整数规划问题可以被视为一个最大化或最小化线性函数服从线性等式。在随后描述非负的不等式将被认为是显式。还需要考虑优化的问题作为一个新的单变量与等式约束。1.2 康托洛维奇1.2.1 列奥尼德康托罗维奇简介图1.2.2 列奥尼德康托罗维奇Fig. 1.2.2 Leonid V. Kantorovich 列奥尼德康托罗维奇（(Leonid V. Kantorovich,1912-1986），前苏联著名经济学家、科学院院士、国家科学技术委员会国民经济管理研究所经济问题研究主任。191
31、2年1月19日，康托罗维奇出生在在圣彼得堡一个性病学家家族（1月6日，根据旧的俄罗斯日历）。奇怪的是，许多参考书给另一个日期（也就是前三天）。康托罗维奇不停地笑着解释，他记得自己是1912年1月19日。当他小的时候男孩的天赋就被发现了。1926年，14岁时，他进入圣彼得堡（当时列宁格勒）州立大学（SPSU）。很快他开始参与G。M。Fikhtengolts为学生和描述性的功能理论研讨会。是很自然的，早期的学术年成立了他的第一个环境：D 。 K 。法捷耶夫，I。P 。Natanson，S。 L 。Sobolev，S 。G 。 Mikhlin和其他几个人一起康托罗维奇很友好在一生也参与Fikhten
32、golts的研讨会。这些天以来。旧的亲信叫他“Lenechka”。1930年从SPSU毕业后 康托罗维奇开始教学，结合强化科学研究。在1932年，他已经成为一个完整的列宁格勒土木工程学院的教授、SPSU的副教授。从1934年康托罗维奇在他的母校成为一个真正的教授。康托罗维奇最主要的数学成就在属于“列宁格勒”时期的生活。在1930年代他的许多论文发表为纯数学而1940年代致力于计算数学，作为一个科学家，他在这个国家很快获得领导者的欣赏。院士N. N. Luzin在1934年4月29日的一封信中写到，在康托罗维奇的个人档案发现了其几年前准备出版的文章 On the occasion of the
33、centenary of the birth of L. V. Kantorovich.。1935年康托罗维奇提出了重要的数学概念，康托罗维奇空间，即矢量的每个非空的集合有限子集的上确界和下确界。康托罗维奇空间提供了自然发展中线性不等式的理论框架是一个几乎未知的研究领域。不等式的概念显然是相关的近似计算，而我们总是感兴趣的各种估计结果的准确性。另一个挑战的兴趣来源于经济学问题中关于股票的线性不等式。最后，线性不等式的概念是离不开一个凸集的关键理念。泛函分析表明非平凡的存在连续线性泛函空间考虑，尽管存在这种类型的功能相当于存在非空的适当开放凸子集的环境空间。此外，每个凸集一般同线性不等式的解集在
34、一个适当的系统。在1940年代末康托罗维奇制定和解释应用数学之间相互依存的论文功能分析：“现在有一个传统的查看功能分析作为一个纯粹的理论学科远离直接应用不能解决实际问题。本文试图打破这一传统，至少在一定程度上，揭示功能分析之间的关系和应用数学的问题。“出于经济的新的优化问题他区分了三种方法：柯西方法也叫做最优函数，有限维近似法和拉格朗日方法。康托罗维奇基于他的研究巴拿赫空间版本的牛顿法的最优一般命令为向量空间。有限维近似无限维的空间和运营商的类似物，离散化，必须考虑和计算数学的奇妙的普遍理解的科学有限近似一般（不一定是可度量）紧密的 This revolutionary definition
35、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.。新奇的极值问题在社会科学与多维的存在矛盾的效用函数。这就提出了一个重大问题效应相互冲突的目标，相应的技术可能被视为一个数值实例向量值的目标。从1930年代末康托罗维奇获得新特性的研究在他的大胆突破经济学。康托罗维奇小册子的数学方法在生产组织和计划出现在1939年的物证线性规划的诞生
36、。线性规划技术最大化一个线性函数的正解线性不等式的一个系统。难怪线性规划的发现后立即成为康托罗维奇空间理论的基础。在1940年代康托罗维奇几乎不可见的工作在经济学表面游走。但经济是他的创作研究的问题。在第二次世界大战期间，他完成了他的第一个版本最好的书最佳资源利用的经济计算，在1975年他诺贝尔奖授予他和T。C。Koopmans由于在经济学做出的贡献。1948年苏联部长会议发表了一份绝密指令编号1990 - 774 ss / op3，下令“在两周内组织15位小组计算员工，在列宁格勒的数学研究所的苏联科学院的康托罗维奇任命教授组的负责人。” 这是康托罗维奇是如何加入了苏联制造核武器的军队的项目
37、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年康托罗维奇接受了西伯利亚部门的邀请参加新成立的苏联科学院。他搬到新西伯利亚，在西伯利亚的第一次选举他很快成为经济学的相应部门的成员。从那时起，他的代表作是致力于经济学除了著名的功能分析，“康托罗维奇和Akilov”在学生的术语。这很
38、难想象，更不用说一个才华横溢的科学家康托罗维奇和他的学生在提出一个科学方法出租车计量利率。这个国家的年长一代的人记住，在1960年代，出租车计率是现代化的根本：出现价格搭乘出租车结合少每公里的成本。这使得出租车停车场立即提高效率以及盈利能力的短出租车驱动器。这种经济衡量的结果是数学建模的出租车停车场效率是通过康托罗维奇和一群年轻的数学家和数学调查发表在俄罗斯著名的数学期刊。1960年代成为他被认可的十年。1964年，他被选为正式成员的数学系苏联科学院，1965年，他被授予列宁奖。在这些年中，他积极提出和维护自己的观点之间相互作用的数学和经济学和施加努力灌输现代科学的理念和方法进入前苏联的经济管
39、理，这几乎是徒劳的。1970年代初康托罗维奇离开新西伯利亚莫斯科，他深深地从事经济分析，没有停止他的努力影响日常国民经济经济实践和决策。他的活动主要是这个国家的管理者浪费时间和精力的误解和障碍。1986年4月7日，癌症终止他的科学路径。他被葬在莫斯科新圣女公墓。1.2.2康托罗维奇对线性规划所做贡献苏联的数学家和经济学家康托洛维奇1938年到1939年，发表了一系列文章，其中生产组织与计划中的数学方法（1939年）是最主要的著作。这部著作产生的实际背景是当时苏联正处在第三个五年计划时期。在完成这个这个任务时，苏共中央提出“要广泛的开展运用最新技术及科学的生产组织的工作”，而康托洛维奇正好碰到了
40、属于生产组织的一系列问题，列如最好地给机床或机器分配工作，尽量减少残料，最好的利用原料、当地材料、燃料及运输能力等问题，而这些问题都可以归结为同一极值问题，可是又不能用原有的数学方法求解。针对这一问题康托洛维奇提出“解乘子法”，在19401941年以及19481949年期间康托洛维奇的工作主要在两个方面，一方面在应用中有进一步深化，列如下料问题在很多工厂实际应用，并且在1951年写了工业材料合理下料计算一书；另一方面，在计算方法及经济意义解释上作了进一步工作。值得指出的是，康托洛维奇1943年曾在莫斯科经济研究所工作过，解乘数后来发展成为客观约束估值，赋予了很多经济意义，但遗憾的是，四十年代到
41、五十年代美国独立的，但飞快地发展出“线性规划”这一分支，在苏联未受到重视，一直到五十年代末期，康托洛维奇才写了一本更为完整的重要著作：最佳资源利用的经济计算（1960），后来康托洛维奇由此获得了诺贝尔奖。1.3 丹齐克和冯洛伊曼1.3.1 丹齐克简介美国数学家，美国全国科学院院士，线性规划的奠基人。1914年11月8日生于美国俄勒冈州波特兰市。在马里兰大学获数学和物理学学士学位。在密歇根大学获数学硕士学位。1946年在伯克利加利福尼亚大学数学系获哲学博士学位。1974年丹齐克在总结前人工作的基础上创立了线性规划，确定了这一学科的范围，并提出了解决线性规划问题的单纯形法。19371939年任美国
42、劳工统计局统计员，19411952年任美国空军司令部数学顾问、战斗分析部和统计管理部主任。19521960年任美国兰德公司数学研究员，19601966年任伯克利加利福尼亚大学教授和运筹学中心主任。1966年后任斯坦福大学运筹学和计算机科学教授。1971年当选为美国全国科学院院士。1975年获美国科学奖章和诺伊曼理论奖金。丹齐克还获马里兰大学、耶鲁大学、瑞典林雪平大学的以色列理工学院的名誉博士学位。丹齐克是美国运筹学会和国际运筹学会联合会 （IFORS）的主席和美国数学规划学会的创始人。他发表过100多篇关于数学规划及其应用方面的论文，1963年出版专著线性规划及其范围，这本著作至今仍是线性规划
43、方面的标准参考书。1.3.2 冯洛伊曼简介（冯诺依曼）冯诺依曼（John von Neumann，1903-1957），20世纪最重要的数学家之一，在现代计算机、博弈论、核武器和生化武器等诸多领域内有杰出建树的最伟大的科学全才之一，被后人称为“计算机之父”和“博弈论之父”诺曼麦克雷 范秀华 朱朝晖天才的拓荒者冯诺依曼传，上海科技教育出版社，2008.。原籍匈牙利。布达佩斯大学数学博士。先后执教于柏林大学和汉堡大学。1930年前往美国，后入美国籍。历任普林斯顿大学、普林斯顿高级研究所教授，美国原子能委员会会员。美国全国科学院院士。早期以算子理论、共振论、量子理论、集合论等方面的研究闻名，开创了冯
44、诺依曼代数。第二次世界大战期间为第一颗原子弹的研制作出了贡献。为研制电子数字计算机提供了基础性的方案。1944年与摩根斯特恩（Oskar Morgenstern）合著博弈论与经济行为，是博弈论学科的奠基性著作。晚年，研究自动机理论，著有对人脑和计算机系统进行精确分析的著作计算机与人脑。1.3.3 丹齐克和冯洛伊曼的相识提出“线性规划”是在1947年，当时与美国的空军军事规划有关，在第二次世界大战期间，英国和美国的军事小组遇到了广泛的与军事有关的各种各样的线性规划问题。（当时并不这样认为）二次世界大战后不久，美国空军召集一批科学家研究把数学技术运用到军事规划的预算和计划中去的可能性。广泛的军事后
45、勤问题受到重视。乔治丹齐格就是这个研究小组的成员，他最早提出一个大组织的活动之间的相互关系，可以看做一个线性规划的模型。而最优规划是根据将一个线性目标函数（单目标）最小化来确定的。这个观点导致了美国空军组织一个研究小组的产生。命名为SCOOP（scientific Computation of optimum Programs最优规划的科学计算）。SOOP计划开始于1947年6月，同年夏末，丹齐克和他的同事们建立了线性规划的一般模型，很可惜，当时没有现成的解法，于是丹齐克自己研究找到了一种解法，由于这种解法中用了特殊的几何空间形式，这种几何空间的维数同规划问题中列的维数一致，而不是同行的维数，
46、这种几何形式即为单纯形。对于这种单纯形为背景的方法，后来即称为单纯形算法，但是开始对它的威力以及进一步的理论基础并不是一下子认识的很清楚。丹齐克带着这个解法拜访了当时的大数学家冯洛伊曼，他讲了不到一分钟，而洛伊曼接着讲了一个半小时，其中讲到了线性规划的数学理论。事实上前不久，洛伊曼正好写了一本竞赛论与经济行为，里面提到的基本理论正好和线性规划的基本理论是等价的。洛伊曼还答应进一步考虑别的解法，后来果然提出了一种新解法。1952年单纯形法和Motgkin 的方法由Hoham 在美国国家标准局里试用过，结果表明还是单纯形法最好 李银兴. 线性规划发展的几个时期J. 宝鸡文理学院学报:自然科学版, 1993(2):68-72.。然而，如果我们仔细观察很容易发现冯洛伊曼的博弈论与经济行为中的博弈论和经济均衡理论均与线性规划的对偶模型有紧密的联系。冯洛伊曼的著名极小极大定理和经济均衡理论中的鞍点和公式就是丹齐克线性规划理论中的对偶规划模型的前身。这就是冯洛伊曼对线性规划的贡献。冯洛伊曼对数学规划的另一个贡献就是证明线性不等式的“选择矩阵定理”。这个著名的定理证明将极大极小定理、经济均衡理论和输入-输出模型联系起来了。- 49 -第2章 单纯形法的提出与发
