数 学 建 模 题目：
A 队号：
2014045A 2014年5月25 题目A：通信网络的设计问题 摘 要 本文主要研究通信网络在铺设线路上遇到的总铺设成本，及网络结点和链路可靠性问题的建模建立并对某通信公司所建立的80个结点所铺设线路提出最优铺设方案。

问题1是网络设计常见的成本最低化问题，通过简化将问题转为寻找权值最小的最小生成树问题，并利用避圈法和破圈法得到最小生成树（结果见8页图2）。最终求得最省铺设费用为294.78万元。并通过仿真计算对该方案的可靠性检验,结果表明，任意一条链路被破坏时，能够保证通信畅通的结点数最低只有结点数的53.75%，网络链路不太稳定。通过模拟结点出现故障，发现若22号结点出现故障，能够保证通信畅通的结点数只有结点数的46%（结果见14页表2）。由此可见利用最小生成树模型涉及网络铺线优点是成本低，缺点是保证结点通信畅通的可能性低. 对问题2，根据邻接矩阵计算了可达矩阵，并根据可达矩阵与链路连通性的关系，将结点出现故障时的最小生成树，分解为若干组内联通的子树。然后，在保证90%以上的结点通信畅通的条件下，对分解后的图进行了连接修复，对每一结点出现故障时，为保证通信畅通90％以上，建立了0-1整数规划规划模型（12页）。考虑整数规划模型求解的复杂性，设计了贪婪算法，对其中17个结点出现故障后结点的具体连接方法见（详见14页表2）。若结点出现故障后，网络本身仍能保持90％则无需在连链路，故在表2中未进行考虑。由表2知，贪婪算法的结果能保证92.5％的结点通信畅通。

对于问题3，要求任意一条链路破坏时，为保证90%以上的结点通信畅通分两种情况进行考虑。如果任意一条链路破坏后，仍有90％以上的结点保持通信畅通，这些链路无需追加链接（详15页见表3）。另外一些链路在破坏后，不能保证90％的结点通信畅通，需追加链接，即加边。要加边时，若允许某些结点连2条边，则只需对原最小生成树的某些结点连两条一样边（复制某最小生成树的某两结点间的被破坏的边，使之形成回路即可），该链路仍然为总铺设费用最省方案。如果不允许任意结点连两条边，由于破坏一边，整个树一分为二，只需计算两组结点间的最短距离，即可连一条新的最短路。在可靠性不小于90%的情况下，得到总铺设费用方案（详17页见表4）. 对于问题四，综合考虑网络的可靠性以及铺设费用后，根据问题2和问题3的结果，将结点出现故障后需加的边和链路破坏后需加的边全部加到问题1 的最小生成树上，得到可靠性相当高的铺线模型(见19页图8)，该模型任意一结点出现故障后，结点保持畅通的可能性最低在90％以上（详18页见表5）。考虑到该模型成本高，需增加的铺设费用为750.75万元。因此，依次移除成本高的边（此处只移除图8中一条边71－76），从得到一成本更低，稳定性友好的模型模型(见20页图9)，此时只需增加成本5032万元。任意一结点出现故障后，结点保持畅通的可能性最低在90％以上（详21页见表6）。对边有类似的结果分别见表7，则此方案合理。

关键词：最小生成树，破圈法，网络模型，图论 一、问题重述 随着科学技术的进步，计算机和网络技术取得了快速发展，成为信息交流手段，渗透到社会的各个方面，其发展也在不断的推动人类社会逐渐走向信息时代。网络技术的发展在给人们生活及社会生产力的提高提供了巨大贡献的同时，也存在着许多安全隐患、信息漏洞，如最近出现的网络OpenSSL“心血”漏洞等。这些对于人们的工作和生活造成了很大的影响。

对于一个系统，可靠性是其重要的整体指标，通信网络亦不例外。通信网络的可靠性不仅与通信设备、链路有关，而且还与网络结构有关。由于网络结构的复杂多变，通信网络的可靠性分析一直是个棘手的问题。

某通信公司拟建一个具有80个结点的通信网络，需要在这些结点之间铺设线路，进行数据传输。结合结点之间的距离和铺设线路的单位费用见附件1，本文需要具体完成以下问题：
问题1：要使得通信网络的总铺设费用最省，请建立问题的数学模型，设计求解算法，给出铺设方案，并讨论方案的可靠性；

问题2：考虑到通信网络结点的可靠性，若要求任意一个结点出现故障时，其它结点间仍然能够保持通信畅通的可能性都达到90%，请建立问题的数学模型，设计求解算法，并给出使总铺设费用最少的铺设方案；

问题3：考虑到通信网络链路的可靠性，若要求任意一条链路被破坏时，能够保持通信畅通的结点都能够达到90%，请建立问题的数学模型，设计求解算法，并给出使总铺设费用最少的铺设方案；

问题4：综合考虑网络的可靠性以及铺设费用，试确定合理的铺设方案。

二、模型假设 1、假设结点与结点之间的连接不存在先后顺序，且均以直线连接 2、假设不考虑结点大小 3、假设不考虑线路铺设费用对线路连通的影响 4、假设通信网络中结点间距离固定不变且数据可靠 5、假设链路和结点只有故障、正常两种状态 6、假设网络中链路故障的概率是统计独立的 7、不考虑网络线路及结点内容量问题 三、定义与符号说明 ：链路权值=结点间距离×结点间铺设线路单位费用 ：结点个数、 ：结点名 ：边 ：树 四、问题分析 计算机网络通信是现代最为流行、最为尖端和最为新颖的通信技术手段，也是现代信息技术发展的极致。发展到现在,已经进入到了一个智能化、宽带化与综合化的阶段，其发展的前景也被广泛看好[1]。因此，在保证网络通信安全的前提下，网络可靠性是一个系统中比较重要的整体指标。网络可靠性评估是网络可靠性相关研究的基础，是目前网络可靠性研究领域的一大热点，而基于可靠性的网络设计则能针对网络可靠性、网络构建费用等网络设计目标，提供各种优化方案供网络管理者参考[2]。

从问题重述可知，本题属于网络路线优化问题。在网络通信时，数据需要在结点间传输，这就需要在结点间铺设线路。由于地理位置和距离等其它因素, 使各结点之间架设网线的费用不同, 公司想使各结点之间的网络畅通并且把费用降到最低, 那么应该怎样来设计各结点间的线路，这是本文的关键。

