数学建模_自来水管道铺设问题.docx

C

PAGE1

基于最小生成树的自来水管道铺设问题

摘要

本文对自来水管道的铺设及最优二级供水站的升级进行了深入探讨，将实际问题转化为求解最小生成树问题。建立了关于求解最短铺设公里数以及选取最优二级供水站升级的数学模型，主要应用MATLAB软件进行求解得到具体的管道铺设及供水站的升级方案。

问题一：根据各个供水站的坐标计算各点之间的欧式距离得到对应的距离矩阵，再利用Prim算法分别求得Ⅰ型管道和Ⅱ型管道的最小生成树，将其合并。为了去除合并过程中可能产生的回路，考虑中心供水站与一级供水站之间的最小生成树已为最优，应使其保留完整；然后利用Prim算法得到总体的最小生成树即为最终的铺设方案。