第0章最优化理论与算法起因和发展

1最优化理论与算法教师：唐明伟专业：计算机应用技术职称：教授学位：工学博士联系电话mail:tmw@欢迎同学咨询与合作！2最优化的发展历程费马:1638皮耶·德·费马（PierredeFermat）是一个17世纪的法国律师，也是一位业余数学家。之所以称业余，是由于皮耶·德·费马具有律师的全职工作。费马最后定理在中国习惯称为费马大定理，西方数学界原名“最后”的意思是：其它猜想都证实了，这是最后一个。著名的数学史学家贝尔（E.T.Bell）在20世纪初所撰写的著作中，称皮耶·德·费马为”业余数学家之王“。贝尔深信，费马比皮耶·德·费马同时代的大多数专业数学家更有成就。3最优化的发展历程牛顿,1670他在1687年发表的论文《自然定律》里，对万有引力和三大运动定律进行了描述。提出牛顿运动定律，发明了反射望远镜和发展出微积分学。提出了“牛顿法”以趋近函数的零点和金本位制度4最优化的发展历程欧拉,1755Minf(x1x2···xn)

f(x)=0莱昂哈德·欧拉，瑞士数学家、自然科学家。1707年4月15日出生于瑞士的巴塞尔，1783年9月18日于俄国圣彼得堡去世。16岁获得硕士学位。欧拉是18世纪数学界最杰出的人物之一，他不但为数学界作出贡献，更把整个数学推至物理的领域。他是数学史上最多产的数学家，平均每年写出八百多页的论文，还写了大量的力学、分析学、几何学、变分法等的课本，《无穷小分析引论》、《微分学原理》、《积分学原理》等都成为数学界中的经典著作。欧拉对数学的研究如此之广泛，因此在许多数学的分支中也可经常见到以他的名字命名的重要常数、公式和定理。[1]

此外欧拉还涉及建筑学、弹道学、航海学等领域。5欧拉，拉格朗日：无穷维问题，变分学柯西：最早应用最速下降法拉格朗日，1797Minf(x1x2···xn)s.t.gk(x1x2···xn)=0,k=1,2,…,m-6-线性规划发展的历史法国数学家J.B.J.傅里叶(JosephFourier)和C.瓦莱－普森分别于1832和1911年独立地提出线性规划的想法，但未引起注意。1939年苏联数学家Л.В.康托罗维奇(Kantorovich)在《生产组织与计划中的数学方法》一书中提出线性规划问题，也未引起重视。

TPSHUAI71930年代，康托诺维奇：线性规划1940年代，丹齐格Dantzig：单纯形方法，冯.诺依曼：对策论1950年代，Bellman：动态规划，最优性原理；

KKT条件；1960年代：Zoutendijk,Rosen,Carroll,etc.非线性规划算法，Duffin，Zener等几何规划，Gomory，整数规划,Dantzig等随机规划

60-70年代：Cook等复杂性理论，组合优化迅速发展

