第5章通信网中的流量优化

通信网理论基础通信网理论基础Reference:1.通信网理论基础2.图论与网络流3.运筹学基础11引论（通信网概述）引论（通信网概述）22网内业务分析网内业务分析33多址接入系统分析多址接入系统分析44通信网结构（图论基础）通信网结构（图论基础）55通信网中的流量优化通信网中的流量优化66通信网的可靠性通信网的可靠性第第55章章通信网中的流量优化通信网中的流量优化5.1流量优化的一般性问题5.2最大流问题5.3最佳流问题5.4线性规划简介（选）1.线性规划的标准型；2.单纯型解原理和计算步骤；3.对偶定理；4.罚款的应用；5.计算之例§5.1流量优化的一般性问题1．弧容量c(i,j)：在有向图G(V,E,L)中，对每条弧(i，j)赋的非负数值(或称权值)C(i，j)。2．流(也称为流型,f(i,j))：对图G(V,E,L)中每条弧(i，j)赋一非负权值f(i，j)，这个权值就称为该弧的流。;Ej)(i,0,j)f(i,j)c(i,;fst,-fst,;0ts,i0,,),(),(∈≥≥==≠===−∑∑是的网络流流入汇点条件为流出中间节点的网流恒条件的网为流出源点称条件t;流tisfstsifstijfjifjj3．可行流（连续性）(fst)若fst是网G（V,E,c,f）中从节点S到另一节点t的一个可行流，则可行流fst必须满足下列的守恒方程，即：§5.1流量优化的一般性问题[例]：考察网G(V,E,c,f)中各弧的容量和可行流型，并验证它是否满足流的守恒方程。其中S是源点，t是汇点，a,b,d,f是中间节点。Sacbdt2,11,11,12,11,04,11,02,13,03,11,14,1解：1.写出各弧容量是：c(s,a)=2,c(a,s)=1,……,c(t,a)=1;2.写出各弧的可行流型：f(s,a)=1,f(a,s)=1,……,f(t,d)=1;3.判断各弧的容量是否大于可行流型？即弧c(i,j)≥f(i,j)≥0？4.写出图G的完备关联矩阵Aa，列出可行流的矩阵守恒方程。流量分配（规划）研究的一般问题：1.最大流问题。改变可行流fij，使端到端总流量F最大。2.最佳流或最小费用流问题：图G每条边除了容量Cij外，还有费用aij，表示单位流所需费用。给定F，选择路由分配这个流量，即调整fij，使总费用最小。§5.1流量优化的一般性问题min[]min{}ijijijeEafφ∈=∑§5.2最大流问题一、基本概念1、S-t割(记为C)设图G节点集V=X∪X，其中点S∈X，t∈X，s-t割是指G中所有（X，X）弧的集合。22、、ss--tt割容量割容量∑∈=),(),(),(),(XXyxyxcXXCs-t割(X，X)的容量定义为：)},({)(minminiiiXXCCC=最小s-t割Cmin是最小的s-t割容量ss--tt割例题割例题[例]：求下述网G中可能的s-t割和s-t割容量。sbat-3,-11,01,04,31,11,12,2注：G边赋值（容量，流量）解:1.若X1={s}，则X1={a,b,t}，则s-t割(X1,X1)={(s,a),(s,b)};4.若X4={s,a,b}，则X4={t}，则s-t割(X4,X4)={(a,t)};3.若X3={s,a}，则X3={b,t}，则s-t割(X3,X3)={(s,b),(a,b),(a,t)};2.若X2={s,b}，则X2={a,t}，则s-t割(X2,X2)={(s,a)};4、可增流（流增广路径）定义：在网G(V,E,c,f)中，若节点s到t的路径为Pst，沿Pst从节点s到t的所有前向弧不饱和，即f(i，j)C(i，j)，且所有逆向弧的流都是正值，即f(i，j)0，称路径Pst为流fst的增广路径。33、最大流最小割定理、最大流最小割定理)},({}max{maxminiiiXXCfstf==⎪⎪⎩⎪⎪⎨⎧==;..............................),(;..............................)XC(X,;..............................0;)X(X,,0),(饱和弧非饱和弧正弧弧为零弧称所有XXCXXf定义：对于网G中的任意s-t割),,(XX5.5.最大流最大流),(maxXXCf=即性质：当且仅当fst不存在增广路径时，流f最大.[例]：已知网G(V,E,c,f)如下，求节点s到t的最大流。Sacbdt2,21,01,12,01,14,31,02,23,13,31,14,4解：①若X={s,a,b},则X={c,d,t}，s-t割容量C(X,X)=1+1+4=6;(X,X)的路径有流增广路径。②若Y={s}，则Y={a,b,c,d,t},s-t割容量C(Y,Y)=2+2=5;(Y,Y)路径无流增广路径。节点s到t的最大流fmax=5。二、福特二、福特--福克森福克森((FordFord--Fulkerson)Fulkerson)，，MM算法算法(一)、M算法思想：寻找源—宿端流可增广路径，使网络的流量得到增加，直到最大流为止。算法分2个过程：1是标记过程，通过标记过程找到一条可增广路径；2是增广过程，即沿增广路径增加网络流量的过程。标记：(+，x，w)或(−，x，w)表示，其中x∈V，w是标记值。M算法中图G的节点标记有三种情况：1.未标记节点：所有未赋标记的节点；2.未检查的标记节点：如果节点x已有标记，但其邻接节点y没有完全标记，则x称为未检验的标记节点；3.已检查的标记节点：若节点x已标记，x所有邻接的节点都已标记，则x称为已检验的标记节点；((二二))、福特、福特--福克森算法福克森算法1．标记过程第1步：对源节点S标记(+,s,∞)；第2步：任选一个未检查的标记节点x，对与x邻接未标记节点y：(a).对所有(x,y)∈E的未标记节点y，若f(x,y)C(x,y)，则对节点y标记(+,x,w(y))，其中w(y)=min[w(x),c(x,y)−f(x,y)]。(b).对所有(y,x)∈E的未标记节点y，若f(y,x)0，则对节点y标记（−,x,w(y)），其中w(y)=min[w(x),f(y,x)]；在x的标记+或-上加上圆圈，x就成为已检查的标记节点。第3步：A.若目的节点t被标记，则转至算法的增广过程；B.若节点t虽然未被标记，但标记过程不能继续下去，就结束算法；否则，就返回标记过程的第2步。二、福特二、福特--福克森算法福克森算法（续）（续）2．增广过程第1步：设节点Z=t，转至下面的第2步；(逆向增广)第2步：若Z的标记(+,q,w(t))，或(⊕,q,w(t))，将流f(q,z)变成f(q,z)+w(t)；若Z标记(−,q,w(t))，或(Θ,q,w(t))，将流f(z,q)变成f(z,q)−w(t)；第3步：若q=s，取消网G中所有节点的标记，并转至算法标记过程第1步，进行下一次迭代过程；若q≠s，设q=Z，返回增广过程第2步。(三)、算法复杂度在一次迭代中，标记过程需比较：(n−1)+(n−2)+…+1=0.5n(n−1)次;在增广过程的第2步需进行加法/减法运算为：≤(n-1)次；若网络可增的最大流量为fst，则算法复杂度为O(fst•n2)。[例]：试用福特-福克森算法求网G(V,E,c,f)节点S至t的最大流。Sacbdt2,11,11,12,11,04,11,02,13,03,11,14,1(+,S,∞)(+,S,1)(+,S,2)(−,a,1)(+,d,1)(+,d,1)+1-1+1解：1.用标记过程寻找第1条流增广路径，先标记S节点，(S,+,∞)流增广路径为：S→a→d→t，沿该路径增加1个单位流量。Sacbdt2,11,11,12,11,04,11,02,13,03,11,14,1(+,S,∞)(−,S,1)(+,S,2)(+,b,2)(+,b,1)(+,d,2)+1+2+1+2−1+22.用标记过程寻找第2条流增广路径，先标记S(S,+,∞)流增广路径为：S→b→d→t，增加2个单位流量。流增广路径为：S→a→b→C→t，增加1个单位流量。3.用标记过程寻找第3条流增广路径，先标记S(S,+,∞)Sacbdt2,11,11,12,11,04,11,02,13,03,11,14,1(+,S,∞)(−,S,1)(+,a,1)(+,b,1)(+,b,1)(+,c,1)+1+2+1+2−1+2−1+1+1+1Sacbdt2,11,11,12,11,04,11,02,13,03,11,14,1(S,+,∞)+1+2+1+2−1+2−1+1+1+14.用标记过程寻找第3条流增广路径，先标记S(S,+,∞)由于标记过程不能继续下去，网中再无流增广路径，因此算法中止。最后求得最大流fmax=5。最小割容量C({s},{t,a,b,c,d})=5。MM算法推广算法推广1.1.无向网和混合网中的最大流无向网和混合网中的最大流在无向图或混合网G‘中，无向边(x,y)可理解为：C(x,y)=c(y,x)；c(x,y)≥f(x,y),c(x,y)≥f(y,x)且f(x,y)•f(y,x)=0。求无向网或混合网G’中最大流的一般过程为：1．先将混合网G’(V,E’,c’,f)中的每条无向边变换成一对有向边（x,y)和(y,x)；且c(x,y)=c(y,x)=c’(x,y)。2．为了保证混合网G’(V,E’,c’,f)的无向边的流量只在一个方向上流动，且满足可行流条件，即在有向网G(V,E,c,f)中，满足：max[f(x,y)，f(y,x)]=f’(x,y)，且f(x,y)•f(y,x)=0；3．应用前面介绍的求最大流方法，求有向网G的最大流fmax。4.应用公式f’(x,y)=max[0,f(x,y)−f(y,x)]，构造原网G’可行流型。[[例例]]：求下列混合网的最大流。：求下列混合网的最大流。解：(1)首先将上图的混合网G’变换成有向网G。Sacbdt2,21,01,02,01,14,11,12,23,23,01,04,0(+,S,∞)(+,s,3)(+,b,3)(+,d,3)3+33(2)求出G网的最大流：用福特-福克森算法寻找流增广路径，求出网G的最大流fmx=C(X，X)=C({s}，{a,b,c,t})=2+3=5；(3)根据G网求得最大流时各弧的流量，应用公式f’(x,y)=max[0,f(x,y)−f(y,x)]，重新确定原网G’中无向边的流量：2，02.2.节点节点--弧限容量网的流弧限容量网的流(M(M算法推广）算法推广）求节点-弧限容量网最大流方法：把节点弧容量网G转化为弧限容量网G’，在G’中求出最大流，即是G网的最大流。对每个节点和弧有：可行流存在的条件;h(i)≥f(i,v),i≠t,(i,v)∈E;h(t)≥f(t,v),(t,v)∈E;求节点-弧限容量的一般过程：1．在节点-弧限容量网G(V,E,c,f)中的每一节点i，对应仅有弧限的容量网G’(V’,E’,C’,f’)中的两点i’，i’’,其中i’，i’’∈V’；2．G网中的弧(i,j)∈E，则对应G’中的弧(i’,j’’)∈E’；同时，G’网中弧容量为：C’(i’,j’’)=C(i,j);C(i’’,i’)=h(i),i∈V；3．对弧限网G’，用前面介绍的福特-福克森算法求G’网中s’’到t’的最大流fmax，这即是网G的最大流。[[例例]]：考察下述网：考察下述网G(V,E,c,G(V,E,c,ff))，，求其最大流。求其最大流。sabt34123214234解：(1)将节点-弧限容量网G转换为弧限容量网G’，求s’’到t’最大流；s''s'a''a't''t'b''b'43344211223最后，求出从s到t的最大流也为fmax=4。用Ford-Fulkerson算法找到第1条流增广路径：S’’→S’→a’’→a’→t’’→t’增广3单位流；沿S’’→S’→b’’→b’→t’’→t’增广1单位流。3.3.多源多宿最大流问题多源多