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