在线路建设中不仅需要考虑成本问题，还要考虑到方案的可靠性，以保证在任意结点或链路出现故障时，通信仍能畅通。参考附件1的结点之间的距离和铺设线路的单位费用，下面就每个问题进行分析：
对于问题1：是网络设计方案中常见问题，即成本最低化。可以结合附件1中给出的结点间距离和铺设线路单位费用，由链路权值，可把问题简化为寻找最小生成树问题。一棵生成树的代价就是树上各边的代价之和，此时这颗最小生成树的总权值即为本题中的最省总铺设费用，使用条不产生回路的边来连接网络中的个顶点来构造最小生成树[3]。

对于问题2：由题1结论可知，此最小生成树是在网络连通的基础上，考虑最少总铺设费用。因此，在任意结点和线路不出现故障时，此种解决方案为最优解。在通信网络中，不仅需要考虑铺设费用问题，还往往要考虑可靠性问题。问题二中，要求在结点可靠性90%的基础上，求解最少总铺设费用问题，这就存在两个需要考虑的因素：一是在可靠性达到90%时，优先考虑最省总铺设费用；
二是可靠性在达到90%的情况下优先考虑提高可靠性，再计算最少铺设费用。由于时间的问题和算法的复杂性，本文就前者因素建立模型，并求解。

对于问题3：连通性定义和可靠性定义见题2，本题将不再做定义，直接运用。依据题2的连通性和可靠性定义，运用MATLAB可得破坏任意一条链路时各个结点间连接关系。根据题1可知：所生成的最小生成树已为网络总铺设费用最省的方案，现在考虑任意一条链路被破坏时网络可靠性达90%以上的基础上最省铺设费用问题。

对于问题4：由上述三题的解决方案可知，综合考虑网络可靠性及铺设费用主要从三个方面着手：一是若任意一个结点出现故障时网络的可靠性，二是若任意一条链路被破坏时网络的可靠性，三是总铺设费用。

五、模型的建立与求解 5.1 问题1模型的建立与求解 5.1.1 模型的建立 为了建模的准确性，下面引入最小生成树概念。一般地，设V={ν1，ν2，ν3，…，νp}是P个点的集合，E={e1，e2，e3，…，eq}是q条边的集合，其中 νi ,νj ∈V. 把V和E组成的图形称为无向图，记为。如果G0是一个包含G 中所有顶点且无回路的连通子图，则G0是G的一棵生成树。若G有n个顶点，那么它的生成树有n个顶点，n-1条边。一个图可以有很多不同的生成树。其中，各条边权值之和最小的生成树即为最小生成树。

根据最小生成树的定义及性质可以得到如下几个结论（设图G1是图G的最小生成树）。

（1）G1中的各条边权值之和最小。

（2）G1中有n 个顶点n-1条边。

（3）G1必须是连通的且无回路。

因此，只要在一个连通带权图里找到一个同时满足上述三个条件的图，也就找到了该图的最小生成树。

为了研究的方便，将本题中的通信网络简化为各个结点与结点之间的连线，并不计结点大小，下文中一律将此连线叫做链路。因此，可以得到一个生成树模型。其中链路权值F，详见附件1，结点编号为。

假如该公司所建立的部分结点所在位置简化如图1所示。顶点代表结点编号，边代表可以架设网线的链路,这样就构成了一个带权连通图, 从而最小费用问题就转化为求所得到的带权连通图的最小生成树的问题。

图1 部分结点的通信网络简化图 5.1.2 模型的求解 常用的最小生成树的算法—破圈法和避圈法。本题采用这两种方法分别对模型求解。

（1）避圈法 避圈法计算步骤如下：
Step1：从网络中任选一点vi，令，；

Step2：从连接与的边中选取最小边, 不妨设最小边为（vi，vj），该边必为优化路线中的一条；

Step3：重新修正集合与的组成元素，在集合中增加顶点，显然在集合中减少该顶点；

Step4：如果（空集），则停止，已找到所有的优化路线，否则返回第2 步。

下面就该网络中的一个结点简单说明本通信网络用避圈法求解最小生成树的方法。通信网络铺设最优方案问题用避圈法求解过程如下：
① 假设从结点开始，即 ② 从与的链接中共有79种情况，经过计算比较得出，从结点到结点之间铺设的费用为最小费用。则将连接起来，即标记为最小部分树内的边；

③ 重新修正集合与后，可得与；

④ 因为当前，所以要回到第二步，这时通过计算可以发现连接与的156条边中，从结点到结点之间铺设的费用为最小费用。则将连接起来。而在此过程中没重复一次第二步，通过计算铺设费用，比较出得到最小边，最后连接成最小生成树，即为实现通信网络的总铺设费用最省的铺设方案，并得到铺设费用为29478百元，其中最小生成树图如图2，各结点间的铺设费用如表1。

（2）破圈法 破圈法相比避圈法的思路简单。所谓破圈法就是“任取一圈，去掉圈上权值最大的边”反复执行这一步骤直到没有圈为止[4]。通过前文可知，已将通信网络建立为一个连通图。此时问题可简化为用破圈法求解最小生成树问题。

Step1：在网络图中找到一个圈, 去掉圈中的最长的一条边；

Step2：检查网络图中是否还有圈，如果有，重复第1步，否则停止，表明已找到最优路线。

由于结点数较多，用MATLAB编程实现，就不再具体说明，最终输出结果与避圈法一样。

通过以上两种方法均得到网络线路铺设的最小生成树。

表1：各结点间链路的铺设费用 序号 链接 费用/百元 序号 链接 费用/百元 序号 链接 费用/百元 1 1–34 154 28 40–63 558 55 33–73 230 2 26–34 545 29 63–79 300 56 51–30 279 3 34–61 273 30 35–27 320 57 30–31 43 4 61–50 532 31 27–3 160 58 31–59 231 5 50–32 132 32 3–7 348 59 59–60 1729 6 61–70 115 33 7–13 102 60 59–48 783 7 70–36 160 34 27–42 420 61 30–38 217 8 36–8 468 35 42–53 148 62 38–4 303 9 8–14 901 36 53–22 432 63 4–58 141 10 70–62 84 37 53–37 752 64 22–45 308 11 70–66 426 38 22–56 254 65 45–76 420 12 66–67 98 39 22–54 72 66 76–77 288 13 62–47 372 40 22–16 198 67 77–23 230 14 47–69 690 41 16–52 140 68 23–6 145 15 47–2 198 42 16–55 320 69 23–75 336 16 2–29 483 43 55–25 792 70 23–64 387 17 2–19 114 44 52–21 468 71 64–57 703 18 19–28 368 45 52–43 555 72 77–71 195 19 19–49 345 46 43–9 420 73 71–72 534 20 2–5 336 47 52–18 284 74 71–74 187 21 5–78 342 48 18–51 302 75 74–17 77 22 5–35 101 49 51–12 100 76 17–10 157 23 35–20 489 50 12–68 300 77 10–44 36 24 20–80 1914 51 12–46 207 78 44–15 510 25 20–24 586 52 46–65 636 79 71–11 472 26 24–39 484 53 46–33 80 27 35–40 348 54 33–41 811 5.2 方案的可靠性 根据最小生成树特点和网络连接特性，可以从两个方面考虑方案的可靠性，即网络中连通的可靠性和使用最小树生成法的可靠性。

