《运筹学教学资料》运筹学绪论.ppt

1、运 筹 帷 幄 之 中,决 胜 千 里 之 外,运 筹 学,Operational Research,学习目标,了解运筹学课程的意义 理解运筹学产生发展的概况与发展趋势 理解运筹学性质、特点与学科地位 了解运筹学学习内容、教学计划与方法,第 0 章 绪 论,一、运筹学概况简述 二、运筹学发展简史 三、主要研究内容 四、运筹学的工作步骤、原则及学科特点 五、运筹学方法应用 六、课程教学计划、方法及要求 七、如何学习运筹学课程,附录 中国古代优秀的运筹案例,主要内容,绪 论,古语：“夫运筹帷幄之中，决胜千里之外”,一、运筹学概况简述,英文名称： Operational Research-O.R.

2、，直译为“作业研究”或“（军事）行为研究”。,-史记高祖本纪,运筹学概况简述,英文： Operational Research 缩写： O.R. 日本译作“运用学”， 香港、台湾译为“作业研究”， 我国学者从古语“运筹帷幄之中，决胜千里之外”取“运筹”二字，充分体现了这门学科运心筹谋、策略取胜的精髓。译作“运筹学”。 北美：Management Science 管理科学,运筹学的称谓,运筹学概况简述,研究对象：人类对各种资源的运用及筹划活动。,研究目的: 了解和发现这种运用及筹划活动的基本规律，以便发挥有限资源的最大效益，来达到全局最优的目标。,运筹学研究的两个重要特点: 强调研究过程的完整性

3、、强调理论与实践的结合。,运筹学的研究方法: 显示出各学科研究方法的综合，构造数学模型是运筹学中最重要的方法。,运筹学概况简述,运筹学是为决策机构在对其控制下的业务活动进行决策时，提供的以数量化为基础的科学方法。 -P.M.Morse 运筹学是决策的数量方法。,运筹学是一门应用科学，它广泛应用现有的科学技术知识和数学方法，来解决实际中提出的专门问题，并为决策者选择最优策略提供定量依据。,运筹学是一门交叉学科； 运筹的目标是最优策略。,至今没有一个统一明确的定义。,运筹学概况简述,运筹学是一种给出问题的坏答案的艺术，否则，问题的结果会更坏。 本定义就是未定义。,运筹学是研究事物存在形态、数量以及

4、最佳事物的事理科学。 -许国志,运筹学是确定有限资源合理利用的科学。 资源如人力资源、物力资源、财力资源等。,本义中所谓“事理科学”是相对于研究物体运动变化规律的“物理科学”而提出的。,运筹学概况简述,大英百科全书释义：运筹学是一门应用于管理有组织系统的科学，运筹学为掌管这类系统的人提供决策目标和数量分析的工具。,中国大百科释义：运筹学用数学方法研究国民经济、民政和国防等部门在内外环境的约束条件下合理分配人力、物力、财力等资源，使实际系统有效运行的技术科学，它可以用来预测发展趋势，制定行动规划或优选可行方案。,运筹学概况简述,运筹学问题和朴素的运筹学思想，可以追溯到古代.,如：围魏救赵；田忌赛

5、马；丁渭主持皇宫的修复等.,运筹学诞生的三个来源：军事、管理和经济。,孙武：运筹为计，知人善用，应敌为变；,二、运筹学发展简史,运筹学发展简史,20世纪初, 丹麦工程师,爱尔朗,电话服务等候问题, 标志着排队论的诞生。 1928年, 冯.诺伊曼,二人零和对策,博弈论。 1939年，苏联,JI.B., 生产组织和计划中的数学方法,一书是规划论的开始。,运筹学发展简史,1. 运筹学的军事起源 我国先秦时期的诸子著作中,就存在许多朴素的运筹思想。 春秋时期（公元前770年公元前476年）军事家孙武, 孙子兵法。,运筹学发展简史,孙子兵法.始计篇里讲到：夫未战而庙算胜者，得算多也；未战而庙算不胜者，得

