通信网结构第三节.ppt

1 3 流量问题 网的工作 把一定的业务流从源送出 网的控制流量控制、路由控制、计费控制 流 量泛指传输速率 控制目标流量最大、分配合理、提高效率、 充分利用资源 不任意性受限于网的拓扑。在某些条件限 制下的优化问题 优化问题最大流，最小代价。 2 一、一般问题 对G=V,E (n,m) : Cij边容量 fij边流量 fij一组流，可行流 F源宿间fij的总流量 流满足二条件： a)非负有界：0fijCij 边上，共有2m个条件 b)连续性: 3 4 对端vi有： 式中 （vi）=vj: ( vi, vj)E 流入vi (vi）=vj: ( vj, vi)E 流出vi 有n个连续性条件 共有2m+n个限制条件 满足上述二限制条件的流称为可行流。 可行流不止一个。（举例） 5 流量优化所研究的问题： a) 网络拓扑已定，cij已知，给定源vs与宿vt在二个限 制条件下，求vsvt的最大流量Fmax(2m+n2个条件) （最大流量问题（源宿间） b) 网络拓扑已定，cij已知，单位流量通过边( vi, vj) 所需的代价ij(代价系数)已知，给定流量F。寻求总 代价中最小的可行流fij，其中 =ijfij （最小代价流，或最佳流量分配问题） 若ij 与fij无关，即常数，为fij的线性函数，求 min仍是线性规划问题 若ij 是fij的函数，则与fij 为非线性关系，求解 min 复杂 6 c)网络拓扑未定，给定端集V及端间流量 F1,F2,Fn ，要求以最小代价规划边集E 更广泛的问题 一般，a）、b)前二问题除线性规划外，还有一些 图论算法，易于计算机编程。问题c)较为困难。 7 二、源宿间的最大流量 1.割量：设X是V的真子集，且vsX，vt （X, ）表示使vs,vt分离的割集，方向vsvt 其边分二类: 前向边：与割方向一致的边 反向边：与割方向相反的边 割量定义为前向边容量和 对可行流fij: f(X, )表示前向边的流量（和）fij f( ,X)表示反向边的流量 (和) fji 8 性质： 1) F=f(X, )f( ,X) 证： 对任意viX : 对所有vsX求和上式： 9 10 S: fs1+fs2+fs3 无 1: f14 fs1+f21 2: f21+f23 fs2 3: f3t fs3+f23+f53 f14+f3tf53= f(X, )f( ,X)=F 11 2） 由1）及 非负 12 2.路与可增流路 l路上可能有前向边，反向边 l可增流路径: 前向边均不饱和（fij fij ，则标vj (+,i,j) 其中j =min(cij-fij ,i ) i 为vi 已标值 若（vj vi ）E，且 fji 0, 则标vj (,i,j) 其中j =min（i ，fji ） 其它vj 不标。 所有能加标的邻端vj 已标，则vi已查。倘若所有端已 查且宿端未标，则算法终止。 M3：若宿端vt已标，则沿该路增流。 M4: 返回M1。 21 例: 22 初始令fij =0 标源端vs ：（+,s,）查该端，即标邻端 查vs ：v1（+,s,5） v2 （+,s,1） v3（+,s,3） vs已查 选查v2：标v3（+,2,1） vt（+,2,1）得vsv2v t 增流1：fs2 =1, f2t =1 标vs ：（+,s,），查vs ：标v1 ：（+,s,5） v3 ：（+,s,3） 查v3：标vt ：（+,3,3）得vsv3vt 增流3：fs3 =3， f3t=3 23 标vs ：（+,s,），查vs ：标v1 ：（+,s,5） 选查v1：标v2 ：（+,1,5） 查v2：vt ：（+,2,2） v3 :（+,2,2） 增流2：fs1=2，f12=2, f2t =3 标vs ：（+,s,），查vs ：v1 （+,s,3） 查v1：v2 （+,1,3） 查v2：v3（+,2,2） 查v3：vt ：（+,3,2）得vsv1v2v3vt 增流2：fs1=4，f12=4, f23 =2，f3t=5， Fmax=8 ij= fs1=4,f32=1,fs3=3,f12=4,f23 =2,f2t=3,f3t=5 24 几点推广: 无向图 在M算法中，若令边容量Cij=1，则最大流量 即源宿向不共边有向径权目，即使源宿分离的 应去的最少边数，即图的结合度 25 端容量(转接能力) 多源多宿 如果求多源多宿流量总会最大， 则对上图用M算法，但仍为单商品问题。 26 三、最佳流量分配 最大流，只要求满足限制条件下控制流量最大, 但不一定是费用最省的流。 最佳流量分配最小费用流流量控制的优化 问题 经典问题：给定网结构G=(V，E)，边容量Cij， 流量Fst。边代价系数aij。求解一组可行流fij， 使总费用最小 27 也属线性规划问题，但可用图论方法求解 可能性： 流量为Fst的可行流一般不是唯一的， 未饱和边可增流，饱和边可减流，满足条件。 条件：二端间有二条以上径存在，且不饱和 算法：负价环法 =62+12+11+56+64=69 28 =62+32+31+36+64=63 29 负价环法的步骤： K0：在图上找任一流量的Fst的可行流 K1：做流量补图 K2：在补图上找负价环 。若无负价环， 算法终止。 K3： 在负价环 上沿环方向使各边增流，