从网络连接的可靠性来说（详见题2），若任意一个结点出现故障破坏，题2 由MATLAB程序运行得到的破坏任一结点可靠性结果可知（附件2），网络可靠性大于0.4625，最高可靠性为若任意一条链路被破坏时，网络可靠性大于0.5375，题2 由MATLAB程序运行得到的破坏任一链路可靠性结果可知（附件3）最高可靠性为0.9875。

从本方案的方法上分析，避圈算法是从空图出发，逐步加边得到最小生成树。它是近似求解算法，虽然对于大多数最小生成树问题都能求得最优解，但相当一部分求得的是近似最优解，具体应用时不一定很方便。但是它可以看作是很多种最小树算法的概括，在理论上有一定的意义。破圈法是从图出发，逐步去边破圈得到最小生成树。它最适合在图上工作，当图较大时，可以几个人同时在各个子图上工作，因此破圈法在实用上是很方便的。

因此，综合两个方面来说，此方案中最小生成树的两种算法都适用于本题，可能在计算复杂度方面还需改进，因此对于实际生活中的网络连通是一种较为适用的方案。

图2 最小生成树图 5.2 问题2模型的建立与求解 5.2.1 模型的建立 （1）连通性 A、可达矩阵 为判断网络链路是否连通，在此引入布尔代数、布尔矩阵和可达矩阵概念。

定义1 以二阶布尔代数的元素为元素的阶矩阵,其中，则称为布尔矩阵。给定阶布尔矩阵，，规定矩阵的合成运算“”和取大运算“”如下: 1) ， 2) ；

3) ，; 4) 式中表示元素的取大、小运算。

定义2 在图中，，矩阵 称为可达矩阵。

布尔矩阵定义：矩阵中的元素属于0或1的矩阵，由题1邻接矩阵概念可知，图的邻接矩阵和可达矩阵是一种典型的布尔矩阵。

定理 令，则有。

B、求可达矩阵的新算法 ①可达矩阵的常用求法为 ， 其中为阶单位阵；
为简单图的邻接矩阵，其中 因为简单图，故。

②新算法（布尔代数算可达矩阵） 根据定理有 因此有 采用逐次平方法，即 令，故有，即为得到可达矩阵的最少步数[5]。

C、可达矩阵与连通性 可达矩阵表明了图中任意两结点间是否至少存在一条链以及在结点处是否有回路。通过可达矩阵，我们可以判断链路间 的连通性，例如已知一邻接矩阵 由上述布尔矩阵求可达矩阵的新算法可知，至多需要求步，即可求得可达矩阵，此时只要进行3步即可得到可达矩阵 根据这个可达矩阵，我们可知互相连通，与互不连通，与连通。其中链路权值F，详见附件1， 根据题意，若任意结点出现故障，需查看各点间的连通性，即令邻接矩阵中任意一结点出现故障，则邻接矩阵中第行和第列均定为0，这时得到新的邻接矩阵，并通过新的邻接矩阵用布尔代数可求得最后的可达矩阵，并通过可达矩阵可以判断出各个结点的连通性，具体算法由MATLAB实现。

（2）连通可靠性 在分析问题2之前，为了考虑问题中可靠性的方便和准确，定义连通可靠性为：在最小生成树中，若任意结点或者链路损坏，剩余拥有最多结点的树结点数与最小生成树总结点数之比即可衡量最小生成树的连通可靠性 本文中，由于使用最小生成树方法，此时的连通可靠性就是通信网络的可靠性。

设点个数为， 当时，任意一个结点或链路发生障碍，其最大可靠性小于90%；

当时，任意一个结点或链路发生障碍，其可靠性才有可能大于或等于90%。

例如：有6个结点的最小生成树，其中一个结点或链接发生障碍后，其形状变化分别如下图3和图4。具体如以下几种情况：
A、断结点1：在1结点出现故障后形成2-3、5-4连通的结点与孤立的6结点，此时只有两个结点之间的通信畅通，故可靠性型为。

B、断链路1-2：在链路1-2发生障碍后形成2-3、6-1-5-4两个连通的结点，故可靠性。

图3 图4 在得出连通性基础上，根据连通性定义与可靠性定义，运用MATLAB程序可直接计算得到各个结点出现故障时的连通性和这个通信网络的链接可靠性。详细的运算结果见附件2。

5.2.2 模型的求解 在问题分析及题1最优解的基础上，考虑任意一结点出现故障问题。根据通信网络结点的特性，若任一结点出现故障，则该结点不算在可靠性范围内，与之相连通的其他结点的连通性可能受到破坏，则可靠性将降低。由于除故障点外的所有其他链路均已为最优解，所以，为了提高网络的可靠性，只需将任意结点破坏（网络结点连通性状态详见附件2），并统计破坏结点后可靠性在90%以下的结点和最小生成树状态，并将互不连通的最小生成树分组，并进行下一步建模，下面以一个例子说明，如下图5所示， 图5 若破坏结点1，网络可靠性仍大于90%，则此生成树为总铺设费用最省方案最省；
若破坏结点2，可靠性小于90%，则需MATLAB编程计算出结点2破坏后，其他的结点的连通性，并根据连通性将他们分为1组2组等，再根据分组建立数学模型。

（1）0-1整数规划 若破坏结点后，可靠性小于90%，则可通过建立模型可以得到可靠性大于90%的总铺设费用最少铺设方案。

将互不连通的结点分为形如(1,3,7)的组，并命名为为阿拉伯数字1,2,3等，在以下模型中用,表示。考虑到组与组之间存在连接于不连接的问题，在此我们定义 。

建立0-1整数规划模型如下: 目标函数为 ， 其中，为第组内各结点间的链路的铺设费用总和，为组与组之间的最小铺设费用，表示第组与第组之间是否存在链路，定义如下：
为实现目标规划，本文中，由于要实现0-1整数规划，在编程过程中我们排除时成圈的情况。

， ， ， ， ， 其中表示第组内的结点数。

由于此0-1整数规划中有不成圈的隐含条件，用LINGO或MATLAB软件很难计算所以采用下述的贪婪算法进行建模求解。

