第1页共9页第二讲线性规划初步乐清中学宋爱国一.线性规划发展史1.“线性规划之父”GeorgeBernardDantzig乔治·伯纳德·丹茨格(生于1914年11月8日,于2005年5月13日逝世。享年91岁。)1947年,33岁的美国数学家GeorgeBernardDantzig(丹茨格)提出了解决一种最优化问题的单纯形法,该方法奠定了线性规划的基础,使得经济学、环境科学、统计学应用等学科获得了迅速发展。Dantzig也因而被誉为“线性规划之父”。Dantzig在运筹学建树极高,获得了包括“冯诺伊曼理论奖”在内的诸多奖项。他在Linearprogrammingandextensions一书中研究了线性编程模型,为计算机语言的发展做出了不可磨灭的贡献。Dantzig的父亲是大学数学教授,曾在法国师从著名的科学家HenriPoincare。但是Dantzig直到上初中时,对数学仍不感兴趣,甚至在初中三年级时,代数成绩还不及格。对于这样的结果,Dantzig非常内疚,他感到愧对自己的数学家父亲,于是发奋努力,很快就发现其实数学并不难,逐渐地建立了自信。上高中时Dantzig对父亲的数学题库非常着迷,他解决了所有的题目。Dantzig曾经这样回忆自己的父亲:“在我还是个中学生时,他就让我做几千道几何题……解决这些问题的大脑训练是父亲给我的最好礼物。这些几何题,在发展我分析能力的过程中,起了最最重要的作用。”在伯克利大学攻读统计学博士学位期间,“二战”爆发了,Dantzig作为文职人员参加了空军。1946年,Dantzig返回伯克利并取得博士学位。Dantzig师从著名的统计学家JerzyNeyman(奈曼,1894~1981)教授,在他们之间,发生过一个非常具有传奇色彩的故事。一天,Dantzig因故迟到了,看到黑板上写着两道题目,以为是老师留的课外作业,就抄了下来。在做的过程中,Dantzig感到有点困难,最后用了好几天时间才完成,为此他还特意向Neyman教授道歉。几周后的一个周末清晨,Dantzig被一阵急促的敲门声吵醒,Neyman教授一进门就激动地说:“我刚为你的论文写好一篇序言,你看一下,我要立即寄出去发表。”Dantzig过了要一阵子才明白Neyman教授的意思:原来那是两道统计学中著名的未解决问题,他竟然当成课外作业解决了!后来谈到这件事时,Dantzig感慨道:如果自己预先知道这两道是统计学领域中一直悬而未决的难题,根本就不会有信心和勇气去思考,也不可能解决它们。Dantzig的故事告诉我们:一个人的潜能是难以预料的,成功的障碍往往来自于心理上的畏难情绪;一定要相信自己,保持积极的态度。2.Л·В·康托罗维奇苏联经济学家。苏联科学院院士。1975年诺贝尔经济学奖金获得者。成为“社会主义国家中迄今唯一获得诺贝尔奖金的经济学家”。是最优计划理论的创始人。1912年生。1930年毕业于列宁格勒大学物理数学系。1935年获数学博士学位。1945~1960年任苏联科学院数学研究所列宁格勒分所高级研究员、研究部主任。1964年被选为苏联科学院院士。他还担任过苏联科学院西伯利亚总分院数学研究所副所长,苏联国家科学技术委员会委员,国民经济最优核算法委员会主席等职。1949年获斯大林奖金,1965年获列宁奖金。因提出资源最大限度分第2页共9页配理论,1975年与美籍荷兰学者T.C.库普曼斯一起获得诺贝尔经济学奖金。康托罗维奇的主要贡献是把线性规划用于经济管理,创立了最优计划理论。对有效利用资源和提高企业经济效益起了重大作用。他还提出经济效果的概念和衡量经济效果的统一指标体系,作为经济决策的定量依据,来选择最合理的社会生产结构。主要著作有《生产组织与计划的数学方法》(1939)、《资源最优利用的经济计算》(1959)、《最优计划的动态模型》(1964)等。3.库普曼斯于1910年8月28日生于荷兰,自幼刻若读书,在中学时代,他就立志成为科学家,决心为造福人类做出贡献。线性规划经济分析法的创立者1933年,库普曼斯以优异成绩毕业于乌德勒支大学的数理系。次年,库普曼写出了关于量子力学的论文,获得了硕士学位。从此,开始了他的科学院生涯。然而,不知是西方开始严峻的社会经济问题,还是因为他博览群书受到了什么新启示的问题,还是因为他博览群书受到了什么新启示的缘故,他认为如果能用自己学到的科学知识去解决一些社会经济问题,要比研究量子力学更能直接改善人们当前生活状况。这样,他就不知不觉地越也了自己原来探讨的学科--物理,而进入了经济科学领域。无论是经济理论还是经济实践,对于年轻的库变曼斯来就都是陌生的,他必须从头学起。首先,他阅读了大量的经济理论专著,继而又根据自己的特长钻研发数理统计学,于1936年获得了荷兰莱顿大学的数理统计学博博士学位。为了进一步增长经济学领域的知识,他不仅从书本上学习,而且特别重视从实际经济工作中学习。库普曼斯于1938年至1940年担任日内瓦国际联盟财政秘书,这一职务就是他从实践中学习经济知识的最好开端。但是,第二次世界大战的爆发打乱了他的计划,于是,他在1940年离开荷兰移居美国,在普林斯顿大学研究会研究经济并兼任纽约大学商学院特邀教师。1941年,库普曼斯转任宾夕法尼亚互助人寿保险公司经济员,此后又在英国航运协会任统计员。当他取得了丰富的经验之后,于1944年返回学术界,在芝加哥大学柯尔斯委员会从事经济研究工作。1946年,他任芝加哥大学经济学副教授,1948年升为教授并兼任柯尔斯委员会主任。1955年,他到耶鲁大学任教,此后又受聘于哈佛大学。第一篇为《资源的分配和价格制度》。第二篇文章为《经济知识的构成》。第三篇文章是讨论经济学的工具与经济学问题之间的关系。他谈到在经济学中应用了大量数学上的定理,证明定理的方法及统计推断方法。应用数学至少有两方面,一是以经济文章改写成数学论文形式,二是以不同的数学定理及观念引入经济学。他评价了计量经济学的了展,认为统计假设检查及估计理论已相当成熟,统计推断理论也非常有用。此种方法已被功地大量应用于计量经济学。由于库普曼斯对现代经济计量学的创立做出的贡献,1975年,他和康托罗维奇同时获得诺贝尔经济学奖。库普曼斯1966年获比利时天主卢万大学经济学名誉博士;1975年获美国西南大学数理名誉博士,1976年,获费城大学名誉博士。他还是美国科学院,国际统计学会\美国管理研究学会荷兰皇家科学院成员。4.数学奇才、计算机之父——冯•诺依曼第3页共9页约翰·冯·诺依曼(JohnVonNouma,1903-1957),美藉匈牙利人,1903年12月28日生于匈牙利的布达佩斯,父亲是一个银行家,家境富裕,十分注意对孩子的教育.冯·诺依曼从小聪颖过人,兴趣广泛,读书过目不忘.据说他6岁时就能用古希腊语同父亲闲谈,一生掌握了七种语言.最擅德语,可在他用德语思考种种设想时,又能以阅读的速度译成英语.他对读过的书籍和论文.能很快一句不差地将内容复述出来,而且若干年之后,仍可如此.1911年一1921年,冯·诺依曼在布达佩斯的卢瑟伦中学读书期间,就崭露头角而深受老师的器重.在费克特老师的个别指导下并合作发表了第一篇数学论文,此时冯·诺依曼还不到18岁.1921年一1923年在苏黎世大学学习.很快又在1926年以优异的成绩获得了布达佩斯大学数学博士学位,此时冯·诺依曼年仅22岁.1927年一1929年冯·诺依曼相继在柏林大学和汉堡大学担任数学讲师。1930年接受了普林斯顿大学客座教授的职位,西渡美国.1931年成为该校终身教授.1933年转到该校的高级研究所,成为最初六位教授之一,并在那里工作了一生.冯·诺依曼是普林斯顿大学、宾夕法尼亚大学、哈佛大学、伊斯坦堡大学、马里兰大学、哥伦比亚大学和慕尼黑高等技术学院等校的荣誉博士.他是美国国家科学院、秘鲁国立自然科学院和意大利国立林且学院等院的院土.1954年他任美国原子能委员会委员;1951年至1953年任美国数学会主席.1954年夏,冯·诺依曼被使现患有癌症,1957年2月8日,在华盛顿去世,终年54岁.冯·诺依曼于1937年获美国数学会的波策奖;1947年获美国总统的功勋奖章、美国海军优秀公民服务奖;1956年获美国总统的自由奖章和爱因斯坦纪念奖以及费米奖.二.线性规划问题及其数学模型1.问题的提出:在生产管理的经营活动中,通常需要对“有限的资源”寻求“最佳”的利用或分配方式。有限资源:劳动力、原材料、设备或资金等,最佳:有一个标准或目标,使利润达到最大或成本达到最小。有限资源的合理配置有两类问题(1)如何合理的使用有限的资源,使生产经营的效益达到最大;(2)在生产或经营的任务确定的条件下,合理的组织生产,安排经营活动,使所消耗的资源数最少。第4页共9页2.线性规划的一般数学模型:例1.1如图所示,如何截取x使铁皮所围成的容积最大?例1.2某企业计划生产甲、乙两种产品。这些产品分别要在A、B、C、D、四种不同的设备上加工。按工艺资料规定,单件产品在不同设备上加工所需要的台时如下表所示,企业决策者应如何安排生产计划,使企业总的利润最大?设备产品ABCD利润(元)甲21402乙22043有效台时1281612数学模型由三个要素构成决策变量Decisionvariables目标函数Objectivefunction约束条件Constraints其特征是:(1)问题的目标函数是多个决策变量的线性函数,通常是求最大值或最小值;(2)问题的约束条件是一组多个决策变量的线性不等式或等式。3.线性规划数学模型的一般形式目标函数:1122max(min)nnzcxcxcx约束条件:111122111122100()()nnmmmnnmnaxaxaxbaxaxaxbxxxa第5页共9页三.线性规划的图解法例2.某制药厂生产甲、乙两种药品,生产这两种药品要消耗某种维生素。生产每吨药品所需要的维生素量,所占用的设备时间,以及该厂每周可提供的资源总量如下表所示:已知该厂生产每吨甲、乙药品的利润分别为5万元和2万元。但根据市场需求调查的结果,甲药品每周的产量不应超过4吨。问该厂应如何安排两种药品的产量才能使每周获得的利润最大?分析:定义x1为生产甲种药品的计划产量数,x2为生产乙种药品的计划产量数。数学模型为s.t.12maxZ=5x+2x(subjectto)121211230x20x1605xx15x4x0,x0O51015x1x1=4x25101AB(2,5)C▽Z5x1+x2=1530x1+20x2=1605x1+2x2=5121212112maxZ5x2x30x20x1605xx15x4x0,x012ZZZ==52xx,(,)每吨产品的消耗每周资源总量甲乙维生素(公斤)3020160设备(台班)5115第6页共9页图解法的几种可能结果(1)有唯一最优解,如例1。(2)有无穷多最优解如例1中的目标函数设为maxZ=10x1+2x2则目标函数等值线10x1+2x2=Z与第二约束5x1+x2≤15的边界线平行。将等值线沿梯度▽Z=(10,2)正方向平移至B点时与可行域OABC的整条边界线AB重合。这表明线段AB上的每一点都使目标函数取得同样的最大值,因而都是最优解。21O51015x1x1=4x25101AB(2,5)C▽Z5x1+x2=1530x1+20x2=16010x1+2x2=5212xx10maxZ12ZZZ==2xx,(10,)第7页共9页例5,试用图解法求解下列线性规划问题st.(3)无界解(或称无最优解)无界解是指线性规划问题的最优解无界。若是极大化问题,则可使目标函数值Z→+∝,极小化问题则可使目标函数值Z→-∝,有无界解的线性规划问题的可行域是无界区域,但反之则不必然。12121212minZ3x2x-2xx2x-3x3x0,x0-1O24x1x224-▽Z=(3