图论中的几个典型问题(下).pptVIP

最小费用最大流 双权网路：每条弧不但有容量，还有单位流量的通过费用 两种解法：一种基于最小费用路径算法；一种基于可行弧集的最大流算法 基于最小费用路径算法：总是在当前找到的最小费用的路径上增广流；缺点是每次增广后要改变弧的费用，且出现负权值费用的弧 基于可行弧集的最大流算法：从 0 费用弧集开始应用最大流算法，然后根据计算信息提高费用的限界P，使可行弧集增大，再应用最大流算法，直至所有弧都进入可行弧集。这种算法是一种主-对偶规划的解法。使用这种方法的还有运输问题、匹配问题 * 许多实际问题都可以转化为最小费用流问题 S T 最小费用流问题的例子 公路交通网络：车辆路线确定（同时有两条最大流路线，哪条费用最省？即运送相同数量货物的距离或费用最小问题。） 最短路问题 最小费用流问题 1辆车 多辆车:车流 * 定义：N=(V,E，b,c,s,t) 是每边具有两个非负权函数的网络，f是定义在E上的实值函数，满足： (1).对任意的(x,y)?E,有： b(x,y)?f(x,y)?c(x,y) ，其中b(x,y)， c(x,y)均为边(x,y)上的权 (2).对任意中间点v恒有f +(v)=f -(v) 则称f是N的可行流。 3.1 最小费用流问题 * 3.2最大可行流的算法 1.求初始可行流f，若存在则标发号为(s+,∞)，令?s= ∞；转2，否则停. 2.若点 x已经标号，则对于x相邻所有未标号点y，按下法标号： a.若f(x,y)c(x,y) ，令：?y =min{c(x,y)- f(x,y), ?x } 给y标(x+, ?y );当f(x,y)=c(x,y)时, 不给y标号。 b.若f(x,y)b(x,y)，令：?y =min{f(y,x)-b(y,x), ?x } 给y标(x-, ?y )。 以下同求最大流的3~6步. * 3.3 初始可行流的构造： 先将网络N=(V,E，b,c,s,t) 转化为是每边仅有一个权的网络N*=(V*, E*，c*,s*,t* ) ，其中： (1). V*=V?{s*,t* }其中s*是N*唯一发点， t*是N*唯一收点。 (2). E*=E ?{(t,s)} ?E s* ?Et. 其中： E s* ={(s*,y)x|(x,y)?E }; E t* ={(x, t*)y|(x,y)?E }. (3).边权定义： a.对(x,y) ?E, c*(x,y)=c(x,y)-b(x,y); b. c*(t,s)=∞; c.对(s*,y)x ? Es* ， c*(s*,y)=b(x,y); d.对(x,t*)y ? Et* ， c*(x,t*)=b(x,y); * 定理：网络N中存在可行流?N*中存在使Et* 中所有边都饱和的最大流，其中流f 饱和边(x,y)是指f(x,y)=c(x,y). 求初始可行流的办法： 1.由N构造N*,再将N*简化，即将中两端点均相同的边合并成一条边，被合并边的容量相加作为合并后边的容量。 2.用标号法求N*的最大流f*。 3.检查Et*的边是否饱和，若存在不饱和边，则停(不存在可行流)；否则继续。 4.对(x,y) ?E(N),令f(x,y)=f*(x,y)+b(x,y) ,得N的初始可行流 * 3.4 最小费用流 给定网络N，已知总流值为val f，问如何用最小的费用将量为val f的“物品”从s发送t . 例.下图(a)所示网络，每条边上第一个数表示容量，第二个数表示单位费用. (b),(c),(d)分别给出流值为4的3个流，每条边上3个数从左到右分别表示边的流量，容量与费用。3个网络总费用分别为28,24, 15；换言之，流值相同，而费用不同。问如何求最小费用流 * s v2 v1 t 4, 2 3,1 5, 2 4, 2 3,6 s v2 v1 t 2,4, 2 0,3,1 2,5, 2 4,4, 2 2,3,6 s v2 v1 t 4,4, 2 0,3,1 4,5, 2 4,4, 2 0,3,6 s v2 v1 t 4,4, 2 3,3,1 1,5, 2 1,4, 2 0,3,6 (d) (a) (b) (c) * 设w(i, j), c(i, j), f(i, j)分别表示边(i, j)的费用，容量与流量，val f=?，则上述问题的模型为：求 其中f应满足约束：对任意(i, j)?E，有 注意： 1).若val f为最大流，则问题为最小费用最大流。 2).若val f大于最大流，则问题无解。 * 最小费用最大流问题的算法： 1.求发点s 到收点t的最小