第12讲分析与优化篇part4网络系统

常见问 最大流问 最小费用流问

问题内问题示标记法(直接从起始点S度： 0，显

表示从的起点S到节点K的支路，在节点1附近的方框中标记0

然后找与起点S相邻的各节点中最近的一个节点r，这以 L中去找 是从起点到这一点的直接支路距离，无直接支路者标以∞L与1相邻的有节点2和3 6;

Min(L',L')Min(6,2)2

用数字2标记节点3，并加粗支路

Min(L', 32 Min(L', 32)Min(6,21)L14Min(L14,L13d34)Min(,28)' , dMin{L12,L14}Min{3,10}Min{L12,L14}Min{3,10}3 Min(L', Min(L',L d )Min(10,34) 这样就得到了最短路径（粗线1→3→2→4，长度为7标记法（计算机（）给每个节点T(或永久标记(，T的最短路径长度的上界，P T0(2)=∞T0(3)=∞T0(4)=进行第一轮标T1(2)MinT1(2)Min[T0(2),P(1)d12]Min[,06]

所以对节点3进行永久标记，即再以上面永久标记为基准，进行第二轮in[T 1

重复上一步，得P(4)=T3(4)=7，永久标记值就是最短路径通过占优序号回溯可得到4→2→3→1，即1→3→2→4就是最短路径设备更新问备购进后，维修费为第1年5000元，第2年6000元，第3年8000元，第4年11000元，第年元。这个工厂使用这个设备年，究竟买进后连续用5第1

①②③④

数值dij表示连购 jjdijmkk

① ② ③ ④ Pi是第i年的购置 m则是到第K

⑤ 18 ⑥ 0 初始值P(1)=0，T0(i)=∞

第一轮标

T1(3)22,PRIOR1(3)1;T1(4)30,PRIOR1(4)T1(5)41PRIOR1(5)1;T1(6)59PRIOR1(6) 第二轮标记：T(3Min[22,161622PRIOR(3 T2(4)Min[30,1622]30,PRIOR2(4)T2(5)Min[41,1630]41,PRIOR2(5)T2(6)Min[59,1641]57,PRIOR2(6)第三轮标T3(4)30,PRIOR3(4)1;T3(5)41,PRIOR3(4)T3(6)53,PRIOR3(6)第四轮标T4(5)Min[41,3017],PRIOR4(5)T4(6Min[53,3023PRIOR4(64或第五轮标T5(6Min[53411853PRIOR5(64或可得到最短路径：1→3→6或者 也可以在第1年买进，用3年，第4年在更新，用两年，这时总投资 可见两个方案效果是一多起点多终点问有时候我们不止需要从一个起点到一个终点的最短路径多个起点到多个终点以标记法的例子为①②③

①②③3① 3

① 105D[dij]② 5

[d]② 4③ 8

③ 0 ④ 0如果要想知道经过两步到某一节点的最短距离可以计D(2)[d(2)],其中d(2) d],(k 同样可以计算D(3)，它的各元素d(3)Min[d(2)d],(k 一直算到这样便得到任意两点间的最短距对于有回路的网络与无向网络，也有相应的方法，而上述矩阵运是通用的还有一类最短路径问题，是依次（不重复）走遍各节点（走一环路使路径最短。这类问题称为“旅行商问题”，后面结合启发式算法讲。3对于连接节点i和j的支路，从i到j的流量用

x(i,j)x(j,i)jS

fx(s,2)x(s,3)x(4,t)x(5,t)x(6,t)求最大流问题，就是求Maxf3265559f265559fs44ft9445356Ss(s,3)Ss(s,3)(2,5)2,(s,2)(3,4)(3,2)(2,5)(2,4)(3,4)(2,5)(4,5)(4,6)(4,t)t(4,t)(5,t)2,4,5,(s,2)(3,2)(3,4)s,2,3,(s,3)(4,6)(4,t)s,2,5,(s,2)(3,2)(4,5)(4,6)3,4,(s,3)(2,4)(3,6)(4,6)(4,t)。如图所示进行了一个切割，从S通过L到 称为割元，这里有(,3)、(2,4)、(5,t)3网络拓扑结构分={3,4,5,6,t该定理可以支持使用枚举法3一般来说，从S到的净流量f x(i,j) x(iS, iS,由于x(i,j)≤C(i,j),且x(i,j)≥0，其中C(i,j)为i到j的最大流f x(i,j) x(j,i) C(i,iS, iS, iS,显然，只有当≤取等式时，f取最大值，此f C(i,iS,

iS,

x(j,i)即当最大流情况出现时，从SS各支路流量为0S

的各支路流量x(i,j)必定饱和,而从到 x(j,3算法（标记法先给源节点以标记(-,∞)，-表示开始，∞表示进入s的流 。时s节点已经是标号但未检查的节对任一节点j的标记法如下优先考虑流入量，若i到j的 初始流量小于最大流量，则节点j以记(i+,ε(j))，其ε(j)=Min{ε(i)，[C(i,j)-无流入量则再考虑流出量，若j流向i的 ，则给节点j以记(i+,ε(j))，其如对应不同i有不同的ε(j)值，则选择其中最大的一个作为标记ε(j)过这样处理后j就成了已标记3算法（标记法如果汇节点t还未标记，就一直按(2)做下去，直到t点已标上(n+,ε(t))止然后按反向查找的办法，去找出经过(2)扩充（路径方向与流出方向一致就增加，反之减少）一直做到找不到流量。2652655(-59fs44ft94453563算例18

92

35

8

92

35x(-

7

5 9

(-

7

5 9

3算例8

1

92

35

8

92

35x(-

7

5 9

(-

7

5 9

x→2→3算例

18

92

35

3

7

5 9

(-

87

5 9

5

y

(-

87

5 9

5y 3算例8

92

3

5

18

92

35x(-

7

5 9

(-

7

5 9

18

92

35

x

7

5 9

419193 5x52y 72943算例18

92

35

8

92

5x(-

7

5 9

(-

7

5 9

18

92

35

7

5 9

19193 5x52y 7294

已知fmax代价条件dij（费用 流量约束条问题：找到一个可行流f的流量：f=f0＜=fmax使其代价最小，即思路：1）按照代价条件，选择最短路径进行容量扩充（与求最大流的骤类似）2）将代价最短路径上的饱和弧视为断路，重新按1（先把代价最低的走完），直至不已知fmax代价条件dij（费用

流量约束条

取最短路的流量x该路的饱和弧(i,j1①—③—⑤—73③—2①—④—⑥—853①—②—⑤—83②—4①—③—⑥—92⑥—5①—③—⑥—⑤—1已知fmax

代价条件dij（费用 流量约束条最短路的流量x该路的饱和弧(i,j1①—③—⑤—73③—2①—④—⑥—853①—②—⑤—83②—4①—③—⑥—92⑥—5①—③—⑥—⑤—1已知fmax

5533 代价条件dij（费用

流量约束条最短路的流量x该路的饱和弧(i,j1①—③—⑤—73③—2①—④—⑥—853①—②—⑤—83②—4①—③—⑥—92⑥—5①—③—⑥—⑤—1已知fmax

223 3代价条件（费用 流量约束条最短路的流量x该路的饱和弧(i,j1①—③—⑤—73③—2①—④—⑥—853①—②—⑤—83②—4①—③—⑥—92⑥—5①—③—⑥—⑤—1已知fmax

551代价条件（费用 流量约束条1最短路的流量x该路的饱和弧(i,j1①—③—⑤—73③—2①—④—⑥—853①—②—⑤—83②—4①—③—⑥—92⑥—5①—③—⑥—⑤—1实际流 辆网络特定时间内完成规定功能（保持连通），尽量好地(多、大容量、及时等)完成功能。传统可靠性理论的局限种特性；网络可靠性的评价体

网络可靠性的评网络抗毁性（双端 CHminCH

CN

网络抗毁性（示例1abs1abseTc2dSb3a1dfgc2eT d

网络生存性（两端1s1sT213S2T 网络生存性（两端算例路集:链路的集合，当集合中所有链路都完好时，两端（S-T）最小路集：路集中任意去掉一个链路就不再是路集，该路集就是示例的最小路集为：{a,c}、

aa1cseTbd2网络生存性（两端算例示例的最小路集为：{a,c}{b,d}、{a,e,d}、只要任意最小路集存在，两端S-T之间就保持连设“两端S-T之间就保持连 为S,S(ac)(bd)(aed)S-T之间就保持连R

1 2m相 的概率计mRsP(S)P(Ai P(Ai)P(AiAj) im(1)m1P(Aim

P(AiAjAkmijkm相 概率计算的不交mRsP(S)P(mm1 P(A1)P(A1A2)P(A1A2A3)P(Ai节点故障的处a1a1cseTbd2111a1cSTseTS b22d22

网络生存性（全端网络生成树的算法（破圈法AsTBAsTBAAsTBAsTBAsTBAsTBAsTBAsTBAsTBAsTBAsTBAsTBAsTBAsTBAAsTBAsTBAsTB网络有效。网络有效性（示例

sTsTBAsTB

sAs

AAT0B

B

网络有效性（算法输入数据:网络节点总数n，流量矩阵(C)，起点号点号络中弧的条数h。

用指数分布随量的随机抽样 -1/λInη，产生每条弧或每个节点的故障时ti(i=1,2,……，h+n)

对ti(进行排确定出h条弧n个节点故障的次序。

依次计算ti时刻网络的最大值。

确 将时仿 点依测 与ti时 行比段 以确在 这些中 的最匀 流点

计算多仿 仿 绘次 是求 有达 的 度要 大 线 的值否旅行商问题（TSP问题蚁群寻找食物时总能找到一条从食物到巢程中，会在它经过的留下一种特殊的信息素，并且其他A BA BDC蚂蚁从A点出发，速度相同，食物在D点，可能随机选个时间单位行走一步，本图为经过9个时间单位时的情形：A BA BDC本图为从开始算起，经过18个时间单位时的情形：走36DABD2趟4个单位，而AC了一趟，每一处的信息素为22：1。ABD（共2只），而ACD12431。ACD路线上仍然为一只蚂蚁。再经过36个时间单位后，两条线的信息ACDBD正反馈效应。决最优化问题，如TSP问题 TSP问题的蚁群算蚂蚁在寻找过，或者找到一个解后，会评估该解的在节点的信息，计算出下一步可达节点的选择概率，并TSP问题的蚁群算—基于图的蚁群系统（graph-basedantsystem,Step0n个城市的TSP问题可以理解为有向图G(N,A)，其中N={1,2,…,n},A={i,j|i,j∈N}城市间的距离矩阵为(dij)n×n，好解是w=(1,2,…,n)。Step1（外循环）如果满足算法的停止规则，则停止计算并TSP问题的蚁群算STEP2(内循环)按蚂蚁1≤s≤m的顺序分别计算。当蚂蚁在城市i，若L(sN或者{l|(i,l)∈Al∈L(s)}=φ,完成成第s只L(sN且Tl|ilAlL(s{i0

ij(k

,j

0,jij(k {j},i:到达j，L(s){j},i:L(s)N且Tl|i,lA,lL(s)}{i0则到达i0,i0,L(s) {i0},i:i0;重复STEP2TSP问题的蚁群算若目标函数f(L(t))<f(L(W))，则W:=L(t)。用如 对(k)(1 )(k1)

k

(i,j)为WW k W ij(k)1k1)ij(k (i,j)不是W上的一条弧ij(k),k:k

TSP问题的蚁群算在STEP3中，挥发因子ρkK≥1k

lnk ln(k1)

k k TSP问题的蚁群算 信息素挥发：每个连接上的信息素痕迹的浓度自动逐渐在STEP3中，蚁 到目前为止的最优解 1

D(d) 1 0

D ρk=1/2,k=1,2,3。此时，观察GBA