公园道路设计问题.docx

《公园道路设计问题.docx》由会员分享，可在线阅读，更多相关《公园道路设计问题.docx（24页珍藏版）》请在三一办公上搜索。

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

2、学校（请填写完整的全名）：中北大学参赛队员（打印并签名）:1.张青2. 郭跃军3. 朱晓江指导教师或指导教师组负责人（打印并签名）：薛震日期：2012年6月27日赛区评阅编号（由赛区组委会评阅前进行编号）：2012中北大学数学建模竞赛编号专用页赛区评阅编号（由赛区组委会评阅前进行编号）：赛区评阅记录（可供赛区评阅时使用）：评阅人评分备注全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）：公园内道路设计最短路程问题的优化模型摘要最短路径问题是现实生活中常见的问题，在商业利润估算、生产生活、运输路线选 择等方面都有重要意义。本文研究的是以公园内部道路建设为背景的

3、最短路程问题，采 用规划模型解决了题目提出的若干问题。对于问题一，考虑到边缘道路不计入修建道路总长的题目要求和最短道路长不大于 两点连线1.4倍前提要求，首先依据“能用边缘就用边缘，不能则选用最短路径”的原 则，将那些无需借助交叉点即可满足1.4倍前提要求的点从考虑范围内剔除，从而将8 个点的两两连通问题简化为6个点之间的连通问题。然后针对简化后的问题，建立了 0-1 规划模型，并用LINGO软件求解，最终经过调整，得最短路程长为398.8。对于问题二，从交叉点个数出发进行讨论：将简化后的6个点两两相连，在所产生 的交叉点中选取最优点，得此情况下总路程最优解；对于两个交叉点，巧妙的利用椭圆 定

4、义来满足题目的最短道路长不大于两点连线1.4倍的约束条件，简化了问题，从而建 立非线性规划模型，运用LINGO软件求得此情况下的最优解；对于三个交叉点，在两个 交叉点的基础上，运用费马点的定义一三角形内到三顶点的距离和最小的点，找出第三 个交叉点的约束条件，从而建立非线性规划模型，求得到此情况下的最优解。比较三种 情况，得出问题二的最优方案为借助的三个交叉点，坐标分别为(65.94, 71.59)， (168.96, 40.25)，(117.26, 87.72)，总路程为 357.6918。对于问题三，基于若沿湖建路，则所修道路的长度要计入路程总长的重要假设，分 别以湖的顶点R2,R4为道路交

5、叉点进行讨论，在问题二的基础上建立非线性规划模型， 然后利用费马点逐步进行优化，比较两种情况，最终确定出最优方案下的四个交叉点的 坐标为(69.07, 63.96) , (112.32, 74.27) , (161.75, 30.73) , (140, 45)，总路程长为 358.946。关键字：0-1规划，非线性规划，椭圆定义，费马点020406080100120140160180200图1公园及入口示意图问题重述某大学为了美化校园环境，同时为其学生提供更好的生活条件，计划建设一个如图 所示的矩形公园。公园计划有8个入口，现需要建立一个模型去设计道路让任意两个入 口相连(可以利用公园四周的边

6、，即默认矩形的四条边上存在已经建好的道路，此道路 不计入道路总长)，使总的道路长度和最小，前提要求是任意的两个入口之间的最短道 路长不大于两点连线的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)。10090807060403020100为解决该问题，现需要完成以下问题：问题一：假定公园内确定要使用4个道路交叉点为：A(50,75)，B(40,40)，C(120,40)， D(115,70)，借助交叉

7、点设计道路使公园内道路的总路程最短。建立模型并给出算法。 画出道路设计，计算新修路的总路程。问题二：现在公园内可以任意修建道路，在满足条件下设计公园内道路使总路程最 少。建立模型并给出算法。给出道路交叉点的坐标，画出道路设计，计算新修路的总路 程。问题三：若公园内有一条矩形的湖，新修的道路不能通过，但可以到达湖四周的边。 示意图见图2,重复完成问题二的任务。其中矩形湖为R1(140,70),R2(140,45),R3(165, 45),R4(165,70)。注：以上问题中都要求公园内新修的道路与四周的连接只能与8个路口相通，而不 能连到四周的其它点。10090 -00 -R2 R3-J_*_I