6、算少也。多算胜，少算不胜，而况于无算乎？这里的“庙算”就是谋划作战大计，预计战争胜负之意。其后的军事家们又不断地完善和发展了军事运筹思想。如孙膑兵法、尉缭子、百战奇法等历代军事名著及有关史籍，都有不少关于运筹思想的记载。此外，齐王赛马、围魏救赵、丁渭修皇宫和沈括运军粮等历史记载，也充分说明了我国很早就有了朴素的运筹思想，而且在生产实践中实际运用了运筹方法。,运筹学发展简史,在国外，运筹学思想方法也可追溯到很早以前。阿基米德、达芬奇、伽利略都研究过作战问题。,运筹学发展简史,第一次世界大战期间 1914-1916，英国的F.W.Lanchester的若干军事论文 研究战争的胜负同兵力多寡、火力强

7、弱之间的关系。 这种动态关系后来被人们称为兰彻斯特方程。 爱迪生解决反潜战的“战术对策演示盘” 反潜战的研究项目：汇编各项典型统计数据，用于选择回避 或击毁潜艇的最佳方法，使用战术对策演示盘“解决受潜艇 攻击问题。”,运筹学发展简史,第二次世界大战期间 鲍德西（Bawdsey）雷达站的研究“布莱克特马戏团”的出色工作 项目的巨大实际价值；明确的目标；整体化的思想；数量化的分析；多学科协同；最优化的结果；简明朴素的表达。 大西洋反潜战Morse小组的重要工作 协助英国打破德国对英吉利海峡的海上封锁 英国战斗机中队援法决策,运筹学发展简史,战争结束时，英美及加拿大军队中工作的运筹学工作人员已超过了

8、700人。 正是由于战争需要的促进，以及大批著名科学家的参与，运筹学得到迅速发展。 第二次世界大战期间的军事运筹问题及其解决方法，具有如下的特点： （1） 数据是实践中的真实数据； （2） 解决问题的人员组成是多学科的； （3） 处理问题的方法渗透着物理学的思想。,运筹学发展简史,第二次世界大战结束后，英国军方的一份总结报告曾说：“这种有资深科学家进行的，改善海军技术和物质运作的科学方法，被称为运筹学”，“和以往的历次战争相比，这次战争更是新的技术策略和反策略的较量我们在几次关键战役中加快了反应速度，运筹学是我们赢得了胜利。”,运筹学发展简史,第二次世界大战后，运筹学从单纯军事和战争中的应用研

9、究，扩展到经济和管理领域，并形成了自己的理论与方法。 1948年，美国麻省理工学院率先开设了运筹学课程，许多大学群起效法，内容也日益丰富。 1950年，美国出版了第一份运筹学杂志； 1951年美国的莫尔斯等著的运筹学方法一书出版。,运筹学发展简史,运筹学的管理起源 运筹学的第二个起源是管理。 第一次世界大战前就已经发展成熟的古典管理学派，对运筹学的产生和发展影响很大。 1911年，F.W.Taylor，（美国人，科学管理之父)，科学管理原理。,运筹学发展简史,与泰勒同时代的，对管理改革作出贡献的还有一些学者，其中具有代表性的人物有：HenryLGantt，1861-1919Frank Gilb

10、reth，1868 - 1924,运筹学发展简史,甘特曾是泰勒的亲密合作者，科学管理运动的先驱之一。1902年至1919年期间，他作为一个独立开业的咨询师进行工作，并在哈佛大学、耶鲁大学、哥伦比亚大学等著名高校任教。 甘特的贡献主要有以下几点： 1提出了一种“工资任务加奖金”的工资制度。 21903年，发明了“甘特图”（也称黑道图）。至今还在实践 中使用，并发展为统筹方法。 3强调管理民主和重视人的领导方式。,运筹学发展简史,弗兰克杰尔布雷斯夫妇，他们以进行动作研究而著称，比较有影响的著作有：动作研究（1911年）、科学管理入门（1912年）以及疲劳研究（1916年）等。他们的研究比泰勒的研究

11、更为细致和广泛，其重要贡献在以下几方面： 1提出动作研究和动作经济原理。 2疲劳研究。 3注意到了工作、工人和环境之间的相互影响。,运筹学发展简史,Henry Ford，1863 - 1947，创造了第一条流水生产线汽车流水线，从而提高了整个企业的生产效率，使成本明显降低。,福特为了利于企业向大生产发展，进行了多方面的标准化 工作，包括：产品系列化，零件规格化，工厂专业化，机 器及工具专用化，作业专门化。,运筹学发展简史,3. 运筹学的经济学起源,运筹学的第三个来源是经济学的研究。 经济学理论对运筹学的影响是和数理经济学学派紧密联系的。 数理经济学对运筹学，特别是对线性规划的影响： Qusna

