运筹学最大流.pptx

Page 1网络的最大流网络的最大流如何制定一个运输计划使生产地到销售地的产品输送量最大。如何制定一个运输计划使生产地到销售地的产品输送量最大。这就是一个网络最大流问题。这就是一个网络最大流问题。Page 2网络的最大流网络的最大流基本概念：基本概念：1.1.容量网络：容量网络：容量网络：容量网络：队网络上的每条弧队网络上的每条弧(vi,vj)都给出一个最大的通都给出一个最大的通过能力，称为该弧的过能力，称为该弧的容量容量容量容量，简记为，简记为cij。容量网络中通常规定。容量网络中通常规定一个一个发点发点发点发点(也称源点，记为也称源点，记为s)和一个和一个收点收点收点收点(也称汇点，记为也称汇点，记为t)，网络中其他点称为网络中其他点称为中间点中间点中间点中间点。st4844122679Page 3网络的最大流网络的最大流2.网络的最大流网络的最大流是指网络中从发点到收点之间允许通过的最大流量。是指网络中从发点到收点之间允许通过的最大流量。3.流与可行流流与可行流 流流是指加在网络各条弧上的实际流量，对加在弧是指加在网络各条弧上的实际流量，对加在弧(vi,vj)上的上的负载量记为负载量记为fij。若。若fij=0，称为零流。，称为零流。满足以下条件的一组流称为满足以下条件的一组流称为可行流可行流。容量限制条件。容量网络上所有的弧满足：容量限制条件。容量网络上所有的弧满足：0fijcij 中间点平衡条件。中间点平衡条件。若以若以v(f)表示网络中从表示网络中从st的流量，则有：的流量，则有：Page 4网络的最大流网络的最大流结论：任何网络上一定存在可行流。（零流即是结论：任何网络上一定存在可行流。（零流即是可行流）可行流）网络最大流问题：网络最大流问题：指满足容量限制条件和中间点平衡的条件下，使指满足容量限制条件和中间点平衡的条件下，使v(f)值值达到最大。达到最大。Page 5网络的最大流网络的最大流 割与割集割与割集割是指容量网络中的发点和收点分割开，并使割是指容量网络中的发点和收点分割开，并使st的流中断的流中断的一组弧的集合。割容量是组成割集合中的各条弧的容量之的一组弧的集合。割容量是组成割集合中的各条弧的容量之和，用和，用 表示。表示。如下图中，如下图中，AA将网络上的点分割成将网络上的点分割成 两个集合。并有两个集合。并有 ，称弧的集合，称弧的集合(v1,v3),(v2,v4)是一个割，且是一个割，且 的流量为的流量为18。Page 6网络的最大流网络的最大流stv1v3v2v48(8)9(5)5(5)10(9)6(0)2(0)9(9)5(3)7(6)AABBPage 7网络的最大流网络的最大流定理定理定理定理1 1 设网络设网络N中一个从中一个从 s 到到 t 的流的流 f 的流量为的流量为v(f)，(V,V)为任意一个割集，则为任意一个割集，则 v(f)=f(V,V)f(V,V)推论推论推论推论1 1 对网络对网络 N中任意流量中任意流量v(f)和割集和割集(V,V)，有，有v(f)c(V,V)证明证明 w=f(V,V)f(V,V)f(V,V)c(V,V)推论推论推论推论2 2 最大流量最大流量v(f)不大于最小割集的容量，即：不大于最小割集的容量，即：v(f)minc(V,V)定理定理定理定理2 2 在网络中在网络中st的最大流量等于它的最小割集的容量，的最大流量等于它的最小割集的容量，即：即：v(f)=c(V,V)Page 8网络的最大流网络的最大流增广链增广链增广链增广链在网络的发点和收点之间能找到一条链，在该链上所有在网络的发点和收点之间能找到一条链，在该链上所有指向为指向为st的弧，称为前向弧，记作的弧，称为前向弧，记作+,存在存在f0，则称这样的链为，则称这样的链为增广链。例如下图中，增广链。例如下图中，sv2v1v3v4t。定理定理定理定理3 3 网络网络N中的流中的流 f 是最大流当且仅当是最大流当且仅当N中不包含任何增广中不包含任何增广链链Page 9网络的最大流网络的最大流stv1v3v2v48(8)9(4)5(5)10(8)6(1)2(0)9(9)5(4)7(5)Page 10网络的最大流网络的最大流求网络最大流的标号算法：求网络最大流的标号算法：基本思想基本思想基本思想基本思想 由一个流开始，系统地搜寻增广链，然后在此链上增流，由一个流开始，系统地搜寻增广链，然后在此链上增流，继续这个增流过程，直至不存在增广链。继续这个增流过程，直至不存在增广链。基本方法基本方法基本方法基本方法(1)找出第一个可行流，（例如所有弧的流量找出第一个可行流，（例如所有弧的流量fij=0。）。）(2)用标号的方法找一条增广链用标号的方法找一条增广链 首先给发点首先给发点s标号标号(),标号中的数字表示允许的最大调整量。标号中的数字表示允许的最大调整量。选择一个点选择一个点 vi 已标号并且另一端未标号的弧沿着某条链已标号并且另一端未标号的弧沿着某条链向收点检查：向收点检查：Page 11网络的最大流网络的最大流 如果弧的起点为如果弧的起点为vi，并且有，并且有fij0，则，则vj标号标号(fji)(3)重复第重复第(2)步，可能出现两种结局：步，可能出现两种结局：标号过程中断，标号过程中断，t无法标号，说明网络中不存在增广链，无法标号，说明网络中不存在增广链，目前流量为最大流。同时可以确定最小割集，目前流量为最大流。同时可以确定最小割集，记已标号的点记已标号的点集为集为V,未标号的点集合为未标号的点集合为V,(V,V)为网络的最小割。为网络的最小割。t得到标号，反向追踪在网络中找到一条从得到标号，反向追踪在网络中找到一条从s到到t得由标号得由标号点及相应的弧连接而成的增广链。继续第点及相应的弧连接而成的增广链。继续第(4)步步Page 12网络的最大流网络的最大流(4)修改流量。设原图可行流为修改流量。设原图可行流为f，令，令得到网络上一个新的可行流得到网络上一个新的可行流f。(5)擦除图上所有标号，重复擦除图上所有标号，重复(1)-(4)步，直到图中找不到任何步，直到图中找不到任何增广链，计算结束。增广链，计算结束。Page 13网络的最大流网络的最大流例例6.10 用标号算法求下图中用标号算法求下图中st的最大流量，并找出最小割。的最大流量，并找出最小割。stv1v3v2v48(7)9(3)5(4)10(8)6(1)2(0)9(9)5(4)7(5)Page 14网络的最大流网络的最大流解：解：(1)先给先给s标号标号()stv1v3v2v48(7)9(3)5(4)10(8)6(1)2(0)9(9)5(4)7(5)()Page 15网络的最大流网络的最大流stv1v3v2v48(7)9(3)5(4)10(8)6(1)2(0)9(9)5(4)7(5)()(2)检查与检查与s点相邻的未标号的点，因点相邻的未标号的点，因fs1cs1，故对，故对v1标号标号=min,cs1-fs1=1,(1)Page 16网络的最大流网络的最大流stv1v3v2v48(7)9(3)5(4)10(8)6(1)2(0)9(9)5(4)7(6)()(1)(2)检查与检查与v1点相邻的未标号的点，因点相邻的未标号的点，因f13c13，故对，故对v3标号标号=min1,c13-f13=min1,6=1(1)Page 17网络的最大流网络的最大流stv1v3v2v48(7)9(3)5(4)10(8)6(1)2(0)9(9)5(4)7(5)()(1)(1)(3)检查与检查与v3点相邻的未标号的点，因点相邻的未标号的点，因f3tc3t，故对，故对vt标号标号=min1,c3t-f3t=min1,1=1(1)找到一条增广链找到一条增广链sv1v3tPage 18网络的最大流网络的最大流(4)修改增广链上的流量，非增广链上的流量不变，得到新的修改增广链上的流量，非增广链上的流量不变，得到新的可行流。可行流。stv1v3v2v48(7)9(3)5(4)10(8)6(1)2(0)9(9)5(3)7(5)()(1)(1)(1)Page 19网络的最大流网络的最大流(5)擦除所有标号，重复上述标号过程，寻找另外的增广链。擦除所有标号，重复上述标号过程，寻找另外的增广链。stv1v3v2v48(8)9(4)5(5)10(8)6(0)2(0)9(9)5(3)7(5)()(1)(1)(1)Page 20网络的最大流网络的最大流(5)擦除所有标号，重复上述标号过程，寻找另外的增广链。擦除所有标号，重复上述标号过程，寻找另外的增广链。stv1v3v2v48(8)9(4)5(5)10(8)6(1)2(0)9(9)5(3)7(5)()(2)(2)=min,2=2(2)(1)=min2,3=2(3)=min2,5=2(2)(1)(4)=min2,1=1(1)(t)=min1,2=1Page 21网络的最大流网络的最大流(6)修改增广链上的流量，非增广链上的流量不变，得到新的修改增广链上的流量，非增广链上的流量不变，得到新的可行流。可行流。stv1v3v2v48(8)9(4)5(5)10(8)6(1)2(0)9(9)5(3)7(5)()(2)(2)(2)(1)(1)Page 22网络的最大流网络的最大流stv1v3v2v48(8)9(5)5(5)10(9)6(0)2(0)9(9)5(2)7(6)()(2)(2)(2)(1)(1)(7)擦除所有标号，重复上述标号过程，寻找另外的增广链。擦除所有标号，重复上述标号过程，寻找另外的增广链。Page 23网络的最大流网络的最大流stv1v3v2v48(8)9(5)5(5)10(9)6(0)2(0)9(9)5(2)7(6)()(1)(1)(1)(7)擦除所有标号，重复上述标号过程，寻找另外的增广链。擦除所有标号，重复上述标号过程，寻找另外的增广链。(2)=min,1=1(1)=min1,2=1(3)=min1,4=1Page 24网络的最大流网络的最大流例例6.9 求下图求下图st的最大流，并找出最小割的最大流，并找出最小割stv1v2v3v4v54(3)3(2)10(4)3(2)1(1)4(3)3(2)5(3)4(2)2(2)7(6)8(3)Page 25网络的最大流网络的最大流stv1v2v3v4v54(3)3(2)10(4)3(2)1(1)4(3)3(2)5(3)4(2)2(2)7(6)8(3)解解:(1)在已知可行流的基础上，通过标号寻找增广链。在已知可行流的基础上，通过标号寻找增广链。()(2)=min,6=6(6)(3)=min6,2=2(2)(t)=min2,5=2(2)存在增广链存在增广链存在增广链存在增广链svsv2 2vv3 3 t tPage 26网络的最大流网络的最大流(2)修改增广链上的流量，非增广链上的流量不变，得到新的修改增广链上的流量，非增广链上的流量不变，得到新的可行流。可行流。stv1v2v3v4v54(3)3(2)10(4)3(2)1(1)4(3)3(2)5(3)4(2)2(2)7(6)8(3)()(6)(2)(2)Page 27网络的最大流网络的最大流(3)擦除原标号，重新搜寻增广链。擦除原标号，重新搜寻增广链。stv1v2v3v4v54(3)3(2)10(6)3(2)1(1)4(3)3(2)5(3)4(4)2(2)7(6)8(5)()(6)(2)(2)Page 28网络的最大流网络的最大流(4)重新搜寻增广链。重新搜寻增广链。stv1v2v3v4v54(3)3(2)10(6)3(2)1(1)4(3)3(2)5(3)4(4)2(2)7(6)8(5)()(2)=min,4=4(4)(1)(5)=min4,1=1(3)=min1,2=1(1)(1)(t)=min1,3=1存在增广链：存在增广链：存在增广链：存在增广链：svsv2 2vv5 5vv3 3 t tPage 29网络的最大流网络的最大流(5)修改增广链上的流量，非增广链上的流量不变，得到新的可修改增广链上的流量，非增广链上的流量不变，得到新的可行流。行流。stv1v2v3v4v54(3)3(2)10(6)3(2)1(1)4(3)3(2)5(3)4(4)2(2)7(6)8(5)()(4)(1)(1)(1)Page 30网络的最大流网络的最大流(6)擦除原标号擦除原标号stv1v2v3v4v54(3)3(2)10(7)3(2)1(1)4(3)3(3)5(4)4(4)2(2)7(6)8(6)()(4)(1)(1)(1)Page 31网络的最大流网络的最大流stv1v2v3v4v54(3)3(2)10(7)3(2)1(1)4(3)3(3)5(4)4(4)2(2)7(6)8(6)()(1)(1)(1)(5)=min,1=1(5)=min1,1=1(5)=min1,2=1(7)重新搜寻增广链。重新搜寻增广链。存在增广链：存在增广链：存在增广链：存在增广链：svsv5 5vv3 3 t tPage 32网络的最大流网络的最大流(8)调整增广链上的流量，非增广链流量不变，得到新的可行流调整增广链上的流量，非增广链流量不变，得到新的可行流stv1v2v3v4v54(3)3(2)10(7)3(2)1(1)4(3)3(3)5(4)4(4)2(2)7(6)8(6)()(1)(1)(1)Page 33网络的最大流网络的最大流stv1v2v3v4v54(3)3(3)10(7)3(2)1(1)4(3)3(3)5(5)4(4)2(2)7(6)8(7)()(1)(1)(1)(9)擦除原标号擦除原标号Page 34网络的最大流网络的最大流stv1v2v3v4v54(3)3(3)10(7)3(2)1(1)4(3)3(3)5(5)4(4)2(2)7(6)8(7)(10)重新标号，搜索增广链重新标号，搜索增广链()(1)=min,1=1(1)(5)=min1,1=1(1)(4)=min1,1=1(1)(t)=min1,1=1(1)存在增广链：存在增广链：存在增广链：存在增广链：svsv1 1vv5 5vv4 4ttPage 35网络的最大流网络的最大流stv1v2v3v4v54(3)3(3)10(7)3(2)1(1)4(3)3(3)5(5)4(4)2(2)7(6)8(7)()(1)(1)(1)(1)(11)调整增广链上的流量，非增广链流量不变，得到新的可行流调整增广链上的流量，非增广链流量不变，得到新的可行流Page 36网络的最大流网络的最大流stv1v2v3v4v54(4)3(3)10(7)3(3)1(1)4(4)3(3)5(5)4(4)2(2)7(7)8(7)()(1)(1)(1)(1)(11)擦除标号，在新的可行流上重新标号。擦除标号，在新的可行流上重新标号。Page 37网络的最大流网络的最大流stv1v2v3v4v54(4)3(3)10(7)3(3)1(1)4(4)3(3)5(5)4(4)2(2)7(7)8(7)()(11)擦除标号，在新的可行流上重新标号。擦除标号，在新的可行流上重新标号。(3)(1)=min,3=1无法标号，不存在增广链，此可行流已为最大流。最大流量为无法标号，不存在增广链，此可行流已为最大流。最大流量为14。