公园中道路设计问题的数学建模资料.docVIP

装 订 线 摘 要 如今，人们对于公园中的道路设计越来越人性化，对如何在满足要求的情况下设计总距离最短的道路建设方案，针对本题的要求，我们进行了深入的探讨。 在此，我们首先利用简化的思想，再利用穷举法、网格划分和蚁群算法等方法，对问题进行了探讨和解决。我们先将问题进行了简化，找到了两类有特殊关系的入口点：第一类即入口点之间可以在满足题目要求的情况下通过公园周边的道路直接连接，他们之间的连接就可以先假设是通过公园边线连接的，此时他们之间的连接对总路程的增加量为0；第二种特殊点只在问题一中存在，即入口点之间通过边界连接或通过公园内部任意一个给定的交点连接的道路长度都大于它们间直线距离的1.4倍，这类入口点需要用直线直接连接才能满足要求。 问题一中，我们先利用两类特殊入口点对问题进行简化，从而得到了与原问题等价的简化了的问题，对此问题，我们用matlab对其可能的连接方式进行穷举处理，最终得到了使公园内部道路总长最短的设计方案，设计方案见图()，我们得到最佳设计方案的路程总和S1=394.60m。 问题二中，我们先利用第一类特殊点进行简化处理，然后我们利用网格划分和蚁群算法结合的方法对问题进行了分析处理。并利用matlab进行了模拟预测，最终得到了最佳连接方案如图()，所得交点坐标为A2(63.87,56.45)、B2(106.61,69.35)、C2(165.32,33.85)，所得方案的路程总和S2=351.33m。 问题三与问题二有很大的相同点，在此，我们同样先利用第一类特殊点对问题进行简化，然后我们对问题二的算法进行了局部优化，即将蚂蚁在湖的附近的行走路线进行了调整，最终，我们得到了这种情况下的最佳线路设计方案如图()，所得交点坐标为A3(63.87,56.45)、B3(106.61,69.35)、C3(161.75,30.73),我们得到的最佳设计方案的路程总和S3=351.51m. 关键词：最短路径 简化 穷举法 网格划分 蚁群算法 目录 问题重述 1 问题一重述 2 问题二重述 5 问题三重述 2 问题分析 4 问题一分析 2 问题二分析 5 问题三重述 2 符号说明 4 模型假设与约定 1 模型建立与求解 1 问题一 2 问题二 5 问题三 2 模型检验 1 模型以检验 2 模型二检验 5 模型三检验 2 模型优缺点分析 1 模型优点 2 模型缺点 2 参考文献 4 附录 1 附录一 2 附录二 5 附录三 2 附录四 5 公园中道路设计问题的数学建模 问题重述： 本题要求我们在一个200m*100m的矩形的公园里设计合适的路径将公园的八个入口满足一定条件的情况下两两相连，而且要找出一种使总路程最小的连接方法。而且线路的总长度不包括所经过的四周的路的长度。 问题一重述：在公园内道路交点确定的情况下求出使总路程最短的路线设计方案，并计算出总路程。同时设计的路线要满足任意两个入口之间的最短道路长不大于两点连线的1.4倍 问题二重述：在道路修建方法任意的情况下，求出在满足：任意两个入口之间的最短道路长不大于两点连线的1.4倍的情况下的最短路径，建立模型并给出算法，给出交点坐标，计算总路程。 问题三重述：道路修建方法任意且道路不通过公园内湖的情况下，求出满足：任意两个入口之间的最短道路长不大于两点连线的1.4倍的情况下的最短路径，建立模型并给出算法，给出交点坐标，计算总路程。 问题分析： 三个问题都是要按照一些特定的要求。由于两点之间直线距离最小，所以我们的解答中所有道路连线之间均为直线，没有曲线。而且三个问题有一个共同的前提：任意两个入口之间的最短道路长不大于两点连线的1.4倍。总路程中不包括所经过的公园周边的路径长度，所以在允许的情况下我们可以尽量多地通过周边的路径连接入口。 问题一分析：本问中给出了公园的八个入口以及公园中道路的四个交点所在的位置，我们需要设计道路将任意两个入口连接，而且要满足任意两个入口之间的最短距离长不大于两点之间的直线距离的1.4倍。最终，我们需要给出总道路长度最短的连接方案和此时的道路总长。 我们可以先对问题进行简化：即先找出入口中比较特殊的点，将其进行处理。第一种特殊点：入口点之间可以直接通过公园边线连接且同时满足两点之间连线的总长不大于这两点之间直线距离的1.4倍，对于这种点，就利用公园边来进行连接，这时道路总长的增加量就是0。第二种特殊点：某两个入口点通过公园边界连接入口点会使得两点间总距离大于其直线距离的1.4倍，同时通过公园内部已给定的四个点中任何一个点相连都会使道路长度大于直线距离的1