运用图论理论优化运输方案_设计论文.doc

(此文档为word格式，下载后您可任意编辑修改！) 第一章 引言 1 第二章 最小费用最大流的求解原理 2 2.1流、割等基本概念和记号 2 2.1.1 2 2.1.2可行流与最大流 2 2.1.3增广路 3 2.2最大流与最小割的求解 4 2.2.1求最大流和最小割的思路 4 2.2.2用标记法求最大流和最小割 5 2.3最小费用最大流的理论思想 6 2.3.1计算方法 6 2.3.2计算步骤 7 第三章 最小费用最大流理论的两个应用 8 3.1出土石料运输问题 8 3.1.1求最大流和最小割 9 3.1.2最小费用最大流运输方案的设计 10 3.2防洪物资运输问题 13 3.2.1防洪物资运输模型的建立 13 3.2.2防洪物资运输模型的求解 14 3.2.3具体实例 15 第四章 总结 18 参考文献 19 致 谢 20 第一章 引言 随着科学技术的发展,科学的管理越来越有必要.在经济管理、交通运输、工农业生产等经济活动中,提高经济效益是人们不可缺少的要求而提高经济效果一种途径就是生产组织与计划的改进,即合理安排人力物力资源.要达到这样的要求,作为一种辅助人们进行科学管理的数学方法被越来越广泛的应用2.1流、割等基本概念和记号 2.1.1, 其中,为图中所有的顶点集;为弧集;为各弧上容量集或.在中,称为发点,称为收点,其他点称为中间点.在上的一个函数是上的流,并称为弧上的容量,简记为. 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. 定义是方向自到的一条通路: 与方向一致的弧称为前向弧,与方向相反的弧称为后向弧. 3. 可增广路的定义: 对于一个可行流,若满足 则称为关于的可增广路(链),否则称为不可增广路. 2.1.4割 从网络中分离发点和收点的一个弧的集合称为的一个割.或者更直观的说割是网络从到的必经之路.因此割集中弧的容量大小对全网络的流量起到至关重要的作用.显然易得出:最大流的值不会大于最小割的容量,即 (2.1.5) 其中表示割集中弧的容量. 为了使全网络流量最大,必须设法利用割集中弧的全部容量,使得: (2.1.6) 2.2最大流与最小割的求解 为求解文中提出的问题,就是要在网络中求出最大流和最小割,从而用最大流验证能否满足施工需要,用最小割在割集弧上采取开拓、加宽等措施以加大容量,提高全运输线路上的流量. 2.2.1求最大流和最小割的思路 先假设网络中的任意可行流,然后自此出发设法逐渐增大流值.如果到中存在一条路,其所有的前向弧未饱和,所有后向弧的流具有正值,此时总有可能使这条路的前向弧的流增加一个正整数,所以后向弧的流减少一个,而且可以同时保持全部弧的流为正值且不超过弧的容量.所以这样不会破坏前面所要求的流的相容条件,同时也不会影响不属于此路的其他弧的流.但是自到的流值则增加了,所以总有可能逐次增加,使得自到的全部路中任何一条路到至少有一个前向弧被饱和或一条后向弧的流为零,变为不可增广路为止.当自到无可增广路时,就不再增大,即达到最大.否则总可以按照上述步骤继续增大,最后求得最大流,最小割的流量满足: (2.1.6) 2.2.2用标记法求最大流和最小割 确定最大流的标记法分为两个过程:一个是标记过程,二是增长过程. 1. 标记过程: 标记过程的目的是寻找可增广路,求出最小割. (1) 给标记为,此时称被标记,未检查.其他各点未标记,未检查.其中，第一个记号是代表下标为,即要检查的下标.第二个记号用“+”,“-”是代表:若则记之为“+”;若则记之为“-”.第三个记号则用来表示有关弧上所能增加的流量. (2) 任选一个已标记未检查的顶点,若顶点与相关联,且尚未标记.则当: ① ,时,将标上,其中,此后称已标记,未检查.