公园道路问题设计

1、数学建模案例选讲课程论文公园内道路设计问题2012年5月21日数学建模案例选讲课程论文题目和要求方式：综合性作业题目：公园内道路设计问题要求：根据题目要求，完成一篇完整的论文。论文包括模型的假设、建立和求解、计算方法的设计和计 算机实现、结果的分析和检验、模型的改进等内容。格式请参照下面给出的模版(语言表述与排版格式均计入成绩)。凡抄袭的论文成绩为不及格。数学建模案例选讲课程论文评语及成绩评语摘要10分模型建立35分模型求解35分语言表述10分版式10分总分摘要本题是一个道路设计最优化问题，讨论如何设计道路使矩形公园内道路总路程最短。且满足条件：第一问中，公园的所有入口和亭子都连通，并且用4个

2、亭子作为道路的交叉点；任意两个入口之间的最短道路长度不大于两点连线的1.4倍。第一问要求设计道路最短方案，先不考虑环路问题，构造最小生成树，再用贪婪算法，对不满足条件 的路径进行替换，使新路径满足条件。得到最后的最短路设计方案。第二问要求对任意位置的四个亭子，找出新的最短路径设计方案，可利用第一问方案，用1个亭子替 换原来的4个亭子，再有2个亭子替换1个亭子，最后用新的4个亭子替换2个亭子。关键词：最短路问题，最小生成树，贪婪算法，替换1.问题重述学校准备修建一个长200米、宽100米的矩形公园。按照规划，将在公园的四周上设置8个入口、在公园内修建4个亭子。已知8个入口的坐标分别为:P1(20

3、, 0)，P2(50, 0)，P3(160, 0)，P4(200, 50)，P5(120,100)，P6(35, 100)，P7(10, 100)，P8(0, 25)，4 个亭子的坐标分别为：T1(50, 75)，T2(40, 40)，T3(120, 40)，T4(115, 70)，如图 1 所示。P58060P440P82002040 P2 6080100120140160180200P7 P61000图1公园及入口示意图现在需要你设计公园内的道路，使得:公园的所有入口和亭子都连通，并且用4个亭子作为道路的交叉点;任意两个入口之间的最短道路长度不大于两点连线的1.4倍。问题一：如何设计可使公

4、园内道路的总路程最短？要求建立模型、给出算法、画出道路设计图，并计算出公园内道路的总路程。图2是一种满足要求的设计，但不是最优的。1008060P440P820P502040 P2 6080100120140160180200P7 P60图2 一种可能的道路设计图问题二：如果公园内4个亭子的位置待定，如何设计可使公园内道路的总路程最短？要求建立模型、 给出算法、给出道路交叉点(亭子)的坐标、画出道路设计图，并计算出公园内道路的总路程。注：(1)设计道路时，可以利用公园四周的边，即默认矩形的四条边上存在已经建好的道路，但此道路不计入道路总长。(2)以上问题中都要求公园内修建的道路与四周的连接只能

