基于某Floyd算法的道路优化设计问题.doc

《基于某Floyd算法的道路优化设计问题.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数学建模基于Floyd算法的公园道路优化设计问题小组编号：02小组成员：队员1聪-建模队员2汪涛-建模队员3娜-建模队员4薛向龙-建模队员5蔡诗聂-编程队员6志诚-编程2012年7月21日基于Floyd算法的公园道路优化设计问题摘要本文主要研究了以公园部道路修建为背景的路径优化问题。对于问题一，已知四个交叉点的情况下，考虑到边缘道路不计入修建道路总长的题目要求和最短道路长不大于两点连线1.4倍前提要求，首选边缘路径，将那些无需借助交叉点即可满足1.4倍前提要求的点从考虑围剔除。然后对剩余不满足条件的路径运用Kru

2、skal算法，生成最小生成树的路径，再在此基础上，利用Floyd算法，找出其中不符合1.4倍约束的路径的边，综合对其路径进行调整并将满足条件的所有路径的边用穷举法进行筛选，最终选取最优路径，其总路程为393。对于问题二，我们在第一问结果上进行改进，运用两点之间线段最短原理将第一问最短路径进行优化，然后引入费马点定义，通过数理计算分析，划分三角形区域，建立非线性规划模型进行局部优化。递增交叉点的个数，并在前一个交叉点的最优路径的基础上对后一个交叉点的取点围进行考量，用lingo对不同数目交叉点的情况下的最短路径目标

3、函数进行规划，并以1.4倍的数学关系作为约束条件，进行局部最优解逼近全局最优解，最终确定最优交叉点个数为3个，坐标分别为、、，计算出最短路径。对于问题三，我们在对比道路穿过湖的情况下，考虑到湖边的修路计算到总路程的情况，分析得到在以湖的顶点R2、R4为道路交叉点时比以湖边其他点作为交叉点时的路径要短，所以分别以湖的顶点R2、R4为道路交叉点时进行讨论，在问题二的最短路径的基础上建立非线性规划模型，然后利用费马点逐步进行优化，比较两种不同交叉点的优化模型情况，最终确定出最优方案下的四个交叉点的坐标分别,,，计算出该

4、情况下最优路程长为。关于模型的优化，对于问题二，我们考虑到可以通过蒙特卡洛的方法对公园矩形区域围进行撒点，并借用椭圆法来约束1.4倍的条件关系，此方法可以求出选择不同数目交叉点时的最优路径，结果更精确，但是计算量大、程序运行缓慢。关键词：Kruskal算法Floyd算法局部优化费马点非线性规划一、问题重述为了美化校园环境，同时为学生提供更好的生活条件，某大学计划建一个形状为矩形或其他不规则图形的公园。该公园计划有若干个入口，让任意两个入口相连且任意的两个入口之间的最短道路长不大于两点连线的1.4倍。路线的选择可以

5、利用公园四周的边，即默认矩形的四条边上存在已经建好的道路，此道路不计入道路总长。矩形公园相关数据为：长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公园及入口示意图我们的任务就是结合该公园已有的计划，对其进行合理的道路安排，建立相应的数学模型，解决以下问题：1、在公园假定要使用A(50,75)，B(40,40)，C(120,40)，D(115,7

6、0）这4个点作为道路交叉点时，如何设计出新的道路在满足1.4倍要求的前提下使公园道路总路程最短。2、在公园可以任意修建道路的情况下，如何确定交叉点的个数及坐标设计道路使其在满足1.4倍条件下使总路程最少。3、在公园有一条矩形的湖的，新修的道路不能通过，但可以到达湖四周的边的前提下，如何设计交叉点的个数及坐标设计道路使其在满足1.4倍条件下使总路程最少。注：以上问题中都要求公园新修的道路与四周的连接只能与8个路口相通，而不能连到四周的其它点。图2有湖的示意图二、问题分析本题是一个道路设计的最优化的问题，即是如何设计

7、路径使公园部新修路总长最小，但要满足以下两个控制条件：1、任意两个入口连通；2、任意两个入口的最短路径不超过其直线距离的1.4倍。对于问题一，题中已给出A(50,75)，B(40,40)，C(120,40)，D(115,70）这4个点作为道路交叉点，由于题设中说明公园四周存在修好的道路且允许通行，所以我们先利用四周道路，找出，，，，，，，，，这些沿边道路不能满足1.4倍关系的路径。然后对剩余不满足第2个控制条件的路径运用Kruskal算法，生成最小生成树，再在此基础上，利用Floyd算法，找出其中不符合条件2的路

8、径用穷举法进行优化。对于问题二，我们在第一问结果上进行改进，考虑到两点之间线段最短原理我们将与、与直接相连。引入费马点定义，通过分析划分三角形区域，建立非线性规划模型进行局部优化。假设公园有m个交叉点，从m=0开始，我们继续讨论m=1、m=2和m=3这三种情况，进行局部最优解逼近全局最优解，最终确定交叉点数及坐标并求解出最短路径。对于问题三，首先考虑问题二中设计的道路是否