《最优化方法二线性规划的单纯形法》由会员分享，可在线阅读，更多相关《最优化方法二线性规划的单纯形法（53页珍藏版）》请在金锄头文库上搜索。
1、线性规划的单纯形法线性规划的单纯形法感谢：上海电力薛感谢：上海电力薛感谢：上海电力薛感谢：上海电力薛XXXX老师提供老师提供老师提供老师提供1美国数学家，美国全国，美国全国科学院院士。线性规划线性规划的奠基人。的奠基人。1914年年11月月8日生于美国俄勒冈州波特兰市。日生于美国俄勒冈州波特兰市。1946年在伯克利加利福尼亚大学数学系获哲年在伯克利加利福尼亚大学数学系获哲学博士学位。学博士学位。1947年年丹齐克在总结前人工作丹齐克在总结前人工作的基础上创立了的基础上创立了线性规划线性规划,并提出了解决线并提出了解决线性规划问题的性规划问题的单纯形法单纯形法。19371939年任年任美国劳工统
2、计局统计员美国劳工统计局统计员，19411952年任年任美国美国空军司令部数学顾问空军司令部数学顾问、战斗分析部和统计管理部主任。、战斗分析部和统计管理部主任。19521960年任美国年任美国兰德公司兰德公司数学研究员，数学研究员，19601966年任年任伯克利加伯克利加利福尼亚大学利福尼亚大学教授和运筹学中心主任。教授和运筹学中心主任。1966年后任年后任斯坦福大学斯坦福大学运筹学和计算机科学教授。运筹学和计算机科学教授。1971年当选为年当选为美国科学院院士美国科学院院士。1975年获年获美国科学奖章和诺伊曼理论奖金美国科学奖章和诺伊曼理论奖金。George Bernard Dantzig
3、(1914)2康托罗维奇，康托罗维奇，.苏联经济学家，苏联科学院院士，苏联经济学家，苏联科学院院士，最优计划理论的创始人最优计划理论的创始人。1912年生，年生，1930年毕业于列宁格勒大学物理数学系，年毕业于列宁格勒大学物理数学系，1935年获年获数学博士学位。数学博士学位。1964年被选为苏联科学院院士。因提出资源最年被选为苏联科学院院士。因提出资源最大限度分配理论，大限度分配理论，1975年年与美籍荷兰学者与美籍荷兰学者T.C.库普曼斯一起获库普曼斯一起获得得诺贝尔经济学奖金诺贝尔经济学奖金。康托罗维奇的主要贡献是康托罗维奇的主要贡献是把线性规划用于经济管理把线性规划用于经济管理，创立，
4、创立了了最优计划理论最优计划理论。对有效利用资源和提高企业经济效益起了重。对有效利用资源和提高企业经济效益起了重大作用。他还提出经济效果的概念和衡量经济效果的统一指标大作用。他还提出经济效果的概念和衡量经济效果的统一指标体系体系,作为经济决策的定量依据作为经济决策的定量依据,来选择最合理的社会生产结构。来选择最合理的社会生产结构。主要著作有主要著作有生产组织与计划的数学方法生产组织与计划的数学方法(1939)、资源最、资源最优利用的经济计算优利用的经济计算(1959)、最优计划的动态模型、最优计划的动态模型(1964)等。等。3佳林佳林库普曼斯库普曼斯(1910年年1985年年)，美国人，美国
5、人，1910年年8月月28日生于荷兰，日生于荷兰，1940年离开荷兰移居美国。年离开荷兰移居美国。1975年，他和康托罗维奇同时获得年，他和康托罗维奇同时获得诺贝尔经济学奖诺贝尔经济学奖。线线性规划经济分析法性规划经济分析法的创立者。的创立者。4冯冯诺依曼（匈牙利语：诺依曼（匈牙利语：NeumannJnos；英语：；英语：JohnvonNeumann，1903年年12月月28日日1957年年2月月8日）是出日）是出生于匈牙利的美国籍犹太人生于匈牙利的美国籍犹太人数学家数学家，现，现代代电子计算机创始人电子计算机创始人之一。他在之一。他在计算机计算机科学科学、经济经济、物理学物理学中的量子力学及
6、中的量子力学及几几乎所有数学领域乎所有数学领域都作过重大贡献。都作过重大贡献。冯冯诺伊曼从小就显示出诺伊曼从小就显示出数学天才数学天才，关于他的童年有不少传，关于他的童年有不少传说。大多数的传说都讲到冯说。大多数的传说都讲到冯诺伊曼自童年起在吸收知识和解题诺伊曼自童年起在吸收知识和解题方面就具有惊人的速度。方面就具有惊人的速度。六岁六岁时他能心算做时他能心算做八位数乘除法八位数乘除法，八八岁岁时掌握时掌握微积分微积分，十二岁十二岁就读懂领会了就读懂领会了波莱尔的大作函数论波莱尔的大作函数论要义。要义。冯冯诺伊曼记忆力惊人，读书过目成涌，自幼爱好历史诺伊曼记忆力惊人，读书过目成涌，自幼爱好历史学
7、，他的历史知识堪称渊博，宛如百科全书。学，他的历史知识堪称渊博，宛如百科全书。5他的父亲由于考虑到他的父亲由于考虑到经济上经济上原因，请人劝阻年方原因，请人劝阻年方17的冯的冯诺诺依曼依曼不要专攻数学不要专攻数学，后来父子俩达成协议，冯，后来父子俩达成协议，冯诺依曼便去攻读诺依曼便去攻读化学化学。其后的四年间，冯。其后的四年间，冯诺依曼在布达佩斯大学注册为数学方诺依曼在布达佩斯大学注册为数学方面的学生，但并不听课，只是每年按时参加考试。面的学生，但并不听课，只是每年按时参加考试。1926年他在年他在苏黎世的获得苏黎世的获得化学化学方面的大学毕业方面的大学毕业学位学位，他也获得了布达佩斯，他也获
8、得了布达佩斯大学大学数学博士学位数学博士学位。当他结束学生时代的时候，他已经漫步当他结束学生时代的时候，他已经漫步在数学、物理、化学三个领域的某些前沿。在数学、物理、化学三个领域的某些前沿。1926年春，冯年春，冯诺依曼到哥廷根大学任诺依曼到哥廷根大学任希尔伯特希尔伯特的助手。的助手。中学时中学时，他的老师认为按传，他的老师认为按传统的办法教冯统的办法教冯诺依曼中学数学诺依曼中学数学课程将是毫无意义的，他接受了课程将是毫无意义的，他接受了大学教师大学教师的单独的数学训练。的单独的数学训练。1921年，已被大家当作数学家了。年，已被大家当作数学家了。他的他的第一篇论文第一篇论文是和菲克特合写是和
9、菲克特合写的，那时他还的，那时他还不到不到18岁岁。l933年担任普林斯顿高级研究院教授，当时高级研究院聘有六名教授，其中就包括，其中就包括爱因斯坦，而年仅，而年仅30岁的冯岁的冯诺依曼是他诺依曼是他们当中最年轻的一位。们当中最年轻的一位。6冯冯诺伊曼是二十世纪最重要的数诺伊曼是二十世纪最重要的数学家之一，在学家之一，在纯粹数学纯粹数学和和应用数学应用数学方面方面都有杰出的贡献。他研究希尔伯特空间都有杰出的贡献。他研究希尔伯特空间上线性自伴算子谱理论，为上线性自伴算子谱理论，为量子力学量子力学打打下数学基础；下数学基础；运用紧致群解决了运用紧致群解决了希尔希尔伯特第五问题伯特第五问题；他和默里
10、创造了算子环；他和默里创造了算子环理论，即现在所谓的理论，即现在所谓的冯冯诺伊曼代数诺伊曼代数。1940年以后，冯年以后，冯诺伊曼转向应用数学。在诺伊曼转向应用数学。在力学、经济学、力学、经济学、数值分析和电子计算机数值分析和电子计算机方面作出了卓越贡献。第二次世界大战方面作出了卓越贡献。第二次世界大战时冯时冯诺伊曼因战事需要建立诺伊曼因战事需要建立冲击波理论冲击波理论和和湍流理论湍流理论，发展了流，发展了流体力学；从体力学；从1942年起，他同莫根施特恩合作，写作年起，他同莫根施特恩合作，写作博弈论和博弈论和经济行为经济行为一书，使他成为数理经济学的奠基人之一。一书，使他成为数理经济学的奠基
11、人之一。冯冯诺伊曼对世界上诺伊曼对世界上第一台电子计算机第一台电子计算机ENIAC的设计有决定的设计有决定性的影响，被称为性的影响，被称为“计算机之父计算机之父”。他是现代他是现代数值分析数值分析计计算数学的缔造者之一。算数学的缔造者之一。72 线性规划的标准型和基本概念线性规划的标准型和基本概念p 线性规划问题及其数学模型线性规划问题及其数学模型p 线性规划的图解法线性规划的图解法p 线性规划的标准形式线性规划的标准形式p 标准型线性规划的解的概念标准型线性规划的解的概念p 线性规划的基本理论线性规划的基本理论8n 问题的提出：问题的提出：在在生生产产管管理理的的经经营营活活动动中中，通通常
12、常需需要要对对“有有限限的的资资源源”寻寻求求“最佳最佳”的利用或分配方式。的利用或分配方式。l有限资源：劳动力、原材料、设备或资金等有限资源：劳动力、原材料、设备或资金等 l最佳：有一个标准或目标，使利润达到最大或成本达到最小。最佳：有一个标准或目标，使利润达到最大或成本达到最小。有限资源的合理配置有两类问题有限资源的合理配置有两类问题l如何合理的使用有限的资源，使生产经营的效益达到最大；如何合理的使用有限的资源，使生产经营的效益达到最大；l在生产或经营的任务确定的条件下，合理的组织生产，安排经在生产或经营的任务确定的条件下，合理的组织生产，安排经营活动，使所消耗的资源数最少。营活动，使所消
13、耗的资源数最少。p线性规划问题及其数学模型线性规划问题及其数学模型9例例，某制药厂生产甲、乙两种药品，生产这两种药品要消耗某种维生某制药厂生产甲、乙两种药品，生产这两种药品要消耗某种维生素。生产每吨药品所需要的维生素量，所占用的设备时间，以及该厂每素。生产每吨药品所需要的维生素量，所占用的设备时间，以及该厂每周可提供的资源总量如下表所示：周可提供的资源总量如下表所示：每吨产品的消耗每吨产品的消耗 每周资源总量每周资源总量 甲甲乙乙维生素（公斤）维生素（公斤）30302020160160设备（台班）设备（台班）5 51 11515已知该厂生产每吨甲、乙药品的利润分别为已知该厂生产每吨甲、乙药品的
14、利润分别为5 5万元和万元和2 2万元。但根据万元。但根据市场需求调查的结果，甲药品每周的产量不应超过市场需求调查的结果，甲药品每周的产量不应超过4 4吨。问该厂应如何安吨。问该厂应如何安排两种药品的产量才能使每周获得的利润最大？排两种药品的产量才能使每周获得的利润最大？10 定义定义x x1 1为生产甲种药品的计划产量数，为生产甲种药品的计划产量数，x x2 2为生产乙种药品的计划产量数。为生产乙种药品的计划产量数。数学模型为数学模型为 s.t.s.t.（subject to)subject to)(such that)(such that)每吨产品的消耗每吨产品的消耗 每周资源总量每周资源
15、总量 甲甲乙乙维生素（公斤）维生素（公斤）30302020160160设备（台班）设备（台班）5 51 11515单位利润（万元）单位利润（万元）5 511例例2 2 靠近某河流有两个化工厂，流经第一化工厂的河流流量为每天靠近某河流有两个化工厂，流经第一化工厂的河流流量为每天500500万万m m3 3，在两个工厂之间有一条流量为，在两个工厂之间有一条流量为200200万万m m3 3的支流。两化工厂每的支流。两化工厂每天排放某种有害物质的工业污水分别为天排放某种有害物质的工业污水分别为2 2万万m m3 3和和1.41.4万万m m3 3。从第一化工。从第一化工厂排出的工业污水流到第二化工厂
16、以前，有厂排出的工业污水流到第二化工厂以前，有20%20%可以自然净化。环保可以自然净化。环保要求河流中工业污水含量不能大于要求河流中工业污水含量不能大于0.2%0.2%。两化工厂处理工业污水的成。两化工厂处理工业污水的成本分别为本分别为10001000元元/万万m m3 3和和800800元元/万万m m3 3。现在要问在满足环保要求的条。现在要问在满足环保要求的条件下，每厂各应处理多少工业污水，使这两个工厂处理工业污水的费件下，每厂各应处理多少工业污水，使这两个工厂处理工业污水的费用最小用最小工厂工厂1工厂工厂2200万万m3500万万m312决策变量决策变量：x1、x2分别代表工厂分别代表工厂1和工厂和工厂2处理处理污水的数量污水的数量(万万m3)。则目标函数：min z=1000 x1+800 x2约束条件：第一段河流（工厂1工厂2之间）：(2x1)/500 0.2%第二段河流：0.8(2x1)+(1.4x2)/7000.2%此外有：x12；x21.4化简有：min z=1000 x1+800 x2 x1 1 0.8x1+x2 1.6 x1 2 x21.4 x1、x20称之为上
