按键盘上方向键 ← 或 → 可快速上下翻页，按键盘上的 Enter 键可回到本书目录页，按键盘上方向键 ↑ 可回到本页顶部！
————未阅读完？加入书签已便下次继续阅读！
17（5）
V6
V3 V5
6（6）
图12…9
对图12…9；重新标号、调整，v 1标上（0；＋）；V 3标上（1；＋）；v 4标上（3；＋）；v 6标上（4；＋），得
增广链v1→v3→v4→v6，此增广链上的弧皆为正向弧，由式（12。9）、（12。11）得
ε=ε1=min｛8…4；5…1；11…9｝=2
根据（12。9）调整流量；得新可行流如图12…10
10（10）
8（6）
4（3）
3（2）
5（3）
5（5）
3（3）
11（11）
17（5）
V2 V4
V1
V6
V V5
6（6）
图12…10
对图12…10；重新标号、调整，v1标上（0；＋）；V 3标上（1；＋）；v 4标上（3；＋）；v 5标上（4；…），
v6标上（5；＋），得增广链v 1→v3→v4→v5→v6，其中（v 1；v3）（v3；v4）（v5；v6）为为正向弧，由式
（12。9）得
ε1=min｛8…6；5…3；17…5｝=2
（v4；v5）为反向弧，由式（12。10）得ε 2=3
由式（12。11）得ε=min｛ε 1；ε2｝=2；因此在此增广链的正向弧上流量增加2；反向弧上流
量减少2；得可行流如图12…11。
10（10）
8（8）
4（3）
3（2）
5（5）
5（5）
3（1）
11（11）
17（7）
V2 V4
VB1 VB6
12…15
VB3 VB5
6（6）
图12…11
对图12…11显然用标号法再也不能得到一个增广链；故其所给的可行流即为最大流；最大
流量=x12＋x13=x46＋x56=18
12。3。3 最小费用最大流问题
在实际运输工作中，人们除了考虑运量外，还需考虑成本问题，从而产生了最小费用
最大流问题，即对于某个网络D=（V；A；C），每个弧（v i；vj）上除了容量c ij外，还给出了单位流
量的费用bij，要求找出一个最大流x，使流的总输送费用b（x）=Σb ijxij 最小。
解最小费用最大流问题的基本思想是，通过已知的由v1到收点v n的最小费用流x，寻找
其对应的最小费用增广链，沿此增广链去调整x，实现最大流。
对于网络D=（V；A；C），构造赋权有向图W（X），其顶点为原网络D的顶点，而把D中的每
一条弧（vi；vj）变成两个相反方向的弧（vi；vj）和（vj；vi），定义W（X）中弧的权w ij为（其中长
度为＋∝的弧可从W（X）中略去）：
wij
=
。。bij
若xij0 （12。14）
ij
＋∞
xij=0
。
在w（x）中寻找到的v 1 到vn 的最短路即为关于可行流x的最小费用增广链。
最小费用最大流算法如下：
第一步：取x（o）=0为初始可行流，即流量为0的最小费用流，k=0
第二步：对于可行流x（k），根据式（12。12）、（12。13）构造赋权有向图w（x （k）），并在此
有向图中找出v1到vn的最短路。
第三步：若存在最短路，则此最短路为x（k）的最小费用增广链，在增广链上对x（k）进行
调整，即
。xij
（k
） ＋ε当（vi；vj）是增广链上的正向弧
xij
（k
＋1） =
。。
xij
（k
） 。ε
当（vi；vj）为增广链上的反向弧
。x（k
） 当（vi；vj）不在增广链上
。
ij
ε=
min｛ε1；ε2 ｝
其中 ε1 =
min｛ij
。
xij
（k ）｜ 当（vi；vj）为正向弧 ｝
（k
）
ε2 =
min｛（c） xij
｜ 当（vi；vj）为反向弧 ｝
得到新的可行流x （k＋1） ；此可行流为同一流量中费用最小的可行流，若不存在最短路，
转第五步。
第四步 令k=k＋1，重复第二步至第三步。
第五步 退出计算，所得x （k）即为最小费用最大流。
例12…5 求图12…12所示网络的从v 1到v8的最小费用最大流，图中（vi；vj）上所标的三个数
字依次表示 bij、cij、xij。
解：首先对x（0）=0的初始可行流，根据式（12。13）、（12。14）构造赋权有向图w（x （0））
如图12…13，并找出v 1到v8的最短路径为：v1→v2→v5→v6→v8
12…16
V2 （2；4；0） V5 V2 2 V5
V1
V4 V7
V3 V6
（2；4；0）
（7；3；0）
（4；4；0）
（2；4；0）
（3；2；0）
（3；2；0）
（3；2；0）
（3；3；0）
（6；4；0）
（6；3；0） （8；3；0） （3；2；0）
V1
V8
V3 V6
2
7
4
2
3
3
3
8
3
6
6 3
V8
V4V4 V7 V7
（2；2；0） 2
图12…12图12…13
沿此增广链对x（0）进行调整，显然可增加的流量为2，得可行流x （1），如图12…14所示，对
x（1）根据式（12。13）、（12。14）构造赋权有向图w（x （1））如图12…15，找出v 1到v8的最短路径
为：v1→v3→v7→v8
V2 （2；4；2） V5 V2 2 V5
V1 V1
V8
V3 V6
（2；4；2）
（7；3；0）
（4；4；0）
（2；4；0）
（3；2；0）
（3；2；0）
（3；2；0）
（3；3；2）
（6；4；0）
（6；3；0） （8；3；0） （3；2；2）
V8
V3 V67
2 6 8
4
2
3
3
3
…2
…3
6
…2 …3
3
V4 （2；2；0） V7 V4 2 V7
图12…14 图12…15
沿此增广链对x （1）进行调整，可增加的流量为2，得可行流x （2），如图12…15所示，对x （2）
构造赋权有向图w（x（2））如图12…17，找出v 1到v8的最短路径为：v1→v2→v6→v8
V2 （2；4；2） V5 V2 2 V5
V1
V3 V6
（2；4；2）
（7；3；0）
（4；4；0）
（2；4；2）
（3；2；0）
（3；2；2）
（3；2；0）
（3；3；2）
（6；4；2）
（6；3；0） （8；3；0） （3；2；2）
V1
V8
3
V3 V6
2
72
4 3 6
…2
6
…3
3
…3
…2
…3
8…2
…6
V8
V4 （2；2；0） V7 2
V4 V7
图12…16图12…17
沿此增广链对x （2）进行调整，可增加的流量为1，得可行流x （3），如图12…18所示，对x （3）
构造赋权有向图w（x（3））如图12…19，找出v 1到v8的最短路径为：v1→v4→v7→v8
V2 （2；4；2） V5 V2 2 V5
V1
V8
V3 V6
（2；4；3）
（7；3；0）
（4；4；0）
（2；4；2）
（3；2；0）
（3；2；2）
（3；2；0）
（3；3；3）
（6；4；2）
（6；3；1） （8；3；0） （3；2；2）
V3 V6
2
4
…2
72
6
3
…3
3
8
…3
6
…2
…2
…3
…6
V1
…6
V8
V4 （2；2；0） V7 V4 2 V7
图12…18 图12…19
12…17
沿此增广链对x（3）进行调整，可增加流量2，得可行流x （4），如图12…20所示，对x （4）构造
赋权有向图w（x（4））如图12…21，找出v 1到v8的最短路径为：v1→v2→v5→v8
V2 （2；4；2） V5 V2 2 V5
V1
V3 V6
（2；4；3）
（7；3；0）
（4；4；2）
（2；4；2）
（3；2；0）
（3；2；2）
（3；2；0）
（3；3；3）
（6；4；4）
（6；3；1） （8；3；0） （3；2；2）
V8
V8
V1 V3 V6
2
4
72
…2
6
3
…3
3
8
…3
…6
…2
…2
…3
…6
…4
V4 （2；2；2） V7 V4 …2 V7
图12…20图12…21
沿此增广链对x（4）进行调整，可增加流量1，得可行流x （5），如图12…22所示，对x （5）构造
赋权有向图w（x（5））如图12…23，找出v 1到v8的最短路径为：v1→v3→v6→v2→v5→v8
V2 （2；4；3） V5 V2 2 V5
V1
V8
V3 V6
（2；4；4）
（7；3；0）
（4；4；2）
（2；4；2）
（3；2；0）
（3；2；2）
（3；2；0）
（3；3；3）
（6；4；4）
（6；3；1） （8；3；1） （3；2；2）
V3 V6
…2
4
…2
72
6
3
…3
3
8
…3
…6
…2
…3
…6
…4
V1
…8
V4 （2；2；2） V7 V4 …2 V7
图12 …22 图12 …23（5）（6）（6）
沿此增广链对x 进行调整，可增加流量1，得可行流x ，如图12…24所示，对x 构造
赋权有向图w（x（6））如图12…25，找出v 1到v8的最短路径为：v1→v3→v6→v5→v8
V5
V2 （2；4；4） V5
V3 V6
（2；4；4）
（7；3；1）
（4；4；2）
（2；4；3）
（3；2；0）
（3；2；2）
（3；2；0）
（3；3；3）
（6；4；4）
（6；3；0） （8；3；2） （3；2；2）
V2
V1
V1
V8
V8
V3 V6
…2
4
72
…2
6
3
…3
3
…3
…2
…3
…4
…7
8
…6
…8
（2；2；2）
V4 …2 V7
图12…24图12…25
沿此增广链对x（6）进行调整，可增加流量1，得可行流x （7），如图12…26所示，对x （7）构造
赋权有向图w（x（7））如图12…27，可以看到已无从v 1到v8的最短路径。可知x（7）即为最小费用最
大流，其网络图如图12…26。
V2 （2；4；4） V5 V2
V1
V3 V6
（2；4；4）
（7；3；2）
（4；4；2）
（2；4；4）
（3；2；0）
（3；2；2）
（3；2；0）
（3；3；3）
（6；4；4）
（6；3；0） （8；3；2） （3；2；1）
V8
V8
V