运用图论理论优化运输方案-毕业设计论文

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元.按照上述方法求出运输线路通行能力下的最大流量.若能满足施工需求量,按照此运输方案实施.若不能满足,则需要开拓和加大割集路段的容量或再增加路线.本例运输线路中影响提高运输流量的关键路段时前面所分析得到的割集路段.即料场到工程指

15、挥部段,大桥到坝脚段,工人生活区到坝脚段,泄洪口施工区到坝上段.要提高土石运输量就要采取措施加大这些段的容量.最优的运输方案,不仅要考虑运输量最大,还要使运输方案整体达到最优,即达到最小费用最大流.本例中最小费用最大流运输方案如图10所示,最大流量为27万/日,最小费用为34,000元.这个运输方案比图5中计算的最大流量每日节约运输费用600元.当然执行这个方案要在原实施基础上对有关路段采取一定的措施.3.2防洪物资运输问题3.2.1防洪物资运输模型的建立防洪物资运输要求在满足各水库防洪物资需求的前提下,以最低的运输费用将尽可能多的防洪物资从各仓库运送到各水库大坝,这要求考虑三个问题:1. 满

16、足各水库大坝的最低物资需求;2. 满足各水库大坝的最低物资需求的前提下将尽可能多的物资从各水库运输到各水库大坝;3. 总运输费用最小.为了更好地处理这三个问题,我们定义两个常量和.为运送单位防洪物资从第仓库到第水库所需要的费用;为运送单位防洪物资从第仓库到第水库运送防洪物资的数量.这样以总运输费用最小和物资运送量最大为目标函数,以各仓库的物资储备量、道路运输能力、各水库大坝所需要的最小物资量为约束条件构造模型如下: (3.2.1)式中为第个仓库的物资储备数量;为第个水库所至少需要的物资量;为从第个仓库到第个水库的道路运输能力.第一个约束条件表示从第个仓库运走的所有物资数量必须小于第个仓库的物资

17、储备量;第二个约束条件表示运输到第个水库的所有物资数量必须大于第个水库的至少需求量;第三个约束条件表示从第个仓库到第个水库的物资运输量必须在道路运输能力范围内.3.2.2防洪物资运输模型的求解最小费用最大流理论的求解过程是对单一源点到单一汇点进行的,防洪物资运输问题涉及到多个储存物资的仓库(源点)和多个需求物资的水库(汇点).这就需要引进点作为单源,引进点作为单汇.规定从点到第个仓库的单位物资运输费用为0;规定从第个水库到点的道路运输能力为,从第个水库到点的道路的单位运输费用为0.这样一来运输的总费用不会变,也可以应用最小费用最大流算法对模型进行求解.求解步骤如下:1. 对于初始可行流,它是运

18、输量为0的最小费用流;2. 记为经过次调整得到的最小费用流,构造赋权有向图;3. 在赋权有向图中寻求从源点到汇点的最小费用路(调用Floyd算法),若不存在最小费用路,则就是最小费用最大运量流,计算终止;若存在最小费用路,则此最小费用路即为原网络中相应的增广链,转入下一步;4. 在增广链上对进行调整,调整量为: , (3.2.2)令 . (3.2.3)得到新的可行流, 使流值增大,令,返回到第(2)步骤.模型求解流程如图12所示.图12 模型求解过程3.2.3具体实例桃曲坡水库、玉皇阁水库和高尔塬水库都位于渭河的支流上,古城西安的上游.这3座水库尤其是桃曲坡水库的防洪对西安的安全有着很大的影响

19、,每逢汛期,都会有大量的防汛物资从附近的仓库运送到这3座水库,研究这3座水库的防汛物资运输问题对实际运输的有很大的指导作用.3座水库的最低防洪物资需求量为:桃曲坡,230;高尔塬,190;玉皇阁,110.这附近有7个仓库，每个仓库的物资储备量和从某座仓库运输物资到某座水库的单位运输费用见表1.将表1中的信息网络化,将得到图13,分别代表仓库:马栏、庙湾、瑶曲、柳林、石门关、青草坪、石柱;,分别代表水库桃曲坡、玉皇阁和高尔塬;每条弧上的标注为,代表从到点的道路运输能力(即为第仓库的物资储备量);为从到点的单位物资运输费用.表1 单位物资运费图13 运输网络示意图建立物资运输模型: 式中为总运输费

20、用;代表道路运输流量.的值分别为:90,80,110,105,95,115,95;,的值分别为:230,190,110;,的值见图13中的线上的标注.对模型根据最小费用最大流的求解步骤进行求解，结果见表2(表中物资运输流量表示从各仓库到各水库的防洪物资数量，单位为).表2 运输计算结果计算结果为,满足各水库最低物资需求量的运输方案,总运输费用为54650元.最小费用最大流理论可以求解出任意的对应于某个最低运输量的运输方案,即只要给定每座水库的最低需求量,就可以根据最小费用最大流理论求解出在这个最低运输量限制下的运输方案.实际中可以根据汛情的变化,随时改变每座水库的最低需求量,改变运输方案.第四

21、章 总结最小费用最大流理论在网络优化模型中具有核心位置,因为它不仅具有广泛类型的应用,而且可以被极为有效的求解.与最大流理论相似,它关注的是通过有弧容量限制的网络的流量问题.与最短路径理论相似,它关注的是经过一条弧的流量的费用.事实上,该理论能够研究具有多个发点和多个终点的问题,还考虑费用问题.目的就是在满足给定需求的前提下,使得通过网络发送的有效供给的总成本最小,从而获得最大利益.本文运用图论理论这一数学工具把实际问题抽象为有向网络,进而建立数学模型,并运用最大流和最小割基本理论对具体问题进行求解.在文中引入了流、割等概念与网络图知识点的基本定义,对最大流与最小割基本理论和基本思想进行了概述

22、,并着重介绍了最小费用最大流的理论思想,包括它的计算方法和算法步骤.然后把最小费用最大流理论应用到实际应用问题中,解决出土石料运输问题和防洪物资运输问题,求解给出合理的运输方案.应用图论理论优化运输方案这种方法理论上严密、解题步骤直观清晰、适用性强,该方法同时能够求关键路段,取得最小费用最大运输流量,达到整体最优化.对公路、水路、铁路等其他运输系统有普遍意义.本文考虑的是图论理论在运输问题上的简单的应用.而实际上,也可以应用运筹学中的图论理论原理解决和优化在生活中的其他方面问题,如通信编解码,矩阵运算,任务分配,GPS路径规划等等,这有待于日后对图论理论的继续研究.参考文献1 朱金寿,朱琪,王静.最小费用最大流算法在路径规划中的应用J.湖北:武汉理工大学学报,2002,(3).2 林诒勋.线性规划与网络流M.开封:河南大学出版社,2003.3 钱颂迪.运筹学M.北京:清华大学出版社,1993.4 卢向南,李俊杰,寿涌毅.应用运筹学M.浙江:浙江大学出版社,2005.5 艾素梅,魏文宏,刘力.数学模型的图论方法M.河北:沧州师范专科学校学报,2010,(4).6 杜端甫.运筹图论M.北京:北京航空航天大学出