《（发展战略）线性规划的发展：从傅里叶到卡玛卡(2)》由会员分享，可在线阅读，更多相关《（发展战略）线性规划的发展：从傅里叶到卡玛卡(2)（60页珍藏版）》请在金锄头文库上搜索。
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 & 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.