8、图2有湖的示意图II406080100120140160180200二.问题分析70 -60 -50 -40 -30 -20 -10 -020结合题目要求，我们对各个问题分析如下：对于问题一，要考虑8个入口和4个交叉点共12个点之间最短路径问题，相对复 杂，而题目要求边缘道路不计入道路总长，所以设计道路时依据“能用边缘就用边缘， 不能则选用最短路径”的原则，利用最短路径长不大于两点连线的1.4倍这一前提要求， 先将利用边缘路径满足1.4倍条件的入口从考虑范围内剔除，将问题简化为借助交叉点 连通（P1，P5），（P1，P6），（P1，P8），（P2，P5），（P2, P6），（P3, P4），（

9、P3, P5），（P3, P6），（P3, P7）的最短道路长。又经过计算发现其中的借助任何交叉点和其他入口，都 无法满足条件，因而必须修建P1-P8和P3-P4两条道路。这样问题就进一步简化为求解 借助交叉点连通两组点1,2,35,6,7的最短道路长。对于简化后的问题，讨论发现两 组点平均分布在交叉点的两侧，并且必须经过交叉点连通，因此可从四个交叉点出发考 虑，根据两点之间是否建路定义0-1矩阵，建立0-1规划模型进行求解。对于问题二，由于可以任意修路，只要满足任意两入口之间最短距离长不大于两点 连线的1.4倍，且使修路的总路程最短即可。因而沿袭问题一的方法，借助交叉点来满 足上述要求。由问

10、题一的解决思路可知，1-8, 3-4必连，我们只需要考虑把1，2, 3 借助交叉点与5, 6, 7连通。考虑到实际情况中，交叉点过多会造成困扰，所以在构建 道路过程中，在符合问题要求（两入口之间最短距离长不大于两点连线的1.4倍）的前 提下，尽量使公园中的道路交叉点个数少，不妨从交叉点个数进行讨论，力求新修道路 的总路程最短。对于问题三，首先考虑问题二中设计的道路是否不通过矩形湖，若不通过，则问题 二的结果即为问题三的结果；否则，对问题二方案中穿过湖的道路进行调整一将其调整 为穿过湖的顶点。利用费马点到三个顶点的距离最短，建立出相应的非线性规划模型， 求出相应的交叉点，然后再利用费马点来进行优

11、化，直到不能再优化为止，最终可得到 最优方案。三. 模型假设(1) 假设入口形状与路宽忽略不计，即将入口抽象为点，道路抽象为线。(2) 若沿湖建路，则所修道路的长度要计入路程总长。(3) 假设交叉点位置的选取不受地理位置的限制。四. 符号说明L : 0-1矩阵._ 0z点与_/点没有连线，即未修建道路._._勺 勺1点与点有连线，即修建道路 1 ，2,3,4 1，1S :设计道路总长s.: i点与j点的距离d :费马点到三个顶点的距离和。X : i点横坐标J : i点纵坐标五. 模型建立与求解5.1问题一的模型建立与求解5.1. 1问题简化由题将八个入口及四个交叉点依次设为：1,2,3,4,5

12、,6,7,8,A,B,C,D。(如图3所示) 通过题目已给数据，借助EXCEL软件求得各点之间的距离(见附录1)及各点距离 的1.4倍(见附录2)。由于考虑到最终结果只算公园内部的道路长度总和以及最短道路 长不大于两点连线1.4倍前提要求，先依据“能用边缘就用边缘，不能则选用最短路径” 的原则对问题进行简化。我们通过计算发现，通过边缘路径，只有以下10组入口不满 足最短道路长不大于两点之间距离1.4倍：(1,5),(1,6),(1,8),(2,5),(2,6),(2,7),(3, 4),(3,5),(3,6),(3,7)。因而问题就简化为求利用交叉点连通以上10组入口的最短路 程长。经过计算又

