运筹学概述.ppt

运 筹 学 主讲人：叶娟 juanym@126.com 什么是运筹学？ 主要用数学的方法研究各种系统的优化途径及方案，为决策者提供科学决策的依据。 Operation Research ，OR 主要研究对象：主要为各种有组织系统的管理问题及其生产经营活动 主要研究方法：定量化和模型化方法 目的：针对所研究的系统，求得一个合理运用人力、物力和财力的最佳方案，发挥和提高系统的效能和效益，最终达到系统的最优目标。 历史上运筹学的运用 我国：战国时代 齐王与田忌赛马 国外：1736年欧拉解决 哥尼斯堡七桥问题 齐王与田忌赛马 《史记》中有这样一个故事：有一天，齐王要田忌和他赛马，规定每个人从自己的上、中、下三等马中各选一匹来赛；并规定，每次有一匹马来比赛；并约定，每有一匹马取胜可获千两黄金，每有一匹马落后要付千两黄金。当时，齐王的每一等次的马比田忌同样等次的马都要强，因而，如果田忌用自己的上等马与齐王的上等马比，用自己的中等马与齐王的中等马比，用自己的下等马与齐王的下等马比，则田忌要输三次，因而要输黄金三千两。但是结果，田忌没有输，反而赢了一千两黄金。这是怎么回事呢？　　 在赛马之前，田忌的谋士孙膑给他出了一个主意，让田忌用自己的下等马去与齐王的上等马比，用自己的上等马与齐王的中等马比，用自己的中等马与齐王的下等马比。田忌的下等马当然会输，但是上等马和中等马都赢了。因而田忌不仅没有输掉黄金三千两，还赢了黄金一千两。 　问题表明，在有双方参加的竞赛或斗争中，策略是很重要的。采用的策略适当，就有可能在似乎一定会失败的情况下取得胜利的结果。 研究这种竞赛策略的数学分支，叫作博奕论，也叫对策论；是运筹学的重要分支。 　 历史上运筹学的运用 我国：战国时代 齐王与田忌赛马 国外：1736年欧拉解决 哥尼斯堡七桥问题 哥尼斯堡七桥问题 濒临蓝色的波罗的海，有一座古老而美丽的城市，叫做哥尼斯堡（今俄罗斯加里宁格勒）。 布勒格尔河的两条支流在这里汇合，然后横贯全城，流入大海。河心有一个小岛。河水把城市分成了４块，于是，人们建造了７座各具特色的桥，把哥尼斯堡连成一体。 一天又一天，７座桥上走过了无数的行人。不知从什么时候起，脚下的桥梁触发了人们的灵感，一个有趣的问题在居民中传开了： 谁能够一次走遍所有的７座桥，而且每座桥都只通过一次？ 这个问题似乎不难，谁都乐意用它来测试一下自己的智力。可是，谁也没有找到一条这样的路线。连以博学著称的大学教授们，也感到一筹莫展。“七桥问题”难住了哥尼斯堡的所有居民。哥尼斯堡也因“七桥问题”而出了名。 七桥问题的形象描述 城市分割成4个区域： 河的两岸（A和B），河 中的岛（C）和两条支流 之间的半岛（D）。七座 桥横跨普勒格尔河及其支 流，把河岸、半岛和河心 岛连接起来。 欧拉的解题思路 当时的大数学家欧拉没有亲自去哥尼斯堡 测试可能的路线 。事实上，如果沿着所有可能的路线都走一次的话，一共要走5040次。就算是一天走一次，也需要13年多的时间，而实际上．欧拉只用了几天的时间就解决了七桥问题。 欧拉的解题思路 ?? 1、建立模型： ??? 首先把哥尼斯堡的4个 区域分别用点A、B、C、D 表示，每座连接两个区域的 桥用相应两点的连线a、b、 c、d、e、f、g表示，即把哥 尼斯堡七桥的情景转化为一 个图。 欧拉的解题思路 2、问题转化：在上图中，从任何一点出发，笔不离纸，但又不能重复任何一条边地画出上图，且起点与终点重合，这样的画法存在吗？（这就是众所周知的“一笔画”游戏） ?? 欧拉的解题思路 3、欧拉的结论： 七桥问题中要找的那条路线是不存在的。 ??? 网络能否一笔画出来的关键在于这些点。这些点有两类，如果从一点引出的线是奇数条，就把这个点叫奇点；如果从一点引出的线是偶数条，就把这个点叫偶点。网络中奇点的数是零或二，这个网络就能一笔画出来。 　由于七桥问题中的四个点都是奇点，按欧拉的规律，这个网络是一笔画不出来的。 欧拉的研究所涉及的学科 图论与网络 拓扑学 运筹学学科的形成 普遍认为，运筹学作为一门新兴学科起源于二战期间的军事运筹活动。当时英、美都发明和制造了一批新式武器，但如何使用这些武器却远远落后于这些武器的制造。为此，英国军事管理部门召来了一批具有不同学科和专业背景的科学家，在1940年成立了“OR”小组。这标志着世界第一次开始正式的运筹学活动。随后，美国也成立了运筹学小组。这些早期的运筹工作，主要是进行战术评价、战术改进、作战计划、战略选择、改进后勤