《运筹学论文1汇总》由会员分享，可在线阅读，更多相关《运筹学论文1汇总（4页珍藏版）》请在金锄头文库上搜索。
1、有关运筹学知识的几个简单应用 摘要：运筹学是数学的一大分支，并且在现实生活中有着广泛的应用。本文主要是 利用运筹学中图论中的欧拉回路问题，图的模型建立问题和多人博弈问题加以简单 应用。从而展现运筹学独特的应用魅力.关键词：运筹学 欧拉回路 图的模型建立 多人博弈运筹学是管理类专业的一门重要专业基础课。它是本世纪40年代初发展起来的一门新兴学科，其主要目的是在决策时为管理人员提供科学依据，是实现有效管理、 正确决策和现代化管理的重要方法之一。运筹学的具体内容包括：规划论（包括线 性规划、非线性规划、整数规划和动态规划）、库存论、图论、决策论、对策论、 排队论、博弈论、可靠性理论等。运筹学知识在日
2、常生活中有很广泛的应用。很多问题都可以利用运筹学的方法加以解决。下面的三个应用即是利用简单的运筹 学方法加以解决的。应用笔画图问题考古人员在希腊进行发掘工作时，使一批奇异的古代遗迹重见天日。他们发现很多 纪念碑的碑文反复出现下面这个有圆和三角形组成的符号（如图1）。这个图可以一笔画出，任何线条都不重复画过两次以上。你知道怎么画吗？解析：一笔画图问题在图论中其实可以归结到欧拉回路问题。可以表述成在一个连 通图中，若存在一条回路，经过每边一次且仅一次，则称这条路为欧拉回路，具有 欧拉回路的图被称为欧拉图。而且在判断一个无向连通图是否是欧拉图时，只要看 该图中是否有奇点（通过该店的边数为奇数个）。首
3、先在图中以AO依次标出十五个顶点（如图2）。然后根据欧拉图的判定定理可以每个定点的边数均为偶数， 即满足欧拉图的条件。下面是具体的画图阶段。具体思路如下：我们其实可以将该图分为三个部分。 ADF孤AKADKM弧 KOAFMO弧OA,这三部分是一个重复过程，只要将其中一个解决就可以了，同时 原图剩下的 EHI可以在处理第一个重复部分的时候同时处理。这样剩下的两块只 要重复 ADF孤AK的画法就可以了。图2具体操作如下: 第一步：画 EHI+AADF孤 AKo 从 A 点出发，A BC E H I EB D EF CA+ 弧 AK,第二步：画 DKM弧 KQ 从 K点出发，K LG- H L M
4、H D G- K+弧 KO 第三步：画 AFMO弧 0A 从 O点出发，O J N-1 J F I M N O+弧 OA 应用二 多叉路口交通灯的管理问题通常在十字交叉路口只需设红、绿两色的交通灯便可以保持正常的交通秩序，而在 多叉路口需设几种颜色的交通灯才能既使车辆相互之间不碰撞，又能到达车辆的最 大流通。假设有如图3所示的五叉路口，其中C和E为单行道，在路口有13条可 行的通路，其中有的可以同时通行，如 AB和iC,而有的不能同时通行，如 EB和AD，那么在路口应如何设置交通灯进行车辆的管理呢？解析：就此问题我们将其转化为 图”来解决。可以将图中的一个顶点表示一条通 路，而通路之间相互矛盾
5、的关系以两个顶点之间的连线表示，所以可以用圆圈表示 五叉路口上的一条通路，两个圆圈之间的连线表示两条通路不能同时通行，这样设 置交通灯问题等价为对图中的顶点染色问题，要求对图上的每个顶点染一种颜色， 并且要求有线相连的两个顶点不能具有相同的颜色，而总的颜色种类应该最少。于 是我们可以得到图4的结果。图4具体操作如下：第一步：先找出所有的通路，有 ABCDE5个顶点，最多可以形成20条通路，由 于C、E是单行道，所以CA、CB、CD、CE、AE、BE、CE都不是通路，所以只 剩下 13 条通路，分别是 AB、AC、AD、BA、BC、BD、DA、DB、DC、EA、EB、EC、ED。在图中用圆圈表示
6、，同时在圆圈上方写上代表的通路，第二步：对有矛盾的通路进行连线。以 AB为例，将AB与其他的通路进行比较， 看两者之间是否存在矛盾，若存在矛盾，即将两者用线连起来。例如AB和AC可以同时保证车辆的安全行驶，所以二者之间不需要连线，而AB和BC之间由于可能出现两车相撞的情况，所以两者直接用线连接。诸如此类，可以将所有的线连 好。第三步：染色。染色的要求是每个顶点染一种颜色，并且有线相连的两个顶点 不能具有相同的颜色，而总的颜色种类应该最少。可以给出如图4的一个染色方案，综上即可以设置4种颜色的交通灯来解决该五叉路口问题。应用三强盗分赃5个海盗抢到了 100颗同样大小且价值连城的宝石，他们决定怎么
7、分。用抽签的方 法决定自己的号码（1，2，3，4，5）。首先由1号提出分配方案，然后5人进行 表决，当且仅当超过半数的人同意时，才能按照他的提案进行分配，否则他会被扔 入大海里喂鲨鱼。如果1号死后，再由2号提出分配方案，然后4人进行表决， 当且仅当超过半数的人同意时，才能按照他的提案进行分配，否则他会和1号一样，被扔到海里喂鲨鱼。其他的分配方法以此类推。因为每个海盗都是很聪明的 人，所以他们会很理智地判断得失，做出选择。他们的判断原则是：保命、尽量多 得宝石、尽量多杀人。解析：这是其实是一个博弈的问题。我们可以用逆向思维的方法来分析这个问题。如果13号强盗都喂了鲨鱼，只剩下 4号和5号，5号一
8、定头反对票让4号喂鲨 鱼，这样他就可以独吞全部金币。所以 4号为了保命只有支持3号让3号活下来 才能保住自己的生命。3号知道了这一点，就会提出（100，0，0）的分配方案， 对4、5号一毛不拔而将全部金币划归己有。因为他知道4号即使是一无所获也会为了保命而透赞成票的。再加上自己的一票，他的方案就会通过的。不过2号推知了 3号的方案，就会提出（98，0，1，1）的分配方案。这样由于4、5号会由 于比3号提出的方案得到更多的金币，而赞成 2号的方案。但是1号洞悉了 2号 的方案后，他会采取（97，0，1，2，0）或（97，0，1，0，2）的方案，即放弃 2号，给3号一个金币，给4号或者5号两个金币
9、。由于1号的方案对于3号、4 号（或5号）来说，相比2号的方案分配时更优。所以他们会投赞成票，再加上 1 号自己的一票。1号的方案就可以通过。所以1号最多能获得97枚金币。分配方 案是（97，0，1，2，0）或（97，0，1，0，2）.三个应用分别从图论中的欧拉回路问题，图论中的图的模型建立和博弈论中的多人 博弈问题出发。重点是在于运筹学方法和思想的运用。可见运筹学思想和方法的掌 握，对于我们发现问题和解决问题的重要性。并且以上也只是运筹学知识的简单的 运用，对于更多高深的知识还是有待于我们的继续探索。参考文献1运筹学教程 第三版胡运权主编p240p2412200个聪明人的逻辑思维游戏p20、p58、p199p2003数据结构C语言版严蔚敏吴伟民编著p3 4百度百科一一运筹学定义
