通信网理论基础第二章_通信网拓扑结构分析3.ppt

2.3网络流量问题 n 网络的目的是把一定的业务流从源端送到宿端。流量分配的优劣将直接关系到网络的使用效率和相应的经济效益。网络的流量分配受限于网络的拓扑结构，边和端的容量以及路由规划等。本节中关于流量的内容均在有向图上考虑，并且均是单商品流问题，即网络中需要输出的只有一种商品或业务。通信网络的服务对象有随机性的特点,关于通信业务随机性特点将在下一章中考虑,本节中假设网络源和宿之间的流量为常量。n2.3.1基本概念n 给定一个有向图G=（V，E），c(e)是定义在E上一个非负函数，称为容量；对边eij，边容量为cij ，表示每条边能通过的最大流量。设f=fij是上述网络的一个流，若能满足下述二限制条件，称为可行流。na)非负有界性：0fijcij；nb)连续性:对端vi有：nv(f)=F为源宿间流fij的总流量。n式中流出vi的边的末端集合；流入vi的边的始端集合；n有n个连续性条件，共有2m+n个限制条件，满足上述二限制条件的流称为可行流。n需要解决的问题分为两类:n1最大流问题n 在确定流的源和宿的情况下,求一个可行流f,使v(f)=F为最大；n2最小费用流问题n 如果边(i,j)的单位流费用为di,j,流f的费用为:n所谓最小费用流问题:n 在确定流的源和宿的情况下,求一个可行流f,使为最小。n下面介绍割量和可增流路的概念。n设X是V的真子集，且vsX，vtXc，（X，Xc）表示起点和终点分别在X和Xc的边集合，这是一个带方向的反圈或割集,割集的正方向为从vs到vt。割量定义为这个割集中边容量的和:n对可行流fij:nf(X，Xc)表示前向边的流量和fij,n其中viX，vjXcnf(Xc，X)表示反向边的流量和fji,n其中viX，vjXcnn则源为vs宿为vt的任意流f有:n1.v(f)=f(X,Xc)-f(Xc,X)vsX，vtXcn对任viX:n对所有viX,将上述等式求和：n2.v(f)C(X,Xc)n由f(X,Xc)非负，可得：nn下面讨论可增流路的概念。n从端s到端t的一个路，有一个自然的正方向，然后将路上的边分为两类：前向边集合和反向边集合。对于某条流，若在某条路中，前向边均不饱和（fijfi,j，标vj为:(+，i，j)n其中j=min(ci,j-fi,j，i)i为vi已标值。n若（vj,vi）E，fj,i0，标vj为:(-，i，j)，n其中j=min（i，fj,i）其余vj端不标。n所有能加标的邻端vj已标，则称vi已查。n倘若所有端已查且宿端未标，则算法终止。nM3：若宿端vi已标，则沿该可增流路增流。nM4:返回M1。n上面的算法是针对有向图且端无限制的情况。若是有无向边，端容量及多源多宿的情况，可以进行一些变换，化为上述标准情形。这个算法的复杂度不是多项式的，但是经过简单改进后算法为多项式复杂度。n需要解决下面的情况：n1.端有容量限制；n2.无向边；n3.多源多宿；2.3.3最小费用流问题 n如果网络为图G=(V,E)，源端为vs,宿端为vt，边(i,j)的单位流费用为di,j，流f的费用为:n所谓最小费用流问题:n在确定流的源和宿的情况下,求一个可行流f,使为最小。n最小费用流问题是线性规划问题，但也可用图论方法求解,效率更高。对于它的存在性可以这样理解，流量为F的可行流一般不是唯一的，这些不同的流的费用一般也不一样,有一个流的费用最小。n寻找最小费用流，可以用负价环法算法(Klein,1967)。所谓负价环的意义如下:负价环为有向环,同时环上费用的和为负。负价环算法的具体步骤如下：nK0：在图G上找任意流量为F的可行流f;nK1：做流f的补图;做补图的方法如下:nK2：在补图上找负价环C-。若无负价环，算法终止。nK3：在负价环上沿环方向使各边增流n增流数：nK4：修改原图每边的流量，得新可行流。nK5：返回K1。n上面的算法中需要寻找负价环，这个可以通过FLOYD算法来解决。n例2.7：已知ci,j，di,j，要求F=9。求最小费用流。n上面可行流安排总费用为:=102。下面做补图,寻找负价环,调整可行流。n