12、y，1758年，经济表； Walras，经济平衡问题。,运筹学发展简史,1928年，Von Neumann, “二人零和对策”，对策论；1932年，又提出了广义经济平衡模型。 1939年，康托洛维奇，生产组织和计划中的数学方法。,运筹学发展简史,诺贝尔经济学奖从1969年首发至今的57位获奖者中就有多位是运筹学家。,1975年诺贝尔经济学奖授给了库普曼和康脱罗维奇，以表彰首先将线性规划与经济问题相联系而做出的贡献； 1994年诺贝尔经济学奖授给了三位博弈论专家：纳什、泽尔腾、海萨尼。博弈论已经成为当代经济学的基石。 2005年以色列经济学家罗伯特-奥曼和美国经济学家托马斯-斯切林，因“通过博弈

13、论分析加强了我们对冲突和合作的理解”所作出的贡献而获奖。,运筹学发展简史,战国时，魏将庞涓率军围攻赵国都城邯郸。赵求救于齐，齐王命田忌、孙膑率军往救。孙膑发现魏军主力在赵国，内部空虚，就带兵攻打魏国都城大梁，因而，魏军不得不从邯郸撤军，回救本国，路经桂陵要隘，又遭齐兵截击，几乎全军覆没。 这个典故是指采用包抄敌人的后方来迫使它撤兵的战术。围魏救赵这一避实就虚的战法为历代军事家所欣赏，至今仍有其生命力。,围魏救赵,运筹学发展简史,田忌赛马,战国时期，齐王提出与大将军田忌赛马。双方约定：从各自的上、中、下三个等级的马中各选一匹参赛，每匹马均只能比赛一次，每次比赛双方各处一匹马，三局量胜，负者要付给

14、胜者千金。已知:在同级的马中，田忌得马不如齐王的马；不同等级中，田忌的马可胜齐王低一等级的马。,运筹学发展简史,赢,赢,丁渭主持皇宫的修复,北宋时代，皇宫因火焚毁，由丁渭主持修复工作。,宫前大街取土烧砖,挖成大沟灌水成渠,利用水渠运送建筑材料,废砖乱瓦 填沟修复大街,特点：减少和方便运输，加快了工程进度。,运筹学发展简史,1948年美国麻省理工学院把运筹学作为一门课程介绍； 1947年丹齐克(G.B.Danzig)在研究美国空军资源的优化配 置时提出了线性规划及其通用解法 单纯形法; 50年代初用电子计算机求解线性规划获得成功; 1951年莫尔斯(P.M.Morse)和金博尔(G.E.Kimb

15、aU)合著的 “运筹学方法”一书正式出版。,1从1945年到50年代初，被称为创建时期。,特点：从事研究的人数不多，范围较小，人员从军事转为 民用。,所有这些，标志运筹学这门学科的基本形成。,运筹学发展简史,50年代末，美国大约有半数的大公司在自己的经营管理中应用运筹学，如用于制订生产计划、物资储备、资源分配、设备更新等方面酌决策。 有更多刊物、学会出现。 1957年在英国牛津大学召开了第一次国际运筹学会议。 1959年成立国际运筹学联合会。,250年代初到50年代末，被认为是其成长时期。,特点：电子计算机技术的迅速发展，使得运筹学中一些方法如单纯形法、动态规划方法等，得以用来解决实际管理系统

16、中的优化问题促进了运筹学的推广应用。,运筹学发展简史,3自60年代以来，是其迅速发展和开始普及的时期。,第三代电子数字计算机的出现，促使运筹学得以用来研究一些大的复杂的系统，如城市交通、环境污染、国民经济计划等。,特点：运筹学进一步细分为各个分支，专业学术团体的迅速增多，更多期刊的创办，运筹学书籍的大量出版以及更多学校将运筹学课程纳入教学计划之中。,运筹学发展简史,成熟的学科分支向纵深发展 新的研究领域产生 与新的技术结合 与其他学科的结合加强 传统优化观念不断变化,运筹学的发展趋势,运筹学发展简史,我国于上世纪50年代开始研究运筹学。,50年代中期由钱学森、许国志等教授由西方引入； 投入产出

