数学建模-数模-公园内道路建设问题-最优化-西北工业大学(共19页)

1、精选优质文档-倾情为你奉上装 订 线“工大出版社杯”第十三届西北工业大学数学建模竞赛暨全国大学生数学建模竞赛选拔赛题目A (B)题密封号2012年5月2日剪 切 线密封号2012年5月2日 航空 学院 第 六十七 队队员1队员2队员3姓名陈 静徐晓娟张 鑫班级装 订 线专心-专注-专业摘 要 针对公园道路设计的规划的不同问题，我们分别采用了含约束的prim算法和非线性规划问题进行求解。 针对问题1，我们采用含约束的prim算法生成最短路径，首先生成八个出口和四个交叉点的邻接矩阵，对出口边界距离小于其直线距离1.4倍的出口对应的邻接矩阵元素进行赋0处理以保证最短路径中包含这些边界路径，对于需要通

2、过交叉点连接的出口，我们提出采用椭圆区域的方法对其进行约束，从而用prim算法求得满足约束的最优路径，该最优路径长度为400.86. 针对问题2，我们提出采用两步循环法进行求解，第一步固定交叉点由含约束prim算法求得最优路径，第二步固定路径采用非线性优化求得最优交叉点，如此循环直到前后两次所求最优交叉点位置不再变化则认为是最优路径和最优交叉点。我们采用该方法分别对包含一个和两个交叉点的情形进行求解，求得包含两个交叉点对应的最优路线长度为375.20. 针对问题3，我们在问题2求解的基础上，在prim算法求解最优路径过程中将过湖路径长度赋为无穷大，使路径不过湖区，在非线性优化求解最优交叉点位置

3、中加入线性不等式约束将矩形湖区域剔除出交叉点可行域，求得了不过矩形湖区域的最优路径，该最优路径长度为376.02.关键词：最优路径；椭圆区域约束；非线性优化；prim算法；可行区域; 两步法一问题重述 西安某大学计划建一个形状为矩形或其他不规则图形的公园，不仅为了美化校园环境，也是想为其学生提供更的生活条件。公园计划有若干个入口，如Error! Reference source not found.所示。现在你需要建立一个模型去设计道路让任意两个入口相连（可以利用公园四周的边，即默认矩形的四条边上存在已经建好的道路，此道路不计入道路总长），使总的道路长度和最小，前提要求是任意的两个入口之间的最

