城市公园内的道路设计.doc

A题 城市公园内的道路设计 摘要 本模型属于非线性规划模型.依据规划论原理对公园道路进行优化设计.建立相应的数学模型,并利用数学软件计算、分析、比较.找出一个较满意的计划方案. 本文首先利用Matlab算法处理数据,得到各点间的最短距离,然后根据公园各入口坐标求出任意两个入口之间沿公园四周的最短距离.最后,依次对问题给出答案. 第一问,要求设计公园内道路的总路程最短并且根据题目要求给出答案.本文构造了两个模型.一个是尽可能多的使用交叉点和公园入口之间所形成的公共道路,及矩形对边两点之间连线近似为平行线,然后在这两条平行线上找出两点之间最短连线.另一个模型为规划模型,通过在12个点之间任意连线求出最短路程,并运用lingo处理求解,得出最短距离为394.5596m. 第二问,所给条件与第一问相同,不同的是对交叉点没有要求.本问可在第一问的基础上对道路交叉点的选取进行假设,通过Lingo对这些点逐次求解,然后进行比较得出最短路程,再给出答案.当假设有一个坐标点时,分为两种情况,分别求出最短路程,再做比较,得出更短路程为379.6124m,坐标为（59.8585、77.6387）.假设有二个坐标点时,最短路程为431.0043,坐标为（48.7728,0.25）（119.6576,1.2531）.但是由于三角形两边之和大于第三边,所以交叉点越多路程越长.综上,最短设计路程为379.6124m,坐标为（59.8585,77.6387）. 第三问,文章给出了一个矩形湖,要求修建的道路不仅路程最少还不能通过湖.本问是基于第二问的模型的上,在不经过矩形湖时所得的最短路径.分析第二问的图形连线,只需调整p3p5这条路线,故在不经过湖的情况下,可以连接p5R1和p3到R2垂线.从而计算出最短总路程.则总路程长度为：352.9636m.最后文章讨论了模型的优缺点,提出改进方向.关键字：公园道路设计 Matlab lingo 非线性规划 优化设计 数字化处理 一、问题重述某城市决定在市中心建立一个公园.公园计划有若干个入口,现在你需要建立一个模型去设计道路让任意两个入口相连（可以利用公园四周的边,即默认矩形的四条边上存在已经建好的道路,此道路不计入道路总长）,使总的道路长度和最小,前提要求是任意的两个入口之间的最短道路长不大于两点连线的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).示意图见图1,其中图2即是一种满足要求的设计,但不是最优的.现完成以下问题：问题一：假定公园内确定要使用4个道路交叉点为：A(50,75),B(40,40),C(120,40),D(115,70）.问如何设计道路可使公园内道路的总路程最短.建立模型并给出算法.画出道路设计,计算新修路的总路程.问题二：现在公园内可以任意修建道路,如何在满足条件下使总路程最少.建立模型并给出算法.给出道路交叉点的坐标,画出道路设计,计算新修路的总路程.问题三：若公园内有一条矩形的湖,新修的道路不能通过,但可以到达湖四周的边,示意图见图3.重复完成问题二 的任务.其中矩形的湖为R1(140,70),R2(140,45),R3(165,45),R4(165,70).注：以上问题中都要求公园内新修的道路与四周的连接只能与8个路口相通,而不能连到四周的其它点. 图 1 公园及入口示意图 图 2 一种可能的道路设计图图3 有湖的示意图二、问题分析分析题目的特征及题中所给出的条件,可以知道,所要解决的是一个非线性规划的问题,因此需要建立相应的非线性的模型.第一问的分析：本文中明显指出：设计道路让任意两个入口相连并且任意两个入口之间的最短道路长不大于两点连线的1.4倍.在满足题目要求的前提下,设计时,一方面尽量使用公园四周已修好的道路.另一方面,由于公园是长为200米,宽为100米的矩形,在使用四个交叉点时尽量选用交叉点和公园入口形成的公共道路,及它们连线近视为两条平行线,以减少成本投资,然后在这两条平行线上找出两点（这两点必须在交叉点或入口点上）之间的最短连线.经计算p1到p8,和p3到p4的最短路径距离大于它们最短距离的1.4倍,故它们应一定相连.在此基础上,画出图形,经过删选,选出满足题目要求下的最短路程,算出总长.对于本问来说,可以采用规划模型来解.通过8个公园入口点和4个交叉点的任意连线,来找出最短路程.故可以归纳为单目标规划模型,通过Lingo的处理即可求解.因此,本问计划构造两个模型,分别进行求解.第二问的分析：本问可在第一问的模型上,对道路的交叉点的选取进行假设（依次选1,2,3）,这一问仍然是个追求单一的目标一最短的路径.通过Lingo逐次的进行求解,在比较逐次求出来的最短路径,从而确定最短路径,确定交叉点的个数和坐标,画出道路的设计.第三问的分析：本问是基于第二问的模型的上,在不经过矩形湖时所得的最短路径.分析第二问的图形连线,只需调整p3p5这条路线,故在不经过湖的情况下,可以连接p5R1和p3到R2垂线.从而计算出最短总路程.三、基本假设1.公园内所修的道路为平展的,不任何凹凸处.2.公园内所修的道路为直线,无任何歪曲.3.所修道路的交叉点可视为质点.4.所修道路可视为一条线,不考虑道路的宽度. 四、定义符号说明 ： 表示i,j两点之间直线距离； ： 表示i,j两点之间最短距离；： 表示第i,j两点所有的直线；： 表示通过第i,j两点之间所有的直线交点的横坐标；： 表示通过第i,j两点所有的直线交点纵坐标；五、模型准备5.1数据的处理 1. 公园的八个入口点中任意两点之间连线距离的1.4倍：p1p2p3p4p5p6p7p8p1042196261.54156197.98996141.56618140.6983244.82184p2420154221.35946170.89184141.56618150.7846278.26252p319642089.64368150.78462224.10934252.38864226.71782p4261.54156221.3594689.643680132.07572241.37316275.05632282.17896p5197.98996170.89184150.78462132.075720119154198.11358p6141.56618141.56618224.10934241.37316119035115.87058p7140.69832150.78462252.38864275.05632154350105.92918p844.8218478.26252226.71782282.17896198.11358115.87058105.929180 2. 公园的八个入口点和四个交叉点任意两点连线的长度：（见附录） 3. 公园的八个入口点中任意两点只沿着公园的边的最短路径长度：（见附录） 4. 对数据进行分析与整理,找出符合题目要求在公园四边的任意八个入口点中两点的组合：（p1p2）,（p1p3）,（p1p4）,（p1p7）,（p2p3）,（p2p4）,（p2p8）,（p3p8）,（p4p5）,（p4p6）,（p4p7）,（p4p8）,（p5p6）,（p5p7）,（p5p8）,（p6p7）,（p6p8）,（p7p8）. 六、模型建立与求解6.1问题一模型与求解6.1.1问题一的分析 本问需要在使用4个道路交叉点：A（50、75）,B（40、40）,C（120、40）,D（115、70）的基础上,且满足题目的前提要求：任意的两个入口之间的最短道路长不大于两点连线的1.4倍.要在公园内修最短的道路,可以有这样的原则：1. 所需要修的道路尽量使用公园四边修好的道路. 2.使用四个交叉点时尽量选用交叉点和公园入口形成的公共道路,及它们连线近视为俩条平行线,然后在这两条平行线上找出两点（这两点必须在交叉点或入口点上）之间的最短连线.又根据模型准备5.1的数据处理,P1到P8的连线距离的1.4倍为：44.8219m,P1到P8沿着公园边的最短路径长度为：45m.因为45>44.8219,不满足题目要求.并且由图形可知：p1到p8在经过园内的最短路径的长度大于P1到P8沿着公园边的最短路径长度.故p1和p8应该连线,才能满足题目要求.通过计算分析可知,这样的情况还有p3和p4,所以p3和p4连线,作为所需的道路.6.1.2模型的建立与求解观察公园的八个入口点和四个交叉点在图中的位置,根据原则2,可以有以下的连接方式（图一）：连接方式的一种（其他见附录）经过删选和比较,选出在满足题目要求下的最短路径,为：p8p1p2BAp5DCp3p4,p6A（路径为无向的）.如下图表示（图二）：根据模型准备5.1的数据处理,计算出上图的路径为：394.5596m.及公园设计出的最短总路程为：394.5596m.6.1.3规划模型的建立与求解将公园的八个入口点和四个交叉点进行依次排序p1为1,p2为2,p8为8,A为9,D为12.要选取出总路程最短的道路,下面特构造特殊控制变量： 1. 目标函数： 即路径总长度的最小值.2.约束条件：（1）任意的两个入口之间的最短道路长不大于两点连线的1.4倍： （2） ui,uj交点的横坐标在图上十二个横坐标上： （3） ui,uj交点的纵坐标在图上十二个纵坐标上： （4）任意的两个入口之间沿着公园四边的最短道路长不大于两点连线的1.4倍： 3. 最终的规划模型如下 ; ; ; 在Lingo的支持下,可以直接解出此方程,求出最短路径的长度及连接方式.但求出的最短路径的长度还要减去在公园四边所连接方式的长度,及求出在公园内的总路程的长度.6.2 问题二模型与求解6.2.1问题二分析对于本问,可以在公园内任意修建道路,仍然追求单一的目标一一最短的路径方式.可以换句话说就是要在200×100的矩形内选出点,使得选出来的点和公园入口点所连线的总长最短,但还要满足题目要求：任意的两个入口之间的最短道路长不大于两点连线的1.4倍.可以基于模型一的基础上,来进行选点.但需选出的点的个数不能确定,故依次去建立模型,找出每次模型的最短总路程,进行对比,找出规律,加以总结.故本问是个典型的非线性规划问题.6.2.2模型的建立6.2.2.1 在问题一模型的基础上,连接p1和p8,p3和p4使它们为所修道路的一部分, 然后在园内的道路先选一个的交叉点M（x,y）,连接Mp6,Mp5,Mp3,Mp2.使得所构成的道路满足：任意的两个入口之间的最短道路长不大于两点连线的1.4倍.在构成道路的图形若有三角形,应满足三角形的基本定理：三角形的两边之和大于第三边.在连接p1和p8,p3和p4的图形任选一个交叉点的两种情况M(x,y),Z(x,y)如下图表示（图三）： 当交叉点选取为M(x,y)时：1. 目标函数：2. 约束条件：（1） 在Mp6,Mp2和p6p2所构成的三角形中： （2）p1到p6的连线长度的1.4倍大于等于p1到p6的最短路径的长度： （3） 在Mp5,Mp2和p5p2所构成的三角形中： （4）p2到p5的连线长度的1.4倍大于等于p2到p5的最短路径的长度： （5） 在Mp3,Mp5和p3p5所构成的三角形中： （6） p3到p6的连线长度的1.4倍大于等于p3到p6的最短路径的长度： （7）x,y在200×100的矩形中,如图可得： 35<x<160; 0<y<160至此,就建立起了问题二中选取一个交叉点的描述性的规划模型,完整表示如下： ; ; ; ; ; ; 35<x<160; 0<y<160 运用Lingo进行求解,结果为：最短总路程为：387.3621m.M的坐标为：x=66.6382,y=46.7248. 图形连接为（图四）当交叉点选取为Z(x,y)时：3. 目标函数：4. 约束条件： (1)在Zp6,Zp2和p6p2所构成的三角形中： （2）p1到p6的连线长度的1.4倍大于等于p1到p6的最短路径的长度： （3)在Zp5,Zp2和p5p2所构成的三角形中： （4）p2到p5的连线长度的1.4倍大于等于p2到p5的最短路径的长度： (5) 在Zp3,Zp5和p3p5所构成的三角形中： （6）x,y在200×100的矩形中,如图可得： 35<x<160; 0<y<160至此,就建立起了问题二中选取一个交叉点的描述性的规划模型,完整表示如下： ; ; ; ; ; 35<x<160; 0<y<160 运用Lingol进行求解,结果为：最短总路程为：379.6124m.Z的坐标为：x=59.8585,y=77.6387. 图形连接为（图五）：6.2.2.2在问题一模型的基础上,连接p1和p8,p3和p4使它们为所修道路的一部分,然后在园内选取两个交叉点J(x1,y1),K(x2,y2).连接Jp6,Jp2,Kp5,Kp3,JK.使得所构成的道路满足：任意的两个入口之间的最短道路长不大于两点连线的1.4倍.1.目标函数：2.约束条件：（1）在Jp6,Jp2和p6p2所构成的三角形中：（2）p2到p5的连线长度的1.4倍大于等于p2到p5的最短路径的长度： （3）p2到p5的连线长度的1.4倍大于等于p2到p5的最短路径的长度： （4） 在Kp3,Kp5和p3p5所构成的三角形中： （5） p3到p6的连线长度的1.4倍大于等于p3到p5的最短路径的长度 （6）J(x1,y1),K(x2,y2),在200×100的矩形中： 35<x1<x2<160; 0<y1<100; 0<y2<100;至此,就建立起了问题二中选取两个交叉点的描述性的规划模型,完整表示如下： 35<x1<x2<160; 0<y1<100; 0<y2<100;运用Lingo进行求解,结果为：最短总路程为：431.0043m.J的坐标为：x1=48.7728、y1=0.25,K的坐标为：x2=119.6576,y2=1.2531.连接图形为（图六）：6.2.2.3 对于交叉点大于等于三个的选取,图中的任意地方画出交叉点的选取位置,根据三角形的两边之和大于第三边的定理.分析可知：随着交叉点选取个数增加,在园中所修建的道路的总长度增加. 对于交叉点选取为三个的,下图（图七）为局部图,在进行简要的分析： 试着连接p6N,在三角形NGp6中p6N和NG的总长度大于Gp6的长度,故和选取两个点作比较,很显然三个交叉点的总长度大于两个点的总长度.综上所述：在满足题目的要求下,选取的交叉点,使在公园内所修的道路最短.比较上面的分析结果可得：交叉点选取一个,坐标为（66.6382,46.7248）,最短道路总长度为387.3621m.其连接方式为图（五）.6.3 问题三模型与求解6.3.1问题三分析 本问要求在公园内有个矩形湖,湖的位置为：R1（140,70）,R2（140,45）R3（165,45）,R4（165,70）.第二问求出来的最短总路程为379.6124m,图形连线如图所示,在此基础上不经过湖,需调整p3p5的连线.但还需满足题目要求. 6.3.2模型的建立在满足题目要求的情况下,对p3p5的路线进行调整.在根据三角形的两边之和大于第三边的定理.故在不经过湖的情况下,计算可得,应连接p3到R2的垂线和p5R1.从而求出最短路径的总长度.新的路线的总长度为：352.9636m. 七、模型的评价 7.1 模型的优点本模型比较简单,本模型是属于传统的非线性规划模型,在确定目标函数的情况下,对其加以约束,即可求出最优解.计算过程采用Lingo软件,程序较简单.本模型适用普遍,具有很好的推广性. 7.2 模型的缺点 本模型的结果具有一定的局限性,只是考虑道路总长度的最短,但没有考虑到所修的道路对于整个区域的覆盖面积,和游客的观赏性. 八、模型的推广 模型准确地解决了公园道路的铺设问题,在不影响游客观看公园景色的同时,大大的减少了从一个门到另外一个门之间的距离.并且做到了尽可能路线最短. 本模型属于非线性规划问题,将复杂的公园道路铺设问题,简化成能利用非线性规划知识解决的数学模型,由于本模型是规划问题,稍作修改可以运用于最短路径的问题,石油运输问题,灾情巡查问题等. 九、参考文献1姜启源,谢金星,叶俊.数学模型第三版.北京.高等教育出版社,20032胡红亮,赵芳玲数学建模与竞赛辅导.西北大学出版社 .20103陕西赛区组委会 高职高专数学建模培训讲义. 附录：1.公园的八个入口点中任意两点只沿着公园的边的最短路径长度：p1p2p3p4p5p6p7p8p103014023024015513045p230011020027018516075p3140110090220295270185p4230200900130215240275p5240270220130085110195p615518529521585025110p713016027024011025085p84575185275195110850 2.第二问中交叉点选取一个时方程的编程：objmin=(x-50)2+y2)(1/2)+(x-35)2+(100-y)2)(1/2)+(x-160)2+y2)(1/2)+(x-120)2+(y-100)2)(1/2);(x-50)2+y2)(1/2)+(x-35)2+(100-y)2)(1/2)>101.1187;(x-50)2+y2)(1/2)+(x-35)2+(100-y)2)(1/2)<111.5602;(x-50)2+y2)(1/2)+(x-120)2+(y-100)2)(1/2)<170.8918;(x-160)2+y2)(1/2)+(x-120)2+(y-100)2)(1/2)>107.7033;(x-160)2+y2)(1/2)+(x-120)2+(y-100)2)(1/2)<139.1093;(x-50)2+y2)(1/2)+(x-160)2+y2)(1/2)>110;(x-50)2+y2)(1/2)+(x-160)2+y2)(1/2)<154; x>35;x<160;y>0;y<100; 3.第二问中交叉点选取两个时的方程：objmin=(x1-50)2+(y1)2)(1/2)+(x1-35)2+(100-y1)2)(1/2)+(x2-160)2+(y2)2)(1/2)+(x1-120)2+(100-y2)2)(1/2)+(x1-x2)2+(y1-y2)2)(1/2);(x1-50)2+(y1)2)(1/2)+(x1-35)2+(100-y1)2)(1/2)<101.1187;(x1-50)2+(y1)2)(1/2)+(x1-35)2+(100-y1)2)(1/2)>141.5602;(x1-50)2+(y1)2)(1/2)+(x1-x2)2+(y1-y2)2)(1/2)+(x2-120)2+(100-y2)2)(1/2)<170.8918;(x2-160)2+(y2)2)(1/2)+(x2-120)2+(100-y2)2)(1/2)>107.7033;(x2-160)2+(y2)2)(1/2)+(x2-120)2+(100-y2)2)(1/2)<139.1093;x1>35;x1<x2;x2<160;y2>0;y2<100;4.任意两个入口点之间的距离：clc;clear;x=20 50 160 200 120 35 10 0 50 40 120 115;y=0 0 0 50 100 100 100 25 75 40 40 70;r=zeros(length(x);for i=1:length(x) for j=1:length(y) r(i,j)=sqrt(x(i)-x(j)2+(y(i)-y(j)2); endendrclc;clear;x=35 120 66.63818 50 160;y=100 100 46.72475 0 0;r=zeros(length(x);for i=1:length(x) for j=1:length(y) r(i,j)=sqrt(x(i)-x(j)2+(y(i)-y(j)2); endendr 5.连接方式图：