数学建模论文学校广播站网络的建立与优化.docVIP

第七届数学建模竞赛 题号 A题 论文题目 学校广播站网络的建立与优化 姓名 XXXXXX XXXXXXX XXXXXXXX 手机 班级 诚信承诺书 本论文是我组独立完成，论文中所有引用其他已有成果处均已标明。论文一经提交，组委会有权对其进行审阅、评定，并对获奖论文有权组织公开发表。 如果论文是抄袭他人成果，本组将承担所有相关责任。 签名： XXXXXXXXXXXXXXXX 摘要 本问题要求我们建立一种合理的模型，使得学校的十二个广播站能够达到信息互通的目的，组成广播站网络。 首先通过了MATLAB对十二组坐标数据进行处理和分析，得出了十二个坐标点，并通过算法得到了每两点之间的距离。 在对数据的分析之后，建立一个模型。该模型为：运用“floyd”经典算法对题目进行分析和研究，得出两个“欧拉回路”，再通过比较两个“欧拉回路”之间的坐标点的最短距离并连接，从而最终形成一张最佳的广播站网络。 关键词：floyd 欧拉回路 最短距离 问题重述 为丰富同学的业余生活，现学校要架设12个广播站，选取适当的坐标系后，它们的位置可以用如下的坐标表示为： , , , ,, , , , ，，，。 现在要求把这些广播站连接成一张网络，而连线费用与长度成正比，应该如何连接才能使总费用最省。 对于所建立的网络的理解，可以是多种多样的。例如对于每个站点的连接要求，是每个点都要和其余11个站点都要连接还是一条线将12个站点串起来等等，对于这些我们都要进行分析。 问题的分析 问题是通过建立一个预测模型，来计算在十二个广播站之间建立网络的最短长度。 建立模型的关键：能够计算出广播站点之间的最短距离，组成最短距离的广播站网络。 通过对问题的分析，在建立模型的过程中需要做到以下几点； 1）建立一个简单实用的数学模型； 2）通过算法对每组数据进行处理，计算出两点之间的距离； 3）假设出多种模型方案，利用两点之间的距离算出总距离，寻找出最短总距离； 4）将优化后的最短距离利用MATLAB进行绘图，形象化的以图片形式呈现出广播站网络。 对于网络建立的方法，我们做出如下几种假设： 1）将所有的站点两两相连，形成每个站点都与其余十一个站点互通的网络连接方式，此种的连接方式，线路总长始终是一个定值； 2）寻找任意一个站点，将其余的十一点都连接到这个站点，如此也能形成信息互通的广播站网络，以这样的方式连接的网络，有十二种连接总长结果； 3）从A点开始，将该点与其最近点连接，形成“欧拉回路”，之后再将“欧拉回路”以最短的线路连接，如此便有了一张信息互通的广播站网络。 然后我们对这三种假设进行对比： 假设一中，所有站点两两相连，总长即是将所有两点之间的距离相加，并未符合题目中距离最短，费用最少的要求。假设二中以任意点为起点，再将另外十一点与之连接，这十一点与该点距离有长有短，所以线路也并未达到最短。假设三中，首先是利用“floyd”经典算法算出最短距离，再将最短距离的两点连接，如此所以的连接距离皆是最短，总长便也是最短[1]，符合题目要求。 通过对三种假设的阐释对比，我们了解到假设三的方法形成的网络相比较假设一和假设二是更加优化的，所以我们以假设三的网络连接方法建立模型。 模型假设 模型建立的假设： 1）连线费用与长度成正比； 2）所提供的广播站坐标准确，无误差； 3）广播站之间可以直线连接线路，即广播站之间没有阻隔； 4) 不考虑外界干扰因素。 符号说明 ：第个点的横坐标； ：第个点的纵坐标； ：最近点的距离总和，它表示每个点与其最近的一个点的距离之和； ：DF与IL距离之和，它表示在求与其最近一个点距离之和过程中，最近点重复的两端线段的距离之和； ：GF的距离，它表示在将最近点连接之后，坐标点被分为两部分，用最近的坐标点将这两部分连接，S3即为这两最近坐标点之间的距离之和； ：最近的网络连接距离，它表示用最短的连接方式将坐标点连接成网络的这段距离。 基本模型的建立 根据对题目的初步分析，设想出用“floyd”算法来建立一种最优化的数学模型。 对十二个坐标点： , , , ,, , , , ，，，进行分析，我们可以通过使用MATLAB来画出十二个点的位置的分布图[2]。 于是，我们把十二个坐标点数据输入MATLAB中做