13、发现(1,8),(3,4)借助任何其他点都无法满足条件，因而必须修建1-8 和3-4两条道路(如图4所示)(画图程序见附录3)，而借助路径1-8和边缘路径，(2,7) 也满足了 1.4倍前提要求，这样问题就变为求解借助交叉点(1,5),(1,6),(2,5),(2,6), (3,5),(3,6),(3,7)的最短路径问题。1 DU90日口70605C40,JU20W0 2U 40 配 W 1DU 12014U WO 1SU 2DU图3公园入口及交叉点示意图对于借助交叉点求解连通(1,5),(1,6),(2,5),(2,6),(3,5),(3,6),(3,7)的最短路 径问题。考虑6个入口平均分

14、布在矩形公园的两侧，故将其分成两组g 1,2,3和g 5,6,7进行考虑。问题即转化为通过交叉点，求使g中任意一点与G中任意一点的连 通的最短路径问题。而两组点又分别分布在四个交叉点的两边，而且连线过程中必须经 过交叉点，所以从交叉点的连线情况出发进行求解。考虑使用0-1规划模型求解该问题。在此我们对交叉点与该问题涉及的入口对应点 重新编号为A-1,B-2,C-3,D-4,1-5,2-6,3-7,5-8,6-9,7-10。根据是否与交叉点连线定义 以下0-1矩阵：其中_ 0i点与j点没有连线，即未修建道路._._勺|1i点与j点有连线，即修建道路 1 l，2,34j I”.。则所求问题转化为求

15、解：min S = X X li=1 j = i+1 其中S为设计道路总长，s为i点与j点的距离。即至少有两个点与A,B,C,D作为交叉点，一般认为必定至少有两条道路经过该点 其相连，因而可得约束条件：i = 1,2,3,4X l 2j q则所求问题转化为求解0-1规划模型:目标函数：min S = X X l sij ij i=1 j = i+1 J矣 j js.t. 7 s 为 i点到j点的距离i = 1,2,3,4; j = 1,.,10j 0或15.1.3模型求解利用LINGO软件对上面建立的0-1规划模型进行求解（程序见附录4），其中s的数值见附录1，求得结果为i = i = i =

16、 i = i = i = i = i = 1，剩余的为0。即建立1219252634374748道路 A-B,A-6,B-1,B-2,C-D,C-3,D-6,D-7,道路图如图 5 所示。道路总长为 352.1205。5.1.4模型的改进验证图5设计方案是否满足两个入口之间的最短道路长不大于两点连线的1.4倍。 通过计算发现只有(2,5)不满足上述条件。下面对初始方案进行调整：(1) 考虑3点和5,6,7三点经过计算发现点3通过C-D路径到达5,6,7点时，道路长度满足1.4倍要求，因 而为保证路径最短，将路径3-D从设计路径中剔除，如图6(b)所示。(2) 考虑2点和5点的问题利用枚举法，列

17、举出2-C，2-D，B-C，B-D，B-5,A-D，A-5这7种假设路线。再利 用总道路长度(不含矩形边)最短，最短道路(含矩形边)长不大于两点连线的1.4倍 这两个条件进行筛选，最后得出增添A-5为最优路径方案，如图6(c)所示。而建立A-5路径后，又发现点1通过2-B-A路径到达5,6点与点2通过1-B-A路径 到达5,6点的距离都能满足1.4倍条件，但路径1-B比2-B长，故将1-B路径剔除，从 而得改进后方案如图6(d)所示。(a)改进前道路示意图(b)第一次改进道路示意图(d)第三次改进道路示意图(c)第二次改进道路示意图图6模型改进道路示意图综上所述，将1-8与3-4加入图6中，得