（2）贪婪算法模型 若任意破坏一个结点，此时最小生成树可分为个组，将其编号为，为连线平均成本，其中为初始被选的组，均为结点，，，设为第组与第组之间的最短铺设费用，链接为第组总铺设费用，为第组结点个数，且规定初始组内结点数，为结点数。

在可靠性小于90%的基础上，若任意一个结点出现故障，由MATLAB编程可得到详细分组情况（见附件2），选择连线平均成本最小的组，并一一计算组与其他组的连线平均成本，选择与之相连最小的连线平均成本的组，，令，计算组内的可靠性，若可靠性大于90%，则停止运算，若可靠性小于90%，则继续计算组与剩余组的连线平均成本，一直计算到可靠性大于90%计算停止。具体算法过程如下：
例如图6，有以下4个组，若初始组（编号为1）（连线平均成本最小组），分别计算与其他三组的连线平均成本，得出与（编号为2）组的连通的连线平均成本最小，则，并计算其可靠性，若可靠性大于90%，则停止连通其他组；
否则，再计算组（此时为编号1,2组重新组的组）与其他两组的连线平均成本，若与4组的连线平均成本最小，则，若可靠性大于90%，则停止连通其他组，否则继续与其他组连通。

图6 由于本文中结点数较多，且算法相对复杂，运用MATLAB方法计算可得结果如下表2所示， 表2 结点出现故障后解决的情况 出现故障的结点 出现故障后系统可靠性 重新连接结点 连接后系统可靠性 成本/百元 未接入结点 2 0.7500 47连49、40连66 0.9750 24192 2、29 5 0.7250 40连66 0.9750 44917 5、78 16 0.7000 71连76 0.9625 16766 16、{25,55} 18 0.7875 46连71 0.9875 12708 18 22 0.4625 2连10、55连62 0.9625 24532 22、54、56 27 0.5750 3连74、2连10 0.9875 13524 27 35 0.6250 2连10 0.9000 34954 35、{20,29,34,80}、{40,63,79} 42 0.5625 2连10 0.9875 13316 42 45 0.8000 23连54 0.9875 24958 45 47 0.8125 40连66 0.9750 49095 47、69 51 0.8000 46连71、31连33 0.9875 10127 51 52 0.7375 46连71 0.9500 13312 52、21、{9，43} 53 0.5375 2连10 0.9750 13736 37、53 62 0.8375 66连40 0.9875 50781 62 70 0.8500 40连66、61连68 0.9500 4066 {8,14,36}、70 76 0.8125 23连54 0.9875 25266 76 77 0.8250 2连10 0.9250 4041 {6，23,57,64，75}、77 5.3 问题3模型的建立与求解 根据链路情况，现在分两种情况讨论，若铺设方案中允许出现两结点间重复铺路，则只需在破坏的链路上多铺设一条链路即可在保证可靠性达到90%的基础上，总铺设费用最省；
若不允许出现两个结点间重复铺路，则需从考虑组间最短距离着手，下面从这两个方面分别讨论。

（1）允许结点间重复铺路 根据网络连接特性，发现若一条链路被破坏，由于最小生成树只有（代表结点数）条链路，则会影响生成树的连通性，从而影响可靠性。在提高网络的可靠性兼顾铺设费用的基础上，因链路破坏后可靠性可达90%的情况下铺设费用仍然是最省的（不加边），就只需考虑链路破坏后可靠性不及90%的情况（加边）。

通过分析可知，本题任意一条链路被破坏，在题1的最小生成树方案的基础上，由于最小生成树中各点间的铺设费用已为最小值，所以只需在可靠性小于90%的链路之间再多铺设一条链路，这样在保证任意一条链路破坏后，可靠性仍大于90%的情况下，总铺设可达最少。例如在下图7最小生成树中，链路1-2破坏，可靠性小于90%，则在1-2间多铺设一条链路（见红色虚线边）， 图7 通过MATLAB编程可得任意一条链路被破坏之后的可靠性，并统计出可靠性小于90%的链路，多铺设一条相同的链路。

（2）不允许结点间重复铺路 在题1最小生成树的基础上，若不允许结点间重复铺路，任一链路被破坏， 则最小生成树将被分为若干个组，由于组内总的铺设费用已为最省铺设方案，因此在这里我们只需要在保证可靠性大于90%考虑组与组的最短距离，在本题中，由MATLAB程序得到的分组情况和可靠性，并统计可靠性小于90%的解决方案，总费用最少铺设方案如下表4所示：
表3系统出现故障后可靠性高于90%的情况 被破坏的链路 链路破坏后系统可靠性 剩余的结点 铺设费用（百元） 系统可靠性 30-51 0.9 4,30,31,38,48,58,59,60 26098 0.9 71-77 0.9 10,11,15,17,44,71,74 27310 0.9 12-51 0.9125 12,33,41,46,68,65,73 27114 0.9125 61-70 0.925 1,26,32,34,61,50 27727 0.925 12-46 0.9375 33,41,46,65,73 27514 0.9375 23-77 0.9375 6,23,57,64,75 27677 0.9375 71-74 0.9375 10,15,17,44,74 28511 0.9375 17-74 0.95 10,15,17,44 28698 0.95 20-35 0.95 20,24,39,80 26005 0.95 30-31 0.95 31,48,59,60 26692 0.95 30-38 0.9624 4,38,58 28817 0.9624 2-19 0.9625 19,28,49 28651 0.9625 3-27 0.9625 3,7,13 28868 0.9625 10-17 0.9625 10,15，44 28775 0.9625 31-59 0.9625 48，59,60 26735 0.9625 33-46 0.9625 33,41,73 28357 0.9625 34-61 0.9625 1,26,34 28506 0.9625 35-40 0.9625 40,63,79 28272 0.9625 36-70 0.9625 8,14,36 27949 0.9625 3-7 0.975 7,13 29028 0.975 4-38 0.975 4,58 29034 0.975 8-36 0.975 8,14 28109 0.975 10-44 0.975 15,44 28932 0.975 16-55 0.975 25,55 28366 0.975 20-24 0.975 24,39 28408 0.975 23-64 0.975 57,64 28388 0.975 40-63 0.975 63,79 28620 0.975 43-52 0.975 9,43 28503 0.975 50-61 0.975 32,50 28814 0.975 66-70 0.975 66,67 28954 0.975 1-34 0.9875 1 29324 0.9875 2-29 0.9875 29 28995 0.9875 4-58 0.9875 58 29337 0.9875 5-78 0.9875 78 29136 0.9875 6-23 0.9875 6 29333 0.9875 7-13 0.9875 13 29376 0.9875 8-14 0.9875 14 28577 0.9875 9-43 0.9875 9 29058 0.9875 11-71 0.9875 11 29006 0.9875 12-68 0.9875 68 29178 0.9875 15-44 0.9875 15 28968 0.9875 19-28 0.9875 28 29110 0.9875 19-49 0.9875 49 29133 0.9875 20-80 0.9875 80 27564 0.9875 21-52 0.9875 21 29010 0.9875 22-54 0.9875 54 29406 0.9875 22-56 0.9875 56 29224 0.9875 23-75 0.9875 75 29142 0.9875 24-39 0.9875 39 28994 0.9875 25-55 0.9875 25 28686 0.9875 26-34 0.9875 26 28933 0.9875 32-50 0.9875 32 29346 0.9875 33-41 0.9875 41 28667 0.9875 33-73 0.9875 73 29248 0.9875 37-53 0.9875 37 28726 0.9875 46-65 0.9875 65 28842 0.9875 47-69 0.9875 69 28788 0.9875 48-59 0.9875 48 28695 0.9875 57-64 0.9875 57 28775 0.9875 59-60 0.9875 60 27749 0.9875 63-79 0.9875 79 29178 0.9875 66-67 0.9875 67 29380 0.9875 71-72 0.9875 72 28944 0.9875 表4 链路出现故障后系统可靠性低于90%的情况 被破坏的链路 链路破坏后系统可靠性 连接 铺设费用（百元） 系统可靠性 22-53 0.5375 2连10 29516 1 42-53 0.5625 2连10 29800 1 27-42 0.575 2连10 29528 1 27-35 0.625 2连10 29628 1 16-22 0.7 55连62 29805 1 5-35 0.725 40连66 29812 1 16-52 0.7375 46连71或61连68 29866 1 2-5 0.75 40连66 29577 1 18-52 0.7875 46连71或61连68 29722 1 18-51 0.8 46连71或61连68 29704 1 22-45 0.8 23连54 29635 1 2-47 0.8125 47连49 29640 1 45-76 0.8125 23连54 29523 1 76-77 0.825 23连54 29655 1 47-62 0.8375 40连66 29541 1 62-70 0.85 40连66 29829 1 5.4 问题4模型的建立与求解 基于上述对问题4提出的三个方面，建立数学模型如下：
若在任意一条链路破坏以后，为保证可靠性达到90%，在题1的基础上需要再连接的链路令为{}，其中代表第条边。

