运筹学 绪论.ppt

1、系统工程,主讲教师：杨毓玲E-mail：yyl.yyl,课程导论,课程类别必修开课层次本科学分3学时48(理论学时：40，实验学时：8)内容提要是运用数学方法对经济管理系统中的各种有限资源进行统筹安排，为决策者提供有依据的最优方案，以实现最有效的管理的科学。其主要内容包括线性规划、动态规划、整数规划、图论初步、决策分析等,教材运筹学原理与方法，西南交通大学出版社，郭耀煌等参考书1运筹学（I类），徐玖平等编著，科学出版社2运筹学教程，胡运权主编，清华大学出版社，19983运筹学，运筹学教材编写组，清华大学出版社，20054或其他的运筹学方面本科教材,本课程授课方式与考核本课程理论课程授课方式（4

2、学时/周，共10周）：讲授为主，结合习题作业实验环节授课方式：上机（时间安排在所有理论课程结束之后，即11周开始）成绩结构：平时成绩（作业、出勤情况）：15实验成绩（作业、出勤情况）：15期末考试（闭卷考试）成绩：70统一使用作业本，封面写上姓名，班级，学号,课程性质和教学目的,交通工程专业的专业必修课程（主干课程之一）运筹学是经济与管理类学生的专业基础课。通过本课程的学习，使学生获得经济管理决策中常用的运筹学的基本概念、基本理论与基本方法，为进一步学习与掌握现代管理理论奠定必要的理论基础，并培养与提升学生对实际问题运用定量方法分析与求解，以及进行辅助决策的能力。,第一讲绪论,一、运筹学的形成

3、与发展二、运筹学的特点及分析步骤三、运筹学的定义及学科体系四、运筹学在经济管理中应用的主要课题,学习目的学习本章要了解运筹学的形成和发展历史、典型案例，以及运筹学研究的主要内容等。要掌握运筹学的性质、主要分支、分析步骤和发展方向等。,第一节运筹学的形成和发展,运筹学（OperationsResearch）是系统工程的最重要的理论基础之一，在美国有人把运筹学称之为管理科学(ManagementScience)。运筹学所研究的问题，可简单地归结为一句话：“依照给定条件和目标，从众多方案中选择最佳方案”，故有人称之为最优化技术。,一、中国古代的运筹学思想中国史记中的“运筹策于帷幄之中，决胜于千里之外

4、”表达了中国古代运筹学思想，在古代中国有许多运筹学思想的应用案例，如丁谓修宫、田忌赛马、侯叔献治水、赵括送粮、李冰修堰等，都蕴藏着神奇的运筹学思想，这些案例至今仍有很高的参考和借鉴价值。,1丁谓修宫宋朝梦溪笔谈中记载了这样一个故事：北宋真宗年间，皇宫失火，皇帝召各大臣商议如何在很短的时间内修复好皇宫，而修复皇宫包括取土烧砖，运输建筑材料，清理废墟三大工程，但在当时的条件下，这是相当繁重的工程，大家都无以言答。当时有个叫丁谓的大臣，他提出了一个一举三得的方案：,在皇宫前的大道上挖沟取土烧砖，解决了取土烧砖的问题。引汴河水入沟，由汴河从水路运入材料、石材等建筑材料，解决运输建筑材料的问题修复好皇宫

5、后将碎砖废瓦再填回原来的沟内以修好大道，解决清理废墟问题该方案三环节环环紧扣，缺一不可，真可谓一举三得。这正是我国古代劳动人员自发引用这种思想的典型例子，从这个例子可以看出，丁谓在解决问题时，并没有把三个工程孤立地分割开来，而是把他们有机地放在一个整体中，从中找到他们之间的有机联系，从而解决了问题。,2田忌赛马,战国时期齐王和田忌赛马,各从自己上等马、中等马、下等马中选送一匹进行比赛，每输一局，输银千两，齐王的马都比田忌的好，但田忌的下等马与齐王的上等马赛，用上等马对中等马，用中等马对下等马，这样田忌非但没有输，反而嬴了一千两银子，这便是系统中从整体出发，选最优方案，到最后实施的对策策略。,二

