《运筹学概述ppt课件.ppt》由会员分享，可在线阅读，更多相关《运筹学概述ppt课件.ppt（35页珍藏版）》请在三一文库上搜索。
1、1,运 筹 学,主讲人：叶娟 ,2,什么是运筹学？,主要用数学的方法研究各种系统的优化途径及方案，为决策者提供科学决策的依据。 Operation Research ，OR 主要研究对象：主要为各种有组织系统的管理问题及其生产经营活动 主要研究方法：定量化和模型化方法 目的：针对所研究的系统，求得一个合理运用人力、物力和财力的最佳方案，发挥和提高系统的效能和效益，最终达到系统的最优目标。,3,历史上运筹学的运用,我国：战国时代 齐王与田忌赛马 国外：1736年欧拉解决 哥尼斯堡七桥问题,4,齐王与田忌赛马,史记中有这样一个故事：有一天，齐王要田忌和他赛马，规定每个人从自己的上、中、下三等马中各
2、选一匹来赛；并规定，每次有一匹马来比赛；并约定，每有一匹马取胜可获千两黄金，每有一匹马落后要付千两黄金。当时，齐王的每一等次的马比田忌同样等次的马都要强，因而，如果田忌用自己的上等马与齐王的上等马比，用自己的中等马与齐王的中等马比，用自己的下等马与齐王的下等马比，则田忌要输三次，因而要输黄金三千两。但是结果，田忌没有输，反而赢了一千两黄金。这是怎么回事呢？,5,在赛马之前，田忌的谋士孙膑给他出了一个主意，让田忌用自己的下等马去与齐王的上等马比，用自己的上等马与齐王的中等马比，用自己的中等马与齐王的下等马比。田忌的下等马当然会输，但是上等马和中等马都赢了。因而田忌不仅没有输掉黄金三千两，还赢了黄
3、金一千两。 问题表明，在有双方参加的竞赛或斗争中，策略是很重要的。采用的策略适当，就有可能在似乎一定会失败的情况下取得胜利的结果。 研究这种竞赛策略的数学分支，叫作博奕论，也叫对策论；是运筹学的重要分支。,6,历史上运筹学的运用,我国：战国时代 齐王与田忌赛马 国外：1736年欧拉解决 哥尼斯堡七桥问题,7,哥尼斯堡七桥问题,濒临蓝色的波罗的海，有一座古老而美丽的城市，叫做哥尼斯堡（今俄罗斯加里宁格勒）。 布勒格尔河的两条支流在这里汇合，然后横贯全城，流入大海。河心有一个小岛。河水把城市分成了块，于是，人们建造了座各具特色的桥，把哥尼斯堡连成一体。 一天又一天，座桥上走过了无数的行人。不知从什
4、么时候起，脚下的桥梁触发了人们的灵感，一个有趣的问题在居民中传开了： 谁能够一次走遍所有的座桥，而且每座桥都只通过一次？ 这个问题似乎不难，谁都乐意用它来测试一下自己的智力。可是，谁也没有找到一条这样的路线。连以博学著称的大学教授们，也感到一筹莫展。“七桥问题”难住了哥尼斯堡的所有居民。哥尼斯堡也因“七桥问题”而出了名。,8,七桥问题的形象描述,城市分割成4个区域： 河的两岸（A和B），河 中的岛（C）和两条支流 之间的半岛（D）。七座 桥横跨普勒格尔河及其支 流，把河岸、半岛和河心 岛连接起来。,9,欧拉的解题思路,当时的大数学家欧拉没有亲自去哥尼斯堡 测试可能的路线 。事实上，如果沿着所有
5、可能的路线都走一次的话，一共要走5040次。就算是一天走一次，也需要13年多的时间，而实际上欧拉只用了几天的时间就解决了七桥问题。,10,欧拉的解题思路,1、建立模型： 首先把哥尼斯堡的4个 区域分别用点A、B、C、D 表示，每座连接两个区域的 桥用相应两点的连线a、b、 c、d、e、f、g表示，即把哥 尼斯堡七桥的情景转化为一 个图。,11,欧拉的解题思路,2、问题转化：在上图中，从任何一点出发，笔不离纸，但又不能重复任何一条边地画出上图，且起点与终点重合，这样的画法存在吗？（这就是众所周知的“一笔画”游戏）,12,欧拉的解题思路,3、欧拉的结论： 七桥问题中要找的那条路线是不存在的。 网络
6、能否一笔画出来的关键在于这些点。这些点有两类，如果从一点引出的线是奇数条，就把这个点叫奇点；如果从一点引出的线是偶数条，就把这个点叫偶点。网络中奇点的数是零或二，这个网络就能一笔画出来。 由于七桥问题中的四个点都是奇点，按欧拉的规律，这个网络是一笔画不出来的。,13,欧拉的研究所涉及的学科,图论与网络 拓扑学,14,运筹学学科的形成,普遍认为，运筹学作为一门新兴学科起源于二战期间的军事运筹活动。当时英、美都发明和制造了一批新式武器，但如何使用这些武器却远远落后于这些武器的制造。为此，英国军事管理部门召来了一批具有不同学科和专业背景的科学家，在1940年成立了“OR”小组。这标志着世界第一次开始
7、正式的运筹学活动。随后，美国也成立了运筹学小组。这些早期的运筹工作，主要是进行战术评价、战术改进、作战计划、战略选择、改进后勤调度和训练计划等方面的研究。不同学科的相互渗透所产生的协同作用，成功的解决了许多重要的问题，为以后运筹学的发展积累了丰富的经验。,15,运筹学的特点,运筹学作为一门定量决策科学，利用数学、计算机科学与其它科学的新成就，研究各种系统尤其是经济管理中运行的数量化规律，合理使用与统筹安排人力、物力、财力等资源，为决策者提供有依据的最优方案，以实现最有效的管理并获得满意的经济效益和社会效果，就其理论与应用意义上归纳，运筹学具有如下一些主要特点：,16,运筹学的特点,1.运筹学研
8、究和解决问题的基础是最优化技术，并强调系统整体最优。 2. 运筹学研究和解决问题的优势是应用各学科交叉的方法，具有综合性。 3.运筹学研究和解决问题的方法具有显著的系统分析特征，其各种方法的运用，几乎都需要建立数学模型和利用计算机进行求解。 4.运筹学研究和解决问题的效果具有连续性。 5.运筹学具有强烈的实践性和应用的广泛性。,17,模型的概念,人们在对现实世界进行研究、认识时， 必须对现实世界进行抽象，现实世界才能成为思维的对象。 在解决实际问题时，经常使用一些文字、数字、符号、公式、图表以及实物，用以描述客观事物的某些特征和内在联系，从而表示或解释某一系统的过程，这就是模型。由此可见，模型
9、是客观世界抽象的描述，能帮助人们认识、分析和解决实际问题。,18,模型的功能,1.模型是实现问题某一主要方面的描述或抽象，比现实本身简单和概括，使人易于认识、理解和操作； 2.模型是由与研究问题有关的主要因素所构成，并表明这些因素的相互关系，从而能够更简明地揭示出问题的本质； 3.通过模型可以进行试验，用以分析和预测所研究事物或系统的特征及性质； 4.利用模型可以在相对短的时间内获得所研究问题的结果； 5.利用模型可以根据过去和现在的信息进行预测，并可用来培训教育人才。,19,模型的分类,从建模的方法上分： 1、实物模型 2、数学模型 3、模拟模型 从模型中所包含的变量特性分： 1、确定性模型
10、 2、不确定性模型,20,模型的求解,数学的方法 运筹学的推广与计算机的发展分不开，由于其处理的问题的复杂性，计算机成为求解运筹学模型的有力工具。,21,运筹学的求解步骤,1.提出并形成问题； 2.建立模型； 3.分析并求解模型； 4.检验并评价模型； 5.应用或实施模型的解。,22,运筹学的重要分支,数学规划（线性规划、非线性规划、整数规划、目标规划、动态规划、随机规划等）、图论与网络、排队论（随机服务系统理论）、存贮论、对策论、决策论、维修更新理论、搜索论、可靠性和质量管理等。,23,目录,线性规划 运输问题 图与网络 动态规划 目标规划,24,运筹学在管理中的典型应用,生产计划问题 运输
11、问题,25,生产计划问题,在工厂计划期内要安排生产A、B两种产品，已知生产单位产品所需的设备台时及a、b两种原材料的消耗如下表。又该工厂每生产一件A产品可获利2元，每生产一件B产品可获例3元。问：如何安排计划使该工厂获利最大？,26,解 : 设A、B两种的产量分别为（决策变量），该问题的数学模型为： 目标函数 约束函数 （Subject To：s.t.）,电子表格求解见例1.xls,27,运输问题,两煤矿产的煤运往三个城市销售，各煤矿的供应量、各城市的需求量以及煤矿与城市之间的单位运费如下表。试列出其数学规划模型。,28,解 设,为第i煤矿向第j城市的供应量。,电子表格求解见例2.xls,29
12、,请同学们自己动手,尝试为下面的3个问题建立模型,30,1、某厂为进行生产需采购A、B两种原材料，单价分别为70元/公斤和50元/公斤。现要求购买资金不超过5000元，总购买量不少于80公斤，而A原材料不少于20公斤。问如何确定最好的采购方案（即花掉的资金最少或购买的总量最大）？,31,2、某纺织厂生产A、B两种布料，平均生产能力均为1千米/小时，工厂正常生产能力是80小时/周。又A布料每千米获利2500元，B布料每千米获利1500元。已知A、B两种布料每周的市场需求量分别是70千米和45千米。试寻找最优的产品组合，使总利润最大。,32,3、某配送公司要将两工厂生产的产品运送到两仓库，工厂1的
13、产品只能运到仓库1，数量不限，工厂2的产品只能运到仓库2，数量也不限，也可以由工厂将产品运到配送中心，再由配送中心将产品运到仓库，但配送中心一次运入与运出的产品数量有限。该问题的目标是：如何安排运送，才能使总的运送成本最小？有关数据如下表.,33,电子表格求解见例3.xls,34,总结-本章几个名词,模型：对事物中各因素之间关系的描述和抽象，它应反映事物的多种特征，使人们进行理论思维成为可能。 系统：由相互联系的各个部分组成。 算法：对模型的求解方法。 设计算法分析算法编制程序上机调试得到解 模拟：原型不能建立数学解析式，用计算机模拟系统行为，采用数据处理的方法求解原型。 运筹学OPERATING RESEARCH。从全局的观点出发，通过建立模型（数学模型或模拟模型），对要求解的问题得到最合理的决策。 运筹学范畴：市场营销、生产计划、库存管理、运输、财会、人事管理、计算机和信息系统 运筹学分支：LP、NLP、动态规划、多目标规划、图与网络、排队论、存储论、对策论、决策论。,35,本章结束!,