北邮-通信网规划理论 第二章--电信网规划(三).ppt

通信网规划理论
制作人:孙青华
第二章电信网规划的基础知识
第二章电信网规划的基础知识
第一节图论基础知识
第二节随机服务系统及其在电信中的应用
第三节业务预测的基本方法
第四节流量预测的基本方法
第五节电信网规划中的评价准则
第六节电信网规划中的财务经济评价指标及经济分析方法
第七节多目标方法及其应用
第八节智能算法及其应用
3
网络流及其算法
网络的最大流及其算法
最小费用最大流算法
网络流的归并问题
4
1 网路的最大流及其算法
(1) 网路的最大流的概念
网路流一般在有向图上讨论
定义网路上支路的容量为其最大通过能力,记为 cij ,支路上的实际流量记为 fij
图中规定一个发点s,一个收点t
节点没有容量限制,流在节点不会存储
容量限制条件:0 fij  cij
平衡条件:
满足上述条件的网路流称为可行流,总存在最大可行流
当支路上 fij = cij ,称为饱和弧
最大流问题也是一个线性规划问题
vi
A(vi)
B(vi)
5
(2) 截集与截集容量
定义:把网路分割为两个成分的弧的最小集合,其中一个成分包含 s 点,另一个包含 t 点。
一般包含 s 点的成分中的节点集合用V表示,包含 t 点的成分中的节点集合用V表示
截集容量是指截集中正向弧的容量之和
福特-富克森定理:网路的最大流等于最小截集容量
作业:利用线性规划法求解最大流(通过软件或编程度实现)
6
(3) 确定网路最大流的算法——标号法
从任一个初始可行流出发,如 0 流
基本算法:找一条从 s 到 t 点的增广链(augmenting path)
若在当前可行流下找不到增广链,则已得到最大流
增广链中与 s 到 t 方向一致的弧称为前向弧,反之后向弧
增广过程:前向弧 fij=fij +q , 后向弧 fij=fij q
增广后仍是可行流
7
最大流最小截的标号法步骤
第一步:标号过程,找一条增广链
1、给源点 s 标号[s+,q(s)=],表示从 s 点有无限流出潜力
2、找出与已标号节点 i 相邻的所有未标号节点 j,若
(1) (i, j)是前向弧且饱和,则节点 j 不标号;
(2) (i, j)是前向弧且未饱和,则节点 j 标号为[i+,q(j)],表示从节点 i 正向流出,可增广 q(j)=min[q(i), cijfij] ;
(3) (j, i)是后向弧,若 fji=0,则节点 j 不标号;
(4) (j, i)是后向弧,若 fji>0,则节点 j 标号为[i,q(j)],表示从节点 j 流向 i,可增广 q(j)=min[q(i), fji] ;
3、重复步骤 2,可能出现两种情况:
(1) 节点 t 尚未标号,但无法继续标记,说明网路中已不存在增广链,当前流 v(f) 就是最大流;所有获标号的节点在 V 中,未获标号节点在 V 中,V 与 V 间的弧即为最小截集;算法结束
(2)节点 t 获得标号,找到一条增广链,由节点 t 标号回溯可找出该增广链;到第二步
8
最大流最小截的标号法步骤
第二步:增广过程
1、对增广链中的前向弧,令 f=f+q(t),q(t) 为节点 t 的标记值
2、对增广链中的后向弧,令 f=fq(t)
3、非增广链上的所有支路流量保持不变
第三步:抹除图上所有标号,回到第一步
以上算法是按广探法描述的,但在实际图上作业时,按深探法进行更快捷
一次只找一条增广链,增广一次换一张图
最后一次用广探法,以便找出最小截集
9
最大流最小截集的标号法举例
(s+,)
(s+,6)
(2,6)
(3+,1)
(4+,1)
(s+,)
(s+,5)
(2+,2)
(5,2)
(4+,2)
10