通信网络的设计问题

1、基于规划模型对通信网络的设计问题的求解摘要本文主要就通信网络的设计问题进行讨论，随着当今社会信息的迅猛发展，计算机在许多领域的应用范围已经逐步广泛起来，信息网络再给我们带来便捷的同时， 也给我们带来了一定的隐患。 通信网络的可靠性不仅与通信设备、 链路有关，而且还与网络结构有关。 因此，通信网络的设计对我们的日常生活有十分重要的意义。对于问题一， 我们首先要求出各节点间的铺设费用，我们对给出的数据做预处理，将节点间距离和节点间单位铺设费用在excel 表格中做乘法处理， 所得结果就是各节点间的铺设费用，要使得通信网络的总铺设费用最省，利用lingo编程计算，可知总铺设费用最少为29478 百元

2、。对于问题二， 在问题一的基础上， 我们考虑到若其中有一个重要节点发生故障时，会造成八个节点（包括自己）以上故障，那么通信畅通的可能性就不能保证达到90%，所以，我们可以通过节点删除法找到重要节点，然后再从重要节点引起故障的其他失效节点中找到一个节点与其他正常节点连通使得发生故障的节点数少于八个，我们就能保证通信畅通的可能性达到90%。利用lingo编程计算，可知总铺设费用最少为 30542百元。关键词：最小生成树节点删除法最省费用一、问题重述1 某通信公司拟建一个具有80个节点的通信网络，需要在这些节点之间铺设线路， 进行数据传输。 节点之间的距离和铺设线路的单位费用见附件 1，请对以下问题

3、进行研究：问题1要使得通信网络的总铺设费用最省，请建立问题的数学模型，设计求解算法，给出铺设方案，并讨论方案的可靠性；问题2考虑到通信网络节点的可靠性，若要求任意一个节点出现故障时，其它节点间仍然能够保持通信畅通的可能性都达到90%，请建立问题的数学模型， 设计求解算法， 并给出使总铺设费用最少的铺设方案；二、问题分析本题旨在研究分析通信网络铺设线路的费用以及可靠性, 解决问题的关键在于如何使费用最省，找出准确的求解方法。针对问题一： 主要是考虑在确定各个节点之间的关系时，以铺设费用为最少为前提， 然后根据 prim法求最小生成树， 先以一个节点为基点设为1，在剩下 79个节点中找出一个节点与

4、1相连使费用最少，然后以这两个节点为新的基点设为2，再在剩下的 78个节点中找出一个节点与2相连使费用最少，然后以这三个节点为新的基点设为3，以此类推可以得到4、580，即可得出结果。针对问题二： 在问题一的基础上稍作改进，在任意一个节点出现故障时其它节点间仍然能够保持通信畅通的可能性都达到90%时，就是在任何的一个节点发生故障时，要保证不会因此超过八个点出现2 故障。所以我们要解决造成超过八个点故障的情况，我们分析可知可以将发生故障的某个节点外的失效节点与其他正常节点相连接，就能确保通信畅通的可能性都达到90%。然后求出的最短路径可以算出最省总铺设费用。三、模型的假设1.假设所给数据准确无误

5、2.假设两个节点之间的费用仅由单位费用和距离决定四、符号说明（1）节点；(2) ija第i与第j节点间的距离；（3）ijb第i与第j节点间单位铺设费用；（4）ijc第i与第j节点间铺设费用；（5）iss重要节点出现故障后造成可靠性小于90%节点集合（6）iss重要节点出现故障后不影响可靠性的节点集合（7）ijdis中节点到js中节点的最省费用（8）idis中节点到非is中节点的最省费用五、模型的建立与求解1.通信网络的总铺设费用最省1.1 首先，求出各节点间铺设费用。根据附件中所给的数据（节点距离表、节点单位铺设费用表） ，根据公式 : 3 *ijijijcab即可算出节点间的铺设费用。1.2

6、 节点间的铺设费用即为由80个节点所围的最小生成树的权，再用lingo编程（见附件 1）即可求出最小生成树的权，最小生成树的权即为最少的费用（见图1）。图1 即最省费用为 29478百元。1.3 利用附件 1程序的结果可以画出最小生成树图（见图2）. 4 图2 2. 通信网络节点的可靠性2.1 要保证在任意一个节点出现故障时其它节点间仍然能够保持通信畅通的可能性都达到90%，就要找到这些重要节点。 确定通信网中最重要节点的方法节点删除法。分析图2可以找到 51、 70、77三个重要节点。2.2将最小生成树图分为图 3所示区域：5 图3 然后分别求出12d、2313dd、以及123ddd、，最后

7、考虑可靠性增加到费用最省为 min12d+3d，23d+1d，13d+2d。2.3 用lingo编程（见附件 2）计算得12d、2313dd、分别为 2091（6061） 、 536 （1538） 、 780 （172） 百元。123ddd、，分别为 528（6168） 、536（1538） 、470（210）百元。由于考虑可靠性增加的费用最省为min2561 ，1064，1316=1064 百元。所以，最省费用为 29478+1064=30542 （百元） 。最后的路线图为图 4所示：6 图4 六、模型推广可以在保证节点数不变的情况下，任意改变节点间的信息， 运用该模型同样可以求得连接节点的

8、最省费用。且不需要过多改动， 不需要人工进行修改计算的结果。 如果想继续优化， 但是在节点数变化的情况下，则需要较大改动，即寻找重要节点。同时该模型可以应用到修建管道、公路等。七、参考文献1 姜启源等，数学模型（第四版），北京：高等教育出版社，20117 2 薛定宇，陈阳泉，高等应用数学问题的matlab 求解，清华大学出版社， 20083 赵静，但琦等，数学建模与数学实验 ，高等教育出版社， 2008 八、附录附件1：model: sets: cities/1.80/:level; link(cities,cities):distance,x; endsets data: distance=

9、 （数据 80*80）；enddata n=size(cities); min=sum(link(i,j)|i#ne#j :distance(i,j)*x(i,j); sum(cities(i)|i#gt#1:x(1,i)=1; for(cities(i)|i#gt#1: sum(cities(j)|j#ne#i:x(j,i)=1; for(cities(j)|j#gt#1#and#j#ne#i:level(j)=level(i)+x(i,j)-(n-2)*(1-x(i,j)+(n-3)*x(j,i);); bnd(1,level(i),999999); level(i)=n-1-(n-2)*x(1,i); ); for(link:bin(x); end 附件2：8 mo