若在任意一个结点故障以后，为保证可靠性达到90%，在题1的基础上需要再连接的链路令为{}。

在同时对题1中最小生成树中加上和时，网络的可靠性最低为0.9875，一方面可靠性很高，但另外一方面增加了75075百元费用，不符合尽量减少铺设费用的原则。

设定合理性定义为，则此方案不合理。

为使得在保证可靠性到90%的情况下，尽可能减少总铺设费用，切断铺设成本最高的链路，则当71-76链路切断时，此时的任意链路破坏的能够保证通信畅通的结点至少在0.95以上（详见表5），增加了5032百元，此时考虑到可靠性相对较高，且新增线路铺设费用相比题1 原费用相对增加少，，则此方案合理；

且任意结点故障的能够保证通信畅通的结点至少在0.9以上（详见表6），增加了5032百元，，则此方案合理。

表5 结点出现故障后再加一条边网络的可靠性 结点 网络可靠性 结点 网络可靠性 结点 网络可靠性 结点 网络可靠性 1 0.9875 21 0.9875 41 0.9875 61 0.925 2 0.975 22 0.975 42 0.9875 62 0.9875 3 0.9625 23 0.9375 43 0.975 63 0.975 4 0.975 24 0.975 44 0.975 64 0.975 5 0.975 25 0.9875 45 0.9875 65 0.9875 6 0.9875 26 0.9875 46 0.975 66 0.975 7 0.975 27 0.9875 47 0.975 67 0.9875 8 0.975 28 0.9875 48 0.9875 68 0.9875 9 0.9875 29 0.9875 49 0.9875 69 0.9875 10 0.9625 30 0.95 50 0.975 70 0.9625 11 0.9875 31 0.95 51 0.9875 71 0.9625 12 0.9875 32 0.9875 52 0.95 72 0.9875 13 0.9875 33 0.9625 53 0.975 73 0.9875 14 0.9875 34 0.9625 54 0.9875 74 0.9875 15 0.9875 35 0.9 55 0.975 75 0.9875 16 0.9875 36 0.9625 56 0.9875 76 0.9875 17 0.9875 37 0.9875 57 0.9875 77 0.9875 18 0.9875 38 0.9625 58 0.9875 78 0.9875 19 0.975 39 0.9875 59 0.9625 79 0.9875 20 0.95 40 0.9625 60 0.9875 80 0.9875 图8 结点出现故障后需加的边和链路破坏后需加的边全部加到问题1 的最小生成树上可靠性相当高的铺线模型 图9 依次移除成本高的边（此处只移除图8中一条边71－76），从得到一成本更低，稳定性友好的模型模型 表6 结点出现故障后网络的可靠性 故障点 网络可靠性 故障点 网络可靠性 故障点 网络可靠性 故障点 网络可靠性 1 0.9 21 0.975 41 0.9875 61 0.9875 2 0.925 22 0.975 42 0.9875 62 0.9875 3 0.9375 23 0.975 43 0.9875 63 0.9875 4 0.95 24 0.975 44 0.9875 64 0.9875 5 0.95 25 0.975 45 0.9875 65 0.9875 6 0.95 26 0.975 46 0.9875 66 0.9875 7 0.95 27 0.975 47 0.9875 67 0.9875 8 0.9625 28 0.975 48 0.9875 68 0.9875 9 0.9625 29 0.975 49 0.9875 69 0.9875 10 0.9625 30 0.975 50 0.9875 70 0.9875 11 0.9625 31 0.975 51 0.9875 71 0.9875 12 0.9625 32 0.975 52 0.9875 72 0.9875 13 0.9625 33 0.975 53 0.9875 73 0.9875 14 0.9625 34 0.975 54 0.9875 74 0.9875 15 0.9625 35 0.975 55 0.9875 75 0.9875 16 0.9625 36 0.9875 56 0.9875 76 0.9875 17 0.9625 37 0.9875 57 0.9875 77 0.9875 18 0.975 38 0.9875 58 0.9875 78 0.9875 19 0.975 39 0.9875 59 0.9875 79 0.9875 20 0.975 40 0.9875 60 0.9875 80 0.9875 表7 移除成本最长的边以后再测切断一条边模型的稳定性 切断的一条边 切断边后网络的可靠性 切断的一条边 切断边后网络的可靠性 切断的一条边 切断边后网络的可靠性 10—17 1 23—77 1 4—58 0.9875 10—44 0.975 24—39 0.9875 46—65 1 11—71 0.9875 2—47 1 47—49 1 12—46 1 2—5 1 47—62 1 12—51 1 25—55 0.9875 47—69 1 12—68 1 26—34 0.9875 48—59 1 1—34 0.9875 27—35 1 50—61 0.975 15—44 0.9875 27—42 1 55—62 1 16—22 1 30—31 1 57—64 0.9875 16—52 1 30—38 0.9625 5—78 0.9875 16—52 1 30—51 1 59—60 0.9875 17—74 1 31—33 1 61—68 1 18—51 1 31—59 0.9625 61—70 1 18—52 1 32—50 0.9875 6—23 0.9875 18—52 1 3—27 1 62—70 1 19—28 0.9875 33—41 0.9875 63—79 0.9875 19—49 1 33—46 1 66—67 0.9875 20—24 0.975 33—73 0.9875 66—70 1 20—35 0.95 34—61 0.9625 67—66 0.9875 20—80 0.9875 35—40 1 7—13 0.9875 2—10 1 36—46 1 71—72 0.9875 21—52 9.875 36—70 1 71—74 1 2—19 1 3—7 0.975 71—76 1 22—45 1 3—74 1 71—77 1 22—53 1 37—53 0.9875 7—3 0.975 22—54 1 40—46 1 8—14 0.9875 22—56 0.9875 40—63 0.975 8—36 1 2—29 0.9875 42—53 1 9—43 0.9875 23—64 1 43—52 0.975 45—76 1 23—75 1 4—38 0.975 　 　 六、模型优缺点及其改进 优点：本文中很好的运用了可达矩阵来判断连通性，在通过定义可靠性，用0-1整数规划和贪婪算法分析了在任一结点或者链路破坏的情况下，其他结点间仍然能够保持畅通的可能性未能达到90%的总费用最省方案。且这个模型和本题网络适应性良好，得到的解均最大近似最优点。

