现代物流学-第34部分

快捷操作: 按键盘上方向键 ← 或 → 可快速上下翻页 按键盘上的 Enter 键可回到本书目录页 按键盘上方向键 ↑ 可回到本页顶部! 如果本书没有阅读完，想下次继续接着阅读，可使用上方 "收藏到我的浏览器" 功能 和 "加入书签" 功能！


对于包含n个顶点V1，V2。。。；Vn的网络流，V　1为发点，Vn为收点，各段弧（V　i；Vj）上容量为　
Cij，设｛Xij｝是一个可行流，如果存在一条从V1到Vn的路线，这条路线具有以下特点：　

（1）所有正向弧（弧的方向与流向一致）上　Xij0。
则称此条路线为可行流｛Xij｝的一个增广链，记　
ε1=min｛cij…xij｜　当（v　i；vj）为正向弧｝　


（12。8）　
ε2=min｛xij｜　当　（v　i；vj）为反向弧｝　（12。10）　
ε=min｛ε1；　ε2｝　（12。11）
由增广链的特点可知ε》0；按如下公式调整可行流｛x　ij｝为｛x　’ij｝：　
当（vi；vj）是增广链的正向弧　


当（vi；vj）是增广链的反向弧　（12。12）　

当（vi；vj）不在增广链上　


V3　

V5　

12…13　



。x　
＋ε

ij　
x'ij　
=　
。。
xij　
。ε　
。


。　
xij　


显然；此时｛x’ij｝仍为可行流；且它的值比｛x　ij｝增加了ε。　

由此不难看出；对于可行流｛x　ij｝；判断它是否最大流及对它进行调整；关键在于求出其增
广链；标号法就是基于此来寻求最大流的；其具体步骤如下：　

　第1步　给发点以标号（0；＋）　

　第2步设v　i已经有了标号；与v　i相邻的点vj尚未标号。若在弧（v　i；vj）上；　x　ij0；则给v　j以标号（i；…）。继续这个步骤，直到给收点v　n以
标号为止。　

第3步利用“反向追踪”，找出v　1到vn的增广链，例如设v　n的标号为（k；＋），则在增广
链上vn前面的一点为v　k；且弧（vk；vn）是正向弧，接下来检查v　k，若其标号为（i；＋），则找出正
向弧（vi；vk）；若标号为（i；…）；则找出反向弧（v　k；vi），依此下去，一直追踪至具有标号（0；＋）
的发点v1，得到由v1到vn的一个增广链。　

第4步　调整过程，由式（12。9）至（12。11）得出增广链的调整量ε；根据式（12。12）得出
新的可行流｛x　’ij｝；令可行流｛x　ij｝=｛x’ij｝；去掉所有标号；重新上述标号、寻找增广链及调整
过程，如果标号过程进行不下去，而v　n尚未标号，则说明再也找不出增广链，当前可行流
即为最大流。　

例12…4　求出图12…5的最大流　

解：　

第1步　首先给v　1标上（0；＋）　

第2步　检查v　2，在弧（v1；v2）上，x12=5