校园景观道路设计问题

1、1 陇东学院第二届大学生数学建模竞赛陇东学院第二届大学生数学建模竞赛 承承 诺诺 书书 我们仔细阅读了陇东学院数学建模竞赛的竞赛规则. 我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子 邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关 的问题。 我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他 公开的资料（包括网上查到的资料） ，必须按照规定的参考文献的表述方式在正 文引用处和参考文献中明确列出。 我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违 反竞赛规则的行为，我们将受到严肃处理。 我们参赛选择的题号是（从 a/b/c

2、/d 中选择一项填写） b 我们的参赛报名号为（如果赛区设置报名号的话）： 所属院系（请填写完整的全名）： 参赛队员 (打印并签名) ：1. 2. 3. 指导教师或指导教师组负责人 (打印并签名)： 日期： 2012 年 5 月 27 日 2 校园文化景观中心道路设计问题校园文化景观中心道路设计问题 摘要：摘要： 对于所给的校园文化景观中心道路设计问题，我们主要使用了 matlab 软件， 这样在数值计算和调用函数方面有着很强的功能，尤其在编程解决具体问题时 它操作简便，效率高，节省时间。 本文研究的是最短路线设计问题，属于优化问题。通过道路设计来探讨如何 使得新修路总路程最小，为此，我们有了

3、了两个基本的思路：一是充分利用边 界上的道路，能通过边界解决的问题尽量不再去另外修路。二是充分利用已经 修过的道路，通过“少修多连”的方法，尽量减少路程，我们称其为“借路原理”。 在问题的解决过程中，我们主要是计算出数据，然后考虑是否满足思路一，紧 接着通过思路二来进一步优化、减少路程。我们不是直接求出最优路径，而是 利用排除法思维，先找到一条优化道路，但紧跟其后又找到了更优化的路径， 通过层层对比，最终确定出最优路线。 关键字关键字：matlab 软件 基本思路一 基本思路二 排除法 3 目录 一、问题的重述一、问题的重述:.3 二问题的分析和符号说明二问题的分析和符号说明.5 三、模型假设

4、三、模型假设.6 四、模型建立四、模型建立.6 五、模型求解：五、模型求解：.6 问题一：.6 1.求解前提条件：.6 2.开始求解：.8 问题二：.15 1.求解前提条件：.15 2.开始求解.15 六模型评价：六模型评价：.22 七参考文献：七参考文献：.22 4 一、问题的重述一、问题的重述: 我校计划在逸夫教学楼与信息楼之间建一个形状为矩形或其他不规则图形 的校园文化景观中心，不仅为了美化校园环境，也是想为其学生提供更的生活 条件。该中心计划有若干个入口，现在你需要建立一个模型去设计道路让任意 两个入口相连（可以利用四周的边，即默认矩形的四条边上存在已经建好的道 路，此道路不计入道路总

