校园景观道路设计问题.docx
《校园景观道路设计问题.docx》由会员分享，可在线阅读，更多相关《校园景观道路设计问题.docx（26页珍藏版）》请在冰点文库上搜索。
校园景观道路设计问题
陇东学院第二届大学生数学建模竞赛
承诺书
咱们仔细阅读了陇东学院数学建模竞赛的竞赛规则.
咱们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。
咱们知道，剽窃他人的功效是违背竞赛规则的,若是引用他人的功效或其他公开的资料（包括网上查到的资料），必需依照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。
咱们郑重许诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。
如有违背竞赛规则的行为，咱们将受到严肃处置。
咱们参赛选择的题号是（从A/B/C/D当选择一项填写）B
咱们的参赛报名号为（若是赛区设置报名号的话）：
所属院系（请填写完整的全名）：
参赛队员（打印并签名）：
1.
2.
3.
指导教师或指导教师组负责人（打印并签名）：
日期：
2012年5月27日
[
校园文化景观中心道路设计问题
摘要：
对于所给的校园文化景观中心道路设计问题，咱们主要利用了matlab软件，这样在数值计算和挪用函数方面有着很强的功能，尤其在编程解决具体问题时它操作简便，效率高，节省时间。
本文研究的是最短线路设计问题，属于优化问题。
通过道路设计来探讨如何使得新修路总路程最小，为此，咱们有了了两个大体的思路：
一是充分利用边界上的道路，能通过边界解决的问题尽可能再也不去另外修路。
二是充分利用已经修过的道路，通过“少修多连”的方式，尽可能减少路程，咱们称其为“借路原理”。
在问题的解决进程中，咱们主要是计算出数据，然后考虑是不是知足思路一，紧接着通过思路二来进一步优化、减少路程。
咱们不是直接求出最优路径，而是利用排除法思维，先找到一条优化道路，但紧跟其后又找到了更优化的路径，通过层层对比，最终肯定出最优线路。
关键字：
matlab软件大体思路一大体思路二排除法
一、问题的重述:
3
二．问题的分析和符号说明5
三、模型假设6
四、模型成立6
五、模型求解：
6
问题一：
6
1.求解前提条件：
6
2.开始求解：
8
问题二：
15
1.求解前提条件：
15
2.开始求解15
六．模型评价：
22
七．参考文献：
22
一、问题的重述:
我校计划在逸夫教学楼与信息楼之间建一个形状为矩形或其他不规则图形的校园文化景观中心，不仅为了美化校园环境，也是想为其学生提供更的生活条件。
该中心计划有若干个入口，此刻你需要成立一个模型去设计道路让任意两个入口相连（可以利用周围的边，即默许矩形的四条边上存在已经建好的道路，此道路不计入道路总长），使总的道路长度和最小，前提要求是任意的两个入口之间的最短道路长不大于两点连线的倍。
主要设计对象可假设为如图所示的矩形校园文化景观中心，其相关数据为：
长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）。
问如何设计道路可使公园内道路的总路程最短。
成立模型并给出算法。
画出道路设计，计算新修路的总路程。
问题二：
此刻校园文化景观中心内可以任意修建道路，如安在知足条件下使总路程最少。
成立模型并给出算法。
给出道路交叉点的坐标，画出道路设计，计算新修路的总路程。
注：
以上问题中都要求景观中心内新修的道路与周围的连接只能与8个路口相通，而不能连到周围的其它点。
图1公园及入口示用意
图2一种可能的道路设计图
二．问题的分析和符号说明
题目中有对道路建设的要求是:
“任意的两个入口之间的最短道路长不大于两点连线的倍”，于是咱们首先考虑P1与P7间的直线距离乘以等于，而P1和P7仅通过边界限路相连接的最短距离为130,由于130<，知足题目所给的要求，所以无需再专门修路连接P1和P7。
同理，对于其他任意两点也可尝试上述计算方式，尽可能排除无关紧要的点，从而可简化问题，减少了计算量。
咱们对一些常常利用变量进行命名：
1,2,3,4,5,6,7,8……………………….P1,P2,P3,P4,P5,P6,P7,P8
S（m，n）……………………………………….m,n仅通过边界限路相连的最短距离
m--n……………………………………m,n间的直线距离
m~n（q）……………………………………….m,n间通过方式q相连的距离
（示例：
1~6（1--B--A--6）即为通过方式（1—B--A--6）使1连接上6的距离。
）
然后，我们可以运用matlab来计算上面提出的问题，用一个循环结构，便可以省去很多繁琐的运算。
然后我们得到下面一个概览表：
图-1
通过观察得知，仅1~5,1~6,1~8,3~4,3~5,3~6,3~7,2~5,2~6,2~7之间不符合S（m，n）>=*（m--n）的条件，需要从头计划线路。
从而问题变得很简明。
三、模型假设
1.近似以为每一个入口都是一个质点，不占用空间位置，从而mn之间修的直线线路的长度即为|mn|。
2.以为道路的宽度为0，即所修的路都是线段，长别离是a和b的两条线路相交，则两条路的总长度是a+b。
3.以为公园的地面是完全平整无凹陷和突起的。
四、模型成立
按照上面的陈述，咱们大致可总结出修路要遵循的两个原理：
A1:
知足m~n（q）<=*（m--n）的两点m,n间不需再专门修路。
A2：
应充分利用已有或已经修过的路作为条件来完成需修而未修的两点间的路。
下面是咱们尝试在这两个原理的基础上，按照两个问题的不同要求，运用排除比较的方式来尽可能肯定最优道路。
五、模型求解：
问题一：
1.求解前提条件：
该问题有一个大体要求就是“肯定要利用4个道路交叉点为：
A（50,75），B（40,40），C（120,40），D（115,70）。
首先要说明道路交叉点。
咱们取”任一个交叉点Q，则至少有两条不同的道路通过Q，下面列出的三种情况都是符合题意的：
图-2
情况一：
一点通过三条不同道路
图-3
情况二：
一点通过量条不同道路
图-4
情况三：
一点通过两条不同道路
这里需要特别注意解题用图-4中所给的情况，只有两条道路以折线方式相交仍视点Q为道路交叉点。
前面所提到的“至少有两条不同的道路通过Q”中的“不同道路”具体指两条不能连成线段的道路，如图-5，
图-5
此时以为只有一条路通过Q，即Q不是道路交叉点，这是一种不符合Q为交叉点的情况。
另一种不符合Q为交叉点的情况是没有任何道路通过Q。
2.开始求解：
观察需要从头修建道路的各点组合，即1~5,1~6,1~8,3~4,3~5,3~6,3~7,2~5,2~6,2~7，发现1,2,3均需要连到5,6，所以选择从5,6点开始着手。
先考虑6点。
一．1，6 之间需要知足原理A1，最简单的办法就是1--6，连接后，（如图-6）若再也不修建其他道路，2~6（2--1--6）=<*S（2,6）=，知足原理A1（下面再有此种论断则简化些为m~n（q）=a，不符A1。
专门再为2~7修路代价太大，因此改变1~6 之间的连接方式。
二．考虑1~6通过1--B--6的方式，而且连接2--B（原理A2），则1~6（1--B--6）=<，A1。
2~6（2--B--6）=<，A1。
2~7（2--B--6--7）=<，A1。
如图-7
图-6
图-7
为了能使1,2能与5相连，当在连接1~6（1--6）时但2~7（2--B--6--7）不符A1，不能像连接2--B一样，从2或7到（1--6）直线上修一条路（A2）。
如图-8
图8
同理查验可得
3~6（3--2--B--6）=<，A1。
3~7（3--2-B--6--7）=<，A1。
接着考虑1,2,3和5的连接。
3~5较简单，为使路程尽可能短且通过C，D点，3~5取3--C--D--5，又3~5（3--C--D--5）=<，A1。
1~5由于A点尚未通过任何道路，所以考虑1~5（1--B--A--5）,此时1~5=<198，A1。
2~5取2~5（2--B--A--5）（A2），此时2~5=<170，A1。
如图-9
由于2~5（2--B--A--D--5）=>，不符A1。
所以不通过1~5（1--B--A--D--5），2~5（2--B--A--D--5），这样修路。
如图-10
图-9
图-10
此刻看1~5,1~6,3~5,3~6,3~7,2~5,2~6,2~7，之间的路程修建似乎可以结束了，但通过观察现有图形，考虑将A--6代替B--6（A2），因为前者明显比后者短些。
下面咱们进行一些替换后的查验（主要靠A1）：
1~6（1--B--A--6）=<140，A1。
2~6（2--B--A--6）=<，A1。
2~7（2--B--A--6--7）=<，A1。
3~6（3--2--B--A--6）=<，A1。
3~7（3--2--B--A--6--7）=<252，A1。
1,2,3到5的线路和原来完全一样，不用再赘述。
所以数据完全符合要求，即可以用B--A--6代替B--6。
图-11
又有以下情况：
B--A--6代替B--6后，A点成了交叉点，那么若取1~5（1--B--C--D--5），2~5（2--B--C--D--5），路程会不会更短？
通过计算即便换线路后新数据完全符合A1，但（B--C）>（A--5），路程反而增加，舍弃不用。
如图-12
又有以下情况2~5（2--C--D--5），1~5（1--2--C--D--5）。
但通过计算，虽然换线路后新数据完全符合A1，但（2--C）>（A--5），路程反而增加，舍弃不用。
如图-13
图-12
图-13
接下来考虑1~8和3~4.
1~8：
最直接最简便的方式固然是直接连接1,8两点，但考虑（A2），咱们可以过8做1--B的垂线，（如图-14）设垂足为O显然比直接连接减少了路长，下面查验，
1~8（1--P--8）=<，A1。
3~4：
和1~8思路完全相同，过4做3--C的垂线，垂足设为P，查验。
3~4（3--P--4）=<，A1。
（如图-14）
对1~8和3~4的求解进程的补充。
因为上述方式可用有一个前提，就是（∠43C）和（∠81B）都是锐角，咱们证明如下：
∠43C：
∠23P=arctan
（1）=45度；180度-∠P34=arctan（）>45度所以（∠43C）=180-∠23P-180度-∠P34<90，是锐角。
同理可证得∠81B；
图-14
综上所述，咱们已经解决了问题一，这里附上最后决定的连接图，如图-15
图-15
并计算取得优化后的总路程s=436.1米。
问题二：
1.求解前提条件：
“此刻公园内可以任意修建道路“就是问题二的条件，在求解进程中，仍需用到原理A1,A2。
相较问题一，问题二没有了交叉点的牵绊，但连线的灵活度也更大了。
2.开始求解
仍需从1~5,1~6,1~8,3~4,3~5,3~6,3~7,2~5,2~6,2~7找下手点。
相似地，1,2,3均需要连到5,6，所以选择从5,6点开始着手。
由于“以上问题中都要求公园内新修的道路与周围的连接只能与8个路口相通，而不能连到周围的其它点”,咱们有一下两种方案.方案一:
连接1--6,3--5,（如图-16）。
显然1~6（1--6）符合A1.
1~5（1--3--5）=>,不符A1。
2~6（2--1--6）=<141，A1.
2~7（2--1--6--7）=>，不符A1。
2~5（2--3--5）=>,不符A1。
3--5，则3~5符合A1。
3~6（3--5--6）=<，A1。
3~7（3--5--6--7）=<,A1.
图-16
所以，这种方案目前不符合要求的点对是1~5,2~5,2~7.
先讨论2~7。
实验一，过7做1--6垂线，垂足为M，（如图-17）。
则2~7（2--1--M--7）=>,不符A1。
实验二，过2做1--6垂线，垂足为N，（如图-17）。
则2~7（2--N--6--7）=>,不符A1。
实验三：
综合实验一二。
则2~7（2--N--M--7）=<,A1。
可是考虑到做了两条垂线，路程太长，应该寻求更节省路长的画法。
因为原来什么都没做时2~7超出规定的长度是，所以考虑A2，从2向1--6做线段，与1--6交点去N1，并设1--N1=x，2--N1=a，通过matlab，运用余弦定理，即（1--2）^2+x^2-2*x*（1--2）=a^2,联立（1--2）+x-a=6，即可算出比实验三更优化的实验四：
此时x=，a=,2~7（2--N1--6--7）=<，A1。
对应地，过7做（1--6）垂线垂足设为M1，一样可得实验五：
此时x=，a=,2~7（2--1--M--7）=<;
比较实验三四五所修路程长度，即可得最佳方案为方案五，（如图-18）所修长度L=.
图-17
图-18
再讨论1~5,2~5
若连接2--5，则2~5（2--5）显然符合A1。
1~5（1--2--5）=<,A1.（如图-19）
图-19
考虑到A2，咱们可以过2做3--5垂线垂足为C，（如图-20）。
则2~5（2--C--5）=<,A1.
1~5（1--2--C--5）=<,A1.
所以此方案才是最佳方案
考虑1~8,3~4：
同问题1，咱们过8做1--6垂线垂足为O，过4做3--5垂线，垂足为P【做垂线之前咱们一样要先判断（角816）和（角435）是不是为锐角的问题，方式和问题一同理，经判断两角都是锐角】，
1~8（1--O--8）=<,A1
4~3（4--P--3）=<,A1（如图-21）
图-20
图-21
方案一已经将问题二解决，最后的线路图如图-22：
图-22
且总路程S=。
方案二：
连接2--6，3--5,
1~6（1--2--6）=<，A1
2~6（2--6）显然符合A1
2~7（2--6--7）=<,A1
3~6（3--2--6）=<,A1
3~7（3--2--6--7）=<,A1
3~5（3--5）显然符合A1
1~5（1--3--5）=>,不符A1。
2~5（2--3--5）=>,不符A1。
到此，再往下的问题和方案一里的重复。
考虑1~8,3~4：
3,4和方案一完全一样（如图-23）
但1,8和方案一有不同，若是做了垂线，则8--O=>45,（如图-24）那么8~1（8--O--1）更大于45，不符A1，舍去。
所以1,8间的线路选择直接连接。
图-23
图-24
方案二已经将问题二解决，最后的路程图如图-25：
图-25
且总路程S=397.9m
综合方案一和方案二,咱们最终肯定选方案二。
并给出该方案线路交叉点坐标：
P（,），C（,）总路程S=397.9m。
六．模型评价：
该模型的长处：
运用排除法，减少了需要考虑的点对的数量，减少了计算量，简化了计算，能够很快的比较得出结果。
该模型的缺点：
具体问题具体对待，不能运用到更广的地方，具有局限性。
七．参考文献：
1.姜启源.数学建模案例选集，北京：
高等教育出版社，2006
2.白其峥.学建模案例分析，北京：
海洋出版社，2000
3.吴建国.学建模案例精编，北京：
中国水利水电出版社，2005
4.朱道元.学建模案例精选，北京：
科学出版社，2003
升级会员 