电子计算机----------最优化2006/08-8-线性规划发展的历史利奥尼德·康托洛维奇(L.V.Kantorovich,1912—1986)，苏联数学家，出生于俄国圣彼得堡的一个医生家庭.1930年毕业于列宁格勒大学,1934年成为该校最年轻的数学教授,1935年获该校数学博士学位.1948—1960年任列宁格勒科学院数学所研究室主任,1958年当选为苏联科学院通讯院士,并于1964年成为苏联科学院院士.-9-线性规划发展的历史1960—1971年任苏联科学院西伯利亚分院数学所副所长,1971—1976年任苏联国家科学技术委员会管理研究所室主任.1976年任苏联科学院系统分析所所长.他曾于1949年获斯大林数学奖,1965年获列宁经济学奖.康托洛维奇对经济学的贡献主要在于,他建立和发展了线性规划方法,并运用于经济分析,对现代经济应用数学的重要分支——线性规划方法的建立和发展做出了开创性贡献.他把资源最优利用这一传统的经济学问题,由定性研究和一般的定量分析推进到现实计量阶段,对于在企业范围内如何科学地组织生产和在国民经济范围内怎样最优地利用资源等问题做出了独创性的研究.康托洛维奇的主要著作包括:《生产组织和计划中的数学方法》(1939年),《经济资源的最优利用》(1959年),《经济最优决策》(1972年,合著),《最优规划文集》(1976年)等.因在创建和发展线性规划方法以及革新、推广和发展资源最优利用理论方面所做出的杰出贡献，与美籍荷兰经济学家库恰林·库普曼斯(T.C.Koopmans,1910—1985)一起分享1975年度诺贝尔经济学奖.2006/08---第1章线性规划----10-乔治·伯纳德·丹齐格（Dantzig）（G.B.Dantzig，1914—2005），美国数学家.因创造了单纯形法，被称为“线性规划之父”.他在去世之前拥有3个院士头衔(国家科学院，国家工程院和美国科学院).1947年,美国数学家G.B.丹齐克提出线性规划的一般数学模型和求解线性规划问题的通用方法──单纯形法，为这门学科奠定了基础。线性规划发展的历史2006/08---第1章线性规划----11-中断丹齐格的伯克利研究生学习.他成了美国空军管理部统计控制战斗分析处主任，处理供应链的补给和管理成千上百的人员和物资.线性规划发展的历史第二次世界大战-12-据史料记载，到1945年,美军总兵力达到1050万人二战结束时，美国陆军有89个师，600多万人；海军有各型舰船10759艘，总吨位1382万吨，总兵力为385万，其中海军陆战队50万人其军事工业的规模已经发展到可以年产飞机4万架,坦克2万辆的水平,二战时美国共生产8万辆坦克,有进4万辆是位于底特律的克莱斯特工厂生产的M4谢尔曼坦克.线性规划发展的历史第二次世界大战美国兵力2006/08---第1章线性规划----13-1946年，丹齐格获得伯克利的博士学位，仍回到美国空军管理部.丹齐格的上司伍德（M.Ｗood）和希奇赫克（D.Hitchock）要他解决如何使计划过程机械化的问题.具体任务是：寻找一个方法能更快地计算出分时间段的调度、训练和后勤供给的方案.当时计算这些问题，都是依靠经验总结出的优先准则，而不是当成一个大系统来考虑，也没有一个明确的目标函数.丹兹格深入研究了这个问题以后，提出了目标函数的概念，并提出了单纯形求解方法(1947年).这个方法在线性规划领域沿用多年，至今还在发挥作用.线性规划发展的历史第二次世界大战后-14-1947年，美国数学家VonNeumann诺伊曼提出对偶理论,开创了线性规划的许多新的研究领域，扩大了它的应用范围和解题能力。线性规划发展的历史-15-1951年美国经济学家T.C.库普曼斯(Koopmans)把线性规划应用到经济领域，为此与康托罗维奇一起获1975年诺贝尔经济学奖。50年代后对线性规划进行大量的理论研究，并涌现出一大批新的算法。例如，1954年C.莱姆基提出对偶单纯形法，1954年S.加斯和T.萨迪等人解决了线性规划的灵敏度分析和参数规划问题，1956年A.塔克提出互补松弛定理，1960年G.B.丹齐克和P.沃尔夫提出分解算法等。

线性规划发展的历史-16-1971年，KLee和Murty提出一个例子，在这个例子中单纯形法需要迭代2n-1步，说明单纯形算法不是一种好算法。1979年苏联数学家L.G.Khachian(哈奇扬)提出解线性规划问题的椭球算法，并证明它是多项式时间算法。