5、长） ，使总的道路长度和最小，前提要求是任意的两个 入口之间的最短道路长不大于两点连线的 1.4 倍。 主要设计对象可假设为如图所示的矩形校园文化景观中心，其相关数据为： 长 200 米，宽 100 米，1 至 8 各入口的坐标分别为： p1(20,0),p2(50,0),p3(160,0),p4(200,50), p5(120,100),p6(35,100),p7(10,100),p8(0,25). 问题一：假定校园文化景观中心内确定要使用4个道路交叉点为：a(50,75)， b(40,40)，c(120,40)，d(115,70） 。问如何设计道路可使公园内道路的总路程最 短。建立模型并给

6、出算法。画出道路设计，计算新修路的总路程。 问题二：现在校园文化景观中心内可以任意修建道路，如何在满足条件下使总 路程最少。建立模型并给出算法。给出道路交叉点的坐标，画出道路设计，计 算新修路的总路程。 注：以上问题中都要求景观中心内新修的道路与四周的连接只能与8个路口相通， 而不能连到四周的其它点。 图 1 公园及入口示意图 5 图 2 一种可能的道路设计图 二问题的分析和符号说明二问题的分析和符号说明 题目中有对道路建设的要求是:“任意的两个入口之间的最短道路长不大于 两点连线的 1.4 倍”，于是我们首先考虑 p1 与 p7 间的直线距离乘以 1.4 等于 141.0，而 p1 和 p7

7、 仅通过边界路线相连接的最短距离为 130,由于 130=1.4*(m-n)的条件，需要重新规划路线。从而问题变得很简明。 三、模型假设三、模型假设 1.近似认为每个入口都是一个质点，不占用空间位置，从而 mn 之间修的 直线路线的长度即为|mn|。 2.认为道路的宽度为 0，即所修的路都是线段，长分别是 a 和 b 的两条路 线相交，则两条路的总长度是 a+b。 3.认为公园的地面是完全平整无凹陷和突起的。 四、模型建立四、模型建立 根据上面的陈述，我们大致可总结出修路要遵循的两个原理： a1: 满足 mn（q）=1.4*（m-n）的两点 m,n 间不需再专门修路。 a2：应充分利用已有或已

8、经修过的路作为条件来完成需修而未修的两点 间的路。 下面是我们尝试在这两个原理的基础上，根据两个问题的不同要求，运用 排除比较的方法来尽量确定最优道路。 五、模型求解：五、模型求解： 问题一： 1. 求解前提条件： 该问题有一个基本要求就是“确定要使用 4 个道路交叉点为：a(50,75)， b(40,40)，c(120,40)，d(115,70） 。首先要说明道路交叉点。我们取 ” 任一个 交叉点 q，则至少有两条不同的道路通过 q，下面列出的三种情况都是符合题 意的： 7 图-2 情况一：一点通过三条不同道路 图-3 情况二：一点通过多条不同道路 图-4 情况三：一点通过两条不同道路 这里

9、需要特别注意解题用图-4 中所给的情况， 只有两条道路以折线方式 相交仍视点 q 为道路交叉点。 前面所提到的“至少有两条不同的道路通过 q”中的 “不同道路”具体指两条 不能连成线段的道路，如图-5， 8 图- 5 此时认为只有一条路通过 q，即 q 不是道路交叉点，这是一种不符合 q 为交叉点的情况。 另一种不符合 q 为交叉点的情况是没有任何道路通过 q。 2. 开始求解： 观察需要重新修建道路的各点组合，即 15, 16, 18, 34, 35, 36, 37, 25, 26, 27，发现 1,2,3 均需要连到 5,6，所以选择从 5,6 点开始着手。 先考虑 6 点。 一1，6 之

10、间需要满足原理 a1，最简单的办法就是 1- -6，连接后， （如 图-6）若不再修建其他道路，26（2- -1- -6）=131.11.4*s（2,6）=141.6，满足 原理 a1（下面再有此种论断则简化些为 mn（q）=a150.8，不符 a1。 专门再为 27 修路代价太大，因此改变 16 之间的连接方法。 二考虑 16 通过 1- -b- -6 的方法，并且连接 2- -b（原理 a2） ，则 16（1- -b- -6）=104.9141.6，a1。 26（2- -b- -6）=141.4141.6，a1。 27（ 2- -b- -6- -7 ）=126.4150.8 ，a1。 如图

11、-7 9 图- 6 图- 7 10 为了能使 1,2 能与 5 相连，当在连接 16(1- -6)时但 27（2- -b- -6- - 7）不符 a1，不能像连接 2- -b 一样，从 2 或 7 到（1- -6）直线上修一条路 （a2） 。如图-8 图 8 同理检验可得 36（3- -2- -b- -6）=211.4224.1，a1。 37（3- -2-b- -6- -7）=236.4252.4，a1。 接着考虑 1,2,3 和 5 的连接。 35 较简单，为使路程尽量短且通过 c，d 点，35 取 3- -c- -d- -5，又 35（3- -c- -d- -5）=117.4150.8，a

12、1。 15 由于 a 点还没有通过任何道路，所以考虑 15（1- -b- -a- -5）, 此 时 15=155.4198，a1。 25 取 25（2- -b- -a- -5） （a2） ，此时 25=151.9170.9，不符 a1。所以不通过 15（1- -b- -a- -d- -5） ，25（2- -b- -a- -d- -5） ，这样修路。 如图-10 11 图- 9 图- 10 12 现在看 15, 16, 35, 36, 37, 25, 26, 27，之间的路程修建似乎可以 结束了， 但通过观察现有图形，考虑将 a- -6 代替 b- -6（a2） ，因为前者 明显比后者短些。 下

13、面我们进行一些替换后的检验（主要靠 a1） ： 16（1- -b- -a- -6）=110.2140，a1。 26（2- -b- -a- -6）=106.7140.7，a1。 27（2- -b- -a- -6- -7）=131.7151.8，a1。 36（3- -2- -b- -a- -6）=216.7224.1，a1。 37（3- -2- -b- -a- -6- -7）=241.7（a- -5） ，路程反 而增加，舍弃不用。如图-12 又有以下情况 25（2- -c- -d- -5） ，15（1- - 2- -c- -d- -5） 。 但经过计算，虽然换线路后新数据完全符合 a1，但（2-

14、-c）（a- -5） ， 路 程反而增加，舍弃不用。 如图-13 13 图- 12 图- 13 14 接下来考虑 18 和 34. 18： 最直接最简便的方法当然是直接连接 1,8 两点，但考虑（a2） ，我们可 以过 8 做 1- -b 的垂线， （如图-14）设垂足为 o 显然比直接连接减少了路长， 下面检验， 18（1- -p- -8）=42.944.8，a1。 34： 和 18 思路完全相同，过 4 做 3- -c 的垂线，垂足设为 p，检验。 34(3- -p- -4)=70.645 度 所以（ 43c）=180-23p -180 度-p34198.0,不符 a1。 26（2- -1

15、- -6）=131.1150.8，不符 a1。 25（2- -3- -5）=217.1170.9,不符 a1。 3- -5，则 35 符合 a1。 36（3- -5- -6）=192.1224.1，a1。 37（3- -5- -6- -7）=217.1150.8,不符 a1。 实验二，过 2 做 1- -6 垂线，垂足为 n， （如图-17） 。 则 27（2- -n- -6- -7）=150.9150.8,不符 a1。 试验三：综合试验一二。 则 27（2- -n- -m- -7）=146.6150.8,a1。 但是考虑到做了两条垂线，路程过长，应该寻求更节省路长的画法。因为原 来什么都没做

16、时 27 超出规定的长度是 156.1-150.86，所以考虑 a2，从 2 向 1- -6 做线段，与 1- -6 交点去 n1，并设 1- -n1=x，2- -n1=a，通过 matlab，运 用余弦定 理，即（1- -2）2+x2-2*x*(1- -2)=a2,联立（1- -2）+x-a=6，即可 算出比试验三更优化的试验四： 此时 x=5.7，a=29.7,27（2- -n1- -6- -7）=149.9150.8，a1。 对应地，过 7 做（1- -6）垂线垂足设为 m1，同样可得试验五： 此时 x=5.8，a=24.8,27（2- -1- -m- -7）=150.1150.8; 比

17、较试验三四五所修路程长度，即可得最佳方案为方案五， （如图-18）所修长 度 l=24.7. 17 图- 17 图- 18 18 再讨论 15,25 若连接 2- -5， 则 25（2- -5）显然符合 a1。 15（1- -2- -5）=152.1198.0, a1. （如图-19） 图- 19 考虑到 a2，我们可以过 2 做 3- -5 垂线垂足为 c， （如图-20） 。 则 25（2- -c- -5）=159.2170.9, a1. 15(1- -2- -c- -5)=189.2198.0, a1. 所以此方案才是最佳方案 考虑 18,34： 同问题 1，我们过 8 做 1- -6

18、垂线垂足为 o，过 4 做 3- -5 垂线，垂足为 p【做垂线之前我们同样要先判断（角 816）和（角 435）是否为锐角的问题， 方法和问题一同理，经判断两角都是锐角】 ， 18（1- -o- -8）=43.444.8, a1 43(4- -p- -3)=87.289.6, a1（如图-21） 19 图- 20 图- 21 方案一已经将问题二解决，最后的路线图如图-22： 20 图- 22 且总路程 s=413.7。 方案二： 连接 2- -6，3- -5, 16（1- -2- -6）=131.1141.0，a1 26（2- -6）显然符合 a1 27（2- -6- -7）=126.1150.8,a1 36(3- -2- -6)=211