笔者于2012年5月参加西北工业大学数模竞赛,试题详见问题充数部分。问题一:把矩形框架的四个顶点、八个入口点和花园内部四个交叉点总共是十六个点都看做是顶点,构造道路建设费用矩阵B,求得连接这十六个点的最小生成树,接下来,用迪杰斯特拉算法加以修改和完善(简述一下方法:按P1,P2……的先后顺序,用迪杰斯特拉算法,求得总述中11对入口之间最短路径,若该路径小于这两个入口直线距离的1.4倍,就保留这个路径,若某两个入口之间没有这样的路径,就通过已保留的路径,结合线性规划的方法,构建新的路径,使得该两入口之间存在小于其直线距离的1.4倍的路径,且使得新构建的路径之和尽量的小)使得总述中所说的11对入口之间存在路径总长不大于直线距离的1.4倍的道路,即为最佳路径设计。最终得到符合题意的最短路径为394.56m。问题二:在问题1得到方案的基础上进行优化,用Floyd算法求解出任意两个路口仅通过矩形图边的最短路径矩阵Df=(dfij)n*n,用求出的最短路径dfij与vi,vj,两点的直接连接的距离dfij的1.4倍做比较得出不可周向矩阵T=(tij)n*n,并用matlab程序计算出矩阵T,最终得到符合题意的最短路径为358.62m。针对问题三:在问题2中,道路有经过湖面的,这不符合第三问的要求,因此,在假设第二问的解是最优的情况下,绕过湖面所在地,求出其长度最小的道路设计,模型仍沿用第二问的原理,在第二问的基础上求解出满足题意的解,最终得到符合题意的最短路径为360.7149m。