4、短道路长不大于两点连线的1.4倍。图 1 公园入口示意图主要设计对象可假设为如图所示的矩形公园，其相关数据为：长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).现完成以下问题：问题一：假定公园内确定要使用4个道路交叉点为：A(50,75)，B(40,40)，C(120,40)，D(115,70）。如Error! Reference source not found.所示。问如何设计道路可使公园内道路的总路程最短。建立模型并给出算法。

5、画出道路设计，计算新修路的总路程。图 2 问题1交叉点示意图问题二：现在公园内可以任意修建道路，如何在满足条件下使总路程最少。建立模型并给出算法。给出道路交叉点的坐标，画出道路设计，计算新修路的总路程。问题三：若公园内有一条矩形的湖，新修的道路不能通过，但可以到达湖四周的边，示意图见。重复完成问题二 的任务。其中矩形的湖为R1(140,70),R2(140,45),R3=(165,45),R4=(165,70)。图 3 问题三矩形湖示意图。注：以上问题中都要求公园内新修的道路与四周的连接只能与8个路口相通，而不能连到四周的其它点。二问题分析 内部道路设计是公园规划中极其重要也必须考虑

6、的环节，它的合理规划既涉及到美化效果，又是一种实用价值的体现。在本题中公园有八个入口，且要求任意两个路口在一定的距离范围内连通（即两个入口之间连通距离不得大于其直线距离的1.4倍），同时总距离又要最小，因此该问题是包含约束的最小生成树问题。问题一：在该问题中，四个交叉点坐标已知。我们需要以这四个交叉点和出口组成的12个点求取最优路径。由于题设中指出公园边界连通可用且不计入总路径长度 ，因此优先选用边界。针对这一问题，我们算出任意两点间距离，并生成邻接矩阵。当两出口的边界路线长度小于连线距离的1.4倍时，可以令这两个出口对应的邻接矩阵元素为0。在该问题中需要加入任意的两个入口之间的最短道路长不大

7、于两点连线的1.4倍这一约束。由椭圆定义可知，椭圆上的点到两个固定点（焦点）距离之和等于定长。因此可以以每两个出口作为焦点且到该两出口距离之和小于等于该两处出口距离1.4倍的点组成的椭圆区域为约束。在进行了这些前处理和添加约束后即可利用prim算法选取最优路径。问题二：在此问题中，交叉点不固定，交叉点个数也不固定。我们依次考虑只有一个交叉点、有两个交叉点以及有更多个交叉点的路线选取问题。我们采用两步法进行求解。以只含一个交叉点的问题进行说明。所谓两步法即第一步生成最小路径，第二步优化交叉点位置。首先我们选取花园中心为交叉点，进行固定，然后求解最短路径，在求得最短路径后，再对位置坐标进行优化，使

8、得总路径最短，然后再进行路径选取，如此循环，直到前后两次选取的最优交叉点位置不再改变。该问题中最优路径的选取仍然采用带椭圆区域约束的prim法。交叉点位置的优化是一个非线性优化问题，同时要保证到它所连接的两出口的距离之和小于两出口距离的1.4倍。因此是一个含非线性约束的非线性优化问题。此问题可以采用经典优化算法进行求解，例如蚁群算法、遗传算法等。本文采用matlab中的fmincon函数进行求解。问题三：在此问题中，交叉点不确定，且存在障碍区，即路线不能通过的区域。这一问题可以再第二问的基础上进行求解，在prim算法选取最优路径时使得最优路径不通过该障碍区即可。具体的做法为在选取候选出口点（或

9、候选路径）时，该路径为候选集到已选集距离最小的点，若该路径经过障碍区，则不选改点，选候选集中距离次小的点，若改点还不满足，则继续该过程。在交叉点位置的优化时也应该使得交叉点避开障碍区，只需要加入约束使得交叉点避开障碍区即可。三模型假设1、假设任意两点或交叉点都是直线相连；2、假设所有点或线都在同一平面内，不考虑台阶影响；3、不考虑道路拐弯处引起的路径增长，即将拐弯处看作一个点。4、假设道路的宽度都相同，且都可以近似看成直线；5、假设题中所给数据或图形都真实可靠。四符号说明符号说明各出口及交叉点横坐标，（9到12分别代表A、B、C和D）各出口及交叉点纵坐标，出口（交叉点）与出口（交叉点）间的直线

10、距离不含边界的总路径交叉点个数间距权值邻接矩阵五模型的建立与求解5.1、问题一模型建立与求解由第一问的问题分析可知，该问题是含约束的最小生成树问题，首先应该算出 算出邻接矩阵，由解析几何可知两点（和）之间的距离为：生成的邻接矩阵为（matlab程序见附录1）：其中对角线元素（）设为无穷大以保证prim算法求解最小生成树时不产生自身到自身的路线。 通过验证，（1,2）、（1,3）、（2,3）、（4,5）、(4,6)、(5,6)、(6,7)、（5,7）和(7,8)这些出口对满足边界距离小于直线距离的1.4倍，因为这些点对若以边界路径相连，则该路径不算入总路径之内，在邻接矩阵中应将这些点对对应的元素

11、设为0，以保证prim算法生成最短路径一定包含这些路径，即令：并令这些元素的对称元素等于0. 在最小生成树中还应保证两个入口之间连通距离不得大于其直线距离的1.4倍，这一条件可以通过添加椭圆约束来实现。由椭圆定义可知，椭圆是到两个定点距离等于定长的点的集合，因此要保证到两个出口（设为和）路径之和小于该两个出口直线距离的1.4倍只需保证该交叉点（设为）满足下式约束： 到此该问题模型建立完毕，即可采用prim算法生成最短路径。Prim算法的基本原理是：给定集合，和，其中用于存放最小生成树中的顶点，集合用于存放最小生成树的边，为剩余顶点的集合。令集合初值为出口1（即从出口1开始构造最小生成树），从所

12、有中元素找出一个到中元素距离最短且满足椭圆约束的一个点放入中，将对应边放入中，如此不断重复，直到包含所有点。其中距离的判断采用邻接矩阵元素进行判断。由该方法求得的最短路径如Error! Reference source not found.所示。其最短距离为：图 4 由带约束prim算法求得问题1最佳路径 5.2、问题二模型建立及求解问题二为在公园内任意修建道路，在满足题设约束条件的前提下使得选取路线的总路程达到最小，并获取交叉坐标及最短路径长度。为了解决这一问题，我队用matlab编程计算任意两点的距离，同时生成邻接矩阵，并在加入约束条件后采用prime算法对路径和交叉点重复迭代不断优化直至

13、获得最短路径。1、交叉点可行性区域分析我们首先对交叉点的选取进行了深入的分析，在路径设计过程中可能产生交叉点，但是由于约束条件的存在，这些交叉点只可能出现在某些特定的区域。在对题设中任意两入口间距不得大于其两者直线距离1.4倍的要求的分析后，我们创造性的利用了椭圆的几何性质并通过相交椭圆间公共区来确定交叉点位置区域，以求相对精确地获得交叉点的可能位置区域，以大量的减少计算量。由数学知识可知，椭圆上任一点到其两个焦点的距离和为定常数。由题设所给的约束条件即公园中任意两入口相互连通且其间距不得大于其两者直线距离的1.4倍，即满足约束条件的点必然存在于以i,j点为焦点，以为长轴的椭圆以内。任意两个入

14、口点即可构成一个椭圆，不同椭圆的重叠区域则就是交叉点可能出现的区域。编程画图得到如下结果如Error! Reference source not found.所示。对得到图形进行分析可知，图中着色区是交叉点最有可能出现的区域，但是交叉点的个数以及具体位置尚不能确定图 5 问题2椭圆约束区示意图（此图坐标轴区域经过放大）2、交叉点及最优路径的讨论 交叉点个数对最短路径的影响未知，所以必须对不同交叉点个数分别进行讨论比较，得出最优解。假设交叉点个数为k，则有附图三的三个交叉区域可知，交叉点落在此三区中是既满足约束又比较优越的选择。而入口八已在M区内，所以此区内没有再存在交叉点的必要，因此k的优越取

15、值可能为0，1或2，即存在于P区或N区.（1）、当k=0时，即非边界路径无交叉，所有方案都不满足两点间路径之和不大于直线距离1.4倍的条件，因此没有合适路径设计。（2）、当k=1时，显然N区严重偏离各入口的重心，若仅在此区存在一个交叉点显然不能满足约束条件，因而唯一的交叉点必然存在于P区。由于题设所给的边界长度不计入路线总长的特殊条件，因此同样优先选择边界路径把尽可能多的入口连通。经过对公园入口图的整体分析，我们可以看出：其中位于同一条边界上的入口均可用直接选取边界为连通路径，即入口1、2、3以及入口5、6、7直接通过边界相通。同时，利用问题一中已求得的任意两点间距离，经简单计算可发现入口7与

16、8以及入口4与5也可通过边界相连通。此外，在满足题设约束条件同时总路线最短的前提下，经分析可得入口1与入口8，入口3与入口4应采用直线连接的方式，即直接采用直线道路分别连接入口1与8以及入口3与4。经过上述的严密分析后，我们可发现，在该公园的所有路口中，仅有入口1-5、入口2-5、2-6以及入口3-5、3-6、3-7间必须通过交叉点连接才可满足距离限制。在3-6满足要求的情况下3-7必然也满足，因此只需将入口点2,3,5,6在P区进行优化获得最优解，显然可见，四点直线连接距离最短，如Error! Reference source not found.所示. 经检验，各点间路径长度均满足题设要求

17、，因此在只有一个交叉点的情况下，此道路设计为路径最短的最优解。计算可得，交叉点坐标为G（89.487，56.41），总路径长度为：G（89.487,56.41）图 6 问题2只包含一个交叉点情形优化结果 （3）、当k=2时，即交叉点同时存在于P区和N区，求解最优路径的方法是先在交叉点的可行区域即P、N区内分别任意给定两点，用prim算法求出最优路线，固定路线后再以坐标为设计变量，以总路径为目标，使总路径最小进行优化，这样可以分别得到两个优化点，再以此确定改点，与八个入口一起按照prime算法寻找最优路径,再优化点，按此方法不断地进行循环迭代直到前后两次循环中的优化点不发生变化为止，此时得到的两

18、个点即为存在于N区P区内的交叉点。此时该问题与问题一类似，先算出两个交叉点及八个入口点共十个点间任意两点间距，并生成邻接矩阵，采用prim算法程序生成最优路径。尽可能地在满足长度约束的情况下，用边界对最小生成树中某些线段进行替换，并对图形做不断的微调以使总路程最短，道路设计如Error! Reference source not found.所示（程序见附录3）。两个交叉点坐标为：F（91,58.554）和E（161,39.4）。路径总长度为：图 7 问题2包含2个交叉点优化结果 经上述计算，对比分别取一个交叉点（k=1）与取两个交叉点(k=2)时所得到的路径总长度可知：取两个交叉点即分别在P

19、区N区同时取交叉点时，得到的路径总长度最短，也即此时的道路设计为满足题设所有约束条件下的最优公园路径设计。类似我们可以讨论包含三个、四个甚至更多交叉点的优化问题，方法类似，由于时间所限，本文不再具体讨论。5.3、问题三模型的建立及求解此问中假设公园中存在一湖求同样满足约束条件，但避开障碍区的路径优化问题。为解决此问题，如果问题二中解出的最短路径不过障碍区则已是最优道路设计，如过障碍区则需要通过求解障碍区域顶点与八个入口及交叉点的直线方程筛选任意两点之间的有效线段。构造有效线段的带权临接矩阵，将无效线段的距离赋值为无穷大1、判断问题二中最优路径是否通过障碍区通过问题二中已解决的最优路径，如附图五

20、所示，可得其中最有可能通过障碍区的路径为EF，通过求解线段EF的解析方程，判断是否与湖的边界相交。 点E、F的坐标分别为：E (161,39.4)和 F (91,58.554)，则可以求得线段EF的解析方程：湖的边界的方程为：联立可求的：路径EF与湖的边界相交于（140,45.146）和（140.344,45）两点。由此可得，问题二中解得的最优路径并不适用本问题。所以，我们采用了首先筛选出不过障碍区的有效线段，再进行优化设计的方案。2、筛选各点之间的有效线段。将两个交叉点与八个入口任意之间用线段连接，如果任意两个点之间的线段通过障碍区域之内，则为无效线段，作剔除处理，筛选出有效线段。求解所有障

21、碍物的所有边界线段与任意两个可行点连接线段是否相交，若两可行点连接线段与任一条障碍物边界线段相交，则这两个可行点必不能直接相连，其间距赋为无穷大。如果任意两个点的坐标分别为𝐴、𝐵，同一障碍区任意两个顶点坐标为Ri、Rj。则两直线方程分别为：和求解以上方程，设解为，若满足：且：则说明是有效线段。临接矩阵的权值为其中, 为任意两可行点的坐标。由此可得到所有可行点的邻接矩阵𝐵。 在prim算法选取候选点和路径时按照上述方法进行判断即可。接下来还应保证交叉点的优化中使得交叉点不落入矩形湖区域。由上述分析可知，交叉点的确定是一个非线性优化问题，其中“两出口

22、的最短距离不大于直线距离的1.4倍”这一条件通过引入椭圆区域进行约束，在此基础上若要保证交叉点不落入矩形湖区域，只需要在约束中加入线性不等式约束，将矩形湖区域剔除出可行解区域即可。3、最短路径选取在获取有效线段的邻接矩阵后，则该问题与问题二大致相同。首先确定出交叉点的有效区域，然后在有效区域内分别任意给定两点，用prim算法求出最优路线，固定路线后再以坐标为设计变量，以总路径为目标，使总路径最小进行优化，这样可以分别得到两个优化点，再以此确定改点，与八个入口一起按照prim算法寻找最优路径,再优化点，按此方法不断地进行循环迭代直到前后两次循环中的优化点不发生变化为止。对已获得的交叉点，通过ma

23、tlab编程用最小生成树法获得最优路径。通过对题设约束条件的检验，对获取的路线进行微调以获取最优路线设计。最终，得到了如Error! Reference source not found.所示的公园避开障碍区的最佳道路设计方案。K（158,39）H（91,58.554）图 8 问题三包含两个交叉点优化结果其中交叉点的坐标：H（91,58.554）, K（158,39），因此最短路径为：同时，在解决问题二时，我们已经讨论过了只有一个交叉点的情况，此时的最优路线同样不过障碍区，但其道路总长为：378.2。与有两个交叉点且避开障碍区的Error! Reference source not found

24、.方案比较，略有不足。因此，在避开障碍区以及满足所有约束条件的情况下，附图六的方案为最优方案。与问题2的解决方案类似，在本问题中我们只考虑了包含一个交叉点和两个交叉点的情形，如果引入更多交叉点这一结果还会进一步得到优化，含更多交叉点的路径和交叉点优化方法类似，由于时间有限，在本文中我们不再赘述。六模型优缺点分析6.1、模型优点 针对问题一，我们采用prim算法生成最短路径，题目中要求两个出口最短路径不大于其直线路径的1.4倍，针对这一问题，我们首先对出口点之间距离小于其直线1.4倍的对应的邻接矩阵元素赋0，使得prim算法生成最短路径时必选这些点；其次我们创造性的引入椭圆区域约束，保证经过交叉

25、点相连的两个出口的最短距离满足小于直线距离的1.4倍的要求。 针对问题2，我们创造性的提出两步法，第一步进行最优路径选取，第二步进行交叉点坐标优化，如此循环，直到前后两次优化的交叉点坐标不再改变。该方法简单易行，原理清晰易懂。在本文中，由于时间所限，我们只讨论了包含一个和两个交叉点的优化问题，该方法可以类似的推广到包含更多交叉点的问题求解中。 针对问题3，在问题2求解的基础上，我们首先巧妙地对prim算法进行改进，保证所选路径不经过矩形湖区域，其次在交叉点的优化过程中引入线性不等式约束，巧妙地将矩形湖区域剔除出交叉点可行解区域。 6.2、模型缺点： 在问题2的求解过程中，由于时间所限，我们只讨

26、论了包含两个交叉点的最有线路选取和交叉点优化问题，如果添加更多的交叉点，优化目标会得到进一步提高。在问题三使得最优路径避开矩形湖区域求解中我们同样只讨论了包含一个交叉点和两个交叉点的问题，但是求解方法可以类似的推广到包含更多交叉点的情形。七参考文献1 matlab宝典.电子工业出版社2 薛定宇，陈阳泉.高等应用数学问题的Matlab求解.清华大学出版社,20083 数学建模方法及其应用.高等教育出版社4 杨洪，图论常用算法选编，北京：中国铁道出版社，19885 赵静，等，数学建模与数学实验，北京：高等教育出版社，20006 Bela Bollobas. Modern graph theory,

27、 New York: Spring7 唐策善，等。数据结构-用C语言描述，北京：高等教育出版社八附录附录1：生成邻接矩阵matlab程序%生成邻接矩阵clearx=20 50 160 200 120 35 10 0 50 40 120 115;y=0 0 0 50 100 100 100 25 75 40 40 70;for i=1:12 for j=1:12 if i=j S(i,j)=sqrt(x(i)-x(j)2+(y(i)-y(j)2); end endenddisp('邻接矩阵为：')disp(S);附录2：prim算法程序clearx=20 50 160 200 1

28、20 35 10 0 50 40 120 115;y=0 0 0 50 100 100 100 25 75 40 40 70; A=zeros(12); for i=1:12 for j=1:12 A(i,j)=sqrt(x(i)-x(j)2+(y(i)-y(j)2); end; end; A(A=0)=inf; B=A;for i=1:8 for j=1:8 if abs(x(i)-x(j)+abs(y(i)-y(j)<=A(i,j) A(i,j)=0; end endend result=;p=1;tb=2:length(A); while length(result)=length

29、(A)-1 temp=A(p,tb); temp=temp(:); d=min(temp); jb,kb=find(A(p,tb)=d); j=p(jb(1); k=tb(kb(1); result=result,j;k;d; p=p,k; tb(tb=k)=;endplot(x,y,'o')hold;for i=1:11 b=result(1:2,i)' plot(x(b),y(b),'-k')enddistance=sum(result(3,result(1,:)>=8|result(2,:)>=8)附录3：问题2包含两个交叉点的最短路线

30、选取和交叉点位置优化程序clearx1=100;y1=50; x0=90;y0=60;x=20 50 160 200 120 35 10 0 x0;y=0 0 0 50 100 100 100 25 y0;p=0;while 1 if x0=x1&&y0=y1 break; end x0=x1;y0=y1; result=prim1(x0,y0); j=1; for i=1:length(result) if result(1,i)=9 link(j)=result(2,i); j=j+1; elseif result(2,i)=9 link(j)=result(1,i); j

31、=j+1; end end n=length(link); distance9=(P,x,y,link)sum(sqrt(x(link)-P(1).2+(y(link)-P(2).2);% options=optimset('LargeScale','off','display','iter'); % s = fmincon(P) distance9(P,x,y,link),x0,y0,0 0,200 100,(P) myconstrain(P,x,y),options); s = fmincon(P) distance9(P,x

32、,y,link),x0,y0,0 0,200 100,(P) myconstrain_m(P,x,y),options); p=p+1; x1=s(1); y1=s(2);endx(:,end)=x0;y(:,end)=y0;plot(x,y,'o')hold;for i=1:8 b=result(1:2,i)' plot(x(b),y(b),'-k')endfunction result=prim1(x1,y1)x=20 50 160 200 120 35 10 0 x1;y=0 0 0 50 100 100 100 25 y1;A=zeros(9);

33、 for i=1:9 for j=1:9 A(i,j)=sqrt(x(i)-x(j)2+(y(i)-y(j)2); end; end; A(A=0)=inf; result=;p=1;tb=2:length(A); while length(result)=length(A)-1 temp=A(p,tb); temp=temp(:); d=min(temp); jb,kb=find(A(p,tb)=d); j=p(jb(1); k=tb(kb(1); result=result,j;k;d; p=p,k; tb(tb=k)=;endendfunction Qinequ, Qequ = myco

34、nstrain(P,x,y) C1 = sqrt(P(1)-x(3).2+(P(2)-y(3).2). +sqrt(P(1)-x(5).2+(P(2)-y(5).2). -1.4*sqrt(x(3)-x(5)2+(y(3)-y(5)2); C2 = sqrt(P(1)-x(3).2+(P(2)-y(3).2). +sqrt(P(1)-x(4).2+(P(2)-y(4).2). -1.4*sqrt(x(3)-x(4)2+(y(3)-y(4)2); C3 = sqrt(P(1)-x(4).2+(P(2)-y(4).2). +sqrt(P(1)-x(5).2+(P(2)-y(5).2). -1.4*

35、sqrt(x(4)-x(5)2+(y(4)-y(5)2); Qinequ = C1, C2, C3 ; Qequ = 0;function Qinequ, Qequ = myconstrain_m(P,x,y) C1 = sqrt(P(1)-x(3).2+(P(2)-y(3).2). +sqrt(P(1)-x(5).2+(P(2)-y(5).2). -1.4*sqrt(x(3)-x(5)2+(y(3)-y(5)2); C2 = sqrt(P(1)-x(2).2+(P(2)-y(2).2). +sqrt(P(1)-x(6).2+(P(2)-y(6).2). -1.4*sqrt(x(2)-x(6)2+(y(2)-y(6)2); Qinequ = C1, C2; Qequ = 0;附录4：第三问求解clearx1=100;