18、最终方案如图7所示，并求得最短路径长 为 S 398.8。图7问题一道路最终设计图5.2问题二的模型建立与求解问题二与问题一的不同之处在于，可以任意修路，采用问题一的想法借助交叉点。 根据问题一的分析知1-8, 3-4两条路必修，将问题简化为把1,2,3借助交叉点与5,6,7 连通，且在满足题目要求下使修路的总路程最短。因需借助的交叉点个数不确定，下面 就个数进行逐一计算分析，力求得到总路程最短方案。5.2.1 一个交叉点的情况想要在图4中找出一个交叉点，使修路的总路程最小，根据两点间线段最短，可知 该交叉点必为1,2,3与5,6,7两两互连产生的交点之一，表1即为所有不同连线交点下 的道路路

19、程长。表1不同连线交点下的道路路程长1-52-51-62-63-6301.4995282.14373-7321.6990302.3432281.3963281.3963从最短路径出发，在上述结果中优先考虑连3-7与1-6或3-7与2-6，但经计算， 这两种情况（2,5）的最短距离超过了 （2,5）连线的1.4倍，不满足题目要求。经计算分 析，在不产生新的交点的前提下，添加新的连线使得满足要求是不可行的。再考虑3-6与2-5相连的情况，计算得（1,6）的最短距离超过了（1,6）连线的1.4 倍，不产生新交点的前提下，考虑添加1-6，2-6的连线，因1-6，2-6长度一样，且计 算得所有点都满足条

20、件，故添加其中任意一条连线均可，不妨添加1-6连线，此情况下 的总长为383.2624。经计算其余三种情况，都不存在满足题目条件且比3-6与2-5相连的总长小的修路 方案。则所添交叉点的坐标为 （89.49, 56.41）， 新修路的总路程S 479.3093。道路设计如 图8所示。图8公园道路最终设计图5.2.2两个交叉点的情）兄想要在图4中找出两个交叉点，既要保证总的路径长度最短，又要保证路径满足问 题中所给出的约束条件。根据平面几何的相关知识，椭圆上的点到两个焦点的距离是定 值且等于椭圆长轴的长度，我们可以把公园的两个入口作为椭圆的焦点，长轴的长度为 两焦点距离的1.4倍，用MATLAB

21、画出椭圆（程序见附录5），则在椭圆上以及椭圆内部 点就可以保证到两个焦点的距离满足问题的约束。分别作出以3-5,2-6,1-6,2-7为焦点 的椭圆，如图11所示。根据图9可以看出，要想满足问题的约束条件，选取的两个道路交叉点必须分别在 左边三个和右边一个椭圆的范围内。设两个道路交叉点分别为E (X ,y ) , F (X ” )，建立1122非线性规划模型。E点在焦点为2、6的椭圆内，可得椭圆的约束条件：(x - 42.5) 2(y 50) 2|(4)i+ i 1(4)11其中 2c = s = 101.1187 ，2a = 1.4 x 2c = 141.5662 ，a 2 = c 2 +

22、b 21 2611111同理可得F点的约束条件：(X2 140) 2 + (y2 50)2 1(5)a 2b 2其中 2c = s = 107.7033，2a = 1.4 x 2c = 150.7846，a 2 = c 2 + b 22 3522222又因找的交叉点都在矩形内，有0 X 200 (i = 1,2)0 y 100 (i = 1,2)(6)故非线性规划模型为：目标函数：min S = &x - 50)2 + y 2 + &x - 35)2 + (y - 100) 2 + ,：(x - 120) 2 + (y - 100) 2 +111111.(X 一 120) 2 + (y 一 1

23、00) 2 + ；(X 一 160) 2 + y 2 + ：(X 一 200) 2 + (y 一 50) 2(7)222222(X - 42.5) 2(y 一 50) 2bT11st (X -140) 2(y - 50)2s U2+2 1a 220 X 200 (i = 1,2)0 y 100 (i = 1,2)，道路设计如图10所示。运用LINGO软件求出最优解(程序见附录6)：两交叉点坐标 E (62.33, 72.86) , F (173.10, 43.64)经计算3-F-4也可满足3、4的最短距离不超过3、4直线距离的1.4倍，且修路的 总路程更短，故进一步调整，得最终方案：两个交叉点

