大学精品课件：第八章 图论（第6节）.ppt

1、第第1页页已知容量网络已知容量网络 D=(V,A,C)，每条弧，每条弧(vi,vj)除了给除了给出容量出容量 cij 外，还给出单位流量的费用外，还给出单位流量的费用 dij 0，求一，求一个流量为个流量为 W 的可行流的可行流 f=fi j，使其总费用最小。，使其总费用最小。上节讨论的寻求网络最大流问题，只考虑了流的上节讨论的寻求网络最大流问题，只考虑了流的数量，而没有考虑流的费用。数量，而没有考虑流的费用。1.流量为流量为 W 的最小费用流的最小费用流 第第2页页 Avvijijjifdfd),()(该可行流该可行流 f 称为流量为称为流量为 W 时的最小费用流。时的最小费用流。即：容量网

2、络即：容量网络 D=(V,A,C)中，流量为中，流量为 W 的可行的可行流可能有很多个，寻求费用最小的那个可行流。流可能有很多个，寻求费用最小的那个可行流。2.最小费用最大流最小费用最大流 容量网络容量网络 D=(V,A,C)中，最大流可能有很多个中，最大流可能有很多个，寻求费用最小的那个最大流。，寻求费用最小的那个最大流。第第3页页1.原始算法原始算法 流量为流量为 W 的最小费用流：找出所有流量为的最小费用流：找出所有流量为 W 的的流，分别计算费用，费用最小的那个流就是所要流，分别计算费用，费用最小的那个流就是所要找的最小费用流（枚举法）；找的最小费用流（枚举法）；最小费用最大流：找出所

3、有最大流，分别计算最小费用最大流：找出所有最大流，分别计算费用，费用最小的那个最大流就是所要找的最小费用，费用最小的那个最大流就是所要找的最小费用最大流（枚举法）。费用最大流（枚举法）。2.对偶算法对偶算法 第第4页页1.基本概念基本概念（1）增广链的费用）增广链的费用 容量费用网络容量费用网络 D=(V,A,C,d)中，中，f 是是 D 上的一上的一个可行流，个可行流，是从是从 vs 到到 vt 的关于的关于 f 的增广链，则的增广链，则 ijijddd称为增广链称为增广链 的费用。的费用。第第5页页例：例：vsv1v3v5vt(10,5,3)(3,3,5)(5,3,4)(7,6,1)(5,

4、5,7)(7,5,6)v2v4上述为一条增广链，该增广链的费用为：上述为一条增广链，该增广链的费用为：3 5+4+1 7+6=2 第第6页页（2）定理）定理 若若 f 是流量为是流量为 W 的最小费用流，的最小费用流，的从的从 vs 到到 vt 的一条费用最小的增广链，则沿的一条费用最小的增广链，则沿这条费用最小的增广链这条费用最小的增广链 整，从而得到一个新的可行流整，从而得到一个新的可行流，其流量，其流量，则该流，则该流 的最小费用流。的最小费用流。是关于是关于 f 对流对流 f 进行调进行调f )(WWW为为 f 一定一定是流量为是流量为 W 证明：略证明：略 第第7页页2.构造长度网络

5、构造长度网络（1）构造原理）构造原理 D 对容量网络对容量网络 D 进行修正，得到一个新图进行修正，得到一个新图，使新图，使新图中的从中的从 vs 到到vt 的每条链都是增的每条链都是增中如果是前向弧都是非饱和中如果是前向弧都是非饱和即使即使D 广链，广链，D 弧，如果是后向弧都是非零流弧。弧，如果是后向弧都是非零流弧。第第8页页（2）构造方法）构造方法 容量费用网络容量费用网络 D=(V,A,C,d)，有可行流，有可行流 f，对网络，对网络D 作如下调整：作如下调整：保留网络保留网络 D 中的各顶点；中的各顶点；保留网络保留网络 D 中的所有非饱和弧（中的所有非饱和弧（fij cij 的弧）

6、，的弧），令其权值令其权值 wij=dij；第第9页页 删去网络删去网络 D 中的所有饱和弧（中的所有饱和弧（fij=cij 的弧的弧）；）；对于网络对于网络 D 中的非零流弧，增加与其方向相反的中的非零流弧，增加与其方向相反的弧，并另其权值弧，并另其权值 wij=-dij。按照上述方法得到的网络，称为长度网络，即将费按照上述方法得到的网络，称为长度网络，即将费用看作长度，记为用看作长度，记为 L(f)。第第10页页3.对偶算法基本步骤对偶算法基本步骤（1）取零流为初始可行流；）取零流为初始可行流；（2）构造长度网络）构造长度网络 L(f k-1)；（3）在长度网络）在长度网络 L(f k-1

7、)中寻求从中寻求从 vs 到到 vt 的最的最短路，转步骤（短路，转步骤（4）；若不存在最短路，）；若不存在最短路，f k-1 已为已为最大流，停止，转步骤（最大流，停止，转步骤（4）；）；第第11页页（4）在）在 D 中，与这条最短路相应的增广链中，与这条最短路相应的增广链 上，作如下调整：上，作如下调整：)1()(kkffmin),(minmin*ijijijffc 返回步骤（返回步骤（2）。）。第第12页页例：例：vsv1v2v3vt(10,4)(8,1)(2,6)(7,1)(5,2)(10,2)(4,2)求最小费用最大流。求最小费用最大流。第第13页页解：第一次调整：解：第一次调整：（

8、1）取）取 f(0)=0 为初始可行流。为初始可行流。vsv1v2v3vt(10,0)(8,0)(2,0)(7,0)(5,0)(10,0)(4,0)第第14页页vsv1v2v3vt4161222（2）构造长度网络）构造长度网络 L(f 0)：第第15页页（3）寻求最短路：）寻求最短路：(vs,v2,v1,vt)vsv1v2v3vt4161222第第16页页 min 8-0,5-0,7-0 =5，得，得 f(1)：（4）vsv1v2v3vt(10,0)(8,5)(2,0)(7,5)(5,5)(10,0)(4,0)(8,0)(5,0)(7,0)第第17页页第二次调整：第二次调整：（1）构造长度网络

9、）构造长度网络 L(f 1)：2vsv1v2v3vt4161-22-1-1第第18页页（2）寻求最短路：）寻求最短路：(vs,v1,vt)2vsv1v2v3vt4161-22-1-1第第19页页 min10-0,7-5=2，得，得 f(2)：（3）vsv1v2v3vt(10,2)(8,5)(2,0)(7,7)(5,5)(10,0)(4,0)(10,0)(7,5)第第20页页第三次调整：第三次调整：（1）构造长度网络）构造长度网络 L(f2)：增加弧：增加弧(v1,vs)；删去弧；删去弧(v1,vt)2vsv1v2v3vt-416-22-1-14第第21页页（2）寻求最短路：）寻求最短路：(vs

10、,v2,v3,vt)2vsv1v2v3vt-416-22-1-14第第22页页（3）min 8-5,10-0,4-0=3，得，得 f(3)：vsv1v2v3vt(10,2)(8,8)(2,0)(7,7)(5,5)(10,3)(4,3)(8,5)(10,0)(4,0)第第23页页第四次调整：第四次调整：（1）构造长度网络）构造长度网络L(f 3)：增加弧：增加弧(v3,v2)、(vt,v3)；删去弧删去弧(vs,v2)2vsv1v2v3vt-46-22-1-14-2-2第第24页页（2）寻求最短路：）寻求最短路：(vs,v1,v2,v3,vt)2vsv1v2v3vt-46-22-1-14-2-2

11、第第25页页vsv1v2v3vt(10,3)(8,8)(2,0)(7,7)(5,4)(10,4)(4,4)（3）min10-2,5,10-3,4-3=1，得，得 f(4)：(10,2)(5,5)(10,3)(4,3)第第26页页第五次调整：第五次调整：（1）构造长度网络）构造长度网络 L(f4)：增加弧：增加弧(v2,v1)、(vt,v3)；删去弧删去弧(v3,vs)vsv1v2v3vt-46-22-1-14-2-22第第27页页（2）不存在从）不存在从 vs 到到 vt 的最短路的最短路 从而得出最小费用最大流为从而得出最小费用最大流为 f 4。vsv1v2v3vt(10,3)(8,8)(2,0)(7,7)(5,4)(10,4)(4,4)