6、、第二次世界大战中的案例1.巧妙避开德军潜艇1943年以前，在大西洋上英美运输船队常常受到德国潜艇的袭击，当时，英美两国海军实力有限，一时间，德军的潜艇战搞得盟军焦头烂额。为此，一位美国海军将领专门去请教了几位数学家。数学家们运用概率分析后发现，舰队与敌潜艇相遇是一个随机事件。从数学角度来看这一问题，它具有一定的规律：一定数量的船编次越多与敌人相遇的概率就越大。美国海军接受了数学家的建议，命令舰队在指定海域集合，再集体通过危险海域，然后各自驶向预定港口。结果盟军舰队遭袭被击沉的概率下降，大大减少了损失。,2.准确判定日舰行驶路线第二次世界大战新几内亚作战期间，美军得到了日军将从新不列颠岛东岸的

7、腊包尔港派出大型护航舰队驶往新几内亚莱城的情报，日军舰队可能走两条航线，航程都是3天。其中北面航线云多雾大，能见度差，不便于观察；南面航线能见度好，便于观察。美军也有两种行动方案可供选择，即分别在南北航线上集中航空兵主力进行侦察、轰炸。若日军选择走北线，美军也选择北线，由于天气影响只能有两天轰炸时间；美军若选南线，则由于在南线侦察耽搁一天，到北线侦察延误一天，只能争取一天的轰炸时间，因此日军选择北线，被轰炸天数为12天。根据同样的判断，若日军选择南线，则被轰炸数为23天。美军由此断定日军必走北线。真实情况果真如此。日军舰队起航一天后，在北线被美军发现并被轰炸两天，结果损失惨重。,3.理智撤回援

8、法飞机第二次世界大战时期，当德国对法国等几个国家发动攻势时，英国首相丘吉尔应法国的请求，动用了十几个防空中队的飞机和德国作战。这些飞机中队必须由欧洲大陆上的机场来维护和操作。空战中英军飞机损失惨重。与此同时，法国总理要求继续增派10个中队的飞机。丘吉尔决定同意这一请求。内阁知道此事后，找来数学家进行分析预测，并根据出动飞机与战损飞机的统计数据建立了回归预测模型。经过快速研究发现，如果补充率损失率不变，飞机数量的下降是非常快的。用一句话概括，就是以现在的损失率损失两周，英国在法国的“飓风”式战斗机便一架也不存在了。数学家们要求内阁否决这一决定。最后丘吉尔同意了这一要求，并将除留在法国的3个中队外

9、，其余飞机全部撤回英国，为下一步的英伦保卫战保存了实力。,4.算准深水炸弹爆炸深度第二次世界大战期间，英军船队在大西洋里航行时经常受到德军潜艇的攻击。为此，英国空军经常派出轰炸机对德军潜艇实施火力打击，但轰炸效果总是不理想，对潜艇几乎构不成威胁。英军请来一些数学家专门研究这一问题，结果发现，潜艇从发现英军飞机开始下潜到深水炸弹爆炸时止，只下潜了7.6米，而英军飞机投下的炸弹却已下沉到21米处爆炸，从而导致毁伤效果低下。经过科学论证，英军果断调整了深水炸弹的引信，爆炸深度从水下21米减为水下9.1米，结果轰炸效果较过去提高了4倍。德军还误以为英军发明了新式炸弹。,三、运筹学学科的形成,现在普遍认

10、为，运筹学的活动是从第二次世界大战初期的军事任务开始的，以英国为代表的科学家做了奠基性的工作。当时迫切需要把各项稀少的资源以有效的方式分配给各种不同的军事经营及在每一经营内的各项活动，所以美国及随后美国的军事管理当局都号召大批科学家运用科学手段来处理战略与战术问题，实际上这便是要求他们对种种（军事）经营进行研究，这些科学家小组正是最早的运筹小组（O.R.小组）。第二次世界大战期间，运筹学（OR）成功地解决了许多重要作战问题，显示了科学的巨大物质威力，为“OR”后来的发展铺平了道路。,1935年，英国科学家R.Watson-Wart发明了雷达。丘吉尔命令在英国东海岸的Bawdsey建立了一个秘密

11、雷达站。1939年由P.M.S.Blackett（著名物理学家）为首，组织了一个小组，代号“Blackett马戏团”。研究的问题是：设计将雷达信息传送到指挥系统和武器系统的最佳方式；雷达与武器的最佳配置；对探测、信息传递、作战指挥、战斗机与武器的协调，作了系统的研究，并获得成功。“Blackett马戏团”在秘密报告中使用了“OperationalResearch”，即“运筹学”。,当战后的工业恢复繁荣时，由于组织内与日俱增的复杂性和专门化所产生的问题，使人们认识到这些问题基本上与战争中所曾面临的问题类似，只是具有不同的现实环境而已，运筹学就这样潜入工商企业和其它部门，在20世纪50年代以后得到

