《全校性公选课-绪论.ppt》由会员分享，可在线阅读，更多相关《全校性公选课-绪论.ppt（47页珍藏版）》请在三一办公上搜索。
1、运 筹 学,孙滢,北方民族大学信息与计算科学学院,(Operations Research),运 筹,“夫运筹帷幄之中，决胜于千里之外”,史记高祖本纪,参考资料,教材：钱颂迪.运筹学（本科版）.清华大学出版社胡运权.运筹学教程（第二版）.清华大学出版社刁在筠等.运筹学（第三版）.高等教育出版社软件：MatlabLingoLindoExcel,要求,第一章 绪论,运筹学的简史运筹学的性质和特点运筹学的工作步骤运筹学的模型运筹学的应用运筹学的展望,1 运筹学的简史,第二次世界大战期间，英国为了应用雷达探测德国飞机对英国本土的空袭，组成了由物理学家、数学家、天文学家、生物学家和军官参加的作战研究小组
2、。第一次应用了 Operational Research 这个名词。因研究成果显著，后又从空军扩展到海军和陆军。在英国成立这种研究小组不久，美国也建立了类似的小组，但称之为Operations Research，简称OR.,第二次世界大战之后，在英、美军队中相继成立了正式运筹研究组织，以兰德公司（LAND）为首的一些部门开始着重研究战略性问题。例如，为美国空军评价各种轰炸机系统，讨论未来的武器系统和未来战争的战略等；研究苏联的军事能力及未来的预报等。总的来说，在这段时间里运筹学的研究与应用范围主要是与战争相关的战略、战术方面问题。,由于运筹学适应时代的要求，在近六十年中，它无论从理论上还是应用
3、上都得到了快速的发展。在应用方面，今天运筹学已经涉及到了服务、管理、规划、决策、组织、生产、建设等诸多方面，甚至可以说，很难找出它涉及不到的领域。,20世纪50年代中期，我国著名的科学家钱学森、许国志等将运筹学从西方引入我国，并结合我国的特点在国内推广应用。自从引入以来，运筹学在我国已有四十多年的历史。经过这四十多年，运筹学在我国有了很大的发展，确立了它在经济建设中的地位。但是，运筹学在我国的发展状况与世界其它国家相比，尚有不小的差距，其中最主要的是认识与基础的问题。,都江堰水利工程 战国时期（大约公元前250年）川西太守李冰父子主持修建。其目标是：利用岷江上游的水资源灌溉川西平原。追求的效益
4、还有防洪与航运。其总体构思是系统思想的杰出运用。,都江堰由三大工程及120多项配套工程组成：1.“鱼嘴”岷江分水工程：将岷江水有控制地引入内江。2.“飞沙堰”分洪排沙工程：将泥沙排入外江。3.“宝瓶口”引水工程：除沙后的江水引入水网干道。它们巧妙结合，完整而严密，相得益彰。两千多年来，这项工程一直发挥着巨大的效益，是我国最成功的水利工程。,运筹思想的应用,丁谓的皇宫修复工程,北宋年间，丁谓负责修复火毁的开封皇宫。他的施工方案是：先将工程皇宫前的一条大街挖成一条大沟，将大沟与汴水相通。使用挖出的土就地制砖，令与汴水相连形成的河道承担繁重的运输任务；修复工程完成后，实施大沟排水，并将原废墟物回填，
5、修复成原来的大街。丁谓将取材、运输及废墟物的处理用“一沟三用”巧妙地解决了。,上中下 田忌下上中最终净胜一局，赢得1000金。,齐王要与大臣田忌赛马，双方出上、中、下马各一匹，对局三次，每次胜负1000金。田忌在好友、著名的军事谋略家孙膑的指导下，以以下安排：,田忌赛马,齐王,2 运筹学的性质和特点,（1）运筹学的定义 到目前为止，运筹学还没有一个比较完善的统一的定义。下面列出一些比较有代表性的看法：英国运筹学学会认为：运筹学是应用于指导和管理工商业、政府和国防方面有关人员、设备、物资以及资金的大系统中所发生的各种问题的科学方法。美国运筹学学会认为：运筹学是一种进行定量分析的科学方法，它通过评
6、价一个管理系统中可供选择的方案的有关因素，提供改进管理的决策基础。,我国运筹学研究工作者认为：运筹学是指应用系统的、科学的、数学分析的方法，通过建立、检验和求解数学模型，而获得最优决策的科学。综上所述：运筹学是运用数学方法研究解决经济和工程管理中，资源的有效利用，任务的合理分配，方案的正确选择的科学，是一门研究如何以有限的资源，完成最大的任务，取得最优的经济效果的科学。,运筹学是一种给出问题坏的答案的艺术，否则的话问题的结果会更坏；这个定义表明运筹学强调最优决策过分理想，在现实中很难实现，于是用次优、满意等概念来代替最优。,（2）运筹学的特点 第一个特点是从全局的观点看问题，追求总体效果最优。
7、第二个特点是通过建立与求解模型，使问题在量化的基础上得到合理的决策。在建立模型及求解的过程中，要用到一些数学方法和技巧，故运筹学工作者必须具有一定的数学基础。第三个特点是多学科交叉，大而复杂的系统，往往是政治、经济、技术、社会、心理、生态等多种因素交织在一起。第四个特点是与计算机密切相关。历史表明，没有计算机的发展，就没有运筹学的发展。在应用运筹学解决问题时，一般都要借助计算机计算，手算是不现实的。,运用运筹学方法解决问题的一般步骤:,1、提出并形成问题,2、建立模型,3、分析并求解模型,4、检验并评价模型,5、应用或实施模型的解,最优化技术,课程重点,3 运筹学的工作步骤,运筹学建模在理论上
8、，应是属于数学建模的一个部分。因此，运筹学建模所采用的手段、途径与一般在数学建模中所采用的类似。经过长期、深入的研究和发展，运筹学处理的问题归纳成一系列具有较强背景和规范特征的典型问题。因此，运筹学建模就要把相当的精力放在将实际问题合理地描述为某种典型的运筹模型上。在这个过程中，一般要求运筹学工作者具有以下几个方面的知识和能力：,4 运筹学的模型,(1)熟悉典型运筹模型的特征和它的应用背景；(2)有分析、理解实际问题的能力，包括广博的知识、搜集信息、资料和数据的能力；(3)有抽象分析问题的能力，包括善于抓主要矛盾，善于逻辑思维、推理、归纳、联想、类比等形成的创新能力；(4)有运用各类工具知识的
9、能力，包括运用数学、计算机、其它自然科学的知识和工程技术等的能力；(5)有试验校正和维护修正模型等的能力。,根据问题本身的情况，运筹学在解决问题时，按研究对象不同可构造各种不同的模型。模型是研究者对客观现实经过思维抽象后用文字、图表、符号、关系式以及实体描述所认识到的客观对象。模型的有关参数和关系式比较容易改变，这样将有助于问题的分析和研究。利用模型可以对所研究的问题进行一定预测及灵敏度分析等。,模型的三种基本形式：,三种基本形式,形象模型,模拟模型,符号或数学模型,建立、构造模型是一种创造性劳动，成功的模型往往是科学和艺术的结晶，常见的构模方法和思路有以下几种：,直接分析法,类比分析法,数据
10、分析法,试验分析法,构想（构思）法,机理清楚,机理不清楚,五种方法和思路,模型的一般形式,目标评价准则：V=f（xi,yj,k）,约 束 条 件：g（xi,yj,k）0,其中：x i 为可控变量；yj 为已知参数；k 为随机因素,或：max(或min)Z=f(x1.x2.xn)gi(x1.x2.xn)(.)0(i=1.2m)hj(x1.x2.xn)=0(j=1.2l),其中：xj(i=1.2n)为决策变量 Z 为目标函数,gi(x1.x2.xn)0 和 hj(x1.x2.xn)=0 为约束条件,s.t.,5 运筹学的应用,运筹学在早期的研究主要在军事领域，二次大战后运筹学的研究转向民用。经过几
11、十年的发展，运筹学的研究范围已经涉及到社会、政治、经济、军事、科学、技术等各个领域，发挥了巨大作用。这里选择几个管理方面的应用给予简单介绍。1、生产运作：生产总体计划要求从总体确定生产、存贮和劳动力的配合规划以适应波动的需求计划。运筹学的应用主要在生产作业的计划、日程表的编排、合理下料、配料问题、物料管理等方面；,2、物资库存管理：多种物资库存的系统组织与安排管理，确定某些设备的能力或容量，如停车场的大小、新增发电设备的容量大小、电子计算机的内存量、合理的水库容量等。将库存理论与计算机的物资管理信息系统相结合，确定合理的库存方式、计算最佳的库存量等；3、物资运输问题：涉及空运、水运、公路运输、
12、铁路运输、管道运输、厂内运输。常常涉及班次和人员服务时间安排等，需要确定最小成本的运输线路、物资的调拨、运输工具的调度等；,4、组织人事管理：对人员的需求和使用方面的预测，确定人员编制、人员合理分配，建立人才评价体系、人才开发的规划、激励机制的研究等；5、市场营销：广告预算、媒介选择、产品定价、新产品的引入和开发、销售计划制定、市场模拟研究等；6、财务管理和会计：各经济项目的预测、预算，贷款、成本分析、证券管理、现金管理等。常使用的方法有统计分析、数学规划、决策分析、盈亏点分析法、价值分析法等；,7、计算机应用和信息系统开发：运筹学中的数学规划方法、网络图论、排队论、存储论、模拟与仿真方法等均
13、起到巨大作用；8、城市管理：各种紧急服务系统的设计和运用、城市垃圾的清扫、搬运和处理、城市供水和污水处理系统的规划、区域规划、市区交通网络的规划与管理等。,6 运筹学的主要内容,线性规划非线性规划整数规划多目标规划动态规划图与网络优化存储论,排队论对策论决策分析排序与统筹方法随机规划预测智能优化算法简介,7 运筹学的展望,运筹学的理论研究将会得到进一步系统地、深入地发展运筹学向一些新的研究领域发展运筹学分散融于其他学科，并结合其他学科一起发展运筹学沿原有的各学科分支向前发展运筹学中建立模型的问题将日益受到重视运筹学的发展将进一步依赖于计算机的应用和发展,e.g.1 婚姻问题(matching
14、problem),女儿,追求者,A,B,C,E,D,F,3,27,1,5,10,4,26,28,共有3!=6种可能,得到分配矩阵：,如何嫁娶，使获得的礼品最多？,7,8 运筹学的例子,贪婪（Greedy)解一般不会产生最差解；,在某些模型中，贪婪算法能得到最优解；,.可以使用穷举法，但是以时间为代价,贪婪解的结果：28+5+1=34,最优解的结果：27+4+26=57,Note：,最差解的结果：3+10+7=20,e.g.2 阿克米自行车的装配问题,由两名熟练工人进行装配，要求装完时间最早。,0 2 5 7 8 9 1516 23 31,P1,P2,A,B,C,E,F,G,H,I,J,D,如果
15、每道工序的加工时间减少1，最优时间表会小于31吗？,0 1 3 4 5 7 13 20 27,A,B,J,D,C,E,F,G,H,I,P1,P2,最优耽搁排序,A,B,C,D,E,F,G,H,I,J,0 1 3 4 5 7 1213 18 20 32,P1,P2,最优无耽搁排序,忙碌规则：凡有工作可做就不能闲着,如果加工时间不变而增加一个装配工人，最优时间表会小于31吗？,最优耽搁排序,0 2 4 5 6 8 12 1415 22 30,P1,P2,P3,A,D,F,G,E,C,H,B,I,J,最优无耽搁排序,0 2 4 5 6 8 1415 21 36,P1,P2,P3,A,D,E,F,G,
16、H,I,B,C,J,旅行商问题,（Traveling Salesman Problem）,共有（n-1)!种可能,TSP,有一位旅行售货员要到城市 进行商品销售，已知：的距离为他从 n 个城市的某个城市出发，去每个城市一次且仅一次（在欧氏距离下）回到出发的城市。问应如何计划他的旅行路线，使他所走的路线总长度最短？,设有n个城市（有向图）则有（n-1）！种可能方案。以计算机1秒可以完成24个城市所有路径枚举为单位，则,1s,24s,10min,4.3h,4.9d,136.5d,10.8y,325y,若没有现成可直接应用的计算机程序，则需要以下两步工作：计算手段的拟定。在模型研制的同时，需要研究如
17、何用数值方法求解模型。其中包括对问题变量性质(确定性、随机性、模糊性)、关系特征(线性，非线性)、手段(模拟，优化)及使用方法(现有的，新构造的)等的确定；程序明细表的编制。程序设计和调试。对于计算过程需要编制程序来实现计算机运算，运算学研究应包含算法过程的描述，计算流程框图绘制。程序的实现及调试可以交由程序员完成，或会同程序员完成。,(1)直接分析方法。当我们对问题的内在关系、特征等比较熟悉时，可以根据对问题内在机理的认识直接构造出模型。运筹学中已有不少现存的模型，如线性规划模型、投入产出模型、排队模型、存贮模型、决策和对策模型等等。这些模型都有很好的求解方法及求解的软件。有时模型的参数也可
18、直接从问题本身得到。,(2)类比方法。通过对问题的深入分析，结合经验，常常会发现有些模型的结构性质是类同的。这就可以互相类比，通过类比把新遇到的问题用已知类似问题的模型来建立该问题模型。这种情况往往得到的是模型归类，而模型参数需用其它的方法取得。,(3)数据分析法。利用数据处理的方法分析各数据变量之间的关系是确定关系，还是相关关系，以及是何种相关等。这种方法还可以用回归分析找出变量的变化趋势，从而得到合理的数学模型。大量的模型参数求得也常常使用数据处理的统计方法。另外，回归模型常常就是一个无约束最优化模型。,(4)试验分析法。通过试验分析建模是工程管理中常用的方法。这类方法是以局部的试验产生数据，经过统计处理得到总体的模型或模型归类。试验分析更多地用于产生模型参数。,(5)构想法。当有些问题的机理不清，既缺少数据，又不能作试验来获得数据时，例如一些社会、经济、军事问题等。这种情况下，人们只能在已有的知识、经验和某些研究的基础上，对于将来可能发生的情况给出逻辑上合理的设想和描述，然后用已有的方法构造模型，并不断修正完善，直至比较满意为止。这种方法基于人们的构想。,第一章结束,