17、表、质量管理的研究和应用开展较早； 1970年后，华罗庚教授在全国范围内推广统筹法和优选法，一大批数学家开始研究运筹学； 中国运筹学会于1980年成立，1982年作为正式成员加入了国际运筹学联合会（IFORS）。 某些分支的研究达到当时国际水平。,运筹学发展简史,线性规划,数 学 规 划,非线性规划,整数规划,动态规划,学 科 内 容,多目标规划,双层规划,组 合 优 化,最优计数问题,网络优化,排序问题,统筹图,随 机 优 化,对策论,排队论,库存论,决策分析,可靠性分析,三、主要研究内容,运筹学主要研究内容,例1.哥尼斯堡七桥问题(图论),运筹学经典问题,A,C,B,D,桥所连接的地区视为

18、点,每一座桥视为一条线,如何才能在所有桥都恰巧只走一遍的前提下，回到原出发点?,运筹学主要研究内容,例2.匹配问题(整数规划),某团体举行舞会，其中有n 个男士与n 个女士，每个男士恰好认识 r 个女士，每个女士也恰好认识 r 个男士， 问：在这个团中，能否做到：每个男士与其认识的女士跳舞，每个女士也与其认识的男士跳舞。,其他问题：人员分配；球队循环比赛场次安排等。,如：任意6个人，一定有3个人相互认识或者有3个人相互不认识,运筹学主要研究内容,例3.生产计划问题(线性规划),某企业要在计划期内安排生产甲、乙两种产品,这个企业现有的生产资料是：设备18台时,原材料A 4吨,原材料 B 12吨；

19、已知单位产品所需消耗生产资料及利润如下表。问应如何确定生产计划使企业获利最多。,分析：确定生产计划就是确定产品甲、乙的生产量。,运筹学主要研究内容,运筹学主要研究内容,例4.囚徒困境 (博弈论),两个小偷甲和乙联手作案，因私入民宅被警方抓住但未获证据。警方将两人分别置于两间房间分开审讯，政策是若一人招供但另一人未招，则招者立即被释放，未招者判入狱10年；若二人都招，则两人各判刑8年；若两人都不招，则未获证据但因私入民宅各拘留1年。将这些数据列表如下：,四、运筹学的工作步骤与原则,处理问题的过程中需要掌握一定的步骤：,运筹学的工作步骤与原则,在实际工作中应用运筹学需要掌握一定原则：,合伙原则，催

20、化原则，渗透原则， 独立原则，宽容原则，平衡原则,引入数学方法解决实际问题 -定性与定量方法结合 系统与整体性 -从全局考察问题 应用性 -源于实践、为了实践、服务于实践 交叉学科 -涉及经济、管理、数学、工程和系统等多学科 开放性 -不断产生新的问题和学科分支 多分支 -问题的复杂和多样性,运筹学的性质与特点,运筹学的工作步骤与原则,运筹数学,系统工程,管理与运筹学,问题与方法,方法与应用,核心算法与工具,基础理论,应用理论,应用技术,运筹学,运筹学的学科地位,运筹学的工作步骤与原则,五、运筹学方法应用,运筹学方法应用,生产计划：生产计划、合理下料、配料问题、物料管理等 库存管理：多种物资库

21、存量、库存方式的管理等 运输问题：运输线路、物资的调拨、运输工具的调度 人事管理：对人员的需求和使用的预测，确定人员编制、 人员合理分配，建立人才评价体系等 市场营销：广告预算、媒介选择、定价、产品开发与销售 计划制定等 财务和会计：预测、贷款、成本分析、现金管理等 理财与投资：融资方式、资本运营方案、投资组合等 其他：设备维修更新，项目选择评价，工程优化设计等,运筹学方法应用,露天采剥进度计划（线性规划） 露天生产剥采比的优化（动态规划） 地下开拓运输系统的优化设计（网络分析） 露天矿生产车辆调度（线性规划） 露天矿配矿作业管理（线性规划） 边界品位优化(线性规划,动态规划),运筹学在矿业中

