《运用图论理论优化运输方案毕业设计论文》由会员分享，可在线阅读，更多相关《运用图论理论优化运输方案毕业设计论文（22页珍藏版）》请在金锄头文库上搜索。
1、毕业设计论文运用图论理论优化运输方案第一章 引言1第二章 最小费用最大流的求解原理22.1流、割等基本概念和记号22.1.1网络图基本定义22.1.2可行流与最大流22.1.3增广路32.2最大流与最小割的求解42.2.1求最大流和最小割的思路42.2.2用标记法求最大流和最小割52.3最小费用最大流的理论思想62.3.1计算方法62.3.2计算步骤7第三章 最小费用最大流理论的两个应用83.1出土石料运输问题83.1.1求最大流和最小割93.1.2最小费用最大流运输方案的设计103.2防洪物资运输问题133.2.1防洪物资运输模型的建立133.2.2防洪物资运输模型的求解143.2.3具体实
2、例15第四章 总结18参考文献19致 谢20 第一章 引言随着科学技术的发展,科学的管理越来越有必要.在经济管理、交通运输、工农业生产等经济活动中,提高经济效益是人们不可缺少的要求.而提高经济效果一种途径就是生产组织与计划的改进,即合理安排人力物力资源.要达到这样的要求,图论理论作为一种辅助人们进行科学管理的数学方法被越来越广泛的应用.图论(Graph theory)是数学的一个分支,它以图为研究对象.图论中的图是由若干给定的点以及连接两点的线所构成的图形,这种图形通常被用来描述某些事物之间的某种特定关系,用点代表事物,用连接两点的线表示相应的两个事物间具有这种关系.图论本身是应用数学的一部分
3、.因此,图论问题曾经被历史上许多位数学家独立的研究过.关于图论的文字记载最早出现在欧拉1736年的论述中.图论研究的问题大都具有很强的实际背景.本文研究的运用图论理论优化运输方案,就是图论的应用问题的研究之一,对现实生活中的运输问题具有很好的指导意义.本文运用图论理论对车辆流问题抽象和形式化,在线路连接有向图的基础上,建立数学模型,并运用最大流和最小割基本理论对具体问题进行求解.在文章中首先引入流、割等概念与网络图知识点的基本定义,对最大流与最小割基本理论和基本思想进行了概述,并结合实例对车辆流向问题抽象和形式化,建立以线路连接的有向图.在网络图中求出最大流和最小割,用最大流验证能否满足施工需
4、要,用最小割为在割集弧上采取开拓、加宽等措施以加大容量,提高全运输线路上的流量.再着重介绍最小费用最大流的理论思想,包括它的计算方法和算法步骤.接着把最小费用最大流理论应用到实际应用问题中,解决出土石料运输问题和防洪物资运输问题,求解给出合理的运输方案.此方法理论上严密、解题步骤直观清晰、适用性强,对公路、水路、铁路等运输系统有普遍意义.最后本文对应用图论理论优化运输方案的方法给予总结,并研究运用图论理论优化运输方案的优缺点,尝试对该结果进行推广、延展. 第二章 最小费用最大流的求解原理2.1流、割等基本概念和记号2.1.1网络图基本定义我们记网络,其中,为图中所有的顶点集;为弧集;为各弧上容
5、量集或.在中,称为发点,称为收点,其他点称为中间点.在上的一个函数是上的流,并称为弧上的容量,简记为.2.1.2可行流与最大流满足下列两个条件的流称为可行流: 1. 容量限制:对于,有; 2. 平衡条件: (1) 对于发点: (2.1.1) 其中 (2) 对于中间点: (2.1.2) 其中(3) 对于收点: (2.1.3) 其中上述公式中是与,相关联的任一顶点;称为可行流流量,即发点净输出方量,或者称收点净输入方量.求最大流就是求一个流,使其流量最大,且满足 (2.1.4) 其中,.2.1.3增广路1. 给定可行流规定:的弧为饱和弧;的弧为零流弧;的弧为非饱和弧;的弧为非零流弧.2. 定义是方
6、向自到的一条通路:与方向一致的弧称为前向弧,与方向相反的弧称为后向弧.3. 可增广路的定义:对于一个可行流,若满足则称为关于的可增广路(链),否则称为不可增广路.2.1.4割从网络中分离发点和收点的一个弧的集合称为的一个割.或者更直观的说割是网络从到的必经之路.因此割集中弧的容量大小对全网络的流量起到至关重要的作用.显然易得出:最大流的值不会大于最小割的容量,即 (2.1.5)其中表示割集中弧的容量.为了使全网络流量最大,必须设法利用割集中弧的全部容量,使得: (2.1.6)2.2最大流与最小割的求解为求解文中提出的问题,就是要在网络中求出最大流和最小割,从而用最大流验证能否满足施工需要,用最
7、小割在割集弧上采取开拓、加宽等措施以加大容量,提高全运输线路上的流量.2.2.1求最大流和最小割的思路 先假设网络中的任意可行流,然后自此出发设法逐渐增大流值.如果到中存在一条路,其所有的前向弧未饱和,所有后向弧的流具有正值,此时总有可能使这条路的前向弧的流增加一个正整数,所以后向弧的流减少一个,而且可以同时保持全部弧的流为正值且不超过弧的容量.所以这样不会破坏前面所要求的流的相容条件,同时也不会影响不属于此路的其他弧的流.但是自到的流值则增加了,所以总有可能逐次增加,使得自到的全部路中任何一条路到至少有一个前向弧被饱和或一条后向弧的流为零,变为不可增广路为止.当自到无可增广路时,就不再增大,
8、即达到最大.否则总可以按照上述步骤继续增大,最后求得最大流,最小割的流量满足: (2.1.6)2.2.2用标记法求最大流和最小割确定最大流的标记法分为两个过程:一个是标记过程,二是增长过程.1. 标记过程:标记过程的目的是寻找可增广路,求出最小割. (1) 给标记为,此时称被标记,未检查.其他各点未标记,未检查.其中，第一个记号是代表下标为,即要检查的下标.第二个记号用“+”,“-”是代表:若则记之为“+”;若则记之为“-”.第三个记号则用来表示有关弧上所能增加的流量.(2) 任选一个已标记未检查的顶点,若顶点与相关联,且尚未标记.则当: ,时,将标上,其中,此后称已标记,未检查. 并且时将上
9、,其中此后称已标记,未检查. 与相关联的顶点都被标记后,将的第二个记号“+”或“-”用一个小圆圈圈起来,称已标记且被检查.重复步骤2,直至收点被标记或直至不再有顶点可以被标记.在后者情况下,整个算法结束,在前者的情况下,转向至增广过程.2. 增广过程: 增广过程的目的是使沿可增广路的流量增加. (1) 如果收点的标记为（其中是可增广路前面的一个顶点的脚标)则把增加.如果收点的标记为,则把减小.(2) 在增广路上调整至,则把全部标记去掉,重复标记过程和增广过程.当不再有顶点可以被标记,则此时的可行流便是最大流.同时可以找到最小割集,其中为标号点集合;为未标号点集合;弧集合为最小割集.2.3最小费
10、用最大流的理论思想 运输方案设计所要考虑的不仅仅是取得最大流,而且还要设计出最小费用最大流运输方案才能达到优化的目的. 对于网络,每条弧上,除了给的,还给出了一个单位流量的费用,所谓的最小费用最大流就是要求一个最大流,使得流的总运输费用取得最小值,即:,其中.2.3.1计算方法 求费用为权的赋权图的最短通路与网络中的增广路相对应,当沿着一条关于可行流的可增广路以调整得到可行流时,费用增量为: (2.3.1)称 为增广路的“费用”. 若是流量中所有可行流的费用最小者,而是关于的所有增广路中费用最小的增广路.那么沿着调整,即可得到,就是流量为的所有可行流的最小费用流.这样当为最大流时,即为所求的最
11、小费用最大流. 由于,所以必是流量为0的最小费用流.这样总可以从开始,去寻找关于的最小费用增广路.为此需要构造一个赋权有向图,它的顶点是原网络的顶点,而把中的每一条弧变成两个相反方向的弧和,定义的权为: (2.3.2) (2.3.3) 于是在中寻求关于的最小费用增广路等价于在赋权图中寻求以到的最短路.长度为的弧可以从中略去.2.3.2计算步骤1. 取 = 0;2. 若在第步得到最小费用流,则构造赋权图;3. 在中寻求到的最短路.(1) 若不存在最短路(即最短路权为),则就是最小费用最大流.(2) 若存在最短路,则在原网络中取相对应的增广路,在上对进行调整量为: (2.3.4) 令 (2.3.5
12、)得到新的可行流, 构造赋权有向图,重复上述步骤.第三章 最小费用最大流理论的两个应用3.1出土石料运输问题在一个新的施工工地提出需要的最大土石方量后,在图纸上设计出土石料运输线路,计算各段线路容量,然后计算总的最大流量,以验证是否满足施工需要.为了便于理论探讨.本节把某水利工地地形图上设计的运输线路简化为图1.运料线路自下游料场到坝上有三条,即左岸、中线和右岸.三条线路由于地形条件和维修费用等原因,容量也不尽相同,单位运输费用也不相等.图1中路旁第一个数字是线路容量,用表示,单位是万方;第二个数字是单位方量的运费,包括道路维修费、筑路费、运输费等,用表示,单位是百元.第三个数字是设计者认为可
13、能的流量,用表示.图1 运输线路示意图图1所示的运输图可以抽象为图2的有向网络.图2 有向图网络 3.1.1求最大流和最小割 由图2进行标记过程得图3.由图3进行增广过程,增广路为,得图4.在图4中去掉原标记,重新进行标记.按同样方法进行直至得到图5.经过分析可知图5中不再有可增广路,割集弧如图5虚线所截的饱和弧,被标记点为,未被标记点为;割为:, (3.1.1). (3.1.2)图3 第一次标记过程图图4第二次标记过程图图5 最大流与最小割图 3.1.2最小费用最大流运输方案的设计 对图2取初始可行流,见图6所示.构造赋权有向图,如图7所示.观察可知从到的最短路为,如图7中粗线所示.中与图7
14、中最短路相应的增广路,在上对进行调整,调整流量为,调整后见图8所示.再构造赋权有向图,如图9所示.重复上述步骤直至,如图11所示.图6 赋权图图7 赋权有向图图8 赋权图,图9 赋权有向图图10 赋权图,图11 赋权图图11中已经经过六次调整,为了简单起见,中间几步省略.图中已经不存在到的最短路,所以为最小费用最大流.每日最大上坝土石方量为27万,最小费用为34,000元.按照上述方法求出运输线路通行能力下的最大流量.若能满足施工需求量,按照此运输方案实施.若不能满足,则需要开拓和加大割集路段的容量或再增加路线.本例运输线路中影响提高运输流量的关键路段时前面所分析得到的割集路段.即料场到工程指挥部段,大桥到坝脚段,工人生活区到坝脚段,泄洪口施工
