费用最小增广链课件.ppt

1、8.3 最大流问题最大流问题Maximal Flow ProblemCh8 网络模型网络模型 Network Model8.3 最大流问题最大流问题Maximal Flow Problem8.3.1 基本概念基本概念8145633810763图图8184图图618所示的网络图中定义了一个所示的网络图中定义了一个发点发点v1，称为源，称为源(source，supply node)，定义了一个，定义了一个收点收点v7，称为汇，称为汇(sink，demand node)，其余点，其余点v2，v3，v6为为中间点中间点，称为，称为转运点转运点(transshipment nodes)。如果有多个。如果

2、有多个发点和收点，则虚设发点和收点转化成一个发点和收点。图中的权是发点和收点，则虚设发点和收点转化成一个发点和收点。图中的权是该弧在单位时间内的最大通过能力，称为弧的该弧在单位时间内的最大通过能力，称为弧的容量容量(capacity)。最大最大流问题流问题是是在单位时间内安排一个运送方案，将发点的物质沿着弧的方在单位时间内安排一个运送方案，将发点的物质沿着弧的方向运送到收点，使总运输量最大。向运送到收点，使总运输量最大。Ch8 网络模型网络模型 Network Model设设cij为弧为弧(i，j)的容量，的容量，fij为弧为弧(i，j)的流量。的流量。容量是弧容量是弧(i，j)单位时间内的单

