[运筹学]运筹学学习课件概述.ppt.ppt

1运运筹筹学学2什么是运筹学??主要用数学的方法研究各种系统的优化途径及方案,为决策者提供科学决策的依据。?Operation Research ,OR?主要研究对象:主要为各种有组织系统的管理问题及其生产经营活动?主要研究方法:定量化和模型化方法?目的:针对所研究的系统,求得一个合理运用人力、物力和财力的最佳方案,发挥和提高系统的效能和效益,最终达到系统的最优目标。3历史上运筹学的运用?我国:战国时代齐王与田忌赛马?国外:1736年欧拉解决哥尼斯堡七桥问题4齐王与田忌赛马《史记》中有这样一个故事:有一天,齐王要田忌和他赛马,规定每个人从自己的上、中、下三等马中各选一匹来赛;并规定,每次有一匹马来比赛;并约定,每有一匹马取胜可获千两黄金,每有一匹马落后要付千两黄金。当时,齐王的每一等次的马比田忌同样等次的马都要强,因而,如果田忌用自己的上等马与齐王的上等马比,用自己的中等马与齐王的中等马比,用自己的下等马与齐王的下等马比,则田忌要输三次,因而要输黄金三千两。但是结果,田忌没有输,反而赢了一千两黄金。这是怎么回事呢?5在赛马之前,田忌的谋士孙膑给他出了一个主意,让田忌用自己的下等马去与齐王的上等马比,用自己的上等马与齐王的中等马比,用自己的中等马与齐王的下等马比。田忌的下等马当然会输,但是上等马和中等马都赢了。因而田忌不仅没有输掉黄金三千两,还赢了黄金一千两。问题表明,在有双方参加的竞赛或斗争中,策略是很重要的。采用的策略适当,就有可能在似乎一定会失败的情况下取得胜利的结果。研究这种竞赛策略的数学分支,叫作博奕论,也叫对策论;是运筹学的重要分支。6历史上运筹学的运用?我国:战国时代齐王与田忌赛马?国外:1736年欧拉解决哥尼斯堡七桥问题7哥尼斯堡七桥问题濒临蓝色的波罗的海,有一座古老而美丽的城市,叫做哥尼斯堡(今俄罗斯加里宁格勒)。布勒格尔河的两条支流在这里汇合,然后横贯全城,流入大海。河心有一个小岛。河水把城市分成了4块,于是,人们建造了7座各具特色的桥,把哥尼斯堡连成一体。一天又一天,7座桥上走过了无数的行人。不知从什么时候起,脚下的桥梁触发了人们的灵感,一个有趣的问题在居民中传开了:谁能够一次走遍所有的7座桥,而且每座桥都只通过一次?这个问题似乎不难,谁都乐意用它来测试一下自己的智力。可是,谁也没有找到一条这样的路线。连以博学著称的大学教授们,也感到一筹莫展。“七桥问题”难住了哥尼斯堡的所有居民。哥尼斯堡也因“七桥问题”而出了名。8七桥问题的形象描述城市分割成4个区域:河的两岸(A和B),河中的岛(C)和两条支流之间的半岛(D)。七座桥横跨普勒格尔河及其支流,把河岸、半岛和河心岛连接起来。9欧拉的解题思路当时的大数学家欧拉没有亲自去哥尼斯堡测试可能的路线。事实上,如果沿着所有可能的路线都走一次的话,一共要走5040次。就算是一天走一次,也需要13年多的时间,。10欧拉的解题思路 1、建立模型:首先把哥尼斯堡的4个区域分别用点A、B、C、D表示,每座连接两个区域的桥用相应两点的连线a、b、c、d、e、f、g表示,即把哥尼斯堡七桥的情景转化为一个图。