研究生数学建模答案范本.docx
- 文档编号:9896039
- 上传时间:2023-05-21
- 格式:DOCX
- 页数:16
- 大小:27.31KB
研究生数学建模答案范本.docx
《研究生数学建模答案范本.docx》由会员分享,可在线阅读,更多相关《研究生数学建模答案范本.docx(16页珍藏版)》请在冰点文库上搜索。
研究生数学建模答案范本
2021年研究生数学建模答案范本
数学建模题目:
A队号:
xxxxA2021年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:
各结点间链路的铺设费用序号链接费用/百元序号链接费用/百元序号链接费用/百元11–341542840–635585533–73230226–345452963–793005651–30279334–612733035–273202130–3143461–505323127–31605831–59231550–32132323–73485959–601729661–70115337–131026059–48783770–361603427–424202130–38217836–84683542–531486238–430398–149013653–22432634–581411070–62843753–377526422–453081170–664263822–562546545–764202166–67983922–54726676–772881362–473724022–161986777–232301447–696904116–521406823–61451547–21984216–553202123–75336162–294834355–257927023–64387172–191144452–214687164–577031819–283684552–435557277–711951919–493454643–94202171–72534202–53364752–182847471–74187215–783424818–513027574–1777225–351014951–121007617–101572335–202195012–683007710–44362420–8019145112–462021844–155102520–245865246–656367971–114722624–394845346–33802735–403485433–418115.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结点出现故障后解决的情况出现故障的结点出现故障后系统可靠性重新连接结点连接后系统可靠性成本/百元未接入结点20.750047连49、40连660.9750241922、2950.725040连660.9750449175、78160.700071连760.96251676616、{25,55}180.787546连710.98751270818220.46252连10、55连620.96252453222、54、56270.57503连74、2连100.98751352427350.62502连100.90003495435、{20,29,34,80}、{40,63,79}420.56252连100.98751331642450.800023连540.98752495845470.812540连660.97504909547、69510.800046连71、31连330.98751012751520.737546连710.95001331252、21、{9,43}530.53752连100.97501373637、53620.837566连400.98755078162700.850040连66、61连680.95004066{8,14,36}、70760.812523连540.98752526676770.82502连100.92504041{6,23,57,64,75}、775.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-510.94,30,31,38,48,58,59,60260980.971-770.910,11,15,17,44,71,74273100.912-510.912512,33,41,46,68,65,73271140.912561-700.9251,26,32,34,61,50277270.92512-460.937533,41,46,65,73275140.937523-770.93756,23,57,64,
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 研究生 数学 建模 答案 范本