运筹学论文1总结

迎新

摘要：运筹学是数学的一大分支，在现实生活中得到了广泛的应用。 本文主要利用运筹学中图论的欧拉回路问题、图的模型建立问题和多人博弈问题进行简单应用。 展现运筹学独特的应用魅力。 关键词：建立运筹学欧拉电路图模型制作多人游戏

运筹学是管理类专业的一门重要的专业基础课。 它是20世纪40年代初发展起来的新兴学科，其主要目的是为管理者提供科学依据，是实现有效管理、正确决策、现代化管理的重要途径之一。 运筹学的具体内容包括：规划论(包括线性规划、非线性规划、整数规划和动态规划)、库存论、图论、决策论、对策论、排队论、博弈论、可靠性理论等。 运筹学知识在日常生活中得到了广泛的应用。 很多问题可以用运筹学的方法解决。 以下三个应用是用简单的运筹学方法解决的。 当考古学家应用一笔带过的问题在希腊进行挖掘工作时，一个奇怪的古代遗迹重见天日。 他们发现许多纪念碑的碑文上反复出现以下由圆和三角形组成的符号(图1 )。 这幅图可以一笔画画，任何一条线都不会重叠画两次以上。 你知道怎么画画吗？

图1

解析：一笔写的问题在图论中可以归结为欧拉回路问题。 在一个连通图中，当存在一个回路，在每边通过一次，并且只通过一次时，可以把这条路称为欧拉回路，把具有欧拉回路的图称为欧拉图。 并且，在判断一个有向连通图是否是欧拉图时，只需看该图是否有特异点(通过该店的边的数量为奇数个)。 首先，在图中按照a￣o的顺序绘制15个顶点(图2 )。 然后根据欧拉图的判定定理，各定点的边数可以满足偶数，即欧拉图的条件。 接下来是具体的绘画阶段。 具体想法如下。 我们其实可以把这张图分成三个部分。 ADF弧AK、DKM弧KO、FMO弧OA、这三个部分是重复过程，只要解决某一个即可。 另外，原图中剩下的EHI在处理最初的重复部分时可以同时处理。

职教在线

具体操作如下。

绘制步骤EHI ADF弧AK。 从a点出发，画出a-B-C-E-I-E-D-E-F-C-A弧AK，第二步：DKM弧KO，从k点出发，画出k-L-g-H-L-M-M 只需设置绿色双色信号灯就能保持正常的交通秩序，但在多路口需要设置几种颜色的信号灯才能在车辆之间不发生碰撞的情况下达到车辆的最大流通。 如果有如图3所示的五叉路口，其中C和e是单向通行，路口有13条可行的通道，其中有像AB和EC这样可以同时通行的，也有像EB和AD这样不能同时通行的，那么在路口设置红绿灯图3

分析：将此问题转换为“图”解决。 图中一个顶点表示一个通道，通道之间的矛盾关系可以用连接两个顶点的线来表示。 因此，用圆圈表示五叉路的一个通道，连接两个圆圈之间的线可以表示两条通道不能同时通行。 这样设置信号灯的问题与图中顶点的染色问题是等价的，要求图中的每个顶点都染上一种颜色，要求由有线连接的两个顶点具有相同的颜色，总颜色的种类必须最少。 然后，得到图4的结果。 图4具体操作如下。

第一步：首先找出所有的通道。 有ABCDE5的5个顶点，最多可以形成20条通路。 由于C、e是单向行驶，所以CA、CB、CD、CE、AE、BE、CE不是通道，所以只剩下13条通道。 分别是AB、AC、AD、BA、BC、BD。在图中用圆圈表示，同时在圆圈上写上代表的通信，步骤2 :连接有矛盾的通信。 以AB为例，比较AB和其他通道，看两者之间有无矛盾，有矛盾时，用线连接两者。 例如，AB和AC可以同时保证车辆的安全行驶，所以不需要连接在两者之间，但由于AB和BC之间可能会发生车辆碰撞，所以两者通过直接线连接。 这样，所有的线都可以连接起来。 第三步：染色。 染色的要求是每个顶点染一种颜色。 此外，由有线连接的两个顶点不能具有相同的颜色。 另外，总颜色的种类必须最少。 可以给出如图4所示的一个染色方案。 也就是说，可以设置4色信号灯来解决这个五叉路口的问题。

江苏教育信息化

解析：这其实是游戏的问题。 我们可以用逆向思维的方法分析这个问题。 如果1~3号强盗喂了鲨鱼，就只剩下4号和5号了。 5号一定会投反对票，让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号两个金币。 因为第一个方案对3号、4号或5号来说，在分配时比第二个方案优越。 所以他们投了赞成票，加一天投自己的一票。 1号方案可以通过。 所以一天最多可以得到97枚金币。 三个应用分别从图论中的欧拉回路问题、图论中的图的模型建立和博弈论中的多人问题出发。 重点是运筹学方法和思想的运用。 可见掌握运筹学的思想和方法对我们发现问题、解决问题的重要性。 而且，这些只是运筹学知识的简单运用，关于更多的高级知识，还有待于我们的继续探索。 参考文献

1 《运筹学教程》第三版胡运权主编p240~p2412 《200个聪明人的逻辑思维游戏》 p20、p58、p199~p2003 《数据结构 C语言版》严蔚敏吴伟民编著p34百度百科- -运筹学定义