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

I 第七届数学建模竞赛 题号 A 题 论文题目 学校广播站网络的建立与优化 参赛密码 （由组委会填写） II 姓名 XXXXXXXXXXXXXXXXXXXXX 手机 班级 诚信承诺书诚信承诺书 本论文是我组独立完成，论文中所有引用其他已有成果处均已标明。论文一经提本论文是我组独立完成，论文中所有引用其他已有成果处均已标明。论文一经提 交，组委会有权对其进行审阅、评定，并对获奖论文有权组织公开发表。交，组委会有权对其进行审阅、评定，并对获奖论文有权组织公开发表。 如果论文是抄袭他人成果，本组将承担所有相关责任。如果论文是抄袭他人成果，本组将承担所有相关责任。 签名：XXXXXXXXXXXXXXXX 1 摘要 本问题要求我们建立一种合理的模型， 使得学校的十二个广播站能够达到信息互通 的目的，组成广播站网络。 首先通过了 MATLAB 对十二组坐标数据进行处理和分析，得出了十二个坐标点，并 通过算法得到了每两点之间的距离。 在对数据的分析之后，建立一个模型。该模型为：运用“floyd”经典算法对题目 进行分析和研究，得出两个“欧拉回路” ，再通过比较两个“欧拉回路”之间的坐标点 的最短距离并连接，从而最终形成一张最佳的广播站网络。 关键词：floyd欧拉回路最短距离 问题重述 为丰富同学的业余生活，现学校要架设 12 个广播站，选取适当的坐标系后，它们 的位置可以用如下的坐标表示为： 4,7a , 10,3b , 5,20c , 8,13d , 15,10e , 13,17f , 20,20g , 23,15h , 28,12i ， (24,9)j ， (30,5)k ， (33,12)l 。 现在要求把这些广播站连接成一张网络，而连线费用与长度成正比，应该如何连接 才能使总费用最省。 对于所建立的网络的理解，可以是多种多样的。例如对于每个站点的连接要求，是 每个点都要和其余 11 个站点都要连接还是一条线将 12 个站点串起来等等， 对于这些我 们都要进行分析。 问题的分析 问题是通过建立一个预测模型，来计算在十二个广播站之间建立网络的最短长度。 建立模型的关键：能够计算出广播站点之间的最短距离，组成最短距离的广播站网 络。 通过对问题的分析，在建立模型的过程中需要做到以下几点； 1）建立一个简单实用的数学模型； 2）通过算法对每组数据进行处理，计算出两点之间的距离； 3）假设出多种模型方案，利用两点之间的距离算出总距离，寻找出最短总距离； 4）将优化后的最短距离利用 MATLAB 进行绘图，形象化的以图片形式呈现出广播站 网络。 对于网络建立的方法，我们做出如下几种假设： 1）将所有的站点两两相连，形成每个站点都与其余十一个站点互通的网络连接方 式，此种的连接方式，线路总长始终是一个定值； 2）寻找任意一个站点，将其余的十一点都连接到这个站点，如此也能形成信息互 通的广播站网络，以这样的方式连接的网络，有十二种连接总长结果； 3）从 A 点开始，将该点与其最近点连接，形成“欧拉回路” ，之后再将“欧拉回路” 以最短的线路连接，如此便有了一张信息互通的广播站网络。 2 然后我们对这三种假设进行对比： 假设一中，所有站点两两相连，总长即是将所有两点之间的距离相加，并未符合题 目中距离最短， 费用最少的要求。 假设二中以任意点为起点， 再将另外十一点与之连接， 这十一点与该点距离有长有短，所以线路也并未达到最短。假设三中，首先是利用 “floyd”经典算法算出最短距离，再将最短距离的两点连接，如此所以的连接距离皆 是最短，总长便也是最短 1，符合题目要求。 通过对三种假设的阐释对比， 我们了解到假设三的方法形成的网络相比较假设一和 假设二是更加优化的，所以我们以假设三的网络连接方法建立模型。 模型假设 模型建立的假设： 1）连线费用与长度成正比； 2）所提供的广播站坐标准确，无误差； 3）广播站之间可以直线连接线路，即广播站之间没有阻隔； 4) 不考虑外界干扰因素。 符号说明 i x ：第i个点的横坐标； i y：第i个点的纵坐标； 1 S：最近点的距离总和，它表示每个点与其最近的一个点的距离之和； 2 S ：DF 与 IL 距离之和，它表示在求与其最近一个点距离之和过程中，最近点重复的两 端线段的距离之和； 3 S ：GF 的距离，它表示在将最近点连接之后，坐标点被分为两部分，用最近的坐标点 将这两部分连接，S3 即为这两最近坐标点之间的距离之和； S：最近的网络连接距离，它表示用最短的连接方式将坐标点连接成网络的这段距离。 基本模型的建立 根据对题目的初步分析，设想出用“floyd”算法来建立一种最优化的数学模型。 对十二个坐标点： 4,7a , 10,3b , 5,20c , 8,13d , 15,10e , 13,17f , 20,20g , 23,15h , 28,12i ， (24,9)j ， (30,5)k ， (33,12)l 进行分析，我们可以通过使用 MATLAB 来画出十二个点的位置的分布图 2。 于是，我们把十二个坐标点数据输入 MATLAB 中做数据处理，得到了十二个广播站 3 的坐标分布图，如图 1 所示： 05101520253035 0 5 10 15 20 25 30 35 A B C D E F G H I J K L 图 1十二个广播站的坐标分布图 我们可以清楚的看到，十二个点大致都在范围(0,0)到(35,20)中，于是试图通过某 种算法来把这些广播站连接成一张网络，要求线段最短，即费用最少。 通过 MATLAB 计算出了每两点之间的距离，得到所有两点之间最短距离，可以从这 些数据中得到最短连线的方法。以下是我们计算出的数据 3： 表 1：两点之间的距离 ABCDEFGHIJKL A07.2113.07.2111.413.420.620.624.520.126.029.4 B7.2017.710.18.614.319.717.620.115.220.124.6 C13.017.707.614.18.515018.624.321.929.129.1 D7.2110.17.607.66.413.815.120.016.423.425.0 E11.48.614.17.607.211.19.413.19.015.818.1 F13.414.38.546.47.207.610.115.813.620.820.6 G20.619.71513.811.17.605.811.311.718.015.2 H20.617.618.615.19.410.15.805.86.012.210.4 I24.520.124.320.013.115.811.35.80507.25 J20.115.221.916.49.013.611.76.05007.29.4 K26.020.129.123.415.820.818.012.27.27.207.6 L29.424.629.125.018.120.615.210.4509.47.60 模型的求解 4 在计算出每两点之间距离的基础之上，可以计算出与每点距离最近的点，通过表 1 的数据，再利用“floyd”经典算法，得出所有连线最短的点的对应点，如表 2 所示： 表 2：广播站网络中最近坐标点 ABCDEFGHIJKL D/BADFFDHI/GL/JIJI 在对数据进行判断后，通过 A（4,7）与另外十一个坐标点之间距离的比较，得出据 A 点的最近点分别是 B（10,3）和 D（8,13） ，将 A 点与该两点连接，以此类推，将会得 出另外十一个坐标点的最近点，并将其连接，最终会形成一张广播站网络。 由此， 我们得到这样一个计算方法： 对所有每一个点与其最近的一个点的距离求和， 并减去最近点中两个点相互双向是最近的距离，然后加上相互之间不存在最近点的线 段。这样就求得了题目所要求的最近连线距离。 于是，我们推导出公式： 123 SSSS 其中， 1 S 是所有坐标点与其最近的一个点的距离之和，公式如下： 12 12 22 1 1, ( ()() )() (min ijijDFILGF i jj i SxxyySSS 12 1, min () jj i 表示从第一行第一列到第十二行第十二列做循环，寻找坐标点中所有最近两 点之间的距离。 2 S是所有最近点中重复计算的距离之和，公式如下： 2DFIL SSS 3 S是在使用“flyod”算法，形成两个“欧拉回路”之后，连接两个“欧拉回路”的 最短距离，公式如下： 3GF SS 通过我们在 MATLAB 中编程序得出的最近点结果，得出表 2 内容并将这些点依次连 接（即 A 与 B、D 连接，B 与 A 连接，C 与 D 连接，D 与 A、F 连接，F 与 D、E 连接，E 与 F 连接，G 与 H 连接，H 与 G、I 连接，I 与 L、J 连接，J 与 I、K 连接，K 与 J 连接， L 与 I 连接） 。得出如图 2 的坐标连接图： 5 图 2 “欧拉回路”图 从图 2 中可以发现两个“欧拉回路”未进行连接，也就是还没有形成一个最短距离 的网络。所以仍要比较“欧拉回路”中，两个回路之间最短距离的连线。我们通过使用 MATLAB 计算 FG、FH、EG、EH 之间的距离，比较两点之间距离，可以发现 FG=7.6158， FH=10.198，EG=11.18，EH=9.434，从而得出 FG 为最短距离的连线。所以通过 FG 将两 部分连接起来，连接之后的坐标连接图即为最短网络连接图，如图 3 所示： 05101520253035 0 5 10 15 20 25 30 35 A B C D E F G H I J K L 图 3最短距离的广播站网络图 6 图 3 是最优化的广播站网络，网络之中所有两点之间的距离是通过“floyd”经典 算法，得出的最短距离。 “floyd”经典算法对于本题来说是最合适的计算距离的算法。 我们运用公式 123 SSSS ，代入已知的坐标点，得出结果： 12 12 22 1 1, ( ()() )() (min ijijDFILGF i jj i SxxyySSS 由此，我们把通过 MATLAB 处理的数据，即表一中的数据代入公式中，得到结果： 72.2101S 综上所述，利用“floyd”经典算法，我们计算出的最优广播站网络的最短连接距 离为 72.2101。 7 模型的优缺点 1、对于给出数据，我们对数据进行处理，将其转化为有用的数据，如：附件中的各点 的坐标转化为点与点之间的距离。 2、模型建立的思路简单清晰，并且可以得到很好的效果。 3、模型的假设很符合实际生活，以致模型可以很好的运用于相对应得实际生活中。 4、没有考虑特殊情况在内，如：广播站之间的情况没有考虑，若广播站之间有阻隔之 类的问题。 5、如果广播站站点多，数据就会复杂很多，运算本模型不够便捷。 8 参考文献 1 张圣勤，数学实验与数学建模，复旦大学出版社，2004. 2 陈杰，MATLAB宝典，电子工业出版社，2010. 3 徐瑞 黄兆光 阎凤玉，MATLAB科学计算与工程分析，科学出版社，2008. 9 附件： 以下是我们在 MATLAB 中编译的程序： x=4 10 5 8 15 13 20 23 28 24 30 33; y=7 3 20 13 10 17 20 15 12 9 5 12; plot(x(1),y(1),+) text(x(1),y(1)+0.7,A) hold on plot(x(2),y(2),+) text(x(2),y(2)+0.7,B) hold on plot(x(3),y(3),+) text(x(3),y(3)+0.7,C) hold on plot(x(4),y(4),+) text(x(4),y(4)+0.7,D) hold on plot(x(5),y(5),+) text(x(5),y(5)+0.7,E) hold on plot(x(6),y(6),+) text(x(6),y(6)+0.7,F) hold on plot(x(7),y(7),+) text(x(7),y(7)+0.7,G) hold on plot(x(8),y(8),+) text(x(8),y(8)+0.7,H) hold on plot(x(9),y(9),+) text(x(9),y(9)+0.7,I) hold on plot(x(10),y(10),+) text(x(10),y(10)+0.7,J) hold on plot(x(11),y(11),+) text(x(11),y(11)+0.7,K) hold on plot(x(12),y(12),+) text(x(12),y(12)+0.7,L) for i=1:12%求两点间的距离 for j=1:12 dist(i,j)=(x(i)-x(j)2+(y(i)-y(j)2)0.