《2022年研究生数学建模答案范本》由会员分享，可在线阅读，更多相关《2022年研究生数学建模答案范本（21页珍藏版）》请在金锄头文库上搜索。
1、2022年研究生数学建模答案范本数 学 建 模 题目：A 队号：20_45A 20_年5月25 题目A：通信网络的设计问题 摘 要 本文主要研究通信网络在铺设线路上遇到的总铺设本钱，及网络结点和链路可靠性问题的建模建立并对某通信公司所建立的80个结点所铺设线路提出最优铺设方案。问题1是网络设计常见的本钱最低化问题，通过简化将问题转为寻找权值最小的最小生成树问题，并利用避圈法和破圈法得到最小生成树。考虑整数规划模型求解的复杂性，设计了贪心算法，对其中17个结点出现故障后结点的详细连接方法见详见14页表2。假设结点出现故障后，网络本身仍能保持90那么无需在连链路，故在表2中未进展考虑。由表2知，贪
2、心算法的结果能保证92.5的结点通信畅通。对于问题3，要求任意一条链路破坏时，为保证90以上的结点通信畅通分两种情况进展考虑。假如任意一条链路破坏后，仍有90以上的结点保持通信畅通，这些链路无需追加链接详15页见表3。另外一些链路在破坏后，不能保证90的结点通信畅通，需追加链接，即加边。要加边时，假设允许某些结点连2条边，那么只需对原最小生成树的某些结点连两条一样边复制某最小生成树的某两结点间的被破坏的边，使之形成回路即可，该链路仍然为总铺设费用最省方案。假如不允许任意结点连两条边，由于破坏一边，整个树一分为二，只需计算两组结点间的最短间隔 ，即可连一条新的最短路。在可靠性不小于90的情况下，
3、得到总铺设费用方案详17页见表4.对于问题四，综合考虑网络的可靠性以及铺设费用后，根据问题2和问题3的结果，将结点出现故障后需加的边和链路破坏后需加的边全部加到问题1 的最小生成树上，得到可靠性相当高的铺线模型(见19页图8)，该模型任意一结点出现故障后，结点保持畅通的可能性最低在90以上详18页见表5。考虑到该模型本钱高，需增加的铺设费用为750.75万元。因此，依次移除本钱高的边此处只移除图8中一条边7176，从得到一本钱更低，稳定性友好的模型模型(见20页图9)，此时只需增加本钱5032万元。任意一结点出现故障后，结点保持畅通的可能性最低在90以上详21页见表6。对边有类似的结果分别见表
4、7，那么此方案合理。【关键词】：p 】： ：最小生成树，破圈法，网络模型，图论 一、问题重述 随着科学技术的进步，计算机和网络技术获得了快速开展，成为信息交流手段，浸透到社会的各个方面，其开展也在不断的推动人类社会逐渐走向信息时代。网络技术的开展在给人们生活及社会消费力的进步提供了宏大奉献的同时，也存在着许多平安隐患、信息破绽，如最近出现的网络OpenSSL“心血”破绽等。这些对于人们的工作和生活造成了很大的影响。对于一个系统，可靠性是其重要的整体指标，通信网络亦不例外。通信网络的可靠性不仅与通信设备、链路有关，而且还与网络构造有关。由于网络构造的复杂多变，通信网络的可靠性分析p 一直是个棘手
5、的问题。某通信公司拟建一个具有80个结点的通信网络，需要在这些结点之间铺设线路，进展数据传输。结合结点之间的间隔 和铺设线路的单位费用见附件1，本文需要详细完成以下问题：问题1：要使得通信网络的总铺设费用最省，请建立问题的数学模型，设计求解算法，给出铺设方案，并讨论方案的可靠性；问题2：考虑到通信网络结点的可靠性，假设要求任意一个结点出现故障时，其它结点间仍然可以保持通信畅通的可能性都到达90，请建立问题的数学模型，设计求解算法，并给出使总铺设费用最少的铺设方案；问题3：考虑到通信网络链路的可靠性，假设要求任意一条链路被破坏时，可以保持通信畅通的结点都可以到达90，请建立问题的数学模型，设计求
6、解算法，并给出使总铺设费用最少的铺设方案；问题4：综合考虑网络的可靠性以及铺设费用，试确定合理的铺设方案。二、模型假设 1、假设结点与结点之间的连接不存在先后顺序，且均以直线连接 2、假设不考虑结点大小 3、假设不考虑线路铺设费用对线路连通的影响 4、假设通信网络中结点间间隔 固定不变且数据可靠 5、假设链路和结点只有故障、正常两种状态 6、假设网络中链路故障的概率是统计独立的 7、不考虑网络线路及结点内容量问题 三、定义与符号说明 ：链路权值=结点间间隔 结点间铺设线路单位费用 ：结点个数、 ：结点名 ：边 ：树 四、问题分析p 计算机网络通信是现代最为流行、最为尖端和最为新颖的通信技术手段
7、，也是现代信息技术开展的极致。开展到如今,已经进入到了一个智能化、宽带化与综合化的阶段，其开展的前景也被广泛看好1。因此，在保证网络通信平安的前提下，网络可靠性是一个系统中比拟重要的整体指标。网络可靠性评估是网络可靠性相关研究的根底，是目前网络可靠性研究领域的一大热点，而基于可靠性的网络设计那么能针对网络可靠性、网络构建费用等网络设计目的，提供各种优化方案供网络管理者参考2。从问题重述可知，此题属于网络道路优化问题。在网络通信时，数据需要在结点间传输，这就需要在结点间铺设线路。由于地理位置和间隔 等其它因素, 使各结点之间架设网线的费用不同, 公司想使各结点之间的网络畅通并且把费用降到最低,
8、那么应该怎样来设计各结点间的线路，这是本文的关键。在线路建立中不仅需要考虑本钱问题，还要考虑到方案的可靠性，以保证在任意结点或链路出现故障时，通信仍能畅通。参考附件1的结点之间的间隔 和铺设线路的单位费用，下面就每个问题进展分析p ：对于问题1：是网络设计方案中常见问题，即本钱最低化。可以结合附件1中给出的结点间间隔 和铺设线路单位费用，由链路权值，可把问题简化为寻找最小生成树问题。一棵生成树的代价就是树上各边的代价之和，此时这颗最小生成树的总权值即为此题中的最省总铺设费用，使用条不产生回路的边来连接网络中的个顶点来构造最小生成树3。对于问题2：由题1结论可知，此最小生成树是在网络连通的根底上
9、，考虑最少总铺设费用。因此，在任意结点和线路不出现故障时，此种解决方案为最优解。在通信网络中，不仅需要考虑铺设费用问题，还往往要考虑可靠性问题。问题二中，要求在结点可靠性90的根底上，求解最少总铺设费用问题，这就存在两个需要考虑的因素：一是在可靠性到达90时，优先考虑最省总铺设费用；二是可靠性在到达90的情况下优先考虑进步可靠性，再计算最少铺设费用。由于时间的问题和算法的复杂性，本文就前者因素建立模型，并求解。对于问题3：连通性定义和可靠性定义见题2，此题将不再做定义，直接运用。根据题2的连通性和可靠性定义，运用MATLAB可得破坏任意一条链路时各个结点间连接关系。根据题1可知：所生成的最小生
10、成树已为网络总铺设费用最省的方案，如今考虑任意一条链路被破坏时网络可靠性达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 中所有顶点且无回路的
11、连通子图，那么G0是G的一棵生成树。假设G有n个顶点，那么它的生成树有n个顶点，n-1条边。一个图可以有很多不同的生成树。其中，各条边权值之和最小的生成树即为最小生成树。根据最小生成树的定义及性质可以得到如下几个结论设图G1是图G的最小生成树。1G1中的各条边权值之和最小。2G1中有n 个顶点n-1条边。3G1必须是连通的且无回路。因此，只要在一个连通带权图里找到一个同时满足上述三个条件的图，也就找到了该图的最小生成树。为了研究的方便，将此题中的通信网络简化为各个结点与结点之间的连线，并不计结点大小，下文中一律将此连线叫做链路。因此，可以得到一个生成树模型。其中链路权值F，详见附件1，结点编号
12、为。假设该公司所建立的局部结点所在位置简化如图1所示。顶点代表结点编号，边代表可以架设网线的链路,这样就构成了一个带权连通图, 从而最小费用问题就转化为求所得到的带权连通图的最小生成树的问题。图1 局部结点的通信网络简化图 5.1.2 模型的求解 常用的最小生成树的算法破圈法和避圈法。此题采用这两种方法分别对模型求解。1避圈法 避圈法计算步骤如下：Step1：从网络中任选一点vi，令，；Step2：从连接与的边中选取最小边, 不妨设最小边为vi，vj，该边必为优化道路中的一条；Step3：重新修正集合与的组成元素，在集合中增加顶点，显然在集合中减少该顶点；Step4：假如空集，那么停顿，已找到
13、所有的优化道路，否那么返回第2 步。下面就该网络中的一个结点简单说明本通信网络用避圈法求解最小生成树的方法。通信网络铺设最优方案问题用避圈法求解过程如下： 假设从结点开场，即 从与的链接中共有79种情况，经过计算比拟得出，从结点到结点之间铺设的费用为最小费用。那么将连接起来，即标记为最小局部树内的边； 重新修正集合与后，可得与； 因为当前，所以要回到第二步，这时通过计算可以发现连接与的156条边中，从结点到结点之间铺设的费用为最小费用。那么将连接起来。而在此过程中没重复一次第二步，通过计算铺设费用，比拟出得到最小边，最后连接成最小生成树，即为实现通信网络的总铺设费用最省的铺设方案，并得到铺设费
14、用为29478百元，其中最小生成树图如图2，各结点间的铺设费用如表1。2破圈法 破圈法相比避圈法的思路简单。所谓破圈法就是“任取一圈，去掉圈上权值最大的边”反复执行这一步骤直到没有圈为止4。通过前文可知，已将通信网络建立为一个连通图。此时问题可简化为用破圈法求解最小生成树问题。Step1：在网络图中找到一个圈, 去掉圈中的最长的一条边；Step2：检查网络图中是否还有圈，假如有，重复第1步，否那么停顿，说明已找到最优道路。由于结点数较多，用MATLAB编程实现，就不再详细说明，最终输出结果与避圈法一样。通过以上两种方法均得到网络线路铺设的最小生成树。表1：各结点间链路的铺设费用 序号 链接 费
15、用/百元 序号 链接 费用/百元 序号 链接 费用/百元 1 134 154 28 4063 558 55 3373 230 2 2634 545 29 6379 300 56 5130 279 3 3461 273 30 3527 320 57 3031 43 4 6150 532 31 273 160 58 3159 231 5 5032 132 32 37 348 59 5960 1729 6 6170 115 33 713 102 60 5948 783 7 7036 160 34 2742 420 61 3038 217 8 368 468 35 4253 148 62 384 303 9 814 901 36 5322 432 63 458 141 10 7062 84 37 5337 752 64 2245 308 11 7066 426 38 2256 254 65 4576 420 12 6667 98 39 2254 72 66 7677 288 13 6247 372 40 2216 198 67 7723 230 14 4769 690 41 1652 140 68 236 145 15 472 198 42 16
