校园景观道路设计问题 22页

陇东学院第二届大学生数学建模竞赛承诺书我们仔细阅读了陇东学院数学建模竞赛的竞赛规则.我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的,如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。我们参赛选择的题号是（从A/B/C/D中选择一项填写）B我们的参赛报名号为（如果赛区设置报名号的话）：所属院系（请填写完整的全名）：参赛队员(打印并签名)：1.2.3.指导教师或指导教师组负责人(打印并签名)：日期：2012年5月27日[22 校园文化景观中心道路设计问题摘要：对于所给的校园文化景观中心道路设计问题，我们主要使用了matlab软件，这样在数值计算和调用函数方面有着很强的功能，尤其在编程解决具体问题时它操作简便，效率高，节省时间。本文研究的是最短路线设计问题，属于优化问题。通过道路设计来探讨如何使得新修路总路程最小，为此，我们有了了两个基本的思路：一是充分利用边界上的道路，能通过边界解决的问题尽量不再去另外修路。二是充分利用已经修过的道路，通过“少修多连”的方法，尽量减少路程，我们称其为“借路原理”。在问题的解决过程中，我们主要是计算出数据，然后考虑是否满足思路一，紧接着通过思路二来进一步优化、减少路程。我们不是直接求出最优路径，而是利用排除法思维，先找到一条优化道路，但紧跟其后又找到了更优化的路径，通过层层对比，最终确定出最优路线。关键字：matlab软件基本思路一基本思路二排除法22 目录一、问题的重述:3二．问题的分析和符号说明5三、模型假设6四、模型建立6五、模型求解：6问题一：61.求解前提条件：62.开始求解：8问题二：151.求解前提条件：152.开始求解15六．模型评价：22七．参考文献：2222 一、问题的重述:我校计划在逸夫教学楼与信息楼之间建一个形状为矩形或其他不规则图形的校园文化景观中心，不仅为了美化校园环境，也是想为其学生提供更的生活条件。该中心计划有若干个入口，现在你需要建立一个模型去设计道路让任意两个入口相连（可以利用四周的边，即默认矩形的四条边上存在已经建好的道路，此道路不计入道路总长），使总的道路长度和最小，前提要求是任意的两个入口之间的最短道路长不大于两点连线的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）。问如何设计道路可使公园内道路的总路程最短。建立模型并给出算法。画出道路设计，计算新修路的总路程。问题二：现在校园文化景观中心内可以任意修建道路，如何在满足条件下使总路程最少。建立模型并给出算法。给出道路交叉点的坐标，画出道路设计，计算新修路的总路程。注：以上问题中都要求景观中心内新修的道路与四周的连接只能与8个路口相通，而不能连到四周的其它点。图1公园及入口示意图22 图2一种可能的道路设计图二．问题的分析和符号说明题目中有对道路建设的要求是:“任意的两个入口之间的最短道路长不大于两点连线的1.4倍”，于是我们首先考虑P1与P7间的直线距离乘以1.4等于141.0，而P1和P7仅通过边界路线相连接的最短距离为130,由于130<141.0，满足题目所给的要求，所以无需再专门修路连接P1和P7。同理，对于其他任意两点也可尝试上述计算方法，尽量排除无关紧要的点，从而可简化问题，减少了计算量。我们对一些常用变量进行命名：1,2,3,4,5,6,7,8……………………….P1,P2,P3,P4,P5,P6,P7,P8S（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来计算上面提出的问题，用一个循环结构，便可以省去很多繁琐的运算。然后我们得到下面一个概览表：22 图-1通过观察得知，仅1~5,1~6,1~8,3~4,3~5,3~6,3~7,2~5,2~6,2~7之间不符合S（m，n）>=1.4*(m--n)的条件，需要重新规划路线。从而问题变得很简明。三、模型假设1.近似认为每个入口都是一个质点，不占用空间位置，从而mn之间修的直线路线的长度即为|mn|。2.认为道路的宽度为0，即所修的路都是线段，长分别是a和b的两条路线相交，则两条路的总长度是a+b。3.认为公园的地面是完全平整无凹陷和突起的。四、模型建立根据上面的陈述，我们大致可总结出修路要遵循的两个原理：A1:满足m~n（q）<=1.4*（m--n）的两点m,n间不需再专门修路。A2：应充分利用已有或已经修过的路作为条件来完成需修而未修的两点间的路。下面是我们尝试在这两个原理的基础上，根据两个问题的不同要求，运用排除比较的方法来尽量确定最优道路。五、模型求解：问题一：1.求解前提条件：该问题有一个基本要求就是“确定要使用4个道路交叉点为：A(50,75)，B(40,40)，C(120,40)，D(115,70）。首先要说明道路交叉点。我们取”任一个交叉点Q，则至少有两条不同的道路通过Q，下面列出的三种情况都是符合题意的：22 图-2情况一：一点通过三条不同道路图-3情况二：一点通过多条不同道路图-4情况三：一点通过两条不同道路这里需要特别注意解题用图-4中所给的情况，只有两条道路以折线方式相交仍视点Q为道路交叉点。前面所提到的“至少有两条不同的道路通过Q”中的“不同道路”具体指两条不能连成线段的道路，如图-5，22 图-5此时认为只有一条路通过Q，即Q不是道路交叉点，这是一种不符合Q为交叉点的情况。另一种不符合Q为交叉点的情况是没有任何道路通过Q。1.开始求解：观察需要重新修建道路的各点组合，即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）=131.1<1.4*S（2,6）=141.6，满足原理A1（下面再有此种论断则简化些为m~n（q）=a150.8，不符A1。专门再为2~7修路代价太大，因此改变1~6 之间的连接方法。二．考虑1~6通过1--B--6的方法，并且连接2--B（原理A2），则1~6（1--B--6）=104.9<141.6，A1。2~6（2--B--6）=141.4<141.6，A1。2~7（2--B--6--7）=126.4<150.8，A1。如图-722 图-6图-722 为了能使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）=211.4<224.1，A1。3~7（3--2-B--6--7）=236.4<252.4，A1。接着考虑1,2,3和5的连接。3~5较简单，为使路程尽量短且通过C，D点，3~5取3--C--D--5，又3~5（3--C--D--5）=117.4<150.8，A1。1~5由于A点还没有通过任何道路，所以考虑1~5（1--B--A--5）,此时1~5=155.4<198，A1。2~5取2~5（2--B--A--5）（A2），此时2~5=151.9<170，A1。如图-9由于2~5（2--B--A--D--5）=173.1>170.9，不符A1。所以不通过1~5（1--B--A--D--5），2~5（2--B--A--D--5），这样修路。如图-1022 图-9图-1022 现在看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）=110.2<140，A1。2~6（2--B--A--6）=106.7<140.7，A1。2~7（2--B--A--6--7）=131.7<151.8，A1。3~6（3--2--B--A--6）=216.7<224.1，A1。3~7（3--2--B--A--6--7）=241.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），路程反而增加，舍弃不用。如图-1322 图-12图-1322 接下来考虑1~8和3~4.1~8：最直接最简便的方法当然是直接连接1,8两点，但考虑（A2），我们可以过8做1--B的垂线，（如图-14）设垂足为O显然比直接连接减少了路长，下面检验，1~8（1--P--8）=42.9<44.8，A1。3~4：和1~8思路完全相同，过4做3--C的垂线，垂足设为P，检验。3~4(3--P--4)=70.6<89.6，A1。（如图-14）对1~8和3~4的求解过程的补充。因为上述方法可用有一个前提，就是（∠43C）和（∠81B）都是锐角，我们证明如下：∠43C：∠23P=arctan（1）=45度；180度-∠P34=arctan（1.25）>45度所以（∠43C）=180-∠23P-180度-∠P34<90，是锐角。同理可证得∠81B；图-14综上所述，我们已经解决了问题一，这里附上最后决定的连接图，如图-1522 图-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)=247.1>198.0,不符A1。2~6（2--1--6）=131.1<141，A1.2~7（2--1--6--7）=156.1>150.8，不符A1。2~5（2--3--5）=217.1>170.9,不符A1。3--5，则3~5符合A1。3~6（3--5--6）=192.1<224.1，A1。3~7（3--5--6--7）=217.1<252.4,A1.22 图-16所以，这种方案目前不符合要求的点对是1~5,2~5,2~7.先讨论2~7。试验一，过7做1--6垂线，垂足为M，（如图-17）。则2~7（2--1--M--7）=151.9>150.8,不符A1。实验二，过2做1--6垂线，垂足为N，（如图-17）。则2~7（2--N--6--7）=150.9>150.8,不符A1。试验三：综合试验一二。则2~7（2--N--M--7）=146.6<150.8,A1。但是考虑到做了两条垂线，路程过长，应该寻求更节省路长的画法。因为原来什么都没做时2~7超出规定的长度是156.1-150.8<6，所以考虑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=5.7，a=29.7,2~7（2--N1--6--7）=149.9<150.8，A1。对应地，过7做（1--6）垂线垂足设为M1，同样可得试验五：此时x=5.8，a=24.8,2~7（2--1--M--7）=150.1<150.8;比较试验三四五所修路程长度，即可得最佳方案为方案五，（如图-18）所修长度L=24.7.22 图-17图-1822 再讨论1~5,2~5若连接2--5，则2~5（2--5）显然符合A1。1~5（1--2--5）=152.1<198.0,A1.（如图-19）图-19考虑到A2，我们可以过2做3--5垂线垂足为C，（如图-20）。则2~5（2--C--5）=159.2<170.9,A1.1~5(1--2--C--5)=189.2<198.0,A1.所以此方案才是最佳方案考虑1~8,3~4：同问题1，我们过8做1--6垂线垂足为O，过4做3--5垂线，垂足为P【做垂线之前我们同样要先判断（角816）和（角435）是否为锐角的问题，方法和问题一同理，经判断两角都是锐角】，1~8（1--O--8）=43.4<44.8,A14~3(4--P--3)=87.2<89.6,A1（如图-21）22 图-20图-21方案一已经将问题二解决，最后的路线图如图-22：22 图-22且总路程S=413.7。方案二：连接2--6，3--5,1~6（1--2--6）=131.1<141.0，A12~6（2--6）显然符合A12~7（2--6--7）=126.1<150.8,A13~6(3--2--6)=211.1<224.1,A13~7(3--2--6--7)=236.1<252.4,A13~5(3--5)显然符合A11~5(1--3--5)=247.1>198.0,不符A1。2~5（2--3--5）=217.1>170.9,不符A1。到此，再往下的问题和方案一里的重复。考虑1~8,3~4：3,4和方案一完全一样（如图-23）但1,8和方案一有差别，如果做了垂线，则8--O=45.7>45,（如图-24）那么8~1（8--O--1）更大于45，不符A1，舍去。所以1,8间的路线选择直接连接。22 图-23图-24方案二已经将问题二解决，最后的路程图如图-25：22 图-25且总路程S=397.9m综合方案一和方案二,我们最终确定选方案二。并给出该方案路线交叉点坐标：P（148.3,29.3），C（144.8,37.9）总路程S=397.9m。六．模型评价：该模型的优点：运用排除法，减少了需要考虑的点对的数量，减少了计算量，简化了计算，能够很快的比较得出结果。该模型的缺点：具体问题具体对待，不能运用到更广的地方，具有局限性。七．参考文献：1.姜启源.数学建模案例选集，北京：高等教育出版社，20062.白其峥.学建模案例分析，北京：海洋出版社，20003.吴建国.学建模案例精编，北京：中国水利水电出版社，20054.朱道元.学建模案例精选，北京：科学出版社，200322