运用图论理论优化运输方案_毕业论文(编辑修改稿)

运用图论理论优化运输方案_毕业论文(编辑修改稿)内容摘要：

当 : ① (, )i j A , ( ) ( )c i, j f i, j 时 ,将 j 标上 ( ( ))i, ,ε j ,其中 ( ) m i n ( ) , ( , ) ( , )j i c i j f i j,此后称 j 已标记 ,未检查 . ② ( , )j i A 并且 ( , ) 0f j i  时将 j 上 ( ,, ( ))ij ,其中  ( ) m in ( ), ( , )j i f j i此后称 j 已标记 ,未检查 . ③ 与 i 相关联的顶点都被标记后 ,将 i 的第二个记号“ +”或“ ”用一个小圆圈圈起来 ,称 i 已标记且被检查 .重复步骤 2,直至收点 tv 被标记或直至不再有顶点可以被标记 .在后者情况下 ,整个 算法结束 ,在前者的情况下 ,转向至增广过程 . 2. 增广过程 : 增广过程的目的是使沿可增广路的流量增加 . (1) 如果收点 tv 的标记为 ()q, ,ε （其中 q 是可增广路 tv 前面的一个顶点的 脚标 )则把 ()tf q,v 增加  .如果收点 tv 的标记为 ( ,, )q  ,则把 ( , )tf qv 减小  . (2) 在增广路上调整至 svq ,则把全部标记去掉 ,重复标记过程和增广过程 . 6 当不再有顶点可以被标记 ,则此时的可行流便是最大流 .同时可以找到最小割集11( , )vv ,其中 1v 为标号点集合。 1v 为未标号点集合。 弧集合 11( , )vv 为最小割集 . 最小费用最大流的理论思想 运输方案设计所要考虑的不仅仅是取得最大流 ,而且还要设计出最小费用最大流运输方案才能达到优化的目的 . 对于网络 ( , , )D V A C ,每条弧 ()ijv,v A 上 ,除了给的 ijc ,还给出 了一个单位流量的费用 ijb ,所谓的最小费用最大流 9 就是要求一个最大流 f ,使得流的总运输费用取得最小值 ,即 : () ij ijb f b f ,其中 ()ijv,v A . 计算方法 求费用 ijb 为权的赋权图的最 短通路与网络 D 中的增广路 u 相对应 ,当沿着一条关于可行流 f 的可增广路 u 以 1 调整 f 得到可行流 f 时 ,费用增量为 : u u u ub ( ) b ( ) ( ) ( )i j i j i j i j i j i j i j i jf f b f f b f f b b          ,10 () 称   u u ijij bb 为增广路 u 的“费用” . 若 f 是流量 ()vf中所有可行流的费用最小者 ,而 u 是关于 f 的所有增广路中费用最小的增广路 .那么沿着 u 调整 f ,即可得到 f ,就是流量为 ()vf 的所有可行流的最小费用流 .这样当 f 为最大流时 ,即为所求的最小费用最大流 . 由于 0ijb ,所以 0f 必是流量为 0 的最小费用流 .这样总可以从 0f 开始 ,去寻找关于 f 的最小费用增广路 .为此需要构造一个赋权有向图 ()wf ,它的顶点是原网络的顶点 ,而把 D 中的每一条弧 ( , )ijvv 变成两个相反方向的弧 ( , )ijvv 和( , )jivv ,定义 ()wf 的权 ijw 为 : 7。 ,   ijijijijijji cf cfbw ()    .00, ijijijij ffbw () 于是在 D 中寻求关于 f 的最小费用增广路等价于在赋权图 ()wf 中寻求以 sv到 tv 的最短路 .长度为  的弧可以从 ()wf 中略去 . 计算步骤 1. 取 )0(f = 0。 2. 若在第 1k 步得到最小费用流 )1k(f ,则构造赋权图 ( 1)()kwf。 3. 在 ( 1)()kwf 中寻求 sv 到 tv 的最短路 . (1) 若不存在最短路 (即最短路权为 ),则 )1k(f 就是最小费用最大流 . (2) 若存在最短路 ,则在原网络 D 中取相对应的增广路 u ,在 u 上对 )1k(f 进行调整量为 : ) ) ,(m in),(m inm in ( )1()1(   kijukijiju ffc () 令.),(),(),()1()1()1()(uvvfuvvfuvvffjikijjikijjikijkij  () 得到新的可行流 )k(f , 构造赋权有向图 ()kwf ,重复上述步骤 . 8 第三章 最小费用最大流理论的两个应用 出土石料运输问题 在一个新的施工工地提出需要的最大土石方量后 ,在图纸上设计出土石料运输线路 ,计算各段线路容量 ,然后计算总的最大流量 ,以验证是否满足施工需要 .为了便于理论探讨 .本节把某水利工地地形图上设计的运输线路简化为图 路自下游料场到坝上有三条 ,即左岸、中线和右岸 .三条线路由于地形条件和维修费用等原因 ,容量也不尽相同 ,单位运输费用也不相等 .图 1 中路旁第一个数字是线路容量 ,用 ijc 表示 ,单位是万方。 第二个数字是单位方量的运费 ,包括道路维修费、筑路费、运输费等 ,用 ijb 表示 ,单位是百元 .第三个数字是设计者认为可能的流量 ,用ijf 表示 . 图 1 运输线路示意图 图 1 所示的运输图可以抽象为图 2 的有向网络 D . 图 2 有向图 网络 D 9 求最大流和最小割 由图 2 进行标记过程得图 3 进行增广过程 ,增广路 9 为 14( , , , )stv v v v , 4 ,得图 4 中去掉原标记 ,重新进行标记 .按同样方法进行直至得到图 析可知图 5中不再有可增广路 ,割集弧如图 5虚线所截的饱和弧 ,被标记点为 2 3 5( , , , )sv v v v ,未被标记点为 1 4 6( , , , )tv v v v。 割为 :  1 1 1 3 6 2 6 5( , ) ( , ) , ( , ) , ( , ) , ( , )stv v v v v v v v v v ,。