12、了广泛的应用。对于系统配置、聚散、竞争的运用机理深入的研究和应用，形成了比较完备的一套理论，如规划论、排队论、存贮论、决策论等等。由于其理论上的成熟，电子计算机的问世，又大大促进了运筹学的发展。从以上简史可以看出，为运筹学的建立和发展做出贡献的有物理学家、经济学家、数学家、其它专业的学者、军官和各行业的实际工作者。,四、运筹学学科的发展,五、运筹学的发展方向问题,运筹学到20世纪70年代已形成一系列强有力的分支，数学描述相当完善，这是一件好事。正是这一点使不少运筹学界的前辈认为，有些专家钻进运筹数学的深处，而忘了运筹学的原有特色，忽略了多学科的横向交叉联系和解决实际问题的研究，指出有些人只迷恋

13、于数学模型的精巧、复杂化、使用高深的数学工具,而不善于处理面临大量新的不易解决的实际问题。,现代运筹学工作者面临的大量新问题是：经济、技术、社会、生态和政治等因素交织在一起的复杂系统。因此，从20世纪70年代末到80年代初不少运筹学家提出：要注意研究大系统，注意与系统分析相结合。由于面临的问题大多是涉及技术、经济、社会、心理等综合因素的研究，在运筹学中，除了常用的数学方法以外，还引入一些非数学的方法和理论。,六、运筹学与计算机,计算机为运筹学提供解题工具。要学会解题的思路与方法，建立模型很重要。,假设有70艘油轮向70个港口运货，已知每艘油轮驶向每个港口的费用，油轮公司需制订出最优运输方案。采