缺点：计算量较大，算法复杂。

改进：若能将破坏任意结点或链路的网络可靠性自动筛选出可靠性<90%的情况并进行下一步运算。

参考文献 [1] 徐星. 浅议计算机网络通信的技术特点与发展前景[J]. 无线互联科技, 2013, 03: 38. [2] 章筠. 计算机网络可靠性分析与设计[D]. 杭州: 浙江大学, 2012. [3] 董跃华, 李云浩, 姜在东. 用破圈法实现普里姆算法[J]. 江西理工大学学报, 2008, 29(4): 20-22. [4] Lin W.M.,Tsay M.T Wu S.W. Application of geographic information system for substain and feeder planning[J].International Journal of Electrical Power and Energy System,IEEE,Mar 1996:175-183. [5] 杨秀文, 严尚安, 张洁, 曾顺鹏. 可达矩阵的新求法[J]. 电子科技大学学报, 2000, 29(6): 666-668. 附录 附录1：由邻接矩阵计算可达矩阵程序 function y=kedajz(linjiejuzhen,N) %linjiejuzhen表示邻接矩阵,N表示迭代次数 %clear,clc %linjiejuzhen=[0 1 0 0 1 1;1 0 1 0 0 0;0 1 0 0 0 0;0 0 0 0 1 0;1 0 0 1 0 0;1 0 0 0 0 0]; kedajuzhen=linjiejuzhen+eye(size(linjiejuzhen)); Nkedajuzhen=eye(size(linjiejuzhen)); %N=200; for i=1:N Nkedajuzhen01=Nkedajuzhen>0; temp=Nkedajuzhen>0; Nkedajuzhen= Nkedajuzhen*kedajuzhen; Nkedajuzhen01=Nkedajuzhen>0; tttt=abs(Nkedajuzhen01-temp); ibianshu=i-1; if sum(sum(tttt))<0.1,break,end Nkedajuzhen=Nkedajuzhen; Nkedajuzhen01=Nkedajuzhen01 ; end y=Nkedajuzhen01; 附录2：根据可达矩阵将最小生成树分成若干组内走通组间不走通的子树（小组） function [zuidazuds,jiedianzu]=fenzu(kedajuzhen) n=length(kedajuzhen);%可达矩阵的行数，结点数 index=1:n;%初始的所有几点 flag=ones(1,n); for i=1:n temp=[]; for j=1:n if kedajuzhen(i,j)>0&flag(j)>0 temp=[temp,i,j];flag(j)=0; end end jiedianzu0{i}=unique(temp); end zushu=0;zuidazuds=0; for i=1:length(jiedianzu0) if length(jiedianzu0{i})>0 zushu=zushu+1; jiedianzu{zushu}=jiedianzu0{i}; end if length(jiedianzu0{i})>zuidazuds zuidazuds=length(jiedianzu0{i}); end end 附录3：切断任意一条边后计算网络的可靠性 clear,clc load data1.mat %该文件用于切断一条边以后的网络可靠性计算程序 %linjiejuzhen=[0 1 0 0 1 1;1 0 1 0 0 0;0 1 0 0 0 0;0 0 0 0 1 0;1 0 0 1 0 0;1 0 0 0 0 0]; %linjiejuzhen(1,5)=0;linjiejuzhen(5,1)=0; %linjiejuzhen(1,:)=0;linjiejuzhen(:,1)=0;%破坏结点1 %linjiejuzhen(5,:)=0;linjiejuzhen(:,5)=0;%破坏结点1 N=40000;%设置迭代次数 n=length(mintrM);%总的结点数 for i0=1:n for j0=1:n linjiejuzhen=mintrM; clc if linjiejuzhen(i0,j0)>0 linjiejuzhen(i0,j0)=0; linjiejuzhen(j0,i0)=0; [iiii,jjj]=find(mintrM-linjiejuzhen>0) fprintf(＇切断边%d---%d后，计算系统可靠性：＇,i0,j0) kedajuzhen=kedajz(linjiejuzhen,N);%根据邻接矩阵计算的可达矩阵 [zuidazuds,jiedianzu]=fenzu(kedajuzhen);%jiedianzu中的元素已分组，组内连通，组间不联通 disp(＇网络可靠度为：＇) kekaodu=zuidazuds/n for i=1:length(jiedianzu) fprintf(＇第%d组的结点如下，组内结点连通，组间不连通＇,i) eval([＇zu_＇,num2str(i),＇=jiedianzu{i}＇]) end disp(＇－－－－－统计结果后，请按“ENTER”键继续－－－－－－＇),pause end end end 附录4：破坏一个结点后，计算网络的可靠性 clear,clc load data1.mat %该文件用于坏点以后的网络可靠性计算程序 %linjiejuzhen=[0 1 0 0 1 1;1 0 1 0 0 0;0 1 0 0 0 0;0 0 0 0 1 0;1 0 0 1 0 0;1 0 0 0 0 0]; %linjiejuzhen(1,5)=0;linjiejuzhen(5,1)=0; %linjiejuzhen(1,:)=0;linjiejuzhen(:,1)=0;%破坏结点1 %linjiejuzhen(5,:)=0;linjiejuzhen(:,5)=0;%破坏结点1 N=40000;%设置迭代次数 n=length(mintrM);%总的结点数 for i0=1:n linjiejuzhen=mintrM; clc linjiejuzhen(i0,:)=0; linjiejuzhen(:,i0)=0; %[iiii,jjj]=find(mintrM-linjiejuzhen>0) fprintf(＇破坏%d---%d后，计算系统可靠性：＇,i0) kedajuzhen=kedajz(linjiejuzhen,N);%根据邻接矩阵计算的可达矩阵 [zuidazuds,jiedianzu]=fenzu(kedajuzhen);%jiedianzu中的元素已分组，组内连通，组间不联通 disp(＇网络可靠度为：＇) kekaodu=zuidazuds/n for i=1:length(jiedianzu) fprintf(＇第%d组的结点如下，组内结点连通，组间不连通＇,i) eval([＇zu_＇,num2str(i),＇=jiedianzu{i}＇]) end disp(＇－－－－－统计结果后，请按“ENTER”键继续－－－－－－＇),pause end 附录5：若一条边截断可靠性低于90%，计算如何加边以保网络可靠性达90% clear,clc load data1.mat %该文件用于坏点以后的网络再连接计算程序 %linjiejuzhen=[0 1 0 0 1 1;1 0 1 0 0 0;0 1 0 0 0 0;0 0 0 0 1 0;1 0 0 1 0 0;1 0 0 0 0 0]; %linjiejuzhen(1,5)=0;linjiejuzhen(5,1)=0; %linjiejuzhen(1,:)=0;linjiejuzhen(:,1)=0;%破坏结点1 %linjiejuzhen(5,:)=0;linjiejuzhen(:,5)=0;%破坏结点1 N=40000;%设置迭代次数 n=length(mintrM);%总的结点数 %for i0=1:n fflag=0; for i0=1:length(Bianji) linjiejuzhen=mintrM; clc linjiejuzhen(Bianji(i0,1),Bianji(i0,2))=0; linjiejuzhen(Bianji(i0,2),Bianji(i0,1))=0; %[iiii,jjj]=find(mintrM-linjiejuzhen>0) fprintf(＇破坏边%d---%d后，计算系统可靠性：＇,Bianji(i0,1),Bianji(i0,2)) kedajuzhen=kedajz(linjiejuzhen,N);%根据邻接矩阵计算的可达矩阵 [zuidazuds,jiedianzu]=fenzu(kedajuzhen);%jiedianzu中的元素已分组，组内连通，组间不联通 disp(＇网络可靠度为：＇) kekaodu=zuidazuds/n if kekaodu<0.9 fflag=1; end %---------以下计算结算结点破坏后，如何从新铺线 %linjiezhen_zu=linjiejuzhen(zu_3,zu_3)%得到第3组的邻接矩阵 %feiyong_zu=feiyong(zu_3,zu_3)%第i=3组内已有的单位铺线费用 %ci=linjiezhen_zu.*feiyong_zu %第i=3组内已有的铺线费用 %feiyong_zu=feiyong(zu_2,zu_3);%zu_2,zu_3两组点间连线的费用矩阵 %sij=min(min(feiyong_zu));%zu_2,zu_3两组点间连线的最小费用 %[node1,node2]=find(sij==feiyong_zu);%两组点间有最小连线费用的结点 %zu_2,zu_3两组点间连线的平均费用avgsij=(c2+c3+s23)/(d2+d3),其中d2,d3表示组内结点数 %disp(＇－－－－－统计结果后，请按“ENTER”键继续－－－－－－＇),pause %当结点i0被破坏后，必须重结点集删除i0 z0zilianjieidian=[]; if fflag>0; feiyong00=feiyong;ttt0=feiyong00(Bianji(i0,1),Bianji(i0,2)); feiyong00(Bianji(i0,1),Bianji(i0,2))=99999999999999; feiyong00(Bianji(i0,2),Bianji(i0,1))=99999999999999; feiyong_zu=feiyong00(jiedianzu{1},jiedianzu{2});%zu_2,zu_3两组点间连线的费用矩阵 sij=min(min(feiyong_zu));%zu_0,zu_0两组点间连线的最小费用 [node1,node2]=find(sij==feiyong00);%zu_0到zu_i两组点间有最小连线费用的结点 z0zilianjieidian=[node1,node2]; %zu_0,zu_i两组点间连线的最小费用对应的结点. disp(＇==========================================================＇) fprintf(＇破坏边%d--%d后,再连接以后系统可靠性：＇,Bianji(i0,1),Bianji(i0,2)) 1.00 fprintf(＇破坏边%d--%d后,再连接以后联网的成本为：＇,Bianji(i0,1),Bianji(i0,2)) clwcb=disitance+sij-ttt0 fprintf(＇破坏边%d----%d后,重新连接结点为：＇,Bianji(i0,1),Bianji(i0,2)) z0zilianjieidian=z0zilianjieidian pause end end %for 破坏结点i0 附录6：若结点破坏后可靠性低于90%，计算如何加边以保证网络可靠性大于90%。

