数学建模——自来水管道铺设问题

自来水管道铺设问题描述

在村村通自来水工程实施过程中，从保证供水质量以及设备维护方便角度出发，某地区需要建设一个中心供水站，12个一级供水站和168个二级供水站，各级供水站的位置坐标如附件表1所示，其中类型A表示中心供水站，类型V代表一级供水站，类型P为二级供水站。附件图1是各级供水站的地理位置图。

现在要将中心供水站A处的自来水通过管道输送到一级供水站和二级供水站。按照设计要求，从中心站A铺设到一级供水站的管道为I型管道，从一级供水站出发铺设到二级供水站的管道为II型管道。

自来水管道铺设技术要求如下：

• 1.中心供水站只能和一级供水站连接（铺设I型管道），不能和二级供水站直接相连，但一级供水站之间可以连接（铺设I型管道）。
• 2.一级供水站可以与二级供水站相连（铺设II型管道），且二级供水站之间也可以连接（铺设II型管道）。
• 3.各级供水站之间的连接管道必须从上一级供水站或同一级供水站的位置坐标出发，不能从任意管道中间的一点进行连接。
• 4.相邻两个供水站之间（如果有管道相连）所需管道长度可简化为欧氏距离。

请您结合上述管道铺设要求，建立数学模型，完成以下问题

• 问题1：从中心供水站A出发，自来水管道应该如何铺设才能使管道的总里程最少？以图形给出铺设方案，并给出I型管道和II型管道总里程数。
• 问题2：由于II型管道市场供应不足，急需减少从一级供水站出发铺设的II型管道总里程，初步方案是将其中两个二级供水站升级为一级供水站。问选取哪两个二级供水站，自来水管道应该如何铺设才能使铺设的II型管道总里程最少？相对问题1的方案，II型管道的总里程减少了多少公里？
• 问题3：在问题1基础上，假如现实中由于功率的影响，从一级供水站出发铺设的管道最多只能供水40公里（按从该一级供水站管道输送的总里程计算），但从中心供水站A出发铺设的管道供水不受此距离限制。为实现对所有供水站供水，需要将若干个二级供水站升级为一级供水站，但升级后从该供水站出发铺设的管道也最多只能供水40公里。问最少升级几个二级供水站，可实现对所有的供水站供水？在这种配置下铺设管道的总里程数最少是多少公里？
• 

建模思路和方案设计

符号说明

问题一分析

对于问题一，需求解从中心供水站出发铺设管道的最小总里程数，将其转换为最小生成树问题 (MST 问题) 进行求解。本文采取 Prim 算法，将水站作为结点，水站之间的距离作为边的权值，求解管道总里程的最小生成树。此处不应考虑不分等级的全局最优解，即将一级供水站和二级供水站作为相同的节点，会造成部分自来水由二级供水站传送向一级供水站或者自来水交汇的情况，该分布没有形成环流，且不符合实际生活中枝状管道的分布。基于问题设计的要求，采用管道里程数更少的枝状形式对管道铺设进行设计，先考虑中心供水站到各一级供水站的管道，再考虑一级供水站到各二级供水站的管道，即先确定 I 型管道的最小生成树，再确定 II 型管道的最小生成树。

问题一结果

问题二

结果显示。。。

代码

。。。