线性规划发展的历史-17-1984年，美国贝尔电话实验室的印度数学家N.卡马卡(Karmarkar)提出解线性规划问题的新的多项式时间算法。用这种方法求解线性规划问题在变量个数为5000时只要单纯形法所用时间的1/50。现已形成线性规划多项式算法理论。50年代后线性规划的应用范围不断扩大。线性规划发展的历史-18-1998年Smale（斯梅尔）提出21世纪数学的18个数学难题，其中线性规划被列为第九个难题。1.Riemann假设2.Poincare猜想

（已经完全解决）

4.多项式的整数零点

5.丢番图曲线高度的界

6.天体力学中相对平衡态数目的有限性7.2维球面上点的分布8.把动力学引进经济理论中9.线性规划问题

10.封闭引理

11.一维动力学是否通常是双曲的12.微分同胚的中心化子

13.Hilbert第十六问题14.Lorenz吸引子

15.Navier-Stokes方程16.Jocobi猜想17.解多项式方程组18.智能的极限。线性规划发展的历史19最优化理论与算法起因和发展线性规划主要有两个方面的研究内容，一是规划。二是计算方法。线性规划的目标函数和约束函数都是线性函数，线性规划这个名称也是由此而演变形成的。线性规划研究者的主要目的在于如何制定计划，而不在于执行或实施计划。可以把这些有关学问所形成的整个领域称做＂规划＂，在于着重强调极大化或极小化问题时候，还可称做最优规划。简单的说，线性规划所考虑的问题是如何按照最佳可能的（最优）方式来计划一项各种相互关联的活动的集合体。单纯形法是求解线性规划问题的方法之一。20线性规划的起因主要由冯．诺伊曼的博弈论研究、一般经济均衡理论研究和线性不等式的发展研究，李昂铁夫的投入－产出研究，希奇柯克的运输问题研究和斯蒂格勒的营养问题研究等。线性规划形成的主要标志有两个：一个是线性规划模型的建立，另一个是创建求解线性规划问题的单纯形法。线性规划模型建立以后，线性规划的发展主要体现在单纯形法的发展上。最优化理论与算法起因和发展21线性规划的起因最优化理论与算法起因和发展由冯．诺伊曼的博弈论研究一般经济均衡理论研究和线性不等式的发展研究李昂铁夫的投入－产出研究希奇柯克的运输问题研究斯蒂格勒的营养问题研究22单纯形法是由丹齐格创建的，单纯形法的创建标志着线性规划的诞生。丹齐格曾经说：“如果我被要求说出对线性规划的最重要的贡献，我会说一下三点：１．认识到（丹齐格作为战争年代的亲身经历者和实际规划的操作者所获取的经验）具体规划中最实用的关系可用线性不等式系统来表示。２．使用目标函数来明确规划的目标，而不是用该领域有权威的人士的经验来选择最优方案。３．创造了求解线性规划问题的单纯形方法。单纯形法是在探讨经济理论的一个有用方法的过程中产生的，是人们对大型复杂系统做出实际计划的强大工具。最优化理论与算法起因和发展23线性规划和博弈论之间关系是由塔克教授的科研团队来研究完成，然而我们一直把博弈论和线性规划的关系归功于由冯．诺伊曼。一、博弈论研究是线性规划的一个起因最优化理论与算法起因和发展这是为什么呢？24在二次世界大战期间，冯.诺伊曼军事动员和相关军事科学的发展上发挥了显著作用，战后在军内他开展了各种咨询职位。1947年10月，丹齐格在普林斯顿高级研究所拜访冯.诺伊曼时，线性规划与博弈论么间的关联被认可［丹齐格，1982,1988]。一、博弈论研究是线性规划的一个起因最优化理论与算法起因和发展25在［丹齐格，1982］丹齐格中讲述了他是如何想起这次会议，回味着冯.诺伊曼的话：“我［冯.诺伊曼］不想让你［丹齐格］以为我像魔术师似得从袖子中拉出来这一切。我与奥斯卡.摩根斯坦最近刚刚完成了一本关于博弈论的书。我正做的事情是猜测这两个问题（线性规划的对偶理论和博弈论的极大极小理论）是等价的。你概述的有关问题的理论是我们开发的模巧游戏。”一、博弈论研究是线性规划的一个起因最优化理论与算法起因和发展26冯？诺伊曼还写了一个注释，人们私下传阅。1947年11月15－16日，标题为“讨论一个最大值的问题”。1991年，关于送个纸条哈罗德.库恩写道：“冯.诺伊曼私下传阅的简短打印的注释在15年后首次发表。该注释说明建立了线性规划问题的对偶问题，并给了一个最优目标价值观为基础的不均匀无效表单上的平等法卡斯引理有缺陷的证明。［库恩，1991，第85页］一、博弈论研究是线性规划的一个起因最优化理论与算法起因和发展271948年6月，丹齐格访问普林斯顿大学时，会见了Ａ．塔克教授。从此，塔克的团队（塔克及他的学生库恩和戈尔等）开始对博弈论、非线性规划和对偶理论研究作了很多有历史意义的工作。多年来，大家公认冯.诺伊曼是对偶理论的创始人，然而戈尔、库恩和塔克则是最早发表对偶定理严格证明的人。所以（公正的讲，对线性规划对偶理论的建立过程中塔克教授团队的工作是有目共睹的，然而博弈论和线性规划的关系方面首创性的工作依然属于丹齐格和冯.诺伊曼。一、博弈论研究是线性规划的一个起因最优化理论与算法起因和发展28综上博弈论对线性规划问题的最大的影响在于建立对线性规划问题及相关理论。一、博弈论研究是线性规划的一个起因最优化理论与算法起因和发展29丹齐格在美国劳工统计局工作时的同事，也是他的好友埃文斯将李昂铁夫的一篇关于美国经济结构的论文介绍给他。从此单齐格开始研究李昂铁夫的文章。丹齐格认为：李昂铁夫的成就在于他建立了定量模型，从而能够从一系列错综复杂的产业链关系中，衡量出国家政策和消费趋势对生产的影响。李昂铁夫精确地使用＂经验模型＂概念代替了＂纯粹形式模型＂。二、投入－产出间題研究是建立线性规划模型的维形最优化理论与算法起因和发展30李昂铁夫在收集数据和推广成果时显示出非凡的组织活动才能。所有这些都使得丹齐格对李昂铁夫敬仰不己。他曾经说过：＂李昂铁夫一人为应用数学的创立创造了所有的必要条件。丹齐格被李昂铁夫的工作（即被他称之为＂国际投入－产出模型的美国经济＂）迷住了。李昂铁夫已经成功的应用了必要的3个步骤：１．制定产业模式。２．在美国经济大萧条期间收集输入的数据。３．信服决策者使用输出。二、投入－产出间題研巧是建立线性规划模型的维形最优化理论与算法起因和发展31二、投入－产出间題研巧是建立线性规划模型的维形1973年，李昂铁夫因投入－产出模型而获得诺贝尔奖。然而＂李昂铁夫的模型是稳态（静态）的，我想要的高度动态模型，随着时间的推移而变化的模型，空军希望得到一个高度动态的模型，随着事件发生变化的模型＂。对照李昂铁夫和单齐格两个人的工作很容易看出，是丹齐格推广了李昂铁夫的模型，并引进了目标函数。李昂铁夫投入产出思想是第一个关于＂规划＂思想，这个规划思想就是单齐格线性规划的模型中的线性约束条件的前身。当然，更重要的是丹齐格创建了单纯形法。最优化理论与算法起因和发展32三、运输问题是建立线性规划问題的典型例子希奇柯克的关于运输问题的思想是送样的：把一部分物资从凡个不同的地区往几个不同的地区运送，怎么安排才能运送费用最小？这里希奇柯克建立了一个运输问题的模型，并给出一个求解方法。希奇柯克这个模型既有线性目标函数又有线性约束条件，是最早建立的线性规划模型。然而是一个静态的模型，丹齐格建立的是动态的线性规划模型。希奇柯克这些思想无疑对丹齐格线性规划思想的来源。最优化理论与算法起因和发展33三、运输问题是建立线性规划问題的典型例子丹齐格曾经说：“1941年希奇柯克写一篇关于交通问题方面的优秀论文……＂。与此同时，丹齐格最早应用单纯形法的具体问题就是运输问题。更值得一提的是单齐格第一次应用单纯性正是在希奇柯克提出的运输问题中。最优化理论与算法起因和发展34四、营养问题是第一个动态模型斯蒂格勒营养问题的思想是怎样花最少的成本获取最大营养。斯蒂格勒的工作是一个指导性的最低营养成本的意见，这个意见做不到精确，也不可能精确。原因是同类食物由于产地和生产时间的不同而其所含营养成分也不同。既然同类产品的营养成分的不同将导致斯蒂格勒最佳营养组合方案的误差。但是这个方案在很大程度上能够提供相当科学的、保持身体健康的、最低成本的食物。最优化理论与算法起因和发展35四、营养问题是第一个动态模型斯蒂格勒的工作中虽然没有解析式的线性约束和先行目标函数，但是有明确的行动目标和实施方案。虽然在形式上跟线性规划不同，但是内涵上与线性规划一致，是早期的线性规划思想的体现。动态的思想。斯蒂格勒的营养问题有明显的目标，然而不是代数形式的，是第一个动态模型。斯蒂格勒动态的思想是丹齐格动态线性规划需要借鉴的思想。最优化理论与算法起因和发展36五、线性规划的形成线性规划主要有两个方面的内容：一是做出一个好的计划，另一个是找到一个简捷有效的计算方法。线性规划中规划的意思就是要做好一个计划，这里需要强调的是众多学者的目标在于如何制定计划，而不在于如何执行或实施计划。人们把这些有关学问所形成的整个领域成为“规划”；进一步着重考虑极大化或极小化问题时用最优规划这个名称。数学规划所考虑的问题是如何按照最好可能（最优）的方式计划一系列相互关联的活动的集合体。最优化理论与算法起因和发展37五、线性规划的形成从全文能够看到，线性规划研究主要做了两个方面工作。一是线性规划模型建立历原因，二是求解线性规划问题的单纯形法的创建与发展进程。最优化理论与算法起因和发展这个数学规划的目标函数和约束函数全部是线性函数时候称这个规划为线性规划。对于求解线性规划来说，经典的求最值方法是无能为力的，因此求解线性规划问题显得非常重要。故求解线性规划问题的单纯形法的创建标志着线性规划的诞生。385.1、线性规划模型的建立线性规划模型的建立主要起因有几个方面：一是线性不等的系统理论的发展；二是博弈论研究和均衡理论兴起；三是投入－产出问题研究；四是解决运输问题和营养问题的需求。归根结底，数学的内在发展达到一定程度后，社会需求是产生一个新学科的最大的动力。我们己经看到单纯形法是由丹齐格创建的，单纯形法的创建标志着线性规划的诞生。最优化理论与算法起因和发展395.2、单纯形法的创建是线性规划问题诞生的标志单纯形法是1947年由丹齐格创建的，单纯形法的创建标志着线性规划的诞生。正因为此工作丹齐格享有线性规划之父之美誉。单纯形法是在探讨经济理论的一个有用方法的过程中产生的，是人们对大型复杂系统做出实际计划的强大工具。单纯形法在运输问题中的应用看到，单纯形法是求解线性规划问题的崭新的、先进的方法。最优化理论与算法起因和发展405.2、单纯形法的创建是线性规划问题诞生的标志最优化理论与算法起因和发展415.2、单纯形法的创建是线性规划问题诞生的标志

最优化理论与算法起因和发展425.2、单纯形法的创建是线性规划问题诞生的标志

最优化理论与算法起因和发展435.2、单纯形法的创建是线性规划问题诞生的标志如果用标准的单纯形软件，在IBM370-168计算机上去