v1(14,14)(16,14)(3,0)v6(13,8)(22,22)(?,??)(?v3,5)(15,8)vSv2(12,8)(?v4,5)v5(6,0)(7,0)vT(19,9)(9,9)(6,5)(5,5)v3(?vS,5)(4,4)(?v2,5)v4

(d)第四次标号、调整(vSv3v2v4vT,?T?5)

v1(14,14)(?v5,4)(16,14)(3,0)(13,12)v6(22,22)(?,??)(?vS,7)(15,12)vSv2(12,12)v5(6,0)(?v2,4)(?v4,4)(7,4)vT(9,9)(6,5)(5,5)(19,13)v3(4,4)v4(?v,4)6

(e)第五次标号、调整(vSv2v5v6v4vT,?T?4)

图9-11

经过5次标号调整，(vS,v1)、(v2,v5)、(v2,v4)、(v3,v4)已经达到最大流容量限制，不再满足标号条件，标号过程无法继续。令S?{vS,v2,v3}，S?{v1,v4,v5,v6,vT}，

(S,S)为最小割集，其容量即为网络的最大流量，W?C(S,S)?14?12?5?4?35。因此，该企业只要按照图9-11(e)的方式安排运输，即可获得从vS到vT的最大运输能力，最大运输能力为35。 题型 Ⅳ 求网络中的最小费用最大流问题

最小费用最大流问题主要使用对偶算法，其基本步骤：

1、初始可行流取零流，即f(0)?{0}。

2、若有可行流f(k?1)流量满足W(f(k?1))?w*，构造长度网络L(f(k?1))。

21

3、用Dijkstra算法求长度网络L(f(k?1))中从vS到vT的最短路。若不存在最短路，则f(k?1)即为最大流，不存在流量为w*的流，算法停止，否则继续第4步。

(k?1)4、在D中与这条最短路相应的可增广链Q上，作f(k)?fQ?，其中

??min{min(cij?fij(k?1)),minfij(k?1)} ??QQ此时f(k)的流量为W(f(k))?W(f(k?1))??，若W(f(k))?w*则停止，否则令

f(k)代替f(k?1)返回第2步。

例9-8 某集团下有三个煤矿和三个火力发电厂,煤矿生产的煤供应给发电厂,有关煤矿的产能、发电厂的需求量以及相关运输费用见表9-3,要求尽可能多地生产煤供给给发电厂，建立网络模型使总费用最小，并求最小费用。

表9-3

单位运价wij 发电厂 产量ai 50 60 40 3y1y2y3 x1煤矿 16 13 22 14 - 19 - 20 23 70 0 30 70 30 不限 3x2 x3最低需求量b?j ?最高需求量b?j 解：由于三个煤矿总产量为?ai?150，三个发电厂最低需求量?b?j?100，

i?1j?1???80。因此三个发电厂的最高需求量总和为不难知道发电厂y3的最高需求量b3?b???180

jj?13因此为了平衡产销，我们虚拟一个煤矿x4，其产量为30。

对于发电厂y3，由于其需求量在30至80之间，容量网络上很难直接反映

??该需求区间，因此将y3分拆为两个顶点y?3和y3，其需求量分别为30和50，其?中y?3的需求必须得到满足，因此y3不能和虚拟煤矿x4关联。我们假设源和汇分别为x、y，则可得到运输容量网络，见图9-12,弧上参数分别为最大流容量和

22

单位流成本。

x150,050,2250,1650,13y160,14x260,1960,1950,22y270,060,030,0x40,0x340,2040,23y?3y30,040,2350,030,030,0x430,0?y?3图9-12

本问题的最大流显然是180，求最小运输成本归结为最小成本最大流问题。 1、从初始可行流f(0)?{0}开始，作长度网络L(f(0))，见图9-13(a)，用

?Dijkstra算法求出L(f(0))的最短路为：x?x4?y?3?y。在网络中相应的可增广链上用最大流算法进行流的调整：

????Q??{(x,x4),(x4,y?3),(y3,y)}，Q??

?1?min{min(cij?fij(0)),minfij(0)}?{30,30,50}?30

Q?Q?f(1)(0)??fij??1??(0)f?ij?(vi,vj)?Q?，W(f(1))?W(f(0))??1?30

其他d(f(1))?30?0?30?0?30?0?0

f(1)的结果见图9-13(b)。

x1132216y114x10(50,0)(50,0)(50,0)(50,0)y1y2(70,0)(30,0)(60,0)0x201919022y20x2(60,0)(60,0)(50,0)x0x32023230y?3y0(60,0)x(40,0)x3(40,0)(40,0)y?3y(30,0)(40,0)(50,30)0(30,30)(30,0)x40?y?3(0)x4(30,30)?y?3

(a) L(f) (b)f(1)

图9-13

2、作长度网络L(f(1))如图9-14(a)，弧上有负权，故只能采取逐次逼近法

23

求最短路，最短路为x?x1?y2?y。在网络中相应的可增广链上用最大流算法进行流的调整：

Q??{(x,x1),(x1,y2),(y2,y)}，Q???

?2?min{min(cij?fij(1)),minfij(1)}?{50,50,30}?30

Q?Q?f(2)(1)??fij??2??(1)f?ij?(vi,vj)?Q?，W(f(2))?W(f(1))??2?60

其他d(f(2))?30?0?30?13?30?0?390

f(2)的结果见图9-14(b)。

x1132216y114x10(50,0)y1y2(70,0)(50,30)0x201919022y20(50,30)(50,0)(60,0)x2(60,0)(60,0)(50,0)x0x32023230y?3y0(60,0)(30,30)x(40,0)x3(40,0)y?3(30,0)y(40,0)(50,30)?0(30,30)(40,0)(30,0)x40?y?3x4(30,30)?y?3

(a) L(f(1)) (b)f(2)

图9-14

3、作长度网络L(f(2))如图9-15(a)，弧上有负权，故只能采取逐次逼近法求最短路，最短路为x?x2?y1?y。在网络中相应的可增广链上用最大流算法进行流的调整：

Q??{(x,x2),(x2,y1),(y1,y)}，Q???

60,60,70}?60 ?3?min{min(cij?fij(2)),minfij(2)}?min{Q?Q?f(3)(2)??fij??3??(2)f?ij?(vi,vj)?Q?，W(f(3))?W(f(2))??3?120

其他d(f(3))?30?13?60?14?1230

f(3)的结果见图9-15(b)。

24