【摘要】 针对2012年西北工业大学数学建模竞赛的"公园内道路优化设计问题",给出一种解决方案.首先建立最小生成树模型,应用"破圈法"对生成树中不满足直线距离约束的路段进行修正,得出新修建道路长度.其次,建立费尔马点优化模型和椭圆覆盖模型,通过叠加场图提取覆盖重合率较高的区域,离散化取点,设为道路交叉点,经过费尔马点优化修正模型,实现在公园内可以任意修建道路的前提下,得出总路程最少的道路设计方案.最后考虑有障碍物(题中矩形的湖)下道路的优化设计,经过费尔马点优化,得到有湖时的最短道路长度.更多还原

【Abstract】 In this paper,we provide a solution to the problem "Optimal Park Road Design" of the 2012 Northwestern Polytechnical University Mathematical Contest in Modeling.Firstly,a minimum spanning tree model is established.Applying the method of "breaking the circle" to revise the road which does not meet the straight-line distance constraints,the length of the newly constructed road is achieved.The Fermat point optimization model and Elliptical cover model are established accordingly,using the superimposed field map to extract the region that holds high overlap rate,and using the discrete points to set the road crossing points.Applying the optimized Fermat point model,the final road design scheme with minimum total distance is obtained based on the premise of any construction of roads.Finally,considering the obstacles(rectangular lake),with the Fermat point model optimized,the resulted shortest path length with a lake is achieved.更多还原