24、坐标为E(62.33, 72.86)， F (173.10, 43.64)，新修路的总路程为S = 358.8046，道路设计如图11所小。5.2.3此处为了找出第三个交叉点，引入费马点定义。定义：在几何学中，费马点是位于三角形内的一点，给定一个三角形ABC的话， 从费马点P到三角形的三顶点A、B、C的距离之和比其它点都要小。如果三角形的内角全部小于120度则费马点在三角形内部，故在两个交叉点的基础 上，在 EF5中找出费马点，即第三个交叉点。使得第三交叉点到e,F,5的距离总和最 小。同样建立非线性优化模型，不妨设三个交叉点的坐标分别为G(x ,y )，H (x ,y )，1122K (x

25、, y )。3G点在以2、6为焦点的椭圆内，可得G点的约束条件：(x - 42.5) 2(y 50)21+1(8)同理H在以3、5为焦点的椭圆内，可得H点的约束条件：(x 2 -140) 2 +(y 2 - 50)2v 1a 2b 2第三个交叉点K在三角形 GH 52中，故有垃束条件：min x , x ,120 x max x , x ,120 (10)12312min y , y y 100(11)又因找的交叉点都在矩形内，有1 230 x 200 (i = 1,2, 3)0 y 100 (i = 1,2, 3)(12)故非线性规划模型为：i目标函数：min S = &尤-50)2 + y

26、 2 + &尤-35)2 + (y - 100) 2 +、，(x - 120) 2 + (y - 100) 2 + &尤-160) 2 + y 211111122+ ：(x 一 200) 2 + (y 一 50)2 + /(x 一 x )2 + (y 一 y )2 + (x 一 x )2 + (y 一 y )2(13)2223233131(x - 42.5) 2(y - 50)2 八1+1 1a 2b 2(x -140) 2(y - 50)2s.t. 7 22min x , x ,120 x max x , x ,120 12312min y , y y 100 1230 x 200 (i =

27、 1,2, 3)0 y =2);注：Book1.xls见附件附录5： MATLAB绘制四个椭圆程序a=141.5662 141.5662 150.7846 150.7846;c=50.55935 50.55935 53.8516 53.8516;major=a./2; %求半长轴minor二sqrt(major.”2-c.”2); % 求半短轴； inc=0.1489 2.9927 -2.7611 -2.7611; posl=27.5 42.5 140 30;pos2=50 50 50 50;t=r,b,y,k;for i=1:1:4ellipse(minor(i),major(i),inc(

28、i),pos1(i),pos2(i),t(i)hold on;endx=20 50 160 200 120 35 10 0;y=0 0 0 50 100 100 100 25;m=12345678;p=polyfit(x,y,1);plot(x,y,*)hold on;box on;for i=1:1:8gtext(m(i);end附录6：问题二求两交叉点LINGO程序min=sqrt(x1-50)”2+y12)+sqrt(x1-35)”2+(100-y1)2)+sqrt(x1T20)”2+(100 -y1)”2)+sqrt(x2T20)”2+(100-y2)2)+sqrt(x2T60)”2+y22)+sqrt(x2-200)” 2+(50-y2)2);(x1-42.5)2/5009.81+(y1-50)2/2453.495=1;(x2-140)2/5684+(y2-50)2/2784.18=0;X1=0;X2=0;Y1=0;Y1100;附录7：问题二求三交叉点LINGO程序min=sqrt(x1-50)”2+y12)+sqrt(x1-35)”2+(100-y1)2)+sqrt(x2T60)”2+y2”2 )+sqrt(x2-200)”2+(50-y2)2)+sqrt(x1-x3)”2+(y1-y3)2)+sqrt(x2-x3)”2+(y 2-y3)2)+