5、与8个入口相通，而不能连接到四周的其它点。基本假设与符号约定为了简化问题和方便讨论，除问题中给出的假设外，我们进一步做如下的假设和说明：假设目标公园平坦，没有湖泊等不能修建道路的区域，也没有丘陵、盆地等使道路弯曲、延长道 路长度的区域。假设目标公园内环境相同，除了 4个亭子外，没有道路必须经过或必须不经过的特殊区域。假设目标公园是一个矩形，公园门之间、亭子之间没有大小之分，全部可以视为点。假设目标公园内和四周的道路没有宽窄之分，全部可以视为直线。在此，我们也约定文中所用符号如下：(1) Pi(i=1,2,3,4,5,6,7,8 表示公园入口 广8。Ti(xi，yi)(i=1,2,3,4)表示亭

6、子 14 的坐标。Ai(i=1，2，11,12)表示公园入口与亭子共同的编号r %)11121n0-1矩阵：X =(%)=ij%21%22:%2 nI%】n1%n2%nn J表示两点间是否有路径相通，其中% = 0,表示第个和弟个点之间无连线ij1,表示第个和弟个点之间有连线。(5)最短路径矩阵:径长度。r s11s12顼)=s21s22:：:sn21ns2n ，snnS ij表示在设计中第i个和第j个点间最短路(dd- d、ii121n限制矩阵：D = c=d21d22:d2n:I dn1dn 2dnn (i，j=l,2,3,4,5,6,7,8)表示图中第 i 个入口和第j个入口的直线距离的

7、1.4倍。问题的分析本题是一个道路设计最优化问题，讨论如何设计道路使公园内道路总路程最短，但要求满足条件第一问中，公园的所有入口和亭子都连通，并且用4个亭子作为道路的交叉点；任意两个入口之间的最短道路长度不大于两点连线的1.4倍。因为题目中默认矩形的四条边上存在已经建好的道路，因此可先利用四周道路，找出那些仅通过四周 道路相连则不满足条件(2)的路径，在后续讨论中可优先考虑这些路径，使问题简化。通过计算，不满 足条件(2)的路径有 P1-P5 , P1-P6 , P1-P8 , P2-P5, P2-P6 , P2-P7 , P3-P4 , P3-P5 , P3-P6 , P3-P7。 再根据各

8、问题的具体要求进行讨论求解。模型的建立与求解4.1问题一的模型的建立与求解4.1.1模型的建立建立连通网，8个入口和4个亭子就是网的顶点，道路就是两点之间的连线，道路长度就是连线的权 值。因为在此题中有环路存在，因此不能直接用最小生成树法来求解，可结合贪婪算法求解。求解过程分为四部步：首先，不考虑环路问题，使用最小生成树法，得到一个初步道路设计方案。然后，由得到的初步方案计算出任意两点间最短路径长度，做出最短路径矩阵。接着，把最短路径矩阵与任意两入口直线距离的1.4倍的矩阵进行比较，得到不满足条件的路径。最后，对不满足条件的路径进行替换，使得新路径满足条件，替换后的路径可以存在环路。(2)针对

9、上4.1.2模型的求解现有入口与交叉点共同的编号及其坐标：A1(20,0), A2(50,0), A3(160,0), A4(200,50), A5(120,100), A6(35,100), A7(10,100), A8(0,25), A9(50,75), A10(40,40), A11(120,40), A12(115,7).现在分四步进行模型的求解：(1)利用MATLAB，根据克鲁斯卡尔算法，求得最小生成树，为了直观表示，做出网内各点是否有道路 相连的0-1矩阵(0表示没有连线，1表示有连线)。01000001000、01000000001000001000000100010000000

10、00000000000001000000101000000001000000100000000000000001000101010000001000001000000001000010001010同时用MATLAB绘制出对应的初步设计方案:假设不存在环路而得到的初步设计方案，计算由目前8个入口最短路径长度，做出最短in路径矩阵S:8x80 020406080030260324203137300230294173107260230064117181SS ?3242946401812458x820317311718101251371071812451250162132206270150253262

11、292356235169 将上述最短路径矩阵与限制矩阵进行比较，限制矩阵表示任意两入口直线距离的1.4倍。0421962621981421414542015422117114215178196154090151224252227D =，262221900132241275282198171151132011915419814214222424111903511614115125227515435010645782272821981161060发现部分入口间最短路径不满足条件(2) (SijWDij为符合条件，反之不符合)，如下表中突出显示数 据(由于路径无向，因此下三角不显示)：A1A2A3A

12、4A5A6A7A8A103014023024015513032A2011020027018516075A3090220295270185A40130215140275A5085110195A6025110A7085A80对于部分入口，连接它们的园内最短路径比四周路径要长得多，园内最短路径不符合条件但四周路径 符合条件吗，上表中已经对这些路径进行替换。设计到的路径中可替换的边是有限的，利用穷举法，进一步得出满足条件的最优解，对应道路设计方案图如下：4.1问题二的模型的建立与求解4.1.1模型的建立根据分析，当没有交叉点的时候，不满足条件（2）的路径有P1-P5 , P1-P6 , P1-P8 ,

13、 P2-P5, P2-P6 , P2-P7 , P3-P4 , P3-P5 , P3-P6 , P3-P7，因此它们之间必有园内路径。亭子位置、道路设计未定，可 通过替换的方法，用1个亭子替换问题一中的4个亭子，再用2个亭子替换1个亭子，最后用4个亭子替 换2个亭子，就得到新的亭子位置和最短路径设计。4.1.2模型的求解根据分析，P1-P8、P3-P4之间必有园内的路径，下面不再进行分析。（1）亭子数为1时，设该亭子坐标为T1（x,y）。编写C语言程序（见附录1），令x从0至200， y从0至100变化（每次变化间隔为1），求得T1-P2，T1-P3，T1-P5，T1-P6路径总长最短 的亭子

14、坐标，同时要求满足条件（2）。得到结果为：没有满足条件的T1.（2）亭子数为2时，设亭子坐标为T1（x1,y1）和T2（x2,y2）。用2个亭子替换第一题中的4 个亭子，显然，路径P2-T1-P6和P3-T2-P5都应该向中心凹，如图形状：T1, T2限制在P6和P3之间，因此xl, x2应限制在35,160,y1,y2限制在0,100之间。 假设T1在T2左侧，编写C语言程序(见附录2)，令x1, x2从35至到 160变化，y1，y2 从0至至100变化(每次变化间隔为1)，求得T1-P2, T2-P3, T2-P5, T1-P6,T1-T2路径总 长最短的T1，T2坐标，同时要求满足条件

15、(2)。得到坐标T1 (66,55),T2(107,63)。如图:12(107, 63)T1 (66,55)用新的4个亭子替换上面的2个亭子，假设这4个新亭子为T1(x1,y1 ),T2(x2,y2),T3(x3,y3),T4(x4,y4)，且在图中为顺时针排序。显然，新的 T1 在 T1-P6（此处T1为上面2个亭子时的T1 ）路径附近，新的T2在T2-P5 （此处T2为上面2个亭子 时的T2）路径附近，新的T3在T2-P3 （此处T2为上面2个亭子时的T2）路径附近，新的 T4在T1-P2 （此处T1为上面2个亭子时的T1）路径附近。于是有x1,y1,x2,y2,x3,y3,x4,y4 的

16、移动范围为：35Wx1W66,55Wy1W100;107Wx2W120,63Wy2W100;107Wx3W160,0Wy3W63;50Wx4W66,0Wy4W55;因此可编写C语言程序（附录3）,令x1,y1,x2,y2,x3,y3,x4,y4在相应范围变化（每次变 化间隔为 1）求得 T1-P6, T2-P5, T3-P3, T4-P2, T1-T2, T2-T3, T3-T4, T4-T1 路径总长 最短的T1, T2, T3, T4坐标，同时要求满足条件（2）。得到坐标T1 （45, 80） ,T2 （115,85）, T3 （120,32），T4 （55,40），此时园内路径总长为26

17、6.176。应认识到，这是没算上P1-P8、 P3-P4路径的，加上它们后得到路径总长为372.652.最短路径设计如图所示：0204060801001201401601802005.评价本题是一个道路设计最优化问题，讨论如何设计道路使矩形公园内道路总路程最短。且满足条件:（1）第一问中，公园的所有入口和亭子都连通，并且用4个亭子作为道路的交叉点；（2）任意两个入口之间的最短道路长度不大于两点连线的1.4倍。第一问要求设计道路最短方案，先不考虑环路问题，构造最小生成树，再用贪婪算法，对不满足条件 的路径进行替换，使新路径满足条件。得到最后的最短路设计方案。第二问要求对任意位置的四个亭子，找出新

18、的最短路径设计方案，可利用第一问方案，用1个亭子替换原来的4个亭子，再有2个亭子替换1个亭子，最后用新的4个亭子替换2个亭子。相对于整体考虑，先忽略部分问题进行求解，再把被忽略的问题考虑进去，修正方案，以及先用少量 替换多量，再进行替换，都更为简便。但是通过编写C语言程序来进行计算，编写有些复杂。6.附录附录1：亭子数为1时求T1坐标的C语言源程序#include#includevoid main() int m,n,x,y,t=0;/(m, n)为移动中的T1坐标，(x,y)为T1的最终确定坐标，t用来确定是否存在满足条件 的T1；double s2,s3,s5,s6,s,l=1000;/s

19、2,s3,s5,s6为T1到P2,P3,P5,P6的最短路径,s为移动中他们的和,l为最终确定时他们的和for(n=0;n=100;n+)for(m=0;m=200;m+);s2=sqrt(m-50)*(m-50)+n*n);s3=sqrt(m-160)*(m-160)+n*n);s5=sqrt(m-120)*(m-120)+(100-n)*(100-n);s6=sqrt(m-35)*(m-35)+(100-n)*(100-n);if(50+s2+s5=198)&(50+s2+s6=142)&(s2+s5=171)&(s2+s6=142)&(s2+s6+25=151)&(s3+s5=151)&

