第10讲网络流问题ppt课件

最大流与最小费用流问题最大流与最小费用流问题数学建模与数学实验数学建模与数学实验最大流与最小费用流问题数学建模与数学实验1n 流量问题在实际中是一种常见的问题。流量问题在实际中是一种常见的问题。n如公路系统中有车辆流量问题，供电系如公路系统中有车辆流量问题，供电系n统中有电流量问题等等。最大流问题是统中有电流量问题等等。最大流问题是n在单位时间内安排一个运送方案，将发在单位时间内安排一个运送方案，将发n点的物质沿着弧的方向运送到收点，使点的物质沿着弧的方向运送到收点，使n总运输量最大。总运输量最大。流量问题在实际中是一种常见的问题。2例：最大流例：最大流/最小费用流最小费用流从甲地到乙地的输油管网纵横交错，每天每条管道上从甲地到乙地的输油管网纵横交错，每天每条管道上的流量有上限，从甲地到乙地的每天最多能传输多少的流量有上限，从甲地到乙地的每天最多能传输多少油油?若想传输量为若想传输量为m m的油，考虑每条管道上的通行成本，如的油，考虑每条管道上的通行成本，如何确定油的具体传输路线，使总成本最小何确定油的具体传输路线，使总成本最小?(甲甲)A)A F (F (乙乙)5 5 6 6 6 6 7 7 4 4 4 4 5 5 1 1 3 3 B B E E D D C C 例：最大流/最小费用流从甲地到乙地的输油管网纵横交错，每3假假假假设设设设从从从从城城城城市市市市s s s s到到到到城城城城市市市市t t t t的的的的公公公公路路路路网网网网络络络络上上上上每每每每段段段段公公公公路路路路每每每每天天天天可可可可以以以以通通通通过过过过的的的的汽汽汽汽车车车车数数数数量量量量有有有有一一一一个个个个上上上上限限限限，那那那那么么么么经经经经过过过过该该该该公公公公路路路路网网网网，每每每每天天天天最最最最多多多多可可可可以以以以有有有有多多多多少少少少汽汽汽汽车车车车从从从从城城城城市市市市s s s s出出出出发发发发到到到到城城城城市市市市t t t t。可可可可以以以以看看看看出出出出，这这这这一一一一问问问问题题题题考考考考虑虑虑虑的的的的是是是是每每每每天天天天从从从从城城城城市市市市s s s s到到到到城城城城市市市市t t t t的的的的最最最最大大大大车车车车流量，这个问题也是一个求最大流的例子。流量，这个问题也是一个求最大流的例子。流量，这个问题也是一个求最大流的例子。流量，这个问题也是一个求最大流的例子。最大车流量问题最大车流量问题 102374 t6598s3 35 512122 210106 61 15 58 88 87 79 99 93 32 22 27 7假设从城市s到城市t的公路网络上每段公路每天可以通过的汽车数4网络流问题网络流问题 定义定义1 1 设设G=(V,E)为有向图为有向图,在在V中指定一点中指定一点称为称为发点发点(记为记为vs),),和另一点称为和另一点称为收点收点(记为记为vt),),其余点叫做中间点其余点叫做中间点.对每一条边对每一条边vivjE,对应一个对应一个非负实数非负实数Cij,称为它的称为它的容量容量.这样的这样的G称为称为容量网容量网络络,简称简称网络网络,记作记作G=(V,E,C).定义定义2 2 网络网络G=(V,E,C)中任一条边中任一条边vivj有流有流量量 fij,称集合称集合 f=fij 为网络为网络G上的一个上的一个流流.满足下述条件的流满足下述条件的流 f 称为称为可行流可行流：(限制条件限制条件)对每一边对每一边vivj,有有0 fij Cij;(平衡条件平衡条件)对于中间点对于中间点vk有有fik=fkj ,即中间点即中间点vk的输入的输入量量=输出输出量量.网络流问题 定义1 设G=(V,E)为有向图,5弧旁数字：弧旁数字：容量容量(a)图是一个网络图是一个网络v2v5348v3v1v4v65106111735v2v5313v3v1v4v61536222弧旁数字：弧旁数字：流量流量弧旁数字：(a)图是一个网络v2v5348v3v1v4v656 cij fijvivjv2v53 14 08 3v3v1v4v65 010 56 311 617 43 25 3 cij fijvivjv2v53 147定义：设定义：设f是网络是网络N的一个流，则的一个流，则f的流的值的流的值val f 定义为定义为即流的值是发点集的流出量，也是收点集的即流的值是发点集的流出量，也是收点集的流入量。流入量。v2v53 14 08 3v3v1v4v65 010 56 311 617 43 25 3定义：设f是网络N的一个流，则f的流的值val f 定义为即8如何求最大流？如何求最大流？定义：设定义：设 是一个网络，是一个网络，f 是一是一个流，若不存在流个流，若不存在流 ，使，使则称则称f 为为N 的最大流。的最大流。如何求最大流？定义：设 9 设设=（x,u，v,A）是网络）是网络G中的一条初中的一条初等链并且定义链的方向是从等链并且定义链的方向是从x到到A。若。若D中有弧中有弧（u，v），与），与方向一致，则称（方向一致，则称（u，v）为链）为链 的前向弧，若的前向弧，若D中有弧（中有弧（u，v），则称），则称（v,u），为链），为链的后向弧。的后向弧。前向弧与后向弧前向弧与后向弧v2v53 14 08 3v3v1v4v65 010 56 311 617 43 25 3 设=（x,u，v,A）是网络G中的一10增广链增广链对可行流对可行流 f=fij：非饱和弧：非饱和弧：fij 0零流弧：零流弧：fij=0 链的方向：若链的方向：若是联结是联结vs和和vt的一条链，定义链的方向的一条链，定义链的方向是从是从vs到到vt。v2v53.34.18.3v3v1v4v65.110.56.311.617.23.25.2增广链对可行流 f=fij：非饱和弧：fij 11=(v1,v2,v3,v4,v5,v6)+=(v1,v2),(v2,v3),(v3,v4),(v5,v6)-=(v5,v4)v2v53.34.18.3v3v1v4v65.110.56.311.617.23.25.2非饱和弧：非饱和弧：fij 0饱和弧：饱和弧：fij=cij零流弧：零流弧：fij=0=(v1,v2,v3,v4,v5,v6)+=(v12定义定义3 设设 f 是一个可行流是一个可行流,是从是从vs 到到vt 的一条链的一条链,若若满满 足下列条件足下列条件,称之为一条增广称之为一条增广 链。链。(vi,vj)-0 fij cij 后向弧后向弧 是非零流弧，是非零流弧，(vi,vj)+0 fij cij 前向弧是前向弧是 非饱和弧，非饱和弧，v1v2v3v4v5v68 46 06 53 35 4定义3 设 f 是一个可行流,是从vs 到vt 的13割与最小割割与最小割若若 则则称为网络称为网络N 的一个割。的一个割。称为割称为割 的容量。的容量。若若设设K是一个割，若不存在割是一个割，若不存在割 ，使，使则则K为为N 的最小割。的最小割。割与最小割若 14最大流与最小割的关系最大流与最小割的关系定理：设定理：设f 是网络是网络N 的流，的流，是一个是一个割，则割，则v2v53.34.18.3v3v1v4v65.110.56.311.617.23.25.2最大流与最小割的关系定理：设f 是网络N 的流，15定理：设定理：设f 是流，是流，K是割，若是割，若 ，则，则f 是最大流，是最大流，K是最小割。是最小割。定理：网络定理：网络K的最大流的值等于最小割的容量。的最大流的值等于最小割的容量。定理：设f 是流，K是割，若 16如何求最大流？如何求最大流？定理：定理：f 是网络是网络N 的最大流的充要条件的最大流的充要条件是是N不含不含f-增广链。增广链。其中，其中，如何求最大流？定理：f 是网络N 的最大流的充要条件是N不含17寻求最大流的标号法（寻求最大流的标号法（FordFulkerson）从任一个可行流从任一个可行流 f 出发（若网络中没有给定出发（若网络中没有给定 f，则从零流开始），经过标号过程与调整过程。则从零流开始），经过标号过程与调整过程。（一）标号过程（一）标号过程寻求最大流的标号法（FordFulkerson）18标号：（前点标记，前点到该点的弧流量可调整量）标号：（前点标记，前点到该点的弧流量可调整量）开始，开始，vs 标上（标上（0，），），vs 是标号未检查的点，是标号未检查的点，其余点都是未标号点，一般地，取一个标号未检查的其余点都是未标号点，一般地，取一个标号未检查的点点vi，对一切未标号的点，对一切未标号的点vj。（1）若弧（）若弧（vi，vj）上，）上，fij0，则给，则给vj 标号标号(-i，l(vj)，l (vj)=minl(vi),fji,vj 成为标号而未检查的点。成为标号而未检查的点。fij0vivj(-i,l(vj)l(vj)=minl(vi),fji标号：（前点标记，前点到该点的弧流量可调整量）19 重复上述步骤，一旦重复上述步骤，一旦vt被标号，则得到一条被标号，则得到一条vs到到vt的的增广链。若所有标号都已检查过，而增广链。若所有标号都已检查过，而vt尚未标号，结束，尚未标号，结束，这时可行流，即最大流。这时可行流，即最大流。（二）调整过程（二）调整过程 从从vt 开始，反向追踪，找出增广链开始，反向追踪，找出增广链，并在，并在上进上进行流量调整。行流量调整。（1）找增广链）找增广链 如如vt 的第一个标号为的第一个标号为k（或或-k），），则弧（则弧（vk，vt）（或弧（或弧（vt，vk)。检查。检查vk 的第一个标号，若为的第一个标号，若为i（或（或-i），则），则(vi,vk)(或或(vk,vi)。再检查。再检查vi 的的第一个标号第一个标号,依此下去依此下去,直到直到vs。被找出的弧构成了增广。被找出的弧构成了增广链链。重复上述步骤，一旦vt被标号，则得到一条vs20（2）流量调整）流量调整令调整量令调整量 是是 l(vt)，构造新的可行流，构造新的可行流 f，去掉所有的标号去掉所有的标号,对新的可行流对新的可行流 f=fij,重重新进入标号过程。新进入标号过程。（2）流量调整令调整量是 l(vt)，构造新的可行流 f 21例例 用标号法求下图网络的最大流。弧旁的数字是用标号法求下图网络的最大流。弧旁的数字是(cij,fij)。v1v4v2vsv3(3，3)(5，1)(2，2)(6，2)(3，2)(2，2)(2,0)(6，3)(5，2)vt例 用标号法求下图网络的最大流。弧旁的数字是(cij,22解：解：第一轮第一轮 标号过程标号过程（1）vs标（标（0，+），），vs为已标号未检查点。为已标号未检查点。（2）检查）检查Vs，给，给v2标号（标号（vs，l(v2)）,vs成为已标号已检查的成为已标号已检查的 点，点，v2成为已标号未检查的点。成为已标号未检查的点。（3）检查）检查v2，给，给v1标号（标号（-v2，l(v1)）,同理给同理给v4标号为标号为(v2,1)，v2成为已标号已检查的点，成为已标号已检查的点，v1，v4成为已标号未检查的成为已标号未检查的 点。点。（4）检查）检查v1，给，给v3标号为（标号为（v1，2），），v3成为已标号未检查的成为已标号未检查的 点。点。（5）检查）检查v3，给，给vt标号为（标号为（v3，2）。因为）。因为vt已被标号，所以已被标号，所以 说明找到一条增广链。说明找到一条增广链。调整过程按点的第一个标号，以调整过程按点的第一个标号，以vt点开始，回溯找到一条增广点开始，回溯找到一条增广 链，链，如下图红线所示：如下图红线所示：解：第一轮 标号过程（1）vs标（0，+），23vtv1v4v2vsv3(3，3)(5，1)(2，2)(6，2)(3，2)(2，2)(2,0)(6，3)(5，2)在增广链上进行了流量调整。在增广链上进行了流量调整。前向弧前向弧 后向弧后向弧 于是调整后流量如下图所示。于是调整后流量如下图所示。vtv1v4v2vsv3(3，3)(5，1)(2，2)(6，24v1v4v2vsv3(3，3)(5，3)(2，0)(6，4)(3，2)(2，2)(2,0)(6，5)(5，2)vtv1v4v2vsv3(3，3)(5，3)(2，0)(6，4)25 第二轮：第二轮：标号过程标号过程（1）vs标（标（0，+），），vs为已标号未检查点。为已标号未检查点。（2）检查）检查vs，给，给v2标号（标号（vs，2），），v2成为已标号未检查成为已标号未检查 的点。的点。（3）检查）检查v2，给，给v4标号（标号（v2，1），），v4成为已标号未检成为已标号未检 查的点。查的点。（4）检查）检查v4，给，给vt标号为（标号为（v4，1），），vt被标，转入下一被标，转入下一 阶段。阶段。调整过程调整过程 根据标号过程，以根据标号过程，以vt点开始，回溯找到一条增广链，如点开始，回溯找到一条增广链，如 下图红线所示。下图红线所示。第二轮：26v1v4v2vsv3(3，3)(5，3)(2，0)(6，4)(3，2)(2，2)(2,0)(6，5)(5，2)增广链上的三个弧都为前向弧，于是调整如下：增广链上的三个弧都为前向弧，于是调整如下：于是新调整的流量如下图所示。于是新调整的流量如下图所示。vtv1v4v2vsv3(3，3)(5，3)(2，0)(6，4)27v1v4v2vsv3(3，3)(5，3)(2，0)(6，5)(3，3)(2，2)(2,0)(6，5)(5，3)第三轮第三轮 vs标（标（0,+），），v2标号（标号（vs，1），检查），检查v2点，标点，标号号 过程无法继续下去，于是说明了对于上图所示的新过程无法继续下去，于是说明了对于上图所示的新 流，不存在增广链，上图所示的流就是最流，不存在增广链，上图所示的流就是最 大流，算法大流，算法结束。结束。最大流量最大流量=5+3=8 vtv1v4v2vsv3(3，3)(5，3)(2，0)(6，5)28例例 用标号法求下图网络的最大流。弧旁的数字是用标号法求下图网络的最大流。弧旁的数字是(cij,fij)。解：（一）标号过程。解：（一）标号过程。（1）给）给vs标上（标上（0，）；）；v2v3v1vsv4vt(3，3)(4，3)(1，1)(5，3)(5，1)(2，2)(2，1)(1，1)(3,0)（0，）在弧（在弧（vs，v2）上，）上，fs2=cs2=3,不满足标号条件不满足标号条件。（2）检查）检查vs，在弧（，在弧（vs，v1）上，）上，fs1=1，cs1=5，fs10，给给v2标号标号 (-1,l l(v2),在弧（在弧（v1，v3）上，）上，f13=2，c13=2，不满足标号条件。，不满足标号条件。v2v3v1vsv4vt(3，3)(4，3)(1，1)(5，3)(5，1)(2，2)(2，1)(1，1)(3,0)（0，）（s，4）（-1，1）（4）检查）检查v2，在弧（，在弧（v3，v2）上，）上，f32=10，给给v3标号标号 (-2,l(v3),这里这里（-2，1）（3）检查v1，在弧（v2，v1）上，f210，给v2标30在弧（在弧（v2，v4）上，）上，f24=3，c24=4，f24c24,给给v4标号标号(2,l(v4),其中其中（5）检查）检查v3，在弧（，在弧（v3，vt）上，）上，f3t=1，c3t=2，f3tc3t，给给vt标号标号(3,l(vt),这里这里vt得到标号，标号过程结束。得到标号，标号过程结束。v2v3v1vsv4vt(3，3)(4，3)(1，1)(5，3)(5，1)(2，2)(2，1)(1，1)(3,0)（0,）（s，4）（-1,1）（-2,1）(2，1)(3，1)在弧（v2，v4）上，f24=3，c24=4，f24c2431（二）调整过程（二）调整过程：从：从vt 开始逆向追踪，找到增广链。开始逆向追踪，找到增广链。v2v3v1vsv4vt(3，3)(4，3)(1，1)(5，3)(5，1)(2，2)(2，1)(1，1)(3,0)（0,）（s，4）（-1,1）（-2,1）(2，1)(3，1)v2v3v1vsv4vt(3，3)(4，3)(1，0)(5，3)(5，2)(2，2)(2，2)(1，0)(3,0)（二）调整过程：从vt 开始逆向追踪，找到增广链。v2v3v32去掉各点标号，从去掉各点标号，从vs开始，重新标号。开始，重新标号。点点v1：标号过程：标号过程无法进行，所以无法进行，所以f 即为最大流。即为最大流。V（f）=3+2=5v2v3v1vsv4vt(3，3)(4，3)(1，0)(5，3)(5，2)(2，2)(2，2)(1，0)(3,0)（0，）（s，3）去掉各点标号，从vs开始，重新标号。点v1：标号过程V（f 33例例 2 下图中，从三口油井下图中，从三口油井、经管道将油输至经管道将油输至脱水处理厂脱水处理厂和和，中间经，中间经、三个泵站。已知三个泵站。已知图中弧旁数字为各管道通过的最大能力（吨图中弧旁数字为各管道通过的最大能力（吨/小时），小时），求从油井每小时能输送到处理厂的最大流量。求从油井每小时能输送到处理厂的最大流量。87654321201030102015302050102050 多源、多汇的最大流问题多源、多汇的最大流问题单源、单汇。单源、单汇。s208015t6050例 2 下图中，从三口油井、经管道将油输至脱水34最小费用流最小费用流有些网络中，最大流不是唯一的，有些网络中，最大流不是唯一的，那么在这些最大流中，费用最小的那么在这些最大流中，费用最小的那个值就称为最小费用流。那个值就称为最小费用流。上面讨论了网络最大流问题。在实际生活中人们不仅关心流量问题，还关心费用问题，即满足流量到达最大使总费用最小，这就是最小费用最大流问题。最小费用流有些网络中，最大流不是唯一的，那么在这些最大流中，35