3、位时间内的最大通过能力最大通过能力，流量是弧，流量是弧(i，j)单位时单位时间内的间内的实际通过量实际通过量，流量的集合，流量的集合f=fij称为网络的流。发点到收点称为网络的流。发点到收点的总流量记为的总流量记为v=val(f)，v也是网络的也是网络的流量流量。图图618最大流问题的线性规划数学模型为最大流问题的线性规划数学模型为),(000max67475713121312jicfvfffffffffvijijmvmjvimmm所有弧所有中间点8.3 最大流问题最大流问题Maximal Flow ProblemCh8 网络模型网络模型 Network Model满足下列满足下列3个条件的流

4、个条件的流fij 的集合的集合 f=fij 称为称为可行流可行流 (1)0(,)ijijfci j所有弧(3)stsjitvvvff发点发点vs流出的总流量等于流入收点流出的总流量等于流入收点vt的总流量的总流量(2)mmimmjmvvffv所有中间点8.3 最大流问题最大流问题Maximal Flow Problem注：注：条件条件(2)和条件和条件(3)称为流量守恒称为流量守恒(conservation of flow)条件条件;若存在有流入发点的流和收点的流，应从式中减去，条件若存在有流入发点的流和收点的流，应从式中减去，条件(3)变为变为ssttsjisittjvvvvffffCh8

5、网络模型网络模型 Network Model链：链：从发点到收点的一条路线（弧的方向不一定都同向）称为链。从发点到收点的一条路线（弧的方向不一定都同向）称为链。从发点到收点的方向规定为链的方向。从发点到收点的方向规定为链的方向。前向弧：前向弧：与链的方向相同的弧称为前向弧与链的方向相同的弧称为前向弧;前向弧集合记为前向弧集合记为+后向弧：后向弧：与链的方向相反的弧称为后向弧与链的方向相反的弧称为后向弧;后向弧集合记为后向弧集合记为-增广链增广链:设设 f 是一个可行流，如果存在一条从是一个可行流，如果存在一条从vs到到vt的链，满足：的链，满足：1.所有前向弧上所有前向弧上fij0则该链称为增

6、广链则该链称为增广链,记为记为前向弧前向弧后向弧后向弧容量容量流量流量这是一条增这是一条增广链广链84469（5）(2)(3)(4)(6)8.3 最大流问题最大流问题Maximal Flow ProblemCh8 网络模型网络模型 Network Model基本步骤：基本步骤：Step2：对点进行标号找一条增广链。：对点进行标号找一条增广链。(1)发点标号发点标号（）(2)选一个点选一个点 vi 已标号并且另一端未标号的弧沿着某条链向收点已标号并且另一端未标号的弧沿着某条链向收点检查：检查：A如果弧的方向向前（前向弧）并且有如果弧的方向向前（前向弧）并且有fij 0，则，则vj标号标号:jfj

7、i当收点已得到标号时，说明已找到增广链，依据当收点已得到标号时，说明已找到增广链，依据vi 的标号反向跟的标号反向跟踪得到一条增广链。当收点不能得到标号时，说明不存在增广踪得到一条增广链。当收点不能得到标号时，说明不存在增广链，计算结束。链，计算结束。Step1：找出第一个可行流，例如所有弧的流量找出第一个可行流，例如所有弧的流量fij=08.3.2 Ford-Fulkerson标号算法标号算法8.3 最大流问题最大流问题Maximal Flow ProblemCh8 网络模型网络模型 Network ModelStep3：调整流量：调整流量(1)求增广链上点求增广链上点vi 的标号的最小值，

8、得到调整量的标号的最小值，得到调整量 minjj(2)调整流量调整流量),(),(),(1jifjifjiffijijij得到新的可行流得到新的可行流f1，去掉所有标号，返回到第二步从发点重新，去掉所有标号，返回到第二步从发点重新标号寻找增广链，直到收点不能标号为止标号寻找增广链，直到收点不能标号为止【定理定理8.18.1】可行流可行流f 是最大流的充分必要条件是不存在发点到是最大流的充分必要条件是不存在发点到收点的增广链收点的增广链 .8.3 最大流问题最大流问题Maximal Flow ProblemCh8 网络模型网络模型 Network Model8145633810763图图819(

9、10)(6)(3)(6)(3)(7)(0)(6)(1)4(3)(1)(7)【例例6.10】求图求图818发点发点v1到收点到收点v7的最大流及最大流量的最大流及最大流量【解解】给定初始可行流，见图给定初始可行流，见图8-198.3 最大流问题最大流问题Maximal Flow ProblemCh8 网络模型网络模型 Network Model8145633810763图图620(b)(10)(6)(3)(6)(3)(7)(0)(6)(1)4(3)(1)(7)2337第一轮标号：第一轮标号：c12f12,v2标号标号2cij=fij，v4、v5不能标号不能标号后向弧后向弧f320,v3标号标号3

10、=f32增广链增广链(1,2)，(3,2)，(3,4)，(4,7),+=(1,2)，(3,4)，(4,7),=(3，2)，调整量为增广链上点标号的最小值，调整量为增广链上点标号的最小值min，2，3，3，728.3 最大流问题最大流问题Maximal Flow ProblemCh8 网络模型网络模型 Network Model8145633810763图图821(10)(8)(1)(6)(3)(7)(2)(6)(1)4(5)(1)(7)调整后的可行流：调整后的可行流：8.3 最大流问题最大流问题Maximal Flow ProblemCh8 网络模型网络模型 Network Model8145

11、633810763图图822(10)(8)(1)(6)(3)(7)(2)(6)(1)4(5)(1)(7)4415第二轮标号：第二轮标号：Cij=fij，v4、v5不能标号，返回到不能标号，返回到v3增广链增广链(1,3)，(3,4)，(4,7)，调整量为，调整量为 min，4，1，518.3 最大流问题最大流问题Maximal Flow ProblemCh8 网络模型网络模型 Network Model8145633810763图图823(11)(8)(1)(6)(3)(7)(3)(6)yle=font-weight:normal;mso-fareast-language:ZH-CN(1)4(

12、6)(1)(7)调整后得到可行流：调整后得到可行流：8.3 最大流问题最大流问题Maximal Flow ProblemCh8 网络模型网络模型 Network Model8145633810763图图822(11)(8)(1)(6)(3)(7)(3)(6)(1)4(6)(1)(7)314第三轮标号：第三轮标号：增广链增广链(1,3)，(3,6)，(6,4)，(4,7)，调整量为，调整量为 min，3，1，2，4128.3 最大流问题最大流问题Maximal Flow ProblemCh8 网络模型网络模型 Network Model8145633810763图图825(12)(8)(1)(6

13、)(3)(8)(3)(6)(2)4(7)(1)(7)调整后得到可行流：调整后得到可行流：8.3 最大流问题最大流问题Maximal Flow Problem对图对图825进行标号，发现已找不到发点到收点的增广链，说明进行标号，发现已找不到发点到收点的增广链，说明已找到网络的最大流，网络的最大流量为已找到网络的最大流，网络的最大流量为 v=f12+f13=8+12=20Ch8 网络模型网络模型 Network Model无向图最大流标号算法无向图最大流标号算法:无向图不存在后向弧，可以理解为所有弧都是前向弧，对一端无向图不存在后向弧，可以理解为所有弧都是前向弧，对一端vi已标号另一端已标号另一端

14、vj未标号的边只要满足未标号的边只要满足 cijfij0 则则vj就可标号就可标号(cijfij).【例例】求下图求下图v1到则到则v7标的最大流标的最大流71292085148691316(10)(6)(10)(8)(2)(3)(7)(6)(5)(13)(0)(13)2399328.3 最大流问题最大流问题Maximal Flow ProblemCh8 网络模型网络模型 Network Model71292085148691316(12)(6)(10)(8)(4)(3)(7)(6)(7)(2)(15)377117129208514891316(12)(7)(10)(8)(4)(3)(7)(6

15、)(8)(13)(3)(16)V=29105668.3 最大流问题最大流问题Maximal Flow Problem1Ch8 网络模型网络模型 Network Model截截 集集:将图将图G（V，E）的点集分割成两部分）的点集分割成两部分)(1_11_11_1VVVVVvVvts，的弧集合箭头在，则箭尾在及并且、1_1VV称为一个截集，称为一个截集，截集中所有弧的容量之和称为截集的截量截集中所有弧的容量之和称为截集的截量。684412267964113223068.3 最大流问题最大流问题Maximal Flow Problem如下图所示，取点集如下图所示，取点集V1=v1,v3,=v2,v

16、4,v5,v6,v7对应的截集对应的截集为为)5,3(),4,3(),2,1(),(11VV10226),(11VVC截量1_VCh8 网络模型网络模型 Network Model68441226796401322106又如下图所示的截集为又如下图所示的截集为)6,5()4,5(),4,3(),4,2(),(11，VV219624),(11VVC截量又如截集又如截集)5,3(),4,3(),5,2(),4,2(),(11VV92214),(11VVC截量所有截集中截量最小者称为所有截集中截量最小者称为最小截集最小截集。【定理定理】最大流量等于最小截集的截量。最大流量等于最小截集的截量。8.3

17、最大流问题最大流问题Maximal Flow ProblemCh8 网络模型网络模型 Network Model8.3.4 最小费用流最小费用流问题的引出：问题的引出：最大流问题反映了网络通过物量能力的大小，而未最大流问题反映了网络通过物量能力的大小，而未考虑运送费用的多少，但实际上在网络考虑运送费用的多少，但实际上在网络G中运送物量中运送物量v(f)的方案可的方案可能很多，如果考虑费用的话，则必存在费用最小的方案能很多，如果考虑费用的话，则必存在费用最小的方案.(6,1)(2,1)(1,4)(2,1)(3,1)(3,2)(a)(6,1)(0,1)(6,4)(0,1)(0,1)(0,2)(b)

18、(a)图中费用图中费用 d(f)=16+23+13+41+12+12=23(b)图中费用图中费用 d(f)=16+46=30例如：下述两图为流量例如：下述两图为流量v(f)6，费用不同的两个运送方案，费用不同的两个运送方案Ch8 网络模型网络模型 Network Model1.1.数学模型数学模型ijijfdfd)(1)最小费用流问题：最小费用流问题：)()(.min)(*固定vfvtsfdfdijij的最小费用流的最小费用流称为流量称为流量 v(2)最小费用最大流问题：最小费用最大流问题：求求,的的最最大大流流量量为为设设*vG*)(.)(min)(vfvtsfdfdfdijij设网络图中设

19、网络图中G=(V,E,W),弧弧(i,j)的容量为的容量为cij0,弧的单位流量费弧的单位流量费用为用为dij0，设，设f=fij是一个可行流，则总费用为是一个可行流，则总费用为Ch8 网络模型网络模型 Network Model(1)制定一个总运量等于制定一个总运量等于15总运费最小的运输方案总运费最小的运输方案,属于最小费属于最小费用流问题用流问题(3,5)(6,4)(4,2)(3,4)(1,6)(2,3)(9,12)图图827(12,3)(2)制定使运量最大并且总运费最小的运输方案，属于最小费用制定使运量最大并且总运费最小的运输方案，属于最小费用最大流问题最大流问题8.3 最大流问题最大

20、流问题Maximal Flow Problem 图图827是一个运输网是一个运输网络图，将工厂络图，将工厂v1，v2及及v3的的物质物质(数量不限数量不限)运往运往v6，v4和和v5是中转点，弧上的数是中转点，弧上的数字为字为(cij，dij)。Ch8 网络模型网络模型 Network Model2.2.方法的形成：方法的形成：)()()(),()()(dfdfddddfdfdijijijijdddfdfdd即的费用为关于增广链称)(,)()()(2)结论：。的可行流中费用最小者是所有流量为可行流新的小者，则修正后得到的的所有增广链中费用最关于是，而的可行流中费用最小者是所有流量为如)()(f

21、vfffvf满足得可行流增量后时，沿如调整量,1ff的增广链，是关于可行流设f)1()(min)(*dd费用最小增广链费用最小增广链 ：*Ch8 网络模型网络模型 Network Model(3)解题思路：解题思路：最小费用流。时，可产生给定流量的如最大流的流量，则当调整到给定费用最小增广链者，且每次迭代找的是中费用最小为流量为如如果开始的可行流)()()0(*vfvff?用最小增广链待解决问题：如何找费3.3.找费用最小增广链方法找费用最小增广链方法(1)Dijkstra标号法标号法(2)Floyd算法算法Ch8 网络模型网络模型 Network Model第第1步步：取初始流量为零的可行流

22、：取初始流量为零的可行流f(0)0，令网络中所有弧的，令网络中所有弧的权等于权等于dij得到一个赋权图得到一个赋权图D，用，用Dijkstra算法求出最短路，这条算法求出最短路，这条最短路就是初始最小费用增广链最短路就是初始最小费用增广链。第第2步步：调整流量。在最小费用增广链上调整流量的方法与前面：调整流量。在最小费用增广链上调整流量的方法与前面最大流算法一样，前向弧上令最大流算法一样，前向弧上令jcijfij，后向弧上令，后向弧上令jfij，调，调整量为整量为=minj。调整后得到最小费用流。调整后得到最小费用流 f(k)，流量，流量 v(k)v(k1)，当当v(k)v时计算结束，否则转第

23、时计算结束，否则转第3步继续计算。步继续计算。第第3步步：作新的赋权图：作新的赋权图D并寻找最小费用增广链。并寻找最小费用增广链。8.3 最大流问题最大流问题Maximal Flow Problem最小费用流的标号算法步骤最小费用流的标号算法步骤:设给定的流量为设给定的流量为v,(1)对可行流对可行流f(k1)的最小费用增广链上的弧的最小费用增广链上的弧(i，j)作如下变动作如下变动 0,0ijijijijijijjiijijijdfcdfwwfcfCh8 网络模型网络模型 Network Model(3)如果赋权图如果赋权图D不存在从发点到收点的最短路，说明不存在从发点到收点的最短路，说明v

24、(k1)已是已是最大流量，不存在流量等于最大流量，不存在流量等于v的流，计算结束。的流，计算结束。8.3 最大流问题最大流问题Maximal Flow Problem第一种情形：第一种情形：当弧当弧(i，j)上的流量满足上的流量满足0fijcij时，在点时，在点vi与与vj之间之间添加一条方向相反的弧添加一条方向相反的弧(j，i)，权为，权为(dij)。第二种情形：第二种情形：当弧当弧(i，j)上的流量满足上的流量满足fijcij时将弧时将弧(i，j)反向变反向变为为(j，i),权为权为(dij)。不在最小费用增广链上的弧不作任何变动，。不在最小费用增广链上的弧不作任何变动，得到一个赋权网络图

25、得到一个赋权网络图D。(2)求赋权图求赋权图D从发点的收点的最短路，如果最短路存在，则这从发点的收点的最短路，如果最短路存在，则这 条最短路就是条最短路就是f(k1)的最小费用增广链，转第的最小费用增广链，转第2步。步。注：注：赋权图赋权图D D的所有权非负时，可用的所有权非负时，可用DijkstraDijkstra算法求最短路，算法求最短路，存在负权时用存在负权时用FloydFloyd算法。算法。具体使用方法如下：具体使用方法如下：Ch8 网络模型网络模型 Network Model(12,3)(3,5)(6,4)(4,2)(3,4)(1,6)(2,3)(9,12)s(10,0)(6,0)(

26、3,0)图图828(2,3)图图827(3,5)(6,4)(4,2)(3,4)(1,6)(9,12)(12,3)8.3 最大流问题最大流问题Maximal Flow Problem 虚拟一个发点虚拟一个发点vs，弧的费用等于，弧的费用等于0，容量等于以弧的终点为起，容量等于以弧的终点为起点弧的容量之和，得到一个发点一个收点的网络图，见图点弧的容量之和，得到一个发点一个收点的网络图，见图828。图图827是一个运输网络图，将工厂是一个运输网络图，将工厂v1，v2及及v3的物质的物质(数量不数量不限限)运往运往v6，v4和和v5是中转点，弧上的数字为是中转点，弧上的数字为(cij，dij)。Ch8

27、 网络模型网络模型 Network Model(7)求最小费用最大流求最小费用最大流:自学课本自学课本 P142页的内容页的内容(7)与与(8)。小结小结：求最小费用流的求最小费用流的基本思想基本思想从零流从零流(f(0)=0)的费用有向的费用有向图图D(f(0)开始，用求最短路的方法求出发点到收点的最小费用链，开始，用求最短路的方法求出发点到收点的最小费用链，0，并在，并在 0 上按最大流中的方法进行流量调整，从而新的可行上按最大流中的方法进行流量调整，从而新的可行流流f(1)必是最小费用可行流，若必是最小费用可行流，若 v(f(1)=v，则计算终止，否则重新，则计算终止，否则重新构造关于构

28、造关于f(1)的费用有向图的费用有向图D(f(1)，继续在，继续在D(f(1)上求出发点到上求出发点到收点的最小费用链收点的最小费用链 1，并在，并在 1上进行流量的调整上进行流量的调整，如此下去，如此下去，直至求出流量为给定量直至求出流量为给定量 v 为止。如果为止。如果 v 是最大流的流量，则此最是最大流的流量，则此最小费用流就是最小费用最大流，由此可知，小费用流就是最小费用最大流，由此可知，求最小费用流的方法求最小费用流的方法就是求最短路和求最大流方法的综合。就是求最短路和求最大流方法的综合。Ch8 网络模型网络模型 Network Model1.最大流的概念：容量、流量、可行流、最大流、前向弧、后最大流的概念：容量、流量、可行流、最大流、前向弧、后向弧、增广链、截集、截量、最小截量与最大流量的关系、最向弧、增广链、截集、截量、最小截量与最大流量的关系、最小费用流、最小费用最大流。小费用流、最小费用最大流。2.有向图、无向图最大流的有向图、无向图最大流的Ford-Fulkerson标号算法标号算法3.最小费用流、最小费用最大流的算法最小费用流、最小费用最大流的算法作业：作业：P150 108.3 最大流问题最大流问题Maximal Flow ProblemThe End of Chapter 8