clear,clc load data1.mat %该文件用于坏点以后的网络再连接计算程序 %linjiejuzhen=[0 1 0 0 1 1;1 0 1 0 0 0;0 1 0 0 0 0;0 0 0 0 1 0;1 0 0 1 0 0;1 0 0 0 0 0]; %linjiejuzhen(1,5)=0;linjiejuzhen(5,1)=0; %linjiejuzhen(1,:)=0;linjiejuzhen(:,1)=0;%破坏结点1 %linjiejuzhen(5,:)=0;linjiejuzhen(:,5)=0;%破坏结点1 N=40000;%设置迭代次数 n=length(mintrM);%总的结点数 %for i0=1:n fflag=0; for i0=1:n linjiejuzhen=mintrM; clc linjiejuzhen(i0,:)=0; linjiejuzhen(:,i0)=0; %[iiii,jjj]=find(mintrM-linjiejuzhen>0) fprintf(＇破坏%d---%d后，计算系统可靠性：＇,i0) kedajuzhen=kedajz(linjiejuzhen,N);%根据邻接矩阵计算的可达矩阵 [zuidazuds,jiedianzu]=fenzu(kedajuzhen);%jiedianzu中的元素已分组，组内连通，组间不联通 disp(＇网络可靠度为：＇) kekaodu=zuidazuds/n if kekaodu<0.9 fflag=1; end for i=1:length(jiedianzu) % fprintf(＇第%d组的结点如下，组内结点连通，组间不连通＇,i) % eval([＇zu_＇,num2str(i),＇=jiedianzu{i}＇]) end %---------以下计算结算结点破坏后，如何从新铺线 %linjiezhen_zu=linjiejuzhen(zu_3,zu_3)%得到第3组的邻接矩阵 %feiyong_zu=feiyong(zu_3,zu_3)%第i=3组内已有的单位铺线费用 %ci=linjiezhen_zu.*feiyong_zu %第i=3组内已有的铺线费用 %feiyong_zu=feiyong(zu_2,zu_3);%zu_2,zu_3两组点间连线的费用矩阵 %sij=min(min(feiyong_zu));%zu_2,zu_3两组点间连线的最小费用 %[node1,node2]=find(sij==feiyong_zu);%两组点间有最小连线费用的结点 %zu_2,zu_3两组点间连线的平均费用avgsij=(c2+c3+s23)/(d2+d3),其中d2,d3表示组内结点数 %disp(＇－－－－－统计结果后，请按“ENTER”键继续－－－－－－＇),pause %当结点i0被破坏后，必须重结点集删除i0 if fflag>0; %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % if length(jiedianzu{i0zu})==0 %jiedianzu(i0zu)=[]; % end % jiedianzu=jiedianzu %计算每一个结点组的平均成本 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% c=[];avgc=[];%计算每一个结点组的平均成本 for i=1:length(jiedianzu) if length(jiedianzu{i})==0 c(i)=99999999999; %第i3组内已有的铺线费用 avgc(i)=999999999; %第i组内已有的平均每个结点的铺线费用 else zu_i=jiedianzu{i}; linjiezhen_zu=linjiejuzhen(zu_i,zu_i);%得到第3组的邻接矩阵 feiyong_zu=feiyong(zu_i,zu_i);%第i组内已有的单位铺线费用 c(i)=sum(sum(linjiezhen_zu.*feiyong_zu))/2; %第i3组内已有的铺线费用 avgc(i)=c(i)/length(zu_i); %第i组内已有的平均每个结点的铺线费用 end end %选取初始结点z0要求成本最低，结点数大于最多的组且大于10％ [temp,index0]=sort(avgc);% jiedianzu00=jiedianzu;c0=0; for i=1:length(jiedianzu00) if length(jiedianzu{index0(i)})>n*0.10% z0=jiedianzu{index0(i)};%已并入网中的结点 jiedianzu00(index0(i))=[];%从jiedianzu00中移除已并入网中的结点 c(index0(i))=[];%从成本c中移除已并入网中的结点的成本 c0=c0+c(index0(i));%已并入网中的结点的总成本 break end %riwangzuxu=[riwangzuxu,index0(i)];%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% end iter=0; lianxian=[]; while length(z0)<n*0.9 iter=iter+1; fprintf(＇--------------第%d次迭代－－－－－－－＇,iter) %计算z0组到其他各组间的最短距离sij,以及连接的结点 s=[]; z0zilianjieidian=[]; %重新计算jiedianzu00中 for i=1:length(jiedianzu00) feiyong_zu=feiyong(z0,jiedianzu00{i});%zu_2,zu_3两组点间连线的费用矩阵 sij=min(min(feiyong_zu));%zu_0,zu_0两组点间连线的最小费用 s(i)=sij;%zu_0到zu_i两组点间连线的最小费用 [node1,node2]=find(sij==feiyong_zu);%zu_0到zu_i两组点间有最小连线费用的结点 z0zilianjieidian=[z0zilianjieidian;z0(node1(1)),jiedianzu00{i}(node2(1))]; %zu_0,zu_i两组点间连线的最小费用对应的结点. end %计算联入结点的平均总成本 avgs=[]; for i=1:length(jiedianzu00) avgs(i)=(s(i)+c(i))/length(jiedianzu00{i});%计算新连入结点的平均成本 if abs(prod(jiedianzu00{i}-i0))==0 avgs(i)=9999999999999; end end minavgs=avgs(1);t0=1; for i=1:length(jiedianzu00) if minavgs>avgs(i) minavgs=avgs(i);t0=i;%选t0组联入z0时，新连入结点的平均成本最低 end end z0=[z0,jiedianzu00{t0}];%将t0组合并到z0组 lianxian=[lianxian; z0zilianjieidian(t0,:)] jiedianzu00(t0)=[];%删除t0组 c0=c0+c(t0)+s(t0);%计算入网总成本，其余各组成本要重新计算c c(t0)=[]; disp(＇==========================================================＇) fprintf(＇破坏结点%d后,再连接以后系统可靠性：＇,i0) kkd=length(z0)/n fprintf(＇破坏结点%d后,再连接以后联网的成本为：＇,i0) clwcb=c0 fprintf(＇破坏结点%d后,重新连接结点为：＇,i0) lianxian=lianxian end pause end end %for 破坏结点i0 附录7：问题四求解程序 clear,clc %global linjiejuzhen00 load data1.mat linjiejuzhen00=mintrM; %kedajuzhen=kedajz(linjiejuzhen00,N) %[zuidazuds,jiedianzu]=fenzu(kedajuzhen) linjiejuzhen_jianbian linjiejuzhen=linjiejuzhen00; N=40000;%设置迭代次数 n=length(mintrM);%总的结点数 fid=fopen(＇wenti44.txt＇,＇w＇) for i0=1:n for j0=1:n linjiejuzhen=linjiejuzhen00; clc if linjiejuzhen(i0,j0)>0 linjiejuzhen(i0,j0)=0; linjiejuzhen(j0,i0)=0; fprintf(fid,＇-------------------------------------------------＼n＇) fprintf(fid,＇切断边%d---%d后，计算系统可靠性：＼n＇,i0,j0) fprintf(＇切断边%d---%d后，计算系统可靠性：＇,i0,j0) kedajuzhen=kedajz(linjiejuzhen,N);%根据邻接矩阵计算的可达矩阵 [zuidazuds,jiedianzu]=fenzu(kedajuzhen);%jiedianzu中的元素已分组，组内连通，组间不联通 disp(＇网络可靠度为：＇) kekaodu=zuidazuds/n fprintf(fid,＇网络可靠度为：%d＼n＇,kekaodu) for i=1:length(jiedianzu) fprintf(＇第%d组的结点如下，组内结点连通，组间不连通＇,i) eval([＇zu_＇,num2str(i),＇=jiedianzu{i}＇]) end %disp(＇－－－－－统计结果后，请按“ENTER”键继续－－－－－－＇),pause end end end fclose(fid)