最小费用流1.pptVIP

西南交通大学经济管理学院* 最 小 费 用 流 在网络中实现某一输送任务时,流在网络中的分配不同,所花的代价也不同,如何在完成输送任务的前提下使所花的费用最少,这就是最小费用流问题. 有时除了要求费用少之外,还希望发挥即定网络的最大效能, 即以最低费用流过尽量大的流量, 这就是最小费用最大流问题. 一、基 本 概 念 cij ——弧（vi，vj）上的容量 wij ——弧（vi，vj）上单位流量的费用（ wij ? 0） 网络 D=（V，A） 一般说，D中流量为F的网络流不止一个，若 为流量为F的流，且有 则称 为D的流量为F的最小费用流 为D内按网络流运送流量F个单位从起点vs到终点vt的费用。 若 { fij }为D的一个流，流量 = F， 则 若F为D的最大流时， 称为D的最小费用最大流 二. 伴随f的费用网络 cij、fij、wij vi vj 7，4，5 vj vi -5 5 至多可以再输送 cij - fij= 7-4 = 3 个单位流量 至多可以少输送 fij= 4 个单位流量 （1）点集 Vf = V （2）弧集 ，其中 对D=（V，A），对一可行流f，构造一赋权有向图D（f） (3) 费率 D（f）：将D中对应流 f有可能增流的弧（正、反向）及其相应的费率构成一个新图，又称为伴随 f 的费用网络。 对（vi，vj） 若 fij = cij，则D（f）中只有反向弧 （ vj ，vi） 若 fij = 0 ，则D（f）只有正向弧（vi，vj） 例：求下图所示网络D的伴随f的费用网络，图中弧旁的数字依次为 cij、fij、wij。 v1 v2 v4 3,1,5 5,2,3 4,2,2 4,4,3 3,0,4 v3 D( f ) -5 v1 v2 v4 3 -2 -3 4 5 -3 2 v3 三、最小费用流算法 1. 算法思想 把各条弧上单位流量的费用看成某种长度，用求解最短路问题的方法确定一条自vs到vt的最短路； 再将这条最短路作为可增流链，用求最大流的方法，将其上的流量增至最大可能值； 再重新确定各条弧的单位流量的费用。 如此多次迭代，最终得到最小费用最大流。 注：这里将遇到求解带负权的最短问题。 （1）任意安排一最小费用可行流 （一般取 fij = 0，此时总费用 Z = 0。） （2）构造伴随f的费用网络D（f）； （3）在 D（f）中求 vs 到 vt 的最短路 ? ，若路长为无 限大，则已求得最小费用最大流，停止。否则，取 2. 算法步骤 （4）调整D上各弧的流量 得到新的最小费用可行流 ，有 f ’= f + ? ， Z ’ = Z + ? ? 若要求流量为F的最小费用流，则流量调整量? 当 f ’ = F 时，f ’ 即为所求的一个流，终止。 转（2） 例：求图中从v1到v5的最小费用最大流，数字为cij，wij v1 v2 v3 v4 v5 8，4 4，1 7，6 6，1 3，2 2，3 5，2 解：给初始可行流为零流，这时f = 0，Z = 0。 D（f（1））， l = 6 f（1）， f = 0，Z=0 v1 v2 v3 v4 v5 8，0 4，0 7，0 6，0 3，0 2，0 5，0 v1 v2 v3 v4 v5 4 1 6 1 2 3 2 ? =3 f（2）， f=3，Z=18 f（3）, f = 4，Z=24 D（f（2））， l = 6 D（f（3））， l = 7 v1 v2 v3 v4 v5 8，0 4，3 7，0 6，3 3，3 2，0 5，3 v1 v2 v3 v4 v5 8，0 4，4 7，0 6，3 3，3 2，1 5，4 ? =1 ? =1 -1 v1 v2 v3 v4 v5 4 1 6 1 - 2 3 2 -1 -2 v1 -1 v2 v3 v4 v5 4 -1 6 1 -2 3 2 -3 -2 f（4）， f=5，Z=31 D（f（4）），l = 8 D（f（5）) l = 8 v1 v2 v3 v4 v5 8，1 4，4 7，0 6，4 3，3 2，1 5，5 v1 v2 v3 v4 v5 8，4 4，4 7，3 6，4 3，0 2，1 5，5 f（4）, f=8，Z=55 v1