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

12A 题 城市公园内的道路设计摘要 本模型属于非线性规划模型.依据规划论原理对公园道路进行优化设计.建立相应的数学模型,并利用数学软件计算、分析、比较.找出一个较满意的计划方案.本文首先利用 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.9636 m.最后文章讨论了模型的优缺点,提出改进方向.关键字：公园道路设计 Matlab lingo 非线性规划 优化设计 数字化处理一、问题重述3某城市决定在市中心建立一个公园.公园计划有若干个入口,现在你需要建立一个模型去设计道路让任意两个入口相连（可以利用公园四周的边,即默认矩形的四条边上存在已经建好的道路,此道路不计入道路总长）,使总的道路长度和最小,前提要求是任意的两个入口之间的最短道路长不大于两点连线的 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 公园及入口示意图4图 2 一种可能的道路设计图图 3 有湖的示意图二、问题分析分析题目的特征及题中所给出的条件,可以知道,所要解决的是一个非线性规划的问题,因此需要建立相应的非线性的模型.第一问的分析：本文中明显指出：设计道路让任意两个入口相连并且任意两个入口之间的最短道路长不大于两点连线的1.4倍.在满足题目要求的前提下,设计时,一方面尽量使用公园四周已修好的道路.另一方面,由于公园是长为200米,宽为100米的矩形,在使用四个交叉点时尽量选用交叉点和公园入口形成的公共道路,及它们5连线近视为两条平行线,以减少成本投资,然后在这两条平行线上找出两点（这两点必须在交叉点或入口点上）之间的最短连线.经计算 p1到 p8,和 p3到 p4的最短路径距离大于它们最短距离的1.4倍,故它们应一定相连.在此基础上,画出图形,经过删选,选出满足题目要求下的最短路程,算出总长.对于本问来说,可以采用规划模型来解.通过8个公园入口点和4个交叉点的任意连线,来找出最短路程.故可以归纳为单目标规划模型,通过 Lingo的处理即可求解.因此,本问计划构造两个模型,分别进行求解.第二问的分析：本问可在第一问的模型上,对道路的交叉点的选取进行假设（依次选1,2,3…）,这一问仍然是个追求单一的目标—一最短的路径.通过Lingo逐次的进行求解,在比较逐次求出来的最短路径,从而确定最短路径,确定交叉点的个数和坐标,画出道路的设计.第三问的分析：本问是基于第二问的模型的上,在不经过矩形湖时所得的最短路径.分析第二问的图形连线,只需调整 p3p5这条路线,故在不经过湖的情况下,可以连接 p5R1和 p3到 R2垂线.从而计算出最短总路程.三、基本假设1.公园内所修的道路为平展的,不任何凹凸处.2.公园内所修的道路为直线,无任何歪曲.3.所修道路的交叉点可视为质点.4.所修道路可视为一条线,不考虑道路的宽度.四、定义符号说明： 表示i,j 两点之间直线距离； kij6： 表示i,j两点之间最短距离；dij： 表示第i,j两点所有的直线；vji,： 表示通过第i,j两点之间所有的直线交点的横坐标；xvji： 表示通过第 i,j两点所有的直线交点纵坐标；yvji五、模型准备5.1数据的处理1. 公园的八个入口点中任意两点之间连线距离的1.4倍：p1 p2 p3 p4 p5 p6 p7 p8p1 0 42 196 261.54156 197.98996 141.56618 140.69832 44.82184p2 42 0 154 221.35946 170.89184 141.56618 150.78462 78.26252p3 196 42 0 89.64368 150.78462 224.10934 252.38864 226.71782p4 261.54156 221.35946 89.64368 0 132.07572 241.37316 275.05632 282.17896p5 197.98996 170.89184 150.78462 132.07572 0 119 154 198.11358p6 141.56618 141.56618 224.10934 241.37316 119 0 35 115.87058p7 140.69832 150.78462 252.38864 275.05632 154 35 0 105.92918p8 44.82184 78.26252 226.71782 282.17896 198.11358 115.87058 105.92918 02. 公园的八个入口点和四个交叉点任意两点连线的长度：（见附录）3. 公园的八个入口点中任意两点只沿着公园的边的最短路径长度：（见附录）4. 对数据进行分析与整理,找出符合题目要求在公园四边的任意八个入口点中两点的组合： （ p1p2） ,（ p1p3） ,（ p1p4） ,（ p1p7） ,（ p2p3） ,（ p2p4） ,（ p2p8） ,（ p3p8） ,（ p4p5） ,（ p4p6） ,（ p4p7） ,（ p4p8） ,（ p5p6） ,7（ 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沿着公园边的最短路径长度为：45 m.因为45>44.8219,不满足题目要求.并且由图形可知： p1到 p8在经过园内的最短路径的长度大于 P1到 P8沿着公园边的最短路径长度.故 p1和 p8应该连线,才能满足题目要求.通过计算分析可知,这样的情况还有 p3和 p4,所以 p3和 p4连线,作为所需的道路.6.1.2模型的建立与求解观察公园的八个入口点和四个交叉点在图中的位置,根据原则2,可以有以下的连接方式（图一）：8连接方式的一种（其他见附录）经过删选和比较,选出在满足题目要求下的最短路径,为：p8→p1→p2→B→A→p5→D→C→p3→p4,p6→A （路径为无向的）.如下图表示（图二）：根据模型准备5.1的数据处理,计算出上图的路径为：394.5596 m.及公园设计出的最短总路程为：394.5596 m.6.1.3规划模型的建立与求解将公园的八个入口点和四个交叉点进行依次排序 p1为1, p2为2,…, p8为8, A为9,…, D为12.9要选取出总路程最短的道路,下面特构造特殊控制变量 ：mvji,标 上的 交 点 在 图 上 十 二 个 坐 坐 标 上的 交 点 不 在 图 上 十 二 个，vjivjim,10,1.目标函数：dvjiijijMins ,121即路径总长度的最小值.2.约束条件：（1）任意的两个入口之间的最短道路长不大于两点连线的1.4倍：81,4.  jidkjij（2）ui,uj交点的横坐标在图上十二个横坐标上：xivji（3）ui,uj交点的纵坐标在图上十二个纵坐标上：yivji（4）任意的两个入口之间沿着公园四边的最短道路长不大于两点连线的1.4倍：81,.1 jixkjijiij3. 最终的规划模型如下mdvjiijijs12min81,4.  jiyxkjijiij81,.1 ijij10;20xi 20j; 1yi 1j; ivjiyivji在 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倍.在构成道路的图形若有三角形,应满足。