14、用全枚举法（穷举法）需计算方案数为70!(大于10100）；IBM公司当时生产的大计算机1秒种大约可算出109（即10亿）个方案。若要逐个算出全部方案，则需调用占有空间为1050个地球一样大的IBM公司生产的众多大型计算机同时计算几百亿年以上。而在这种大机器上用线性规划的单纯形法计算只需几秒钟。可见，将运筹学与计算机科学及其它科学结合应用，将会产生更好的效果。,运筹学的推广应用前景,据美劳工局1992年统计预测:运筹学应用分析人员需求从1990年到2005年的增长百分比预测为73%,增长速度排到各项职业的前三位.运筹学在国内或国外的推广前景是非常广阔的工商企业对运筹学应用和需求是很大的在工商企

15、业推广运筹学方面有大量的工作要做,第二节运筹学的特点及分析步骤,（1）科学性它是在科学方法论的指导下通过一系列规范化步骤进行的；它是广泛利用多种学科的科学技术知识进行的研究。运筹学研究不仅仅涉及数学，还要涉及经济科学、系统科学、工程物理科学等其他学科。（2）实践性运筹学以实际问题为分析对象，通过鉴别问题的性质、系统的目标以及系统内主要变量之间的关系，利用数学方法达到对系统进行最优化的目的。更为重要的是分析获得的结果要能被实践检验，并被用来指导实际系统的运行。,一、运筹学的学科性质,（3）系统性运筹学用系统的观点来分析一个组织（或系统），它着眼于整个系统而不是一个局部，通过协调各组成部分之间的关

16、系和利害冲突，使整个系统达到最优状态。（4）综合性运筹学研究是一种综合性的研究，它涉及问题的方方面面，应用多学科的知识，因此，要由一个各方面的专家组成的小组来完成。,二、运筹学模型及分析步骤,1模型运筹学模型是用一些数学关系（数学方程、逻辑关系等）来描述被研究对象的实际关系（技术关系、物理定律、外部环境等）。运筹学模型的一个显著特点是它们大部分为最优化模型。一般来说，运筹学模型都有一个目标函数和一系列的约束条件，模型的目标是在满足约束条件的前提下使目标函数最大化或最小化。,2研究方法运筹学的研究方法有：从现实生活场合抽出本质的要素来构造数学模型，因而可寻求一个跟决策者的目标有关的解；探索求解的

17、结构并导出系统的求解过程；从可行方案中寻求系统的最优解法。,3运筹学解决问题的方法步骤,明确问题建立模型设计算法整理数据求解模型评价结果,明确问题,建立模型,设计算法,整理数据,求解模型,评价结果,简化？,满意？,Yes,No,No,4.运筹学应用中的应注意的问题运筹学是一种很好的分析工具，如果使用得当，可以取得理想的效果。如果使用不当，也会造成很糟糕的结果。在复杂的政治经济生活中应用运筹学方法，切不可书生气十足，不要把数学中的“最优解”与现实生活中的最优解等同起来，必须全面考虑多种影响因素，综合分析，对数学“最优解”进行认真审查或修改，然后才能付诸实施。如果不加分析（或修改）地把数学“最优解

18、”应用于实践，往往会造成效果不佳或是根本行不通的局面。这样一来，不但会造成决策失误和损失，而且会使人们失去对运筹学的信任和兴趣，从而疏而远之。,OperationsResearch含义Operations汉语翻译工作、操作、行动、手术、运算OperationsResearch日本运用学港台作业研究中国大陆运筹学OperationalResearch原来名称意为军事行动研究,第三节运筹学的定义及学科体系,运筹学的定义Morse&Kimball（运筹学界元老）运筹学是为决策机构在对其控制的业务活动进行决策时提供的数量化为基础的科学方法。英国人运筹学会（世界上最早的运筹学会）运筹学是运用科学方法（特

19、别是数学方法）来解决工业、商业、政府、国防等部门里有关人力、机器、物资、金钱等大型系统的指挥和管理中出现的复杂问题的一门学科。,由一支综合性的队伍，采用科学的方法，为一些涉及到有机系统（人-机）的控制系统问题提供解答，为该系统的总目标服务的学科。钱学森等二十世纪四十年代开始形成的一门学科，主要研究经济活动与军事活动中能用数量来表达的有关运用、筹划与管理等方面的问题。它根据问题的要求，通过数学分析和运算，作出综合性的合理安排，以达到较经济、较有效地使用人力、物力。近年来，它在理论与应用方面都有较大的发展。运筹学的分支有规划论、对策论、排队论及质量控制等。辞海,数以百计的定义之核心是用科学方法来处

20、理自然物环境和社会环境中有关人和物的运行体系。物包括从机器一直到按人们已经接受的按某些规律运转的复杂的社会结构。,二、学科体系运筹学已经形成了一个庞大的学科体系，其具体内容主要包括：规划论（包括线性规划、非线性规划、整数规划和动态规划）、决策论、对策论、排队论、存储论、网络分析等。,运筹学的分支,线性规划非线性规划整数规划动态规划多目标规划运输问题模糊规划等,图与网络理论存储论排队论决策论对策论排序与统筹方法可靠性理论等,1、Mathematicalprogramming:LinearprogrammingNonlinearprogrammingIntegerprogrammingObject

21、iveprogrammingDynamicprogrammingStochasticprogrammingGeometricprogramming等。,2、Graphtheory3、Networkanalysis4、Queueingtheory5、Gametheory6、Decisiontheory7、Qualitycontrol8、Reliabilitytheory,9、Storagetheory10、Searchtheory11、Maintenancetheory12、Computersimulation13、Schedulingmethod14、Valuetheory15、Renewal

22、theory16、Controltheory17、Militaryoperationsresearch等。,四、运筹学在经济管理中应用的主要课题,生产计划：生产作业的计划、日程表的编排、合理下料、配料问题、物料管理等库存管理：多种物资库存量的管理，库存方式、库存量等运输问题：确定最小成本的运输线路、物资的调拨、运输工具的调度以及建厂地址的选择等人事管理：对人员的需求和使用的预测，确定人员编制、员合理分配，建立人才评价体系等市场营销：广告预算、媒介选择、定价、产品开发与销售计划制定等财务和会计：预测、贷款、成本分析、定价、证券管理、现金管理等,1、绪论2、线性规划3、线性规划的对偶理论与灵敏度分析4、运输问题5、整数规划6、图与网络方法7、网络计划技术8、矩阵对策9、决策分析,运筹学授课目录,本课程特点及要求,目的：不仅掌握优化理论方法的专业知识，更重要的是提高分析问题和解决问题的能力。方法：强调思路、观点及弄清物理概念，掌握一定的