西工大数模竞赛B题公园道路设计论文答案

装订线“工大出版社杯”第十三届西北工业大学数学建模竞赛暨全国大学生数学建模竞赛选拔赛题目B题密封号2012年5月2日剪切线密封号2012年5月2日理学院第182队队员1队员2队员3姓名杜雅丽贾天一潘琦明班级110210021102100211021002装订线公园内新修道路路径设计问题摘要本题讨论的是公园内道路设计最优化问题，即在公园的任意两个入口之间的最短道路不大于两点连线的1.4倍的前提下，使得新修路的总路程最短，并绘出相应的道路设计图。由于公园的四周默认存在已经修好的路，因此先利用公园四周的路找出不满足题意条件的路径，以这些路径为主要研究对象，根据题目的具体条件找出最优建设路径。对于4个交叉点已经确定的问题，先将包括入口在内的12个点构成完全图，根据完全图的邻接矩阵，用Kruskal算法，生成最小生成树。再在此基础上，利用Floyd算法，将不符合条件的路径进行删除或替换，并依据总路程最短的原则，找出最优解。根据逐步逼近的算法，可求得优化后所得的最后结果，即是新修路总长为394.5米。在最后的模型讨论中，通过进一步假设，可求得进一步最优解为351.9米。针对可以任意修建道路的情形，本文从0开始逐步增加公园内部交叉点的数目，发现至少有2个交叉点才能满足题中所给前提条件。本文先找出2个交叉点（）情况下的最优解，修路总长为375.3米。通过添加交叉点来对它进行优化，得到3个交叉点时的最优解为361.6米。最后，通过交替迭代优化算法，控制一部分点，改变其他点的位置，找出最终最优解为327.5米。对于有湖存在的问题，根据假设，湖边的道路距离不计入新修建道路的总长，因此在第二问的基础上，利用湖边的道路对道路修建方案进行进一步优化，再次利用交替迭代优化算法，逐步求解得到最终结果297.68米。关键词：交替迭代优化法Kruskal局部优化贪婪算法Floyd算法目录TOC\o"1-3"\h\u一、问题重述1二、问题分析 1三、符号说明与模型假设 23.1符号说明 23.2模型假设 3四、模型的建立与求解 34.1问题一的模型与解答 34.1.1模型的建立 34.1.2模型的求解 34.2问题二的模型与解答 64.2.1模型的建立 64.2.2模型的求解 74.3问题三的模型与解答 124.3.1模型的建立 124.3.2模型的求解 12五、模型的扩展和讨论 14六、模型评价 15七、参考文献 16八、程序附录 168.1附录1求最小生成树的克鲁斯卡尔算法 168.2附录2求解问题二两个交叉点的源程序 188.3附录3问题二交替迭代求最优解的源程序 218.4附录4求解问题三的源程序 23一、问题重述现在要修建一个有8个入口的公园，即确定公园入口与园内交叉点的适当连线，使得公园的任意两个入口相连，但需满足道路总长度和最小，而且任意的两个入口之间的最短道路长不大于两点连线的1.4倍。同时公园四周的边上存在已经建好的道路，且不计入道路总长。我们将主要设计对象假设为一个长200米，宽100米的矩形公园。我们要做的有以下三项工作：1、假定公园内确定要使用4个道路交叉点为：A(50,75)，B(40,40)，C(120,40)，D(115,70）。问如何设计道路可使公园内道路的总路程最短。建立模型并给出算法。画出道路设计，计算新修路的总路程。2、现在公园内可以任意修建道路，如何在满足条件下使总路程最少。建立模型并给出算法。给出道路交叉点的坐标，画出道路设计，计算新修路的总路程。3、若公园内有一条矩形的湖，新修的道路不能通过，但可以到达湖四周的边，以此为前提，重复完成上一问题中的任务。二、问题分析本题是一个道路设计的最优化的问题，即是如何设计路径使公园内部新修路总长最小，但要满足以下两个控制条件：任两个入口连通；任两个入口的最短路径不超过其直线距离的1.4倍。由于题设中说明公园四周存在修好的道路且允许通行，我们先利用四周道路，找出经过这些道路不能满足条件的路径，通过计算我们得出，，，，，，，，，这10条边不满足题意条件，在后续的问题中我们可将其作为主要条件，主要考虑这些路径，不考虑其他路径，这样就可以使问题简化，然后根据各个问题的具体要求，进行求解。三、符号说明与模型假设3.1符号说明，公园的8个入口；，公园8个入口及内部所设的m=n-8个交叉点依次编号。m，公园内交叉点数目；，公园内部修建道路总长。条件，控制条件，即任两入口之间的最短路径不大于其直线距离的1.4倍；条件，控制条件，即公园中新修路的总路程最短。D=，图中第i个和第j个点之间的直线距离。为控制矩阵，即为了保证设计路线中两入口间最短路径长度小于其直线距离1.4倍。S=，S为最短路径矩阵，元素表示在设计路径中第i和第j个点间（n个入口点）最短路径。，引入0-1矩阵；其中。是表征图中n个点之间关系的邻接矩阵，借助距离矩阵,有。3.2模型假设1、假设所有点间道路均修建为直线；2、交叉点的修建不影响道路总长；3、对于第三问，假设湖的四周已有修建好的道路，且不计入新修建道路的总长。四、模型的建立与求解4.1问题一的模型与解答4.1.1模型的建立已确定有4个交叉点要使用，可构造一个点集。现在需要建立连通网，其中网的顶点表示8个入口点及4个交叉点，边表示两点之间的连线，赋予边的权值表示相应的直线距离。由于在此实际问题中，允许有连通分量，即环路的存在，因此我们不能直接通过构造最小生成树来求解最小路径。但鉴于直接求解最优解算法的复杂性，我们引用了一种直观快捷的问题求解方法：贪婪算法。根据贪婪算法，我们将问题的求解分为3步：首先不考虑网中环路的存在，构造最小生成树；再利用Floyd算法计算出任意两点之间的最短路径，做出最短路径矩阵，检验是否满足条件，若不满足，继续寻找；若满足，执行下一步。最后进行边的删除和替换（此时可以有环路的存在），使得任意点间最短路径满足不超过直线距离1.4倍的要求。根据实际问题的要求，网中可以删除和替换的边并不多，因此利用穷举法可以逐步逼近得到最优解.4.1.2模型的求解现有，表示入口与交叉点构成的点集，坐标分别为接下来我们分3步对此模型进行求解：1）利用MATLAB，根据克鲁斯卡尔（Kruskal）算法，我们求得了最小生成树（程序见附录），为了直观的显示，我们做出如下反应网中各点是否有道路连接的X矩阵（0-1）矩阵，其中0表示对应两点之间没有连线，1则表示两点之间有连线；；同时利用MATLAB绘出如下可能的道路设计图：图4-1对应最小生成树的可能道路设计图针对上面在假设无环路存在条件下得出的道路设计图，用Floyd算法进行了如下检验：先计算出已有条件下8个入口最短路径矩阵如下：并与事先已求得的控制矩作比较，发现部分入口间最短路径不满足条件，如下表中突出显示数据（由于这是一个无向图，因此下三角数据不予列出）：A1A2A3A4A5A6A7A8A103014023024015513055A2011020027018516075A3090220295270185A40130215140275A5085110195A6025110A7085A80表4-1最小生成树对应最短路径不满足条件的路径由于墙的存在，入口间路径长度已经满足条件。而且涉及到的路径中可替换的边是有限的，因此利用穷举法，我们进一步求出了满足条件的近似最优解，对应道路设计图如下：图4-24个交叉点的最优道路设计图4.2问题二的模型与解答4.2.1模型的建立由于在公园里可以任意修建道路，但仍需满足条件及条件，因此，我们需要对用到的交叉点的个数、位置这两个因素进行依次讨论，确定应修建交叉点的数目m，以及它们的坐标。我们依次令m=0、1、2、3，分别进行讨论。当交叉点数目较多，即m>=2时，求解全局最优解时，考虑到问题的复杂性，通过控制局部变量，我们将求解若干部分的局部最优解交替进行来逼近全局最优解。4.2.2模型的求解m=0时实现8个入口的连通，我们仅能依赖四周的围墙。根据我们计算出的两点之间最短路径，与控制矩阵比较后，不符合条件的数据如下表显示：P1P2P3P4P5P6P7P8P10.030.0259.8323.8203.2136.8161.832.0P20.0229.8293.8173.2106.8131.862.0P30.064.0117.4181.3206.3291.8P40.0181.4245.4270.4355.9P50.0124.8149.8235.3P60.025.0168.8P70.0193.8P80.0表4-2不添加交叉点时公园各入口的最短距离与1.4倍距离比较结果因此必须通过添加交叉点才能使得新修道路满足条件.m=1时仅可在公园内建立一个交叉点。根据条件，我们可绘出椭圆来寻找交点的可能存在区域。分别以入口、和、为椭圆的焦点，以1.4倍焦距作为长半轴，绘出如下椭圆。根据椭圆的性质易知，左边灰色区域是使、最短路径满足条件的交叉点可能存在区域，右边灰色区域是使、最短路径满足条件的交叉点可能存在区域，图形如下：图4-3绘出的椭圆但它们并无交集，故易知，一个交叉点的情况也不能满足条件，因此仍须继续添加交叉点。m=2时为了使问题简化，求解方便，我们先假设路径以及存在，然后考虑点集。在确定有2个交叉点的情况下，设为和，我们用C++语言编程，采用逐步逼近及穷举的方法，寻找到了使得路径之和满足条件的两点,坐标为，最短路径。下面是对C++编程思想的简单介绍（具体程序见附录2）：建立4个for循环，分别以作为循环变量，以5为单位进行变化；先让N的纵坐标由100减到0,找到的最佳位置，再依次让N的横坐标由200减到0，M的纵坐标由0加到100，M的横坐标由0加到200，找到两点，此时最短路径；采用逐步逼近的方法，以上面已求得的点为基础，缩小寻找范围。以1为单位进行坐标加减，让N的纵坐标由55加到65,找到的最佳位置，再依次让N的横坐标由100加到110，M的纵坐标由50加到60，M的横坐标由60加到70，找到两点，此时最短路径；考虑到这是一个实际问题，再缩小寻找范围，对的长度的影响幅度在米以内，故不再继续寻找，因此求得的两个交叉点时坐标为，作为最后结果。得到道路设计图如下：图4-42个交叉点时的最优道路设计图m=3时我们在原来2个点的基础上进行局部优化，我们的优化分为两步：A)、由图3中M和N点的位置，我们发现，，均要经过路径，因此我们要对和两条路径在满足条件的前提下，进行继续优化，用了与求解2个交叉点时相同的C++编程思想，求得了点。第一步优化后的道路设计图如下：图4-53个交叉点时第一步优化后的道路设计图B）、在固定点的情况下，继续运用上面求解2个交叉点时逐步逼近的C++编程思想，重新对点进行优化,先将优化算法的控制条件写成表达式如下：记上一步中的、、、、的距离之和为,求得最后三点最优位置为,最短距离。并用Floyd算法进行检验，满足条件。绘出最优道路设计图如下：图4-63个交叉点时第二步优化的道路设计图P1P2P3P4P5P6P7P8P10.0-12.0-56.0-31.5-28.2-0.01-10.7-12.8P2-12.00.0-44.0-21.4-34.5-49.4-33.7-3.3P3-56.0-44.00.0-15.8-27.8-30.5-33.8-41.7P4-31.5-21.4-15.80.0-2.1-26.4-135.1-7.2P5-28.2-34.5-27.8-2.10.0-34.0-44.0-3.1P6-0.01-49.5-30.5-26.4-34.00.0-10.0-5.9P7-10.7-33.7-33.8-135.1-44.0-10.00.0-20.9P8-12.8-3.3-41.7-7.2-3.1-5.9-20.90.0表4-3上图设计方案的（满足条件）从上表中我们可以看到其每个元素都是小于0，即满足题意条件。4.3问题三的模型与解答4.3.1模型的建立现在由于公园内有一个矩形的湖，新修的道路不能通过，故需对问题二中的道路设计进行改进来满足新的要求。我们选择对上一问题中存在两个交叉点的道路设计方案进行改进。由于湖的边可以利用且不计入道路总长度，因此将图4-4中路径和进行优化，如图，当矩形湖的边、、存在交点时可使新修建总路程优化最短。设存在点、、，现需解决的问题是求得此3点的最优位置，并求得最优距离。4.3.2模型的求解我们仍将优化的过程分为两步：利用条件作为限制条件，条件作为控制条件，通过在湖的三条边上不断变化位置，我们可以找到交点、、的最优位置，坐标分别为。求得总路程=304.684，得到优化后图形如下：图4-7第三题时第一步优化的道路设计图现在进行进一步的优化，保持交点、、不动，改变点的位置，利用解决问题二时确定两个交叉点时的算法思想，最后得到结果新修建总路程=297.68米。图4-8第三题第二步优化的道路设计图P1P2P3P4P5P6P7P8P10.00-12.00-56.00-31.54-23.93-0.02-10.70-12.81P2-12.000.00-44.00-21.36-26.83-30.02-14.24-3.26P3-56.00-44.000.00-0.05-18.86-16.01-19.29-41.72P4-31.54-21.36-0.050.00-2.08-26.37-135.1-7.18P5-23.93-26.83-18.86-2.080.00-34.00-44.00-3.11P6-0.02-30.02-16.01-26.37-34.000.00-10.00-5.87P7-10.70-14.24-19.29-135.1-44.00-10.000.00-20.93P8-12.81-3.26-41.72-7.18-3.11-5.87-20.930.00表4-4上图设计方案的矩阵后的结果五、模型的扩展和讨论由于问题一中确定使用四个交叉点，在第一次的求解中，我们考虑了只存在四个点的情况，现在根据问题二及问题三的加点优化模型，对问题一附近的区域用条件进行限制，找出满足条件的最优解。具体通过C语言编程实现。加入的点的坐标为E（115，95）F（158,22）.最优距离为351.895.图5-1对第一题进一步优化的道路设计图P1P2P3P4P5P6P7P8P10.00-12.00-56.00-31.54-15.28-4.7821.09-12.81P2-12.000.00-44.00-21.36-18.18-34.78-19.00-3.26P3-56.00-44.000.00-15.79-24.16-12.49-15.77-41.72P4-31.54-21.36-15.790.00-2.08-26.37-135.1-7.18P5-15.28-18.18-24.16-2.080.00-34.00-44.00-3.11P6-4.78-34.78-12.49-26.37-34.000.00-10.00-5.87P721.09-19.00-15.77-135.1-44.00-10.000.00-20.93P8-12.81-3.26-41.72-7.18-3.11-5.87-20.930.00表5-1上图设计方案的矩阵比较结果六、模型评价本文是在任意的两个入口之间的最短道路长不大于两点连线的1.4倍的前提下，考虑总的道路长度和最小。建立了一个逐步逼近最优解的模型，通过计算机编程穷举其所有可能的点来实现的。6.1模型优点相对于整体考虑问题所带来的难度来说，进行局部之间的交替优化可简化问题。充分利用了公园四周的边，使得总的道路长度最小。对于第一题，我们在已经得到结果的基础上，进一步通过对局部的计算，得到更优解。6.2模型不足对局部的点进行交替来求最优解，虽然简化了问题的难度，但是计算量庞大，使用C语言编程过于繁杂，增加了劳动量。局部最优化处理只能无限逼近全局的最优解，但无法证明我们所得结果是最优解。七、参考文献[1]姜启源、谢金星、叶俊.数学模型[M]（第三版）.北京：高等教育出版社，2003.8.[2]赵静、但琦.数学建模与数学实验（第三版）.北京：高等教育出版社，2008.1.[3]孙蓬.MATLAB基础教程.北京：清华大学出版社，2011.10.[4]严蔚敏、吴伟民.数据结构（C语言版）.北京：清华大学出版社，2009.7.八、程序附录8.1附录1求最小生成树的克鲁斯卡尔算法functionE=Kruskal(w)%图论最小生成树Kruskal避圈算法(使用时根据题目修改w和n)%w为邻接矩阵w=xlsread('distance.xls')[m,n]=size(w);k=1;fori=1:n-1forj=i+1:nifw(i,j)~=0x(1,k)=w(i,j);%记录边x(2,k)=i;%记录起点x(3,k)=j;%记录终点k=k+1;endendendk=k-1;%统计边数k为边数%步骤一%冒泡法给边的大小排序fori=1:kforj=i+1:kifx(1,i)>x(1,j)a=x(1,i);x(1,i)=x(1,j);x(1,j)=a;a=x(2,i);x(2,i)=x(2,j);x(2,j)=a;a=x(3,i);x(3,i)=x(3,j);x(3,j)=a;endendend%给各点标号赋初值fori=1:nl(i)=i;end%初始时选e1加入集合EE(1,1)=x(1,1);%E矩阵的第一行记录最小生成树的边长E(2,1)=x(2,1);%E矩阵的第二行记录边的起点E(3,1)=x(3,1);%E矩阵的第三行记录边的终点a=min([l(E(2,1)),l(E(3,1))]);l(E(2,1))=a;l(E(3,1))=a;b=1;%记录E中边数fori=2:k%步骤四ifb==n-1%如果树中边数达到n-1break%算法终止end%步骤二ifl(x(2,i))~=l(x(3,i))%如果两顶点标号不同b=b+1;%将这条边加入EE(1,b)=x(1,i);E(2,b)=x(2,i);E(3,b)=x(3,i);%步骤三forj=1:n%对于所有顶点ifl(j)==max([l(E(2,b)),l(E(3,b))])%如果该顶点的标号,等于=,新加入边中的顶点标号较大的值l(j)=min([l(E(2,b)),l(E(3,b))]);%将其改为较小的那一个以避圈endendendEndE8.2附录2求解问题二两个交叉点的源程序求解问题二中两个交叉点时点最优位置的C++源程序：#include<iostream>//两个交叉点#include<cmath>usingnamespacestd;intmain(){ doubleA[6][2],D[2][6]; A[0][0]=20; A[0][1]=0; A[1][0]=50; A[1][1]=0; A[2][0]=160; A[2][1]=0; A[3][0]=120; A[3][1]=100; A[4][0]=35; A[4][1]=100; A[5][0]=10; A[5][1]=100; doubleB[2][2],B0[2][2]; doubled15,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; B[0][0]=65; B[0][1]=55; B[1][0]=105; B[1][1]=60; doublek1,k2,k3,k4; doubles0=500,s=0; doublem;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) { D[0][1]=sqrt((B[0][0]+k1-A[1][0])*(B[0][0]+k1-A[1][0])+(B[0][1]+k2-A[1][1])*(B[0][1]+k2-A[1][1])); D[0][0]=D[0][1]+30; D[0][2]=sqrt((B[0][0]+k1-A[2][0])*(B[0][0]+k1-A[2][0])+(B[0][1]+k2-A[2][1])*(B[0][1]+k2-A[2][1])); D[0][3]=sqrt((B[0][0]+k1-A[3][0])*(B[0][0]+k1-A[3][0])+(B[0][1]+k2-A[3][1])*(B[0][1]+k2-A[3][1])); D[0][4]=sqrt((B[0][0]+k1-A[4][0])*(B[0][0]+k1-A[4][0])+(B[0][1]+k2-A[4][1])*(B[0][1]+k2-A[4][1])); D[0][5]=D[0][4]+25; D[1][1]=sqrt((B[1][0]+k3-A[1][0])*(B[1][0]+k3-A[1][0])+(B[1][1]+k4-A[1][1])*(B[1][1]+k4-A[1][1])); D[1][0]=D[1][1]+30; D[1][2]=sqrt((B[1][0]+k3-A[2][0])*(B[1][0]+k3-A[2][0])+(B[1][1]+k4-A[2][1])*(B[1][1]+k4-A[2][1])); D[1][3]=sqrt((B[1][0]+k3-A[3][0])*(B[1][0]+k3-A[3][0])+(B[1][1]+k4-A[3][1])*(B[1][1]+k4-A[3][1])); D[1][4]=sqrt((B[1][0]+k3-A[4][0])*(B[1][0]+k3-A[4][0])+(B[1][1]+k4-A[4][1])*(B[1][1]+k4-A[4][1])); D[1][5]=D[1][4]+25;m=sqrt((B[0][0]+k1-B[1][0]-k3)*(B[0][0]+k1-B[1][0]-k3)+(B[0][1]+k2-B[1][1]-k4)*(B[0][1]+k2-B[1][1]-k4)); d15=D[0][0]+D[1][3]+m; d16=D[0][0]+D[0][4]; d25=D[0][1]+D[1][3]+m; d26=D[0][1]+D[0][4]; d27=D[0][1]+D[0][5]; d35=D[1][2]+D[1][3]; d36=D[1][2]+D[0][4]+m; d37=D[1][2]+D[0][5]+m; if(d15<=1.4*d015) if(d16<=1.4*d016) if(d25<=1.4*d025) if(d26<=1.4*d026) if(d27<=1.4*d027) if(d35<=1.4*d035) if(d36<=1.4*d036) if(d37<=1.4*d037) { s=d26+d35+m; if(s<s0) { s0=s; B0[0][0]=B[0][0]+k1; B0[0][1]=B[0][1]+k2; B0[1][0]=B[1][0]+k3; B0[1][1]=B[1][1]+k4; } } } } } } cout<<B0[0][0]<<","<<B0[0][1]<<endl; cout<<B0[1][0]<<","<<B0[1][1]<<endl;cout<<s0<<endl; return0;}8.3附录3问题二交替迭代求最优解的源程序问题二中交替迭代算法求最优解的源程序：#include<stdio.h>#include<cmath>voidmain(){ doublemx=65,my=58,nx=107,ny=65,mn,m2,m6,n5,no,s0=255.738,ans,s=500;doubleX[2][2]; doubles12=30,s16=101.119,s15=141.421,s25=122.066,s26=101.119,s27=107.703,s36=160.078,s37=180.278,s35=107.703; doublep2x=50,p2y=0,p3x=160,p3y=0,pox=161,poy=30,p5x=120,p5y=100,p6x=35,p6y=100; doublek1,k2,k3,k4;doubleo3=30.017; doublemn0,m20,m60,n50,no0; inti,j; for(k1=-20;k1<=20;k1=k1+0.5) { for(k2=-20;k2<=20;k2=k2+0.5) { for(k3=-20;k3<=20;k3=k3+0.5) { for(k4=-20;k4<=20;k4=k4+0.5) { mn=sqrt((mx+k1-nx-k3)*(mx+k1-nx-k3)+(my+k2-ny-k4)*(my+k2-ny-k4)); m2=sqrt((mx+k1-p2x)*(mx+k1-p2x)+(my+k2-p2y)*(my+k2-p2y)); m6=sqrt((mx+k1-p6x)*(mx+k1-p6x)+(my+k2-p6y)*(my+k2-p6y)); n5=sqrt((nx+k3-p5x)*(nx+k3-p5x)+(ny+k4-p5y)*(ny+k4-p5y)); no=sqrt((nx+k3-pox)*(nx+k3-pox)+(ny+k4-poy)*(ny+k4-poy)); if(m6+mn+m2+n5+no<s0) { if(m2+mn+n5<1.4*s25) { if(o3+no+mn+m6<1.4*s36) { if(o3+no+mn+m6+25<1.4*s37) { if(m2+m6<1.4*s26) { if(m2+m6+25<1.4*s27) { if(o3+no+n5<1.4*s35) { if(s12+m2+m6<1.4*s16) { if(s12+m2+mn+n5<1.4*s15) { ans=mn+m6+m2+no+n5; if(ans<s) { s=ans; X[0][0]=mx+k1;X[0][1]=my+k2;X[1][0]=nx+k3; X[1][1]=ny+k4; mn0=mn; m20=m2; m60=m6; n50=n5; no0=no; } } } } } } } } } } } } } } printf("最小距离"); printf("%lf\n",s); printf("各个点对应的距离mnm2m6n5no\n"); printf("%lf\n",mn0)