22、的应用,教学计划 数学规划以线性规划及对偶问题、运输问题、目标规划、整数规划和动态规划为教授重点，组合优化部分讲授网络优化及网络计划。 教学方法 以授课为主，案例分析与课堂讨论相结合。而讲课中主要培养用最优化方法解决实际问题的能力。,六、课程教学计划、方法及要求,课程安排,一、理解运筹学的基本模型； 二、掌握运筹学的典型算法； 三、了解运筹学的经典应用； 四、学习利用数学知识分析解决实际问题的初步技术。,教学要求,课程安排,七、 如何学习运筹学课程,学习运筹学要把重点放在分析、理解有关的概念、思路上。在自学过程中，应该多向自己提问，例如一个方法的实质是什么，为什么这样进行，怎么进行等。 自学时

23、要掌握三个重要环节： 1. 认真阅读教材和参考资料，以指定教材为主，同时参考其他有关书籍。 2. 要在理解了基本概念和理论的基础上研究例题，注意例题是为了帮助理解概念、理论的。 3. 要学会做学习小结。,课程安排,学习运筹学的关键是掌握使用运筹学思想方法解决实际问题的能力，善于优化利用资源.运筹学的本质，具体说就是在做决策时： 首先要考虑做的事情是否有价值？其次要考虑自己是否有资源和能力完成这个计划？如果资源或能力不足，从哪里可以获得支持？ 善于发现资源和找到支持去完成有价值的决策，同时又能优化利用资源，才能形成竞争力. 希望通过本课程的学习，形成你的运筹帷幄，决胜千里的能力。,课程安排,参考

24、书,运筹学教程（第二版）,胡运权 主编，清华大学出版社，2005.10,运筹学方法与应用（修订版）,吴凤平 编，河海大学出版社，2003.7,新编运筹学题解,罗荣桂等 编，华中科技大学出版社，2001.,教材,运筹学（本科版），,清华大学出版社.,1. 孙武与孙子兵法 孙武，字长卿，后人尊称其为孙武子、孙子，中国历史上著名军事家。 公元前535 年左右出生于齐国乐安（今山东惠民）。后来到了吴国，因为献上兵法十三篇，被吴王阖闾重用，拜为大将，和伍子胥共事，辅佐吴王，后来领兵攻破楚国都城郢（今湖北江陵县纪南城）。孙武在春秋末期（公元前476年前后）所著孙子兵法，是世界上现存最古老的兵书。,中国古代

25、优秀的运筹案例,始计第一论述怎样在开战之前和战争中实行谋划的问题。 作战第二论述速战速胜的重要性。 谋攻第三论述用计谋征服敌人的问题。 军形第四论述用兵作战要先为自己创造不被敌人战胜的条件，以等待敌人可以被我战胜的时机，使自己“立于不败之地”。 兵势第五论述用兵作战要造成一种可以压倒敌人的迅猛 之势，并要善于利用这种迅猛之势。 虚实第六论述用兵作战须采用“避实而击虚”的方针。 军争第七论述如何争夺制胜的有利条件，使自己掌握作战主动权的问题。,中国古代优秀的运筹案例,九变第八论述将帅指挥作战应根据各种具体情况灵活机动地处置问题，不要机械死板而招致失败，并对将帅提出了要求。 行军第九论述行军作战中

26、怎样安置军队和判断敌情问题。 地形第十论述用兵作战怎样利用地形的问题，着重论述深入敌国作战的好处。 九地第十一进一步论述用兵作战怎样利用地形及统兵之道的问题。 火攻第十二论述在战争中使用火攻的办法、条件和原则等问题。 用间第十三论述使用间谍侦察敌情在作战中的重要意义，并论述了间谍的种类和使用间谍的方法。,中国古代优秀的运筹案例,2. 孙膑与齐王赛马 孙膑（约公元前380432），孙武的后世子孙，战国中期著名军事家。少时孤苦，年长后从师鬼谷子（著名隐士，精通兵学和纵横学）学习孙子兵法十三篇等兵书战策。庞涓妒孙膑之才而将其骗至魏，施以膑刑(割去膝盖骨)。其被齐使秘密接到齐国，被大将田忌所赏识。 孙

