运筹学之总论(胡运权版)

《运筹学之总论(胡运权版)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、运筹学主讲人：叶娟juanym@126.com1什么是运筹学？主要用数学的方法研究各种系统的优化途径及方案，为决策者提供科学决策的依据。OperationResearch，OR主要研究对象：主要为各种有组织系统的管理问题及其生产经营活动主要研究方法：定量化和模型化方法目的：针对所研究的系统，求得一个合理运用人力、物力和财力的最佳方案，发挥和提高系统的效能和效益，最终达到系统的最优目标。2历史上运筹学的运用我国：战国时代齐王与田忌赛马国外：1736年欧拉解决哥尼斯堡七桥问题3齐王与田忌赛马《史记》中有这样一个故事：有一天，

2、齐王要田忌和他赛马，规定每个人从自己的上、中、下三等马中各选一匹来赛；并规定，每次有一匹马来比赛；并约定，每有一匹马取胜可获千两黄金，每有一匹马落后要付千两黄金。当时，齐王的每一等次的马比田忌同样等次的马都要强，因而，如果田忌用自己的上等马与齐王的上等马比，用自己的中等马与齐王的中等马比，用自己的下等马与齐王的下等马比，则田忌要输三次，因而要输黄金三千两。但是结果，田忌没有输，反而赢了一千两黄金。这是怎么回事呢？4在赛马之前，田忌的谋士孙膑给他出了一个主意，让田忌用自己的下等马去与齐王的上等马比，用自己的上等马与齐王的中

3、等马比，用自己的中等马与齐王的下等马比。田忌的下等马当然会输，但是上等马和中等马都赢了。因而田忌不仅没有输掉黄金三千两，还赢了黄金一千两。问题表明，在有双方参加的竞赛或斗争中，策略是很重要的。采用的策略适当，就有可能在似乎一定会失败的情况下取得胜利的结果。研究这种竞赛策略的数学分支，叫作博奕论，也叫对策论；是运筹学的重要分支。5历史上运筹学的运用我国：战国时代齐王与田忌赛马国外：1736年欧拉解决哥尼斯堡七桥问题6哥尼斯堡七桥问题濒临蓝色的波罗的海，有一座古老而美丽的城市，叫做哥尼斯堡（今俄罗斯加里宁格勒）。布勒格尔河

4、的两条支流在这里汇合，然后横贯全城，流入大海。河心有一个小岛。河水把城市分成了４块，于是，人们建造了７座各具特色的桥，把哥尼斯堡连成一体。一天又一天，７座桥上走过了无数的行人。不知从什么时候起，脚下的桥梁触发了人们的灵感，一个有趣的问题在居民中传开了：谁能够一次走遍所有的７座桥，而且每座桥都只通过一次？这个问题似乎不难，谁都乐意用它来测试一下自己的智力。可是，谁也没有找到一条这样的路线。连以博学著称的大学教授们，也感到一筹莫展。“七桥问题”难住了哥尼斯堡的所有居民。哥尼斯堡也因“七桥问题”而出了名。7七桥问题的形象描述城

5、市分割成4个区域：河的两岸（A和B），河中的岛（C）和两条支流之间的半岛（D）。七座桥横跨普勒格尔河及其支流，把河岸、半岛和河心岛连接起来。8欧拉的解题思路当时的大数学家欧拉没有亲自去哥尼斯堡测试可能的路线。事实上，如果沿着所有可能的路线都走一次的话，一共要走5040次。就算是一天走一次，也需要13年多的时间，而实际上．欧拉只用了几天的时间就解决了七桥问题。9欧拉的解题思路1、建立模型：首先把哥尼斯堡的4个区域分别用点A、B、C、D表示，每座连接两个区域的桥用相应两点的连线a、b、c、d、e、f、g表示，即把哥尼斯堡七桥

6、的情景转化为一个图。10欧拉的解题思路2、问题转化：在上图中，从任何一点出发，笔不离纸，但又不能重复任何一条边地画出上图，且起点与终点重合，这样的画法存在吗？（这就是众所周知的“一笔画”游戏）11欧拉的解题思路3、欧拉的结论：七桥问题中要找的那条路线是不存在的。网络能否一笔画出来的关键在于这些点。这些点有两类，如果从一点引出的线是奇数条，就把这个点叫奇点；如果从一点引出的线是偶数条，就把这个点叫偶点。网络中奇点的数是零或二，这个网络就能一笔画出来。由于七桥问题中的四个点都是奇点，按欧拉的规律，这个网络是一笔画不出来的。1

7、2欧拉的研究所涉及的学科图论与网络拓扑学13运筹学学科的形成普遍认为，运筹学作为一门新兴学科起源于二战期间的军事运筹活动。当时英、美都发明和制造了一批新式武器，但如何使用这些武器却远远落后于这些武器的制造。为此，英国军事管理部门召来了一批具有不同学科和专业背景的科学家，在1940年成立了“OR”小组。这标志着世界第一次开始正式的运筹学活动。随后，美国也成立了运筹学小组。这些早期的运筹工作，主要是进行战术评价、战术改进、作战计划、战略选择、改进后勤调度和训练计划等方面的研究。不同学科的相互渗透所产生的协同作用，成功的解决了

8、许多重要的问题，为以后运筹学的发展积累了丰富的经验。14运筹学的特点运筹学作为一门定量决策科学，利用数学、计算机科学与其它科学的新成就，研究各种系统尤其是经济管理中运行的数量化规律，合理使用与统筹安排人力、物力、财力等资源，为决策者提供有依据的最优方案，以实现最有效的管理并获得满意的经济效益和社会效果，就其理论与应用