2.2 求M/M/m（n）中，等待时间w的概率密度函数。 解：
M/M/m（n）的概率分布为：
?m?1(m?)k(m?)m1??n?m?1?p0???p0??
k!m!1???r?0??1?(m?)k?k!p0?pk??mmk?k!?p0?0?0?k?m?1m?k?nk?n
假定n>m，n≥0，现在来计算概率P{w>x}，既等待时间大于x的概率。
P{w?x}??pj?Pj{w?x}
j?0n其中，Pj{w>x}的概率为：
Pj{w?x}?0 Pj{w?x}?0?j?m?1?m?x?ei?0j?m(m?x)i?i!m?j?n?1 m?j?nPj{w?x}?1可得：
P{w?x}??Pj??ej?mi?0n?1j?m?m?x(m?x)i??Pni!?mm?n?1jj?m?m?x(m?x)i?P0?????e???n?m!?j?mi!i?0? mmn?m?1?m?x(m?x)i?m?i??n?P0?e??Pnm!i!1??i?0若n??则P0(?m)m?(m???)xP{w?x}??e1??m!特别的，新到顾客需等待的概率为：
P0(?m)m P{W?0}??1??m!第 1 页 共 33 页
而n?m?1n?m?2mmP0(?x)i?m?xmm(?x)fw(x)?e[?(m???)??m??m!(1??)i!(n?m?1)!i?0?m??n(m??)](n?m?1)!n?m?1
在n??注：
mmP0fw(x)??m(m???)e?(m???)xm!(1??)m?1k?0
P{w?0}??PkP{w??}?Pn2.4求M/D/1排队问题中等待时间W的一、二、三阶矩m1、m2、m3，D表示服务时间为定值b，到达率为?。 解：
G(s)?s(1??)
s????B(S)其中 B(s)???0?(t?b)e?stdt?e?sb
?s(1??)i从而 G(s)? 又 G(s)?gs?i?sbs????ei?0
?(?sb)j??i?????gis???s??????j!j?0?i?0?????s(1??) ??
1????b2(1??)(1??)(2?b3??2b4)g0? g1? g2? 231??b2(1??b)12(1??b)?(1?2?b)(1??)?b4g3??424(1??b)(?b??)
?b2m1??G?(0)??g1?2(1??)m2?G??(0)?g2?2?(2??)?b6(1??)23
(1?2?)?b4m3??G???(0)?g3?6?4(1??)32.5 求M/B/1，B/M/1和B/B/1排队问题的平均等待时间W，其中B是二阶指数分布：
f(t)???1e??1t?(1??)?2e??2t?1,?2?00???1
第 2 页 共 33 页
解：M/B/1
B(S)??f(t)e?stdt?0???1(1??)?2??1?s?2?sw2?B??(0)?2?w1??B?(0)??1????1?2?m2??1????12???22w??22(1??)?1?2????1?22?(1??)??12?2 B/M/1
???12?2(1??)?22??1??????w1?????????2??1??B(????)???1(1??)?2?????????1??????2取0???1的根令?1??1?2???2
1??1??2?1?(?1??2)2?2(1?2?)(?1??2)??2w???(1??)?1??1??2?1?(?1??2)2?2(1?2?)(?1??2)?(1??1??2?1?(?1??2)2?2(1?2?)(?1??2))
??1tB/B/1
设到达的概率密度函数为f(t)???1e?(1??)?2e??2t
设离去的概率密度函数为f(t)???3e假设?1??2????3t?(1??)?4e??4t
?1??3?2??4
第 3 页 共 33 页
A(s)?B(s)???1(1??)?2??1?s?2?s???1(1??)?2????1(1??)?2????A(?s)B(s)?1???????s????s??1??s??s22?1??1??????21????1?(1??)?2?s2?s4t2s2?s4?(?1?s)(?2?s)(?1?s)(?2?s)(?1?s)(?2?s)(?1?s)(?2?s)222?取??(s)?s(t?s)(?1?s)(?2?s)w(s)?k??(s)??(s)?s(t?s)(?1?s)(?2?s)k?lim??(s)t?s?0s?1?2k(?1?s)(?2?s)(t?s)22Sw(s)?w???Sw(s)?s?0?'?1?2?(?1??2)t?1?2t22其中
t??1??2?(??1?(1??)?2)2?(1??2)?1?(2???2)?2?2?(1??)?1?22.6 在D/D/1排队问题中，顾客到达的时间间隔为a，服务时间为b，均为恒定值，且a>b，
求：稳定状态时系统的队列长度为k的概率pk，顾客到达时队列的长度为k的概率vk，
顾客离去时队列的长度dk，以及平均等待时间，并用G/G/1上界公式求出此时的平均等待时间，评论计算结果，并讨论a≤b的情况。 解：
由于是D/D/1问题，故子系统运行情况完全确定，第一个顾客到达后，系统无顾客，
经过b后，服务完毕，顾客离去，再经过a-b后，下一个顾客到达。
此时有：
?b?apk??(a?b)?a? ?1rk?dk???0顾客不等待时w?0 G/G/1
上
界
k?1k?0k?0k?0
公式
第 4 页 共 33 页
?r2??t2w?2t(1??)22?p(?)??(??a)?w?0p(t)??(t?b)?????t?0
22?w?????t?02t(1??)当a ab时间后，系统队列长度增长a?b2.7求M/E2/1即时拒绝系统的呼损，其中E2是二阶爱尔兰分布，b(?)?(2?)2?e?2?? 解： 设相邻呼叫到达间隔为t，如果服务时间??t，将造成呼损，??t时无呼损。 ?pc(t)??b(?)d?t??0t?则???t0pc??a(t)??b(?)d?dt???e ??(2?)?et?2?2???2?4??d?dt?(??2?)2 2.8在优先级别队列中，A队为优先级，不拒绝，B队为非优先级，只准一人排队等待（不计在服务中的），且当A队无人时才能被服务，求各状态概率，A队的平均等待时间和B队的拒绝概率。 解： ?1??2?2 说明： 0状态代表系统中无顾客状态； i，j状态代表系统中正在服务且A 0?0 0??20 1?1??1?1 01 1队中有i个顾客，B队列中有j个顾客排队的状态。 ?1??1? 状态转移图如右，A队到达率为?1，B队到达率为?2，服务率?，系统稳定时，应有 第 5 页 共 33 页 ?1??1??1 可得到特征方程如下: ?(?1??2)P0??P00?(?????)P??(P?P)?(???)P12000110120???(???1)P01??2P00??P11?(?????)P??P??Pi?012i,01i?1,0i?1,0???(???1)Pi,1??1Pi?1,1??Pi?1,1??2Pi,0i?0 ?1?2?3 ?4?5由于4是差分方程，不妨设其通解为：pi0?p00xi 代入有： (1??1??2)p00xi??1p00xi?1?p00xi?1?x2?(1??1??2)x??1?0 ?0?x?1221??1??2?1??1??2?2?1?2?2?2?1?2 ?x0?2由于5是非齐次差分方程： pi?1,1?(1?p1)pi,1??1pi?1,1??2pi,0?0 其特征根为：a??1 ii假设其通解为：pi,1?A?1?Bx0代入前式得： i?1ii?1iB?x0?(1??1)B?x0??1B?x0??2p00?x0?0 解之，得：B??p00i?pi,1?A?1i?p00x0 代入3式得：?1??1?p01??2p00?p11 即： A?p00?1??1??2?x0?i?pi，1??1??2?x0??1?xi1?p00? ?ipi，?0?p00x?p00???1??2?p0???由正则条件： 第 6 页 共 33 页 p0???1??2?p0?1??1??2?x0???1i?1i?0???p0?wA?1??11??1???1??2??1??1??2?x0?r????????r?1p?p?r?1p1?????x???r，0r，1001201??r?0r?01?1? ?p00?1??1??2?x0???1??1?2??rPCB??pr，1??1??2?x0??1?x01?p00??rr?0r?0?? p?1??1??2?x0?p?00?00?1??1?1?x02.9排队系统中有三个队列,其到达率分别为其中a类最优先，?a,?b,?c公用同一出线路， 即线路有空闲就发送；b类次之，即a无排队 ?b0??a??b??c?a?a0 0 0???a?b1 0 0??b?a2 0 0时可以发送，c类最低，即a，b类均无排队 0 1 01 1 0??2 1 0时可以发送，不计正在传送的业务，各个队列的截至队长为na＝2，nb=1，nc＝0，试列出 稳定状态下的状态方程，并计算?a??b??c时，各状态的概率和三类呼叫的呼损。 解： r，s，k分别表示a，b，c三队中等待的呼叫数，状态以（r，s，k）表示。 稳态方程： (?a??b??c)p0??p000(?a??b??)p000??(p010?p100)?(?a??b??c)p0(?a??b??)p100??p200??ap000(?b??)p200??ap100(?a??)p010??bp000??p110 ?p210??ap110??bp200(?a??)p110??bp100??ap010??p210第 7 页 共 33 页 归一条件p0??a 若 令?????p?1???i,j,kabcp010p110? p000?3?p0p1003?2?3?3?p02?2?2??13?p022??2??133?2?9?3?12?4?p022??2??16?3?15?4?12?5?p02?2?2??16??15??12?p022??2??1456 p200?p210?2?2?2??1p0?12?6?27?5?36?4?27?3?14?2?5??1 C类呼损为：pc?1?p0?? B类呼损为：pB?p010?p110?p210 A类呼损为：pA?p210?p200 2.10 有一个三端网络，端点为v1,v2,v3，边为e1(v1,v2)及e2(v2,v3)，v1到v3的业务由v2转接，设所有的端之间的业务到达率为?，线路的服务率为?的M|M|1(1)问题，当采用即时拒绝的方式时，求： 1) 2) 3) 解： 令：00表示e1,e2均空闲。 10表示e1忙,e2闲（即e1由v1,v2间业务占用）。 各个端的业务呼损。 网络的总通过量。 线路的利用率。 01表示e1闲,e2忙（即e2由v2,v3间业务占用）。 11表示e1,e2均忙，且分别由v1v2,v2v3间业务占用。 ★表示e1,e2均忙，且由v1，v3间业务占用。 第 8 页 共 33 页 状态转移图如右： 当?12??13??23??时 有下列关系: ★?13?230 0???230 1?12??12?1 0?1 1??pt??p00?3?p???p?p?p?000110*????????p10??p00??p11 ??????p??p??p010011???2?p11???p01?p10? 又 ?p*?p01?p10??p00 解之得: p?1??2?p11??p00这里p00?11?3???2 3???22???2呼损p13?1?p00?而p23?p12?1?p00?p01? 221?3???1?3???3??2?2通过量T??(1?p12)??(1?p13)??(1?p23)? 21?3???2???2线路利用率??p*?p11?(p10?p01)/2? 21?3???2.11上题中的网若用于传送数据包,到达率仍为每秒 平均包长为b比特,边的容量为 c比特/秒,采用不拒绝的方式,并设各端的存储容量足够大,求: (1)稳定条件。 (2)网络的平均时延。 (3)总的通过量。 (4)线路的平均利用率。 解：这是一个无损但有时延的系统。 两条线路上到达率为：2，而服务率为：c/b的M/M/1系统。 (1)稳定条件为： 2b/c<1。 第 9 页 共 33 页 (2)网络的平均时延： 对v1v2和v2v3间的业务：w1?11? ?(1??)c?2?b 对v1v3间的业务：w2?2w1?2c?2?b(3)系统稳定时，总的通过量为：3b/c。 (4)线路的平均利用率==2b/c。 一般来说，通过率与利用率均有增加，这是以稳定性和时延为代价换来的。 2.12在分组交换系统中，设信息包以泊松率到达，平均到达率为，但信息包的长度为固定b比特，信道容量为c比特/秒。由于端内存储量的限制，设除了在传送的包外，只允许有两个信息包等待传送，试： (1)列出关于dr(顾客离去时的队长)的系统方程 (2)解出个dr. (3)求平均时延。 (4)求信息包被拒绝的概率。 解： ?d0?d0q0?d1q0?d?dq?dq?dq011120?1?d2?d0q2?d1q2?d2q1?d3p0 ?（?d3?d0q3?d1q3?d2q2?d31?p0）?3??di?1?i?0其中p0是第4个顾客被拒绝离去之后，第3个顾客的残余寿命中无顾客到达的概率。 这里到达是随机的，可知：p0??b/c 0c??t??b?cc?edt??1?e ?????bb第 10 页 共 33 页 设?b则 ?c?? q0??e???b???d???e??????bd??e??c00q1????e???b???d???e??b????????2????2??q2??eb???d??e022? ?d1? 1?q0d0q0d2?e2???1???e?d0???3??2???2???2???e??1?2??e?e?d02?d3??e??1 ?e?1??di?1d0??4???2??3?22??1???e??1?2??2??e?e2 平均时延： ?m?mv??b3??1?b?32???s?w?bc??vd1???md??e?2???e??d0 ?1?2??2mc?2m222?c????1???1 拒绝概率： pC?d3 2.13有四个端三条边组成的数据网，如图所示。端间的信息包分别为和每秒，信息包长度为负指数分布，平均包长为k比特，各信道容量分别为c1，c2和c3，和一起排队，和一起排队，和一起排队，均不拒绝，求 (1)各种业务的平均时延。 (2)网络的平均时延。 (3)各信道的平均利用率。 第 11 页 共 33 页 解: 由于均不拒绝且到达和离去均随机，故3个信道均等效于3个M/M/1系统，其中： C1：到达为?12??13。服务为：c1/b C2：到达为?12??42。服务为：c2/b C3：到达为?13??43。服务为：c3/b C1的平均迟延为 11? ?1(1??1)c1??12??13b11? c?2(1??2)2??12??42b11? ?3(1??3)c3??13??43bC1的平均迟延为 C1的平均迟延为 s12?sc1?sc2?1c1??12??13b1?1c2??12??42b?1 s13?sc1?sc3?c1??12??13bc3??13??43b s42?sc2?1c2??12??42bs43?sc3?1c1??13??43b 网络的平均时延为：s??12s12??13s13??42s42??43s43 ?12??13??42??43各信道利用率为： ?c1??1???12??13?b/c1?c2??2???12??42?b/c2 ?c3??3???13??43?b/c3 2.14总线上有4个用户v1,v2,v3和v4，它们之间以Alopha方式互相通信，信包到达率均 第 12 页 共 33 页 为每秒，信息包的长度为b比特；总线上的传输速率为c比特/秒，试求通过率r，并大致画出r与b的曲线关系。 解：r与b的曲线关系如右图，从直观上来看，这也是显然的。 总线上一个包的服务时间??b秒， c总的呼叫量为：a?12?b， c通过量为：r?a?e通过率：r?r?2a b?12?e?2a c 3.2 设在一个纯ALOHA系统中，分组长度??20ms，总业务到达率?t?10 pkt/s，试求一个消息成功传输的概率。若为S-ALOHA系统，试求这时消息成功传输的概率，并求一个消息分组传输时和另一个分组碰撞的概率。 解：由题意，??20ms，?t?10pkt/s，则系统的总业务量为 P??t??10?20?10?3?0.2 纯ALOHA系统吞吐量满足p?Pe?2P，一个消息成功传输的概率为 Ps?pP?e?2P?e?2?0.2?e?0.4?0.67 S-ALOHA系统的吞吐量满足p?Pe?P，这时消息成功传输的概率为 Ps?pP?e?P?e?0.2?0.82 一个消息分组传输时和另一个分组碰撞的概率为： 1?Ps?1?0.82?0.18。 3.3 设在一个S-ALOHA系统中每秒共发送120次，其中包括原始发送和重发。每次 发送需占用一个12.5 ms的时隙。试问： （1） 系统的归一化总业务量等于多少？ 第 13 页 共 33 页 （2） （3） 第一次发送就成功的概率等于多少？ 在一次成功发送前，刚好有两次碰撞的概率等于多少？ 解：由题意，?t=120次/秒， ?=12.5 ms。 （1） P??t??120?12.5?10?3?1.5。 （2） P?0??e??t??e?1.5?0.223。 ?P（3） p3?1?e??e2?P??1?0.223??0.223?0.135。 23.4 设一条长度为10 km的同轴电缆上，接有1000个站，信号在电缆上传输速度为200 m/us，信号发送速率为10 Mb/s，分组长度为5000 b。试问： （1） （2） 若用纯ALOHA系统，每个站最大可能发送分组速率等于多少？ 若用CSMA/CD系统，每个站最大可能发送分组速率等于多少？ 解：（1）纯ALOHA中，发送分组不用等待。理想情况下，各站一个接一个发送分组，互不干扰，发送分组的最大速率为 ??2 pkt/s 10M/?5000?1000（2）对于CSMA/CD系统，信号传输速率为200 m/s，对于10 km电缆，单程传播时间为 t?10?10/200?50 ?s 3CSMA/CD系统发送一个分组必须等待的时间为：2t=100 us=0.1 ms。 故每个站的最大可能发送分组速率为：10M?0.1 ms/5000?0.2 pkt/s。 4.4有一个n端的全连接图。试证： （1）无重复端的环数为 ?Cnkk?3n?k?1?! 2（2）经过某一固定边e的环数为 ?k!Ck?3nkn?2 第 14 页 共 33 页 （3）两个固定端之间的径数位1???n?k?2?! k?1n?2?n?2?!k(1)环上有k个端（3≤k≤n），此k个端的选择方式有Cn种；对于某固定的k端来说，考 虑可以生成的环，任指定一个端，下个端的选取方法公有k-1种，再下端的选法有k-2种，等等，注意，这样生成的环可按两种试图顺序取得，故有 (k?1)!种，总的环数为2?Cnkk?3n(k?1)! 2(2)某一固定边e确定了两个端，经过e的环数按其过余下端进行分类，若环再过k个端 k（1≤k≤n-2），有选法Cn?2种；对于某固定端来说，自然可以生成k!个环，从而总的环数 n为 ?Ck?3kn?2k!个。 (3)两个固定端之间的径按其经过端数分类，其中有一条不经过其他端的径，若经过k个端，（1≤k≤n-2），则对于第一个端有（n-2）种选择，第二个端有（n-3）种选择，第k n?2(n?2)!(n?2)!个端有（n-k-1）种选择，共有 总的径数为 1?? (n?k?2)!(n?k?2)!k?14.5 试求图4-44中图的主树数目，并列举所有的主树。 图4-44 所得主树见下: 解：为图的端编号为v1,v2,v3,v4。 取v3为参考点，有： 3S??1?1?1?1200?8 2第 15 页 共 33 页 4.6 试证明端数n大于4的连接图都是非平面图，并求n=2，3，4的全连接图为对偶图。 证明：设有n个端的全联接图为Kn因为K5是非平面图，而当n>5时K5是Kn的子图，从而Kn（n>5）均不是平面图。一下是对偶图（注意K4为自对偶图）。 第 16 页 共 33 页 4.7 ?0?0C???0??0 100001001?0?? 1??0? 已知一个图的邻接矩阵如左，画出此图，并求各端之间的最小有向径长。 解：首先作出图形： 对所绘制图形的端点进行编号，得邻接矩阵。 v1 经计算： ??C????? v2v3v41010?0010? ?0001??0000??0?0C2???0??0因而有 000010000??0?01?? C3??0??0??0??0000000001?0?? 0??0?第 17 页 共 33 页 d(v1,v2)?1 d(v1,v3)?2 d(v2,v4)?2 d(v1,v4)?1 d(v2,v3)?1 d(v3,v4)?1 其余有向径长均为 ∞，或不存在。 4.8 图有六个端，其无向距离矩阵如下： v1v1v2v3v4v5v6 v2?0?1??2??3?2??1v3120110v4v5v6321?232??123??21012?32101??23120?1. 2. 3. 用P算法，求出最短树。 用K算法，求出最短树。 限制条件为两端间通信的转接次数不超过2的最短树。 解： (1)P算法求解： eeee?v1?????v1,v2?????v1,v2,v3?????v1,v2,v3,v6?????v1,v2,v3,v6,v5? e????v1,v2,v3,v6,v5,v4?1223166534(2)K算法求解： 按最小边长顺序取得： e12?e23?e34?e45?e56?1此结果意味着最短树不唯一。 第 18 页 共 33 页 (3)原图有一个边长全为1的基本子图G1，要求转接次数小于等于2，若选取G1的任何4个连续顶点，vivi?1vi?2vi?3,作为基础，然后再按要求增加边，例如以v1v2v3v4为基础，增加v5v6，得到一个树长为7转接次数小于等于2的树T1，事实上，以任何4个连续顶点均可得到树长为7的转接次数小于等于2的树 4.9 图有六个端，端点之间的有向距离矩阵如下： v1v2v3v4v5v6 解： v1v2?09?10??2???????6??7?v3v4v5v613???4?7???0?1???5027?2805??2?20?(1)用D算法求V1到所有其他端的最短径长及其路径。 (2)用F算法求最短径矩阵和路由矩阵，并找到V2至V4和V1至V5的最短径长及路由。 (3)求图的中心和中点。 第 19 页 共 33 页 (1)D算法 V1 0 (2)F算法 最短路径矩阵及最短路由阵为W5，R5 V2 ∞ 9 9 8 8 8 V3 ∞ 1 V4 ∞ 3 3 3 V5 ∞ ∞ 2 V6 ∞ ∞ ∞ 7 7 指定 V1 V3 V5 V4 V6 V2 最短径长 W1＝0 W13＝1 W15＝2 W14＝3 W16＝7 W12＝8 v2?v1?v4有向距离为4 v1?v3?v5有向距离为2 第 20 页 共 33 页 ?0913?????104?7??W?2?0?1???0????5027????62805???7?2?20???0913?????10247??W??211051???1???5027????62805???71621020???091316????10247??W?211051???2????5027???762805???71621020???09132????10243??W??211051???3?7165027???462805???4132720???0913210???1024311?W?21105112??4??7165027???462705???4132720???081327???102438?W??270516??5?684027???462705???482720?? ?023400???103050?R?100050??0??003056???023406???103450???023400???101150?R?110150??1??003056???023406???113150???023420???101150?R?110150??2??003056???223406???113150???023430???101130?R??110150??3?333056???323306???313350???023434???101134?R?110154??4??333056???323306???313350???053435???101135?R?150155??5??555056???323306???353350??第 21 页 共 33 页 (3)MaxWij?(8,8,7,8,7,8) 中心为V3或V5 5j?Wj5ij?(21,18,21,27,24,23) 中心为V2 补充习题：试计算完全图Kn的主树的数目。 解：设A为Kn的关联阵，那么主树的数目为： n?1n?1N?dctA?AT?dct?1?1???1?110???n?1?dct???1??10n?1n?1n?11???11????1n1n00n0n?11n?2?dct??dct?n??n???n?0??0?1n0n证毕。 5.1求下图中Vs到Vt的最大流量fst,图中编上的数字是该边的容量。 解： 本题可以利用M算法，也可以使用最大流－ 最小割简单计算可知： X??vs,v3,v4? X??v1,v2,vt? CX,X?3?5?1?3?12 第 22 页 共 33 页 ??可知：最大流为12，可以安排为fs1 = 3,，fs2 =5，f12=1，f2t＝4，f1t=4，fs3=1，fs4=3，f3t=1，f4t=3。 5. 2试移动上图中的一条边，保持其容量不变，是否能增大fst？如果可以，求此时的最大值，但若所有转接端v1v2v3和v4的转接容量限制在4，则情况将如何？ 解： 依然按照最大流－最小割定理，若 22v14v1'6能依一边从X找到X内部至割 3v244v2'v3'Vt(X,X)中，自然可以增大流量，可以 Vs52v3将e34移去，改为：e41 或者e42均可，使总流量增至12＋2＝14。 64132v44v4'当vi(i = 1,...4)的转接容量限制到4 时，等效图为右图，对于3.11中的流量分配，在本题限制下，若将fs2由5改为4即得到一个流量为11的可行流。 但若X?vS,v3,v3v4,v4,v2， X?v1,v1,v2,vt 则C(X,X)?1?3?4?3?11，换句话说就是11已是最大流。 *?''?*?''?**第 23 页 共 33 页 5.3图5-12中的Vs和Vt间要求有总流量fst＝6，求最佳流量分配，图中边旁的两个数字前者为容量，后者为费用。 解： 本题可以任选一个容量为6的可行流，然后采用负价环法，但也可用贪心算法，从Vs 出发的两条线路费用一样，但进入Vt的两条路径费用为7和2，故尽可能选用费用为2的线路，得下图1。 6,3再考虑V0，进入V0的两条路径中优先满 5,7 3,2足费用为3的路径，得：图2，很容易得 Vt2 ,3Vs 3,2 1,124,到最后一个流量为fst=6的图3，边上的 数字为流量安排。总的费用为 3,4图1 L?3?2?3?2?1?3?2?4?1?1?2?3?4?2?2?7?52 易用负价环验证图4的流量分配为最佳流量分配。 12Vs 44 Vt3Vs 1VtVs34图 22图 3 2图 44 32 22 Vt 2 第 24 页 共 33 页 第 25 页 共 33 页 6.1由n个元件构成的一个系统，各元件的平均寿命都是T。当一个元件失效据使得系统失效的情况下，已知系统的平均寿命将下降至T/n，如果采取容错措施，当m个以上元件失效才使系统失效，求证此系统的平均寿命为： Tm?T ?r?0mn1?r可见比未采取措施前提高至少m倍。当m=n-1时，这一系统实际上即是n个元件的并接系统，试证上式即转化成并连系统的寿命公式。 证：以i状态代表有i个元件失效的状态，此时系统的状态转移框图如下： 0 12…mF 那么状态i的平均寿命为：Si?Tn?i0?i?m 从而系统的平均寿命为：S?S0?S1???Sm?T?n?i i?0m1当m=n-1时S?T1 ?kk?0112131n1n ?C?C?C???(?1)Cn?nnn23nk?0knn而利用数学归纳法易知： 6.3有n个不可修复系统，它们的平均寿命都是T。先取两个作为并接，即互为热备份运行；当有一个损坏时，启用第三个作为热备份；再损坏一个是起用第四个，已知下去，直到n个系统均损坏。忽略起用冷备份期间另一系统损坏的可能性；试计算这样运行下的平均寿命；并与全冷备份和全热备份是的平均寿命相比较。 解：状态图如下：i表示有i个系统损坏，失效在图中标出。 2?012?22?…2?n-1?n 第 26 页 共 33 页 由上图有：Si?T20?i?n?2Sn?1?T 从而，平均寿命： S?S0?S1???Sn?1?S冷?nTS热?S?S冷 Tn?1??n?1??T?T22111?? S热＝?1??????T23n??6.4上题目中n个子系统都是可修复系统，可靠度都是R。仍用上述方式运行，一损坏系统修复后作为最后一个系统排队等候再起用，求稳态可靠度。 解： m，n-m表示n个系统中有m个失效，状态转移图及失效率与修复率如图： 2?2?2?2?2?2??0, n?1, n-12?2, n-23?m,n-mm?(m+1)?n-1, 1(n-1)?n?n, 0 用Pm表示状态m,n-m的概率（稳态），状态方程如下： ?2?p0??p1????(2??m?)pm?2?pm?1?(m?1)?pm?1?????(2??n?)pn?1?2?pn?2?n?pn??p?n?pn?nn?1??p?1i??i?0解状态方程如下：有： 0?m?n?1 第 27 页 共 33 页 m??2??p0?pm?m?m！??n??2??p?p0nn?2n！??0?m?n ?n?11?2??m2n?1?n?由归一性：p0??????? ??nn！???????m?0m！?1?2????m！??????mm?1稳态可靠度：Rs?1?pn?1?2??2?????m！???n！?n??n?1n 其中， ?1?R? R是单一系统的可靠度。 ?R6.5一个复杂系统有n级梯形结构组成如图所示。其中有n个子系统作为桥，2(n+1)个子 系统作为梯边，它们都是可靠度为R的可以修复系统。求这个复杂系统的可靠度递推公式，假定所有子系统都互相独立。 解： 依次考虑1，2，3，… n。依照各个桥的情况可以分类，根据1，2，3，… n的好坏 情况可以得到以下结果： 情况 Ⅰ Ⅱ Ⅲ 概率 R R(1-R) R(1-R)2 可靠度 [1-(1-R)2]Rn-1 [1-(1-R2)2]Rn-2 [1-(1-R3)2]Rn-3 第 28 页 共 33 页 ┇ N N+1 R(1-R)n-1 (1-R)n [1-(1-Rn)2]R0 1-(1-Rn+1)2 ?Rn?R?2R?R2?Rn?1?R?1?R??2R2?R4?Rn?2???R?1?R?n?1?2Rn?R2n?R??1?R??2Rn0n?1?R2n?2? 其中：R0?2R?R2 n?0 6.6有一个故障率为?的系统，为了考虑是否使之成为可修复系统而配备维修力量，分别计算两类可靠度，试证明作为不可修复系统在时间T以内的可靠度大于作为可修复系统的稳态可靠度的条件是：?T?0.995?T?0.01 解：故障率为的不可修复系统在T（?T?0.01）内的可靠度为： R(T)?e??T?e?0.01 ? 现： ?的可修复系统的稳定可靠度为 ???? R(T)> ???? 或 e?0.01> ?T?T??T??T0.01??T ??T?0.995 6.7有一故障率为?，修复率为的系统?，已知此系统的费用是C?A??r?B?s 其中A，B，r，s为已知的非负常量，求可靠度为0.99时的最小费用。 解： ??????0.99???99?C?A?r?B?99s?s?s?1 1r?s 令： dcA?0有?r?B?99s?s?s?1?0d???rA?????s?Bs?99?? 第 29 页 共 33 页 ?rA?Cmin?A?s?Bs?99???rr?s?rA??B?s?Bs?99??sr?s99s 6.8用流量法求图5－9(b)中的二分网的联接度?和结合度?，只考虑端故障，且各端的可靠度均为R，求1端和5'端间的联接概率。 解：图5－9(b)中的二分图，任意一端度数均为4，??4 容易知道： ??????4 一知考虑端故障，故中有一，二， 三失效和无失效是等价图入右： 可靠度分别为： ?1??1?R???C?R?1?R??1??1?R???C?R?1?R?314342422?C?R?1?R??C?R343444? 1和5'之间联接概率为： 33241234R1,5'?C4?R?1?R?1??1?R??C4?R2?1?R??C4?R3?1?R??C4?R4?1??1?R? ??????6.9有一网络结构如图： 1. 2. 3. 验证网络是否为保证网。 求联接度?和结合度?。 若每边的可靠度都是Re，每端的可靠度 Rn,求线路故障下网络的可靠度和局故障的网络的可靠度。 第 30 页 共 33 页 4. 5. 解： 1. 求v1和v2间联接的概率。 要使?和?都为2，如何添加一条边来满足。 原网收缩为： 从而是保证图。 2. 3. 去掉U1,U2可使网中断，故?=1, ?=2。 局故障下网的可靠度： 端的不可靠度为Fn?1?Rn 网络的可靠度R1?1?当Fn??1边故障下： 边的不可靠度为Fe?1?Re： 网的可靠度R2?1?当Fe??14. CF??ii?nin(1?Fn)n?i?1??CiFniRni?1nn?i R1?1?C?Fn??1?2Fn ?BiF(1?Fe)iei?pmm?i?1??CiFeiRei?2mm?i 2R1?1?B?Fem?1?12Fn R1,6?1??1?ReRn?1?ReRn1?1?ReRn222R1,65. ????????1??1?R??1?RR?? ?R?1??1?R??1?RR???1??1?RR???2222een2n222eenen在V1和V3之间连一条边，就使?=?=2 第 31 页 共 33 页 6.11有一个四端全联接的网络，各边的容量都为1，可靠度均为0.999，若网络内部只有两个端之间有业务，呼叫量为0.1爱尔兰，不可靠集定义为转接次数大于1，或呼损大于0.01，设所有端均不出故障，求此两端之间通信的综合可靠度。 解： 考虑到转接此时小于等于1，那么某两端见的等 效网络为右图： 有三条独立的线路可靠度为：R2，R1，R2。 其中：R1＝0.999 R2＝0.9992 呼叫量为0.1个爱尔兰，又因为必有呼损率小于0.01， 那么有爱尔兰公式一可知，在可靠集中应至少有两条线路是正常的， 设x为不正常线路个数： x=0的概率：R1R2 x=1的概率：2R1?1?R2?R2??1?R2?R2 22综合可靠度：2R1?1?R2?R2??1?R2?R2?R1R2 22 6.12有m条边n个端的随机图有Cn(n?1)种，即每条边可在任两端之间，在这许多图中，有 2m多少在某两端vi和vj间有边？已知某边的一端是vi，另一端是vj的占多少？若m=n-1，联接图占总数的百分之几。 解： vi和vj之间有边Cn(n?1)种， 2?1m?1若某边的一端是vi，另一端是vj的概率： 第 32 页 共 33 页 m?1Cn(n?1)2?1mCn(n?1)?2m2m? n(n?1)n(n?1)2数的总数是nn?2nn?2，从而联接图占：n?1 Cn(n?1)2 第 33 页 共 33 页