27、膑的“斗马术”是我国古代运筹思想中争取总体最优的脍炙人口的著名范例。 这个故事后来被传为千古佳话，成为军事上一条重要的用兵规律，即要善于用局部的牺牲去换取全局的胜利，从而达到以弱胜强的目的。他的基本思想是不强求一局的得失，而争取全盘的胜利，这是一个典型的博弈问题。,中国古代优秀的运筹案例,3. 围魏救赵 公元前354年，魏将军庞涓发兵8万，以突袭的办法将赵国的都城邯郸包围. 赵国求救于齐。齐威王拜田忌为大将，孙膑为军师，发兵8万，前往救赵. 孙膑提出应趁魏国国内兵力空虚之机，发兵直取魏都大梁（今河南开封），迫使魏军弃赵回救。这一战略思想，将避免齐军长途奔袭的疲劳，而致魏军于奔波被动之中，立即为

28、田忌采纳，率领齐军杀往魏国都城大梁。庞涓得知大梁告急的消息，忙率大军驰援大梁。 齐军事先在未魏军必经之路的桂陵（今河南长垣南），占据有利地形，以逸待劳，打败了魏军。这就是历史上有名的“围魏救赵”之战。,中国古代优秀的运筹案例,“围魏救赵”之妙，妙在善于调动敌人。调动敌人的要诀，则在“攻其所必救”。 这在近代战争中的许多场合也是适用的。,中国古代优秀的运筹案例,4. 马陵之战（减灶之法） 公元前342年，庞涓带领10万大军攻韩， 韩向齐求救。 齐威王召集群臣商讨对策，齐成侯邹忌主张不救，田忌主张早救。孙膑建议先答应韩国的请求，等到韩、魏双方战到疲惫不堪时再出兵。公元前341年韩再次向齐求助。齐以

29、田忌为主将，孙膑为军师。战役之初，齐军长驱直入攻击矛头指向魏国都城大梁。庞涓听到消息，立即回援，但齐军已经进入魏国境内。孙膑建议田忌：齐军进入魏国境内后先设10万个灶，过一天设5万个灶，再过一天设3万个灶。庞涓行军三天，见到齐军所留灶迹，判断齐军士兵已经逃跑一大半，所以丢下步兵，只率轻车锐骑用加倍的速度追赶齐军。孙膑在马陵（今河南范县西南）设全歼十万魏军。,中国古代优秀的运筹案例,马陵之战，孙膑的因势利导、调动敌人、变劣势为优势、力争发挥突然性的作战指导主动，是颇有参考价值的。 其退军设伏的战法，也给了后人不少的启示。 “围魏救赵”与“减灶之法”都充分体现了如何运用筹划兵力，选择最佳时间、地点

30、，趋利避害，集中优势兵力以弱克强的运筹思想。,中国古代优秀的运筹案例,5. 运筹帷幄中，决胜千里外 在公元前3世纪楚汉相争中，汉高祖刘邦的著名谋士张良为推翻秦朝，打败项羽，统一全国立下了盖世奇功，刘邦赞誉他“运筹帷幄中，决胜千里外”。这千古名句也可以说是对张良运筹思想的赞颂和褒奖。史记在留侯世家及其他多处提及“运筹帷幄中，决胜千里外”。这里的“运筹”，指张良在帷幄中制定作战谋略与决策的过程。在西汉时代，“运筹”已被当作制定谋略与决策职能分工的代名词。,中国古代优秀的运筹案例,6. 贾思勰与齐民要术 贾思勰，北魏时期的科学家，益都(在今山东寿光南)人，祖、父两代都善于经营，有着丰富的劳动经验，并都非常重视农业技术方面的学习和研究。贾思勰从小在田园长大，对很多农作物都非常熟悉，他还跟着父亲身体力行参加各种农业劳动，学习掌握了大量农业科技. 他家里拥有大量藏书，这使他从小就有机会博览群书，从中汲取各方面的知识，也为他以后编撰齐民要术打下了基础。大约在北魏永熙二年（533年）到东魏武定二年（554年）期间，他将自己积累的许多古书上的农业技术资料、询问老农获得的丰富经验、以及他自己的亲身实践，加以分析、整理、总结，写成农业科学技术巨著齐民要术。,中国古代优秀的运筹案例,齐民要术一书，不仅是我国古代农业科学一部杰出的学术著作，也是一部蕴含丰富运筹