公园内道路最优化设计讨论.doc

公园内道路最优化设计的讨论摘要1本题要解决的是公园内道路设计的最优化问题，就是需要建立一个模型去设计公园内部的道路，要求在满足约束条件的前提下找出总路程长度和最短的最优解，并给出相应的道路设计图。针对问题一，首先不考虑ABCD四个点，假设仅利用公园四周的道路，利用matlab通过floyd算法解出P1,P2,P3P8任两点间的最短路程S，再利用matlab算出P1,P2,P3P8任两点之间的最短距离L，通过比较S与1.4*L，选出不符合题目要求的几组：(P1,P5),(P1,P6),(P1,P8),(P2,P5),(P2,P6),(P2,P7),(P3,P4),(P3,P5),(P3,P6),(P3,P7)。结合图容易看出：(P1,P8)和(P3,P4)可以确定必须要相连，则P8与P4都已经符合要求，只需再考虑其它几个点P1，P2，P3，P5，P6，P7，A，B，C，D，利用kruskal算法求最小生成树，在此基础上进行局部调整优化选择最优解。根据以上算法得到的最优解为394.5米，示意图请参见正文。针对问题二，由于没有限定道路结点，所以根据1.4倍的约束条件联想到利用椭圆的性质（边界上点到两焦点的距离和为定值）来进一步缩小取点范围，这样的简化过程使解决问题的效率大大加快。第一步是以任意两点为焦点，以1.4倍的焦距为长轴长作椭圆，观察椭圆的交集，得到覆盖程度不同的区域；第二步将覆盖程度视为符合要求的中间交叉点的可能位置概率，计算出最大覆盖程度区域的坐标范围；第三步在区域中分阶段划分精度并做出程序计算区域中点到入口点的最短距离，比较后得出最佳点。根据以上算法得到最优解为375.2米，示意图请参见正文。针对问题三，湖的存在即使在问题二上增加一块不可利用的矩形区域，仍然可继续借助问题二的模型，但要重新确定交叉点的范围。此问题中，由于矩形湖在公园右边，通过问题二的分析过程可知，该湖只影响右边的交叉点。所以左边的交叉点位置不必改变，只需确定右边的交叉点即可。并在此基础上利用问题二的模型继续求解。由于时间关系与目前知识水平局限还未能完成问题三的最优解。关键词：Floyd Kruskal 局部优化 Matlab 动态步长 穷举法一、 问题重述 某大学计划建一个形状为矩形或其他不规则图形的公园，不仅为了美化校园环境，也是想为其学生提供更的生活条件。公园计划有若干个入口，现在你需要建立一个模型去设计道路让任意两个入口相连（可以利用公园四周的边，即默认矩形的四条边上存在已经建好的道路，此道路不计入道路总长），使总的道路长度和最小，前提要求是任意的两个入口之间的最短道路长不大于两点连线的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倍假设四: 公园内新修的道路与四周的连接只能与8个路口相通，而不能连到四周的其它点假设五：用穷举法在求解问题二时，用划分的每个小区域的中心对称点的坐标来代表该区域的坐标量，当划分的区域越来越小时，两者就近似相等四、 符号系统P1,P2,P3P8任两点间的最短路程矩阵SP1,P2,P3P8任两点之间的最短距离矩阵L五、 模型建立 问题一：初步简化问题：首先不考虑ABCD四个点，假设仅利用公园四周的道路，利用matlab通过floyd算法解出P1,P2,P3P8任两点间的最短路程S：S= 0 30 140 230 240 155 130 45 30 0 110 200 270 185 160 75 140 110 0 90 220 295 270 185 230 200 90 0 130 215 240 275 240 270 220 130 0 85 110 195 155 185 295 215 85 0 25 110 130 160 270 240 110 25 0 8545 75 185 275 195 110 85 0再利用matlab编程技算出P1,P2,P3P8任两点之间的最短距离L：L= 0 30.0000 140.0000 186.8154 141.4214 101.1187 100.4988 32.0156 30.0000 0 110.0000 158.1139 122.0656 101.1187 107.7033 55.9017 140.0000 110.0000 0 64.0312 107.7033 160.0781 180.2776 161.9413 186.8154 158.1139 64.0312 0 94.3398 172.4094 196.4688 201.5564 141.4214 122.0656 107.7033 94.3398 0 85.0000 110.0000 141.5097 101.1187 101.1187 160.0781 172.4094 85.0000 0 25.0000 82.7647 100.4988 107.7033 180.2776 196.4688 110.0000 25.0000 0 75.6637 32.0156 55.9017 161.9413 201.5564 141.5097 82.7647 75.6637 0S-1.4*L= 0 -12.0000 -56.0000 -31.5416 42.0101 13.4338 -10.6983 0.1781 -12.0000 0 -44.0000 -21.3594 99.1082 43.4338 9.2154 -3.2624 -56.0000 -44.0000 0 0.3563 69.2154 70.8907 17.6114 -41.7179 -31.5416 -21.3594 0.3563 0 -2.0757 -26.3732 -35.0564 -7.1790 42.0101 99.1082 69.2154 -2.0757 0 -34.0000 -44.0000 -3.1136 13.4338 43.4338 70.8907 -26.3732 -34.0000 0 -10.0000 -5.8706 -10.6983 9.2154 17.6114 -35.0564 -44.0000 -10.0000 0 -20.9292 0.1781 -3.2624 -41.7179 -7.1790 -3.1136 -5.8706 -20.9292 0通过比较S与1.4*L，也就是计算S-1.4*L的值：选出不符合题目要求的几组(图中已标记)：(P1,P5),(P1,P6),(P1,P8),(P2,P5),(P2,P6),(P2,P7),(P3,P4),(P3,P5),(P3,P6),(P3,P7)。进一步简化问题：结合图容易看出：(P1,P8)和(P3,P4)可以确定必须要相连，则P8与P4都已经符合要求，只需再考虑其它几个点P1，P2，P3，P5，P6，P7，A，B，C，D即可，如图利用kruskal算法求P1、P2、P3、P5、P6、P7、A、B、C、D总共十个点的最小生成树在此基础上，由于（P1,P5）不满足题目条件，所以进行局部调整优化选择最优解。此时得到问题一的最优解为：L(P1,P8)+L(P2,B)+L(A,B)+L(A,6)+L(A,5)+L(5,D)+L(C,D)+L(C,3)+L(3,4)=394.5米问题二：为简化问题，仍使用问题一中的初始模型，即（P1,P8）（P3,P4）默认相连。由于没有限定道路结点，所以根据1.4倍的约束条件联想到利用椭圆的性质（边界上点到两焦点的距离和为定值）来进一步缩小取点范围，这样的简化过程使解决问题的效率大大加快。第一步是以任意两点为焦点，以1.4倍的焦距为长轴长作椭圆，观察椭圆的交集，得到覆盖程度不同的区域；经过讨论可知：最少需要两个交叉点，可使修建的道路满足题目要求，为简化题目，我们这里只讨论公园内有且只有两个道路交叉点的情况。第二步将覆盖程度视为符合要求的中间交叉点的可能位置概率，计算出最大覆盖程度区域的坐标范围；由几个点的空间分布易知，两个交叉点分别在矩形的左右两侧，且各自作用在各自的区域，不会产生相互影响。第三步在区域中分阶段划分精度并做出程序计算区域中点到入口点的最短距离，比较后得出最佳点。利用c程序分别取不同步长来试探最优解的位置，先用大步长的方法找到最优解的大致位置，再将此位置细分后去较小步长比较最优解，如此循环最终得到一个通过局部优化的近似最优解，如下图：两个交叉点坐标为：E（91,58.554）和F（161,39.4）此时得到问题二的最优解为：L(P1,P8)+L(P2,E)+L(P5,E)+L(P6,E)+L(E,F)+L(F,4)+L(F,3)=375.2米问题三：湖的存在即使在问题二上增加一块不可利用的矩形区域，仍然可继续借助问题二的模型，但要重新确定交叉点的范围。此问题中，由于矩形湖在公园右边，通过问题二的分析过程可知，该湖只影响右边的交叉点。所以左边的交叉点位置不必改变，只需确定右边的交叉点即可。并在此基础上利用问题二的模型继续求解。时间问题就不再展开。六、 模型分析 在问题2的求解过程中，由于时间所限，我们只讨论了包含两个交叉点的最有线路选取和交叉点优化问题，如果添加更多的交叉点，优化目标会得到进一步提高。七、 模型推广我们在本文解决了一个在任意的两个入口之间的最短道路长不大于两点连线的1.4倍的前提下，考虑总的道路长度和最小的最优化问题。是建立了一个逐步逼近最优解的模型，通过计算机编程穷举其简化后的所有可能的值来实现的。模型优点1. 相对于整体考虑问题所带来的难度来说，进行局部之间的交替优化可简化问题。2. 充分利用了公园四周的边，使得总的道路长度最小。3. 对于第一题，我们在已经得到结果的基础上，进一步通过对局部的计算，得到更优解。模型不足1. 在研究问题二时，最好再讨论一下交叉点数为3、4、5或者更多时的情况，从而得出最优解2. 问题三的湖边道路的假设与运用可以更加灵活。八、 结论对于问题一,我们得出的最优解为394.5米对于问题二,我们得出的最优解为375.2米九、 参考文献1 赵静 但琦，数学建模与数学实验（第3版），北京：高等教育出版社，2008.2 张志涌 杨祖樱，MATLAB教程R2011a，北京：北京航空航天大学出版社，2011.3 艾冬梅等，MATLAB与数学实验，北京：机械工程出版社，2011.附录1、P1P8各点之间最短距离矩阵L的matlab程序x=20 50 160 200 120 35 10 0;y=0 0 0 50 100 100 100 25;i=1;j=i:8l1=sqrt(x(i)-x(j).2+(y(i)-y(j).2)i=2l2=sqrt(x(i)-x(j).2+(y(i)-y(j).2)i=3l3=sqrt(x(i)-x(j).2+(y(i)-y(j).2)i=4l4=sqrt(x(i)-x(j).2+(y(i)-y(j).2)i=5l5=sqrt(x(i)-x(j).2+(y(i)-y(j).2)i=6l6=sqrt(x(i)-x(j).2+(y(i)-y(j).2)i=7l7=sqrt(x(i)-x(j).2+(y(i)-y(j).2)i=8l8=sqrt(x(i)-x(j).2+(y(i)-y(j).2)L=l;l2;l3;l4;l5;l6;l7;l82、求任意两点间最短路径的Floyd算法的matlab程序function D=floyd(DO)n,n-size(DO);D=zeros(n);max1=floor(log(2*n-3)/log(2)for k=1:max1 for r=1:n;D1=DO(r,:);D(r,:)=min(repmat(D1,1,n)+DO);endendfor k=1:max1 DT=D;DT(find(DT=inf)=1;DO(find(DO=inf)=1;DO=DO-DT;if sum(DO(:)=0 return;endfor r=1:n;D1=DO(r,:);D(r,:)=min(repmat(D1,1,n)+DO);endDO=D;end3、已知十个点坐标求其赋权邻接矩阵的matlab程序x=20 50 160 120 35 10 50 40 129 115y=0 0 0 100 100 100 75 40 40 70i=1,j=1:10l1=sqrt(x(i)-x(j).2+(y(i)-y(j).2)i=2,j=1:10l2=sqrt(x(i)-x(j).2+(y(i)-y(j).2)i=3,j=1:10l3=sqrt(x(i)-x(j).2+(y(i)-y(j).2)i=4,j=1:10l4=sqrt(x(i)-x(j).2+(y(i)-y(j).2)i=5,j=1:10l5=sqrt(x(i)-x(j).2+(y(i)-y(j).2)i=6,j=1:10l6=sqrt(x(i)-x(j).2+(y(i)-y(j).2)i=7,j=1:10l7=sqrt(x(i)-x(j).2+(y(i)-y(j).2)i=8,j=1:10l8=sqrt(x(i)-x(j).2+(y(i)-y(j).2)i=9,j=1:10l9=sqrt(x(i)-x(j).2+(y(i)-y(j).2)i=10,j=1:10l10=sqrt(x(i)-x(j).2+(y(i)-y(j).2)L=l1;l2;l3;l4;l5;l6;l7;l8;l9;l104、计算最小生成数的Kruskal算法实现程序function Kruskal(w,MAX)%此程序为最小生成树的Kruskal算法实现%w为无向图的距离矩阵%MAX为距离矩阵中无穷大的实际输入值len=length(w); edge=zeros(len*(len-1),3);count=1; for i=1:len-1 for j=i+1:len if w(i,j)=MAX edge(count,1)=w(i,j); edge(count,2)=i; edge(count,3)=j; count=count+1; end endendedge=edge(1:count-1,:); tmp,index=sort(edge(:,1); i=3; while 1 x=findcycle(edge(index(1:i),:),len); if x index(i)=0; else i=i+1; end index=index(index0); if i=len break; endendindex=index(1:len-1); s=sprintf(nt%st%st %st,边端点,距离,是否在最小生成树); for i=1:count-1 edge_tmp=edge(i,:); if isempty(find(index=i,1) s_tmp=sprintf(n t (%d,%d)t %dt %st,edge_tmp(2),edge_tmp(3),edge_tmp(1),); else s_tmp=sprintf(n t (%d,%d)t %dt %st,edge_tmp(2),edge_tmp(3),edge_tmp(1),); end s=strcat(s,s_tmp); enddisp(s);endfunction isfind=findcycle(w,N) %此程序用于判断所给的边能否构成圈：有圈，返回1；否则返回0%w：输入的边距阵%N：原图的点数%原理：不断除去出现次数小于2的端点所在的边，最后观察是否有边留下len=length(w(:,1); index=1:len; while 1 num=length(index); p=zeros(1,N); for i=1:num p(w(index(i),2)=p(w(index(i),2)+1; p(w(index(i),3)=p(w(index(i),3)+1; end index_tmp=zeros(1,num); discard=find(p2); count=0; for i=1:num if (isempty(find(discard=w(index(i),2),1) | isempty(find(discard=w(index(i),3),1) count=count+1; index_tmp(count)=index(i); end end if num=count index=index_tmp(1:count); break; else index=index_tmp(1:count); endend if isempty(index) isfind=0; else isfind=1; endend5、求解问题二中两个交叉点最优位置的C语言源程序：#include#includeint main()double A,D;A=20,0;50,0;160,0;120,100;35,100;10,100;double B,B022;double d15,d015,d16,d016,d25,d025,d26,d026,d27,d027,d35,d035,d36,d036,d37,d037;d015=141.421;d016=101.119;d025=122.066;d026=101.119;d027=107.703;d035=107.703;d036=160.078;d037=180.278;B22=65,55;105,60double k1,k2,k3,k4;double s0=500,s=0;double m; for(k1=-10;k1=10;k1=k1+1)for(k2=-10;k2=10;k2=k2+1)for(k3=-10;k3=10;k3=k3+1)for(k4=-10;k4=10;k4=k4+1) D01=sqrt(B00+k1-A10)*(B00+k1-A10)+(B01+k2-A11)*(B01+k2-A11); D00=D01+30; D02=sqrt(B00+k1-A