资源预览内容
第1页 / 共65页
第2页 / 共65页
第3页 / 共65页
第4页 / 共65页
第5页 / 共65页
第6页 / 共65页
第7页 / 共65页
第8页 / 共65页
第9页 / 共65页
第10页 / 共65页
亲,该文档总共65页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
1,网 络 优 化,Network Optimization ,清华大学数学科学系 谢金星 办公室:理科楼2206# (电话:62787812) Email: ,清华大学课号:70420133,第6章 最大流问题 (Maximum Flow Problem) 第1讲,2,许多实际问题都可以转化为最大流问题,S,T,最大流问题的例子,公路交通网络:车流流量,3,定义6.1 在有向图G=(V,A)上定义如下的权函数: (1)L:AR为弧上的权函数,弧(i,j) 对应的权 L (i,j) 记为lij,称为弧 (i,j)的容量下界(lower bound); (2)U:A R为弧上的权函数,弧(i,j)对应的权U(i,j)记为uij ,称为弧(i,j) 的容量上界,或直接称为容量(capacity); (3)D:V R为顶点上的权函数,节点i对应的权D(i)记为di ,称为顶点i的供需量(supply/demand); 此时网络可称为流网络(Flow Network,一般仍简称为网络),记为 N=(V,A,L,U,D).,6.1.1网络中的流,di 0:供应点(supply node)或源(source)、起始点或发货点 di 0:需求点(demand node)或汇(sink) 、终止点或吸收点 di 0:转运点(transshipment node)或平衡点、中间点,4,定义6.2 对于流网络N=(V,A,L,U,D),其上的一个流(flow) x是指从N的弧集A到实数集合R的一个函数x:A R, 即对每条弧(i,j) 赋予一个实数 (称为弧(i,j)上的流). 如果流x满足,存在可行流的必要条件,则称x为可行流(feasible flow). 至少存在一个可行流的流网络称为可行网络(feasible network). 如果流x只满足容量约束(6.2), 但不一定满足流量守恒条件(6.1), 则称x为伪流(pseudoflow), 或容量可行流.,流量守恒/平衡条件,容量约束/可行条件,网络中的流,一般可以把L 0的流网络转化为L=0的流网络进行研究(思考?) 除非特别说明, 以后我们总是假设L=0,网络简记为N=(V,A,U,D).,5,运输网络的特点是只有源或汇,没有中间转运点. 显然,此问题有解的一个必要条件是,网络中的流,例 - 运输网络和运输计划,有一批货物从货源地运往目的地,假设货源集合为S,目的地集合为T. 货源i可提供的货物数量为ai个单位,目的地j对货物的需求量为bj个单位. 以(S,T)为节点集作完全二部图,以 ai ,- bj 为节点上的供需量。通过每条弧的运输量没有限制(非负即可)。 一个运输计划就相当于该网络中的一个流。,6,网络中的流,例6.1 有向网络中,令所有弧上的容量下界为0,容量(上界)为1,并令节点s的供需量为1,节点t的供需量为-1。 从s到t的一条有向路正好对应于网络中的一个可行流x (当xij =1时,表示弧(i,j)位于s-t路上, 当xij=0时,表示弧(i,j)不在s-t路上).,思考:网络中的任意一个可行流是否一定对应于一条有向路?,7,网络中的流,定义6.3 在流网络N=(V,A,U,D)中,对于流x, 如果某条弧(i,j)上的流量等于其容量(),则称该弧为饱和弧(saturated arc);如果某条弧(i,j)上的流量为0(),则称该弧为空弧(void arc).,如果所有弧均为空弧,即 则称x为零流,否则为非零流.,8,网络中的流,定义6.4对于给定流网络N=(V,A,U,D)中的流 x:A R ,如果N中存在一条有向路P,使得 , 则称x为路流(Path flow),v称为该路流的流值(流量). v=0时,称该路流为零路流,否则称为非零路流.,如果N中存在一个有向圈W,使得 , 则称x为圈流(Cycle flow),v 称为该圈流的流值(流量). v=0时,称该圈流为零圈流,否则称为非零圈流.,5,9,定理6.1 在网络N=(V,A,U,D)中,任何一个可行流可以表示为若干个路流和若干个圈流之和,且这些路流和圈流满足下列性质: (1)非零路流对应的有向路从一个源点指向一个汇点; (2)至多有m+n个路流和圈流为非零流,且其中至多有m个圈流为非零流.,流的分解定理 (Flow Decomposition Theorem),证明 (构造性) 记可行流为x,设i0是网络中的一个源点,则存在弧 (i0, i1) 使得 0.,在一个无源无汇的流网络中,一个可行流称为可行循环流。,推论 一个可行循环流一定可以表示为至多m个非零圈流之和.,如果i1是一个汇点, 则找到了从源点指向汇点的一条有向路. 否则从i1出发重复上述过程,直到找到一个汇点或再次遇到前面经过的某个顶点时为止, 即直到下列两种情况之一出现为止:,10,当找到一个路流时, 重新定义使得某个节点的供需量从非零成为零, 或者使得某条弧的流量从非零成为零. 当找到一个圈流时, 重新定义使得某条弧的流量从非零成为零.,对新网络,重复上述过程,直到所有顶点变成为转运点(平衡点).,然后,找到一个至少有一条出弧上的流量为正的顶点, 继续重复上述过程, 这时只有情形(b)会出现, 即一定获得一个非零圈流. 重复上述过程, 直到重新定义的流x成为零流为止.,(b)找到一个有向圈W. 此时,定义,(a)找到一条从一个源点i0指向一个汇点ik的有向路P. 定义,上述过程找到路流和圈流的次数之和不会多于m+n次,且其中找到圈流的次数不会多于m次.,11,单源单汇的网络,可行流x的流量(或流值)为v=v(x)= ds = - dt 如果我们并不给定ds 和dt, 则网络一般记为N=(s, t,V,A,U),容量可行且转运点流量守恒的流称为s-t可行流,有时为了方便也称为可行流. 最大流问题(Maximum Flow Problem)就是在N=(s, t,V,A,U) 中找到流值最大的s-t可行流 (即最大流).,6.1.2 最大流问题的数学描述,定理6.2 (整流定理) 最大流问题所对应的约束矩阵是全么模矩阵. 若所有弧容量均为正整数,则问题存在最优整数解.,12,引理6.1 任意一个s-t可行流流值不超过任意一个s-t割容量.,6.1.3 增广路定理,定义6.5 设S,T是网络N=(s,t,V,A,U)中给定的一个割,且sS,t T ,则称割S,T为s-t割. s-t割S,T中的弧(i,j)(iS,jT)称为割的前向弧,弧(i, j)(jS,iT)称为割的反向弧. s-t割S,T的容量定义为前向弧的容量之和,记为 一个网络中容量最小的s-t割称为最小割.,13,增广路,引理6.2 如果对于一个可行流存在增广路,则该可行流不是最大流.,定义6.6 设x是流网络N=(s,t,V,A,U)中给定的可行流,P是一条s-t路,则P中满足下列两个条件之一的弧(i,j)称为增广弧(augmenting arc): (1)弧(i,j)是P的前向弧且为不饱和弧;或 (2)弧(i,j)是P的反向弧且为非空弧. 如果P中的弧都是增广弧,则称P为关于流x的增广路, 简称增广路(augmenting path).,这一过程称为x 关于P的增广 (augmentation),14,证明 必要性可以由前面的引理直接得到. 下面证明充分性.,定理6.3 (增广路定理) 一个可行流为最大流的充要条件是不存在增广路.,增广路定理,假设流网络N=(s,t,V,A,U)中不存在关于可行流 x 的增广路,记网络中从 s 出发沿增广弧可以到达的节点集合为S, 令 T=VS, 则sS,tT,即 S, T 为 s-t 割. 并且, 对于A中的任意弧(i,j), 如果它是该s-t割的前向弧, 则 ; 如果它是该s-t割的后向弧, 则 =0.,引理6.1证明中的中间结果,因此,S,T为最小割,x为最大流.,定理6.4 (最大流最小割定理) 最大流的流值等于最小割的容量.,15,6.2 增广路算法,6.2.1 Ford-Fulkerson标号算法 (),基本思想:从任何一个可行流开始,沿增广路对流进行增广,直到网络中不存在增广路为止. 问题的关键在于如何有效地找到增广路,并保证算法在有限次增广后一定终止.,基本思想:标号过程来寻找网络中的增广路 pred(j):节点j 在可能的增广路中的前一个节点; maxf(j): 沿该可能的增广路到该节点为止可以增广的最大流量. LIST : 记录可能的增广路上的节点,16,STEP5. 转STEP3.,STEP3. 如果LIST 且maxf(t)=0, 继续下一步; 否则: (3a) 如果 t 已经有标号(即maxf(t)0),则找到了一条增广路,沿该增广路对流 x 进行增广(增广的流量为maxf(t),增广路可以根据pred回溯方便地得到), 转STEP1. (3b) 如果 t 没有标号(即LIST= 且maxf(t)=0), 转STEP1.,STEP4. 从LIST中移走一个节点i;寻找从节点i出发的所有可能的增广弧: (4a) 对非饱和前向弧(i,j),若节点 j 没有标号(即pred(j)=0),则对j进行标号,即令maxf(j) = minmaxf(i), uij- xij, pred(j)=i, 并将j加入LIST中. (4b) 对非空反向弧(j,i),若节点 j 没有标号(即pred(j) =0),则对j进行标号,令maxf(j) = minmaxf(i), xji, pred(j) =i, 并将j加入LIST中.,STEP1.若maxf(t) 0, 继续下一步; 否则结束.,STEP0. 置初始可行流 x(如零流); 对节点 t 标号, 即令maxf(t)=任意正值(如1).,STEP2. 取消所有节点 jV 的标号,即令maxf(j)=0, pred(j)=0;令LIST=s; 对节点 s 标号,即令maxf(s)=充分大的正值.,17,最大流流值为4,Ford-Fulkerson标号算法,例: (uij,xij),18,最大流流值为2*106,Ford-Fulkerson标号算法,例: (uij,xij),19,该算法是否一定在有限步内终止呢? 如果弧上的容量可以是无理数,可以举出例子说明标号算法不一定在有限步内终止;并且,这一增广路算法的极限过程得到的流的流值即使收敛,也不一定收敛到最大流,Ford-Fulkerson标号算法,标号算法终止时,网络中一定不再含有增广路.,如果所有弧上的容量都是正整数,根据整流定理,最大流v也是整数. 实际上,由于割s,Vs中前向弧的条数最多为n条,因此最大流v的上界为nU(U表示网络中弧上的最大容量). 由于每次增广至少使得流值增加1个单位,因此增广的次数不会超过v次,算法一定在有限步内终止. 此外,由于每次增广最多需要对所有弧检查一遍,因此算法的复杂度为O(mv),或表示为O(mnU). 伪多项式时间算法,而不是多项式时间算法.,20,定义6.7 对网络N=(s,t,V,A,U)中给定的s-t可行流x,网络N关于流x的残量网络N(x) = (s, t, V, A(x), U(x) , 其中A(x), U(x)定义如下: (residual network,又常称为增量网络或辅助网络 ),6.2.2 残量网络,讨论算法复杂度时,假定:弧(i,j)A时,弧(j,i) A;并假定在残量网络中A(x)=A,也就是说弧的条数和弧集合都不变. 这只要允许容量为0的弧仍然保留在网络中就可以了.,命题:若v*是原网络的最大流,则残量网络N(x) 中最大流为 v*-v(x).,其中称, uij(x)为弧(i,j)上的残留容量(residual capacity).,21,残量网络,例: (uij,xij),N(x)中的s-t有向路P, 对应于原网络N中的一条增广路 ; 直接称残量网络中的s-t有向路为增广路. 沿P可以增广
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号