20、(s3+s6=224)&(s3+s6+25=252)/ 如果满足条件(2)则继续执行s=s2+s3+s5+s6;if(sl)l=s;x=m;y=n;t=1;if(t=1)printf(x=%d,y=%d,l=%lfn”,x,y,l);elseprintf（没有满足条件的T1n）;附录2：亭子数为2时求T1, T2坐标的C语言源程序#include#includevoid main() int m,n,p,q,x1,y1,x2,y2,t=0;/(m,n),(p,q)为移动中 T1，T2 的坐标，(x1,y1)(x2,y2)为最终确定的 T1，T2坐标，t用来确定是否存在满足条件的T1，T2dou

21、ble s2,s3,s5,s6,s12,s,l=1000;/s2,s3,s5,s6,分别是 T1-P2, T2-P3, T2-P5, T1-P6 的路径长度，s 是移动中 他们的和，l是最终确定的他们的和for(m=35;m=160;m+)for(n=0;n=100;n+)for(p=35;p=160;p+)for(q=0;q=100;q+) s2=sqrt(m-50)*(m-50)+n*n);s3=sqrt(p-160)*(p-160)+q*q);s5=sqrt(p-120)*(p-120)+(100-q)*(100-q);s6=sqrt(m-35)*(m-35)+(100-n)*(100-

22、n);s12=sqrt(m-p)*(m-p)+(n-q)*(n-q);if(30+s2+s12+s5=198)&(30+s2+s6=142)&(s2+s12+s5=171)&(s2+s6=142)&(s2+s6+25=151 )&(s3+s5=151)&(s3+s12+s6=224)&(s3+s12+s6+25=252) s=s2+s3+s5+s6+s12;if(sl)l=s;x1=m;y1=n;x2=p;y2=q;t=1;if(t=1)printf(x1=%d,y1=%dnx2=%d,y2=%dnl=%lfn”,x1,y1,x2,y2,l);elseprintf(没有符合条件的T1，T2n);附录3：亭子数为4时求T1，T2, T3, T4坐标的C语言源程序#include#includevoid main() int a,b,c,d,e,f,g,h,x1,y1,x2,y2,x3,y3,x4,y4,t=0;/(a,b)(c,d)(e,f)(g,h)为移动中 T1 , T2, T3 , T4 坐标， (x1,y1)(x2,y2)(x3,y3)(x4,y4)为最后确定的T1, T2, T3, T4坐标，t用来确定是否存在满足条件的点T1, T2，T3，T4double s2,s3,