2014年研究生数学建模答案范本.doc

数学建模 题目： A 队号： 2014045A 2014年5月25题目A：通信网络的设计问题摘 要 本文主要研究通信网络在铺设线路上遇到的总铺设成本，及网络结点和链路可靠性问题的建模建立并对某通信公司所建立的80个结点所铺设线路提出最优铺设方案。 问题1是网络设计常见的成本最低化问题，通过简化将问题转为寻找权值最小的最小生成树问题，并利用避圈法和破圈法最小生成树（结果见8页图2）。最终求得最省铺设费用为294.78万元。并通过仿真计算对该方案的可靠性检验,结果表明，任意一条链路被破坏时，能够保证通信畅通的结点数最低只有点数的53.75%，网络链路不太稳定。通过模拟点出现故障，发现若22号点出现故障，能够保证通信畅通的结点数只有点数的46%（结果见表2）。由此可见利用最小生成树模型涉及网络铺线优点是成本低，缺点是保证结点通信畅通的可能性低. 对问题2，根据邻接矩阵计算了可达矩阵，并根据可达矩阵与链路连通性的关系，将点出现故障时的最小生成树，分解为若干组内联通的子树。然后，在保证90%以上的点通信畅通的条件下，对分解后的图进行了连接修复，对每一结点出现故障时，为保证通信畅通90％以上，建立了0-1整数规划规划模型（页）。考虑整数规划模型求解的复杂性，设计了贪婪算法，对其中17个结点出现故障后结点的具体连接方法见（详见页表2）。若结点出现故障后，网络本身仍能保持90％则无需在连链路，故在表2中未进行考虑。由表2知，贪婪算法的结果能保证92.5％的结点通信畅通。 对于问题3，要求任意一条链路破坏时，为保证90%以上的结点通信畅通分两种情况进行考虑。如果条链路破坏后，仍有90％以上的结点保持通信畅通，这些链路无需追加链接（详页见表3）。另外一些链路在破坏后，不能保证9％的结点通信畅通，需追加链接，即加边。要加边时，若允许某些结点连2条边，则只需对原最小生成树的某些结点连两条一样边（复制某最小生成树的某两结点间的被破坏的边，使之形成回路即可），该链路仍然为总铺设费用最省方案。如果不允许任意结点连两条边，由于破坏一边，整个树一分为二，只需计算两组结点间的最短距离，即可连一条新的最短路。在可靠性不小于90%的情况下，得到总铺设费用方案（详17页见表4）. 对于问题四，综合考虑网络的可靠性以及铺设费用后，根据问题2和问题3的结果，将结点出现故障后需加的边和链路破坏后需加的边全部加到问题1 的最小生成树上，得到可靠性相当高的铺线模型(见19页图8)，该模型任意一结点出现故障后，结点保持畅通的可能性最低在90％以上（详页见表5）。考虑到该模型成本高，需增加的铺设费用为750.75万元。因此，依次移除成本高的边（此处只移除图8中一条边71－76），从得到一成本更低，稳定性友好的模型模型(见页图9)，此时只需增加成本5032万元。任意一结点出现故障后，结点保持畅通的可能性最低在90％以上（详页见表6）。对边有类似的结果分别见表7则此方案合理。 关键词：最小生成树，破圈法，网络模型，图论 一、问题重述 随着科学技术的进步，计算机和网络技术取得了快速发展，成为信息交流手段，渗透到社会的各个方面，其发展也在不断的推动人类社会逐渐走向信息时代。网络技术的发展在给人们生活及社会生产力的提高提供了巨大贡献的同时，也存在着许多安全隐患、信息漏洞，如最近出现的网络OpenSSL“心血”漏洞等。这些对于人们的工作和生活造成了很大的影响。 对于一个系统，可靠性是其重要的整体指标，通信网络亦不例外。通信网络的可靠性不仅与通信设备、链路有关，而且还与网络结构有关。由于网络结构的复杂多变，通信网络的可靠性分析一直是个棘手的问题。 某通信公司拟建一个具有80个结点的通信网络，需要在这些结点之间铺设线路，进行数据传输。结合结点之间的距离和铺设线路的单位费用见附件1，本文需要具体完成以下问题： 问题1：要使得通信网络的总铺设费用最省，请建立问题的数学模型，设计求解算法，给出铺设方案，并讨论方案的可靠性； 问题2：考虑到通信网络结点的可靠性，若要求任意一个结点出现故障时，其它结点间仍然能够保持通信畅通的可能性都达到90%，请建立问题的数学模型，设计求解算法，并给出使总铺设费用最少的铺设方案； 问题3：考虑到通信网络链路的可靠性，若要求任意一条链路被破坏时，能够保持通信畅通的结点都能够达到90%，请建立问题的数学模型，设计求解算法，并给出使总铺设费用最少的铺设方案； 问题4：综合考虑网络的可靠性以及铺设费用，试确定合理的铺设方案。 二、模型假设 1、假设结点与结点之间的连接不存在先后顺序，且均以直线连接 2、假设不考虑结点大小 3、假设不考虑线路铺设费用对