题目：在村村通自来水工程实施过程中，从保证供水质量以及设备维护方便角度出发，某地区需要建设一个中心供水站，12个一级供水站和168个二级供水站，各级供水站的位置坐标如表1所示，其中类型A表示中心供水站，类型V代表一级供水站，类型P为二级供水站。图1是各级供水站的地理位置图。
现在要将中心供水站A处的自来水通过管道输送到一级供水站和二级供水站。自来水管道铺设技术要求如下： 1.中心供水站只能和一级供水站连接，不能和二级供水站直接相连，但一级供水站之间可以连接。 2.一级供水站可以与二级供水站相连，且二级供水站之间也可以连接。 3.各级供水站之间的连接管道必须从上一级供水站或同一级供水站的位置坐标出发，不能从任意管道中间的一点进行连接。 4.相邻两个供水站之间（如果有管道相连）所需管道长度可简化为欧氏距离。
请您结合上述管道铺设要求，建立数学模型，完成以下问题 1.从中心供水站A出发，自来水管道应该如何铺设才能使管道的总里程最少？以图形给出铺设方案，并给出管道总里程数。 2.为减少输送距离，准备将其中两个二级供水站升级为一级供水站，问选取哪两个二级供水站时，自来水管道应该如何铺设才能使管道的总里程最少？相对问题1总里程减少了多少公里？ 3.在问题1基础上，假如现实中由于功率的影响，从一级供水站出发铺设的管道最多只能供水40公里（按从该一级供水站管道输送的总里程计算），但从中心供水站A出发铺设的管道供水不受此距离限制。为实现对所有供水站供水，需要将若干个二级供水站升级为一级供水站，但升级后从该供水站出发铺设的管道也最多只能供水40公里。问最少升级几个二级供水站，可实现对所有的供水站供水？在这种配置下铺设管道的最小公里是多少？ 问题分析： 对于问题一：分为两个步骤进行建模求解。步骤一利用prim算法建立最小生成树以求解最小管道总里程数，步骤二借用Matlab软件运用欧式距离公式（即两点间距离公式）对步骤一生成的管道是否符合“自来水管道铺设总里程最少”这一条件进行验算。 对于问题二：分为两个步骤进行建模。步骤一利用枚举法，在168个二级供水站中任意选取两个供水站使之升级成为一级供水站，步骤二采用第一问的算法计算路径，逐一进行比对，筛选出路径最少的组合即是所要求的，即可求出哪两个二级供水站升级为一级供水站，同时也计算出了该组合的最少里程。 对于问题三：采用试探法的思想，以枚举法为主，弗洛伊德算法为辅。首先假设不升级供水站，看能否实现全部供水，如若可以则不需要升级，否则任意选取一个二级供水站进行升级，看能否实现全部供水，不行则继续任意选取两个供水站升级，以此类推，直到实现全部供水。
问题一代码：
clc; clear; A=[26 31; %1个中心供水站A 5 33;8 9;10 24;13 34;17 23;20 10;25 47;31 18;35 42;36 25;41 31;45 38]; 个一级供水站V B=[5 33;8 9;10 24;13 34;17 23;20 10;25 47;31 18;35 42;36 25;41 31;45 38; 个一级供水站V 41 35;40 34;38 35;38 37;33 37;31 36;33 35;28 32;24 30;21 31;22 27;28 29;43 37;44 39;25 27;21 29;22 30;24 32;37 33;38 33;37 36;14 13; 8个二级供水站P 16 9;14 7;18 14;12 6;15 14;20 13;13 46;16 39;21 39;26 44;28 40;27 42;29 38;29 44;36 44;41 40;39 52;27 49;23 46;20 46;16 46;22 44;40 44; 42 40;37 42;35 49;35 51;35 52;34 55;26 53;27 51;31 51;31 45;31 41;28 45;27 35;24 38;26 39;13 37;17 36;21 41;18 41;21 43;13 39;14 43;12 43; 10 44;16 44;18 44;24 44;25 49;24 49;24 51;21 48;17 51;10 34;9 35;7 37;4 37;5 42;2 44;7 32;7 30;1 24;2 16;3 18;2 20;4 24;5 28;6 24;9 29;2 33;7 34; 3 30;3 41;10 36;17 34;20 22;24 21;22 17;21 16;27 19;26 16;9 16;12 17;14 15;19 26;14 28;13 25;9 19;2 1;6 6;7 8;6 14;5 17;5 16;16 19;26 13;29 11; 31 14;28 17;20 19;17 22;15 23;21 23;24 23;26 23;25 25;15 31;15 29;10 28;38 26;37 25;33 21;40 24;44 44;41 31;33 24;32 27;40 14;42 26;45 33; 29 23;31 30;30 25;31 23;35 15;40 16;40 20;37 20;35 24;43 23;45 26;37 28;35 28;33 29;37 30;39 30;41 29;43 31;47 34;46 43;42 43;48 45;42 44;43 50]; C=[26 31; %1个中心供水站A 5 33;8 9;10 24;13 34;17 23;20 10;25 47;31 18;35 42;36 25;41 31;45 38; 个一级供水站V 41 35;40 34;38 35;38 37;33 37;31 36;33 35;28 32;24 30;21 31;22 27;28 29;43 37;44 39;25 27;21 29;22 30;24 32;37 33;38 33;37 36;14 13; 8个二级供水站P 16 9;14 7;18 14;12 6;15 14;20 13;13 46;16 39;21 39;26 44;28 40;27 42;29 38;29 44;36 44;41 40;39 52;27 49;23 46;20 46;16 46;22 44;40 44; 42 40;37 42;35 49;35 51;35 52;34 55;26 53;27 51;31 51;31 45;31 41;28 45;27 35;24 38;26 39;13 37;17 36;21 41;18 41;21 43;13 39;14 43;12 43; 10 44;16 44;18 44;24 44;25 49;24 49;24 51;21 48;17 51;10 34;9 35;7 37;4 37;5 42;2 44;7 32;7 30;1 24;2 16;3 18;2 20;4 24;5 28;6 24;9 29;2 33;7 34; 3 30;3 41;10 36;17 34;20 22;24 21;22 17;21 16;27 19;26 16;9 16;12 17;14 15;19 26;14 28;13 25;9 19;2 1;6 6;7 8;6 14;5 17;5 16;16 19;26 13;29 11; 31 14;28 17;20 19;17 22;15 23;21 23;24 23;26 23;25 25;15 31;15 29;10 28;38 26;37 25;33 21;40 24;44 44;41 31;33 24;32 27;40 14;42 26;45 33; 29 23;31 30;30 25;31 23;35 15;40 16;40 20;37 20;35 24;43 23;45 26;37 28;35 28;33 29;37 30;39 30;41 29;43 31;47 34;46 43;42 43;48 45;42 44;43 50]; m=length(A); %m=13 n=length(B); %n=180 a=zeros(181); %带权邻接矩阵 b=zeros(181); %无权邻接矩阵 for i=1:m for j=i+1:m a(i,j)=sqrt(sum((A(i,:)-A(j,:)).^2)); %中心与一级，一级之间距离 if i>1 a(j,i)=sqrt(sum((A(i,:)-A(j,:)).^2)); %一级供水站之间距离 end end end for i=1:n for j=i+1:n a(i+1,j+1)=sqrt(sum((B(i,:)-B(j,:)).^2)); %一级与二级，二级之间距离 if i>12 a(j+1,i+1)=sqrt(sum((B(i,:)-B(j,:)).^2)); %二级供水站之间距离 end end end total=0; %管道总里程数 a(find(a==0))=inf; %prim算法 result=[];p=1;tb=2:length(a); while length(result)~=length(a)-1 temp=a(p,tb);temp=temp(:); d=min(temp); total=total+d; [jb,kb]=find(a(p,tb)==d); j=p(jb(1));k=tb(kb(1)); b(j,k)=1; b(k,j)=1; result=[result,[j;k;d]];p=[p,k];tb(find(tb==k))=[]; end result total A1=[26]; %中心供水站x坐标 A2=[31]; %中心拱水站y坐标 V1=[5 8 10 13 17 20 25 31 35 36 41 45 ]; %一级供水站x坐标 V2=[33 9 24 34 23 10 47 18 42 25 31 38]; %一级供水站y坐标 P1=[41 40 38 38 33 31 33 28 24 21 22 28 43 44 25 21 22 24 37 38 37 14 16 14 18 12 15 20 13 16 21 26 28 27 29 29 36 41 39 27 23 20 16 22 40 42 37 35 35 35 34 26 27 31 31 31 28 27 24 26 13 17 21 18 21 13 14 12 10 16 18 24 25 24 24 21 17 10 9 7 4 5 2 7 7 1 2 3 2 4 5 6 9 2 7 3 3 10 17 20 24 22 21 27 26 9 12 14 19 14 13 9 2 6 7 6 5 5 16 26 29 31 28 20 17 15 21 24 26 25 15 15 10 38 37 33 40 44 41 33 32 40 42 45 29 31 30 31 35 40 40 37 35 43 45 37 35 33 37 39 41 43 47 46 42 48 42 43]; %二级供水站x坐标 P2=[35 34 35 37 37 36 35 32 30 31 27 29 37 39 27 29 30 32 33 33 36 13 9 7 14 6 14 13 46 39 39 44 40 42 38 44 44 40 52 49 46 46 46 44 44 40 42 49 51 52 55 53 51 51 45 41 45 35 38 39 37 36 41 41 43 39 43 43 44 44 44 44 49 49 51 48 51 34 35 37 37 42 44 32 30 24 16 18 20 24 28 24 29 33 34 30 41 36 34 22 21 17 16 19 16 16 17 15 26 28 25 19 1 6 8 14 17 16 19 13 11 14 17 19 22 23 23 23 23 25 31 29 28 26 25 21 24 44 31 24 27 14 26 33 23 30 25 23 15 16 20 20 24 23 26 28 28 29 30 30 29 31 34 43 43 45 44 50]; %二级供水站y坐标 %画线路图 scatter(A1,A2,'bo') %中心供水站位置 hold on; scatter(V1,V2,'k*') %一级供水站位置 hold on; scatter(P1,P2,'b.') %二级供水站位置 hold on; xlabel('x') ylabel('y') gplot(b,C,'r-') hleg=legend('中心供水站','一级供水站','二级供水站','管道','Location','NorthEastOutside'); hold on; T0.9142运行结果：
问题二代码：
clc; clear; A=[26 31; %1个中心供水站A 5 33;8 9;10 24;13 34;17 23;20 10;25 47;31 18;35 42;36 25;41 31;45 38]; 个一级供水站V B=[5 33;8 9;10 24;13 34;17 23;20 10;25 47;31 18;35 42;36 25;41 31;45 38; 个一级供水站V 41 35;40 34;38 35;38 37;33 37;31 36;33 35;28 32;24 30;21 31;22 27;28 29;43 37;44 39;25 27;21 29;22 30;24 32;37 33;38 33;37 36;14 13; 8个二级供水站P 16 9;14 7;18 14;12 6;15 14;20 13;13 46;16 39;21 39;26 44;28 40;27 42;29 38;29 44;36 44;41 40;39 52;27 49;23 46;20 46;16 46;22 44;40 44; 42 40;37 42;35 49;35 51;35 52;34 55;26 53;27 51;31 51;31 45;31 41;28 45;27 35;24 38;26 39;13 37;17 36;21 41;18 41;21 43;13 39;14 43;12 43; 10 44;16 44;18 44;24 44;25 49;24 49;24 51;21 48;17 51;10 34;9 35;7 37;4 37;5 42;2 44;7 32;7 30;1 24;2 16;3 18;2 20;4 24;5 28;6 24;9 29;2 33;7 34; 3 30;3 41;10 36;17 34;20 22;24 21;22 17;21 16;27 19;26 16;9 16;12 17;14 15;19 26;14 28;13 25;9 19;2 1;6 6;7 8;6 14;5 17;5 16;16 19;26 13;29 11; 31 14;28 17;20 19;17 22;15 23;21 23;24 23;26 23;25 25;15 31;15 29;10 28;38 26;37 25;33 21;40 24;44 44;41 31;33 24;32 27;40 14;42 26;45 33; 29 23;31 30;30 25;31 23;35 15;40 16;40 20;37 20;35 24;43 23;45 26;37 28;35 28;33 29;37 30;39 30;41 29;43 31;47 34;46 43;42 43;48 45;42 44;43 50]; C=[26 31; %1个一级供水站A 5 33;8 9;10 24;13 34;17 23;20 10;25 47;31 18;35 42;36 25;41 31;45 38; 个一级供水站V 41 35;40 34;38 35;38 37;33 37;31 36;33 35;28 32;24 30;21 31;22 27;28 29;43 37;44 39;25 27;21 29;22 30;24 32;37 33;38 33;37 36;14 13; 8个二级供水站P 16 9;14 7;18 14;12 6;15 14;20 13;13 46;16 39;21 39;26 44;28 40;27 42;29 38;29 44;36 44;41 40;39 52;27 49;23 46;20 46;16 46;22 44;40 44; 42 40;37 42;35 49;35 51;35 52;34 55;26 53;27 51;31 51;31 45;31 41;28 45;27 35;24 38;26 39;13 37;17 36;21 41;18 41;21 43;13 39;14 43;12 43; 10 44;16 44;18 44;24 44;25 49;24 49;24 51;21 48;17 51;10 34;9 35;7 37;4 37;5 42;2 44;7 32;7 30;1 24;2 16;3 18;2 20;4 24;5 28;6 24;9 29;2 33;7 34; 3 30;3 41;10 36;17 34;20 22;24 21;22 17;21 16;27 19;26 16;9 16;12 17;14 15;19 26;14 28;13 25;9 19;2 1;6 6;7 8;6 14;5 17;5 16;16 19;26 13;29 11; 31 14;28 17;20 19;17 22;15 23;21 23;24 23;26 23;25 25;15 31;15 29;10 28;38 26;37 25;33 21;40 24;44 44;41 31;33 24;32 27;40 14;42 26;45 33; 29 23;31 30;30 25;31 23;35 15;40 16;40 20;37 20;35 24;43 23;45 26;37 28;35 28;33 29;37 30;39 30;41 29;43 31;47 34;46 43;42 43;48 45;42 44;43 50]; m=length(A); %m=13 n=length(B); %n=180 p=length(C); %p=181 a=zeros(181); %带权邻接矩阵 b=zeros(181); %无权邻接矩阵 for i=1:m for j=i+1:m a(i,j)=sqrt(sum((A(i,:)-A(j,:)).^2)); %中心与一级，一级之间距离 if i>1 a(j,i)=sqrt(sum((A(i,:)-A(j,:)).^2)); %一级供水站之间距离 end end end for i=1:n for j=i+1:n a(i+1,j+1)=sqrt(sum((B(i,:)-B(j,:)).^2)); %一级与二级，二级之间距离 if i>12 a(j+1,i+1)=sqrt(sum((B(i,:)-B(j,:)).^2)); %二级供水站之间距离 end end end D=nchoosek(1:168,2); %需要升级的二级供水站组合 mindist=540.9142; %未升级时最小管道总里程 minx=0;miny=0; %需要升级的二级供水站序号 for k=1:length(D) change=D(k,:); x=change(1:1)+13; y=change(2:2)+13; for i=14:p %升级后更改带权邻接矩阵信息 if i==x||i==y a(1,i)=sqrt(sum((C(1,:)-C(i,:)).^2)); end end for i=14:p for j=2:13 if i==x||i==y a(i,j)=sqrt(sum((C(i,:)-C(j,:)).^2)); end end end for i=14:p for j=14:p if i~=x&&j==y a(i,j)=0; end if i==x&&j~=y a(j,i)=0; end end end total=0; %管道总里程数 a(find(a==0))=inf; %prim算法 result=[];p=1;tb=2:length(a); while length(result)~=length(a)-1 temp=a(p,tb);temp=temp(:); d=min(temp); total=total+d; [jb,kb]=find(a(p,tb)==d); j=p(jb(1));k=tb(kb(1)); b(j,k)=1; b(k,j)=1; result=[result,[j;k;d]];p=[p,k];tb(find(tb==k))=[]; end if(total<mindist) %更改最小管道总里程及需要升级的二级供水站序号 mindist=total; minx=x; miny=y; end end mindist minx miny问题二生成图解代码：
clc; clear; A=[26 31; %1个A 5 33;8 9;10 24;13 34;17 23;20 10;25 47;31 18;35 42;36 25;41 31;45 38]; 个V B=[5 33;8 9;10 24;13 34;17 23;20 10;25 47;31 18;35 42;36 25;41 31;45 38; 个V 41 35;40 34;38 35;38 37;33 37;31 36;33 35;28 32;24 30;21 31;22 27;28 29;43 37;44 39;25 27;21 29;22 30;24 32;37 33;38 33;37 36;14 13; 8个P 16 9;14 7;18 14;12 6;15 14;20 13;13 46;16 39;21 39;26 44;28 40;27 42;29 38;29 44;36 44;41 40;39 52;27 49;23 46;20 46;16 46;22 44;40 44; 42 40;37 42;35 49;35 51;35 52;34 55;26 53;27 51;31 51;31 45;31 41;28 45;27 35;24 38;26 39;13 37;17 36;21 41;18 41;21 43;13 39;14 43;12 43; 10 44;16 44;18 44;24 44;25 49;24 49;24 51;21 48;17 51;10 34;9 35;7 37;4 37;5 42;2 44;7 32;7 30;1 24;2 16;3 18;2 20;4 24;5 28;6 24;9 29;2 33;7 34; 3 30;3 41;10 36;17 34;20 22;24 21;22 17;21 16;27 19;26 16;9 16;12 17;14 15;19 26;14 28;13 25;9 19;2 1;6 6;7 8;6 14;5 17;5 16;16 19;26 13;29 11; 31 14;28 17;20 19;17 22;15 23;21 23;24 23;26 23;25 25;15 31;15 29;10 28;38 26;37 25;33 21;40 24;44 44;41 31;33 24;32 27;40 14;42 26;45 33; 29 23;31 30;30 25;31 23;35 15;40 16;40 20;37 20;35 24;43 23;45 26;37 28;35 28;33 29;37 30;39 30;41 29;43 31;47 34;46 43;42 43;48 45;42 44;43 50]; C=[26 31; 5 33;8 9;10 24;13 34;17 23;20 10;25 47;31 18;35 42;36 25;41 31;45 38; 个V 41 35;40 34;38 35;38 37;33 37;31 36;33 35;28 32;24 30;21 31;22 27;28 29;43 37;44 39;25 27;21 29;22 30;24 32;37 33;38 33;37 36;14 13; 8个P 16 9;14 7;18 14;12 6;15 14;20 13;13 46;16 39;21 39;26 44;28 40;27 42;29 38;29 44;36 44;41 40;39 52;27 49;23 46;20 46;16 46;22 44;40 44; 42 40;37 42;35 49;35 51;35 52;34 55;26 53;27 51;31 51;31 45;31 41;28 45;27 35;24 38;26 39;13 37;17 36;21 41;18 41;21 43;13 39;14 43;12 43; 10 44;16 44;18 44;24 44;25 49;24 49;24 51;21 48;17 51;10 34;9 35;7 37;4 37;5 42;2 44;7 32;7 30;1 24;2 16;3 18;2 20;4 24;5 28;6 24;9 29;2 33;7 34; 3 30;3 41;10 36;17 34;20 22;24 21;22 17;21 16;27 19;26 16;9 16;12 17;14 15;19 26;14 28;13 25;9 19;2 1;6 6;7 8;6 14;5 17;5 16;16 19;26 13;29 11; 31 14;28 17;20 19;17 22;15 23;21 23;24 23;26 23;25 25;15 31;15 29;10 28;38 26;37 25;33 21;40 24;44 44;41 31;33 24;32 27;40 14;42 26;45 33; 29 23;31 30;30 25;31 23;35 15;40 16;40 20;37 20;35 24;43 23;45 26;37 28;35 28;33 29;37 30;39 30;41 29;43 31;47 34;46 43;42 43;48 45;42 44;43 50]; m=length(A); %m=13 n=length(B); %n=180 p=length(C); a=zeros(181); b=zeros(181); for i=1:m for j=i+1:m a(i,j)=sqrt(sum((A(i,:)-A(j,:)).^2)); if i>1 a(j,i)=sqrt(sum((A(i,:)-A(j,:)).^2)); end end end for i=1:n for j=i+1:n a(i+1,j+1)=sqrt(sum((B(i,:)-B(j,:)).^2)); if i>12 a(j+1,i+1)=sqrt(sum((B(i,:)-B(j,:)).^2)); end end end for i=14:p if i==27||i==28 a(1,i)=sqrt(sum((C(1,:)-C(i,:)).^2)); end end for i=14:p for j=2:13 if i==27||i==28 a(i,j)=sqrt(sum((C(i,:)-C(j,:)).^2)); end end end for i=14:p for j=14:p if i~=27&&j==28 a(i,j)=0; end if i==27&&j~=28 a(j,i)=0; end end end total=0; a(find(a==0))=inf; result=[];p=1;tb=2:length(a); while length(result)~=length(a)-1 temp=a(p,tb);temp=temp(:); d=min(temp); total=total+d; [jb,kb]=find(a(p,tb)==d); j=p(jb(1));k=tb(kb(1)); b(j,k)=1; b(k,j)=1; result=[result,[j;k;d]];p=[p,k];tb(find(tb==k))=[]; end total A1=[26]; A2=[31]; V1=[5 8 10 13 17 20 25 31 35 36 41 45]; V2=[33 9 24 34 23 10 47 18 42 25 31 38]; U1=[44 25]; U2=[39 27]; P1=[41 40 38 38 33 31 33 28 24 21 22 28 43 21 22 24 37 38 37 14 16 14 18 12 15 20 13 16 21 26 28 27 29 29 36 41 39 27 23 20 16 22 40 42 37 35 35 35 34 26 27 31 31 31 28 27 24 26 13 17 21 18 21 13 14 12 10 16 18 24 25 24 24 21 17 10 9 7 4 5 2 7 7 1 2 3 2 4 5 6 9 2 7 3 3 10 17 20 24 22 21 27 26 9 12 14 19 14 13 9 2 6 7 6 5 5 16 26 29 31 28 20 17 15 21 24 26 25 15 15 10 38 37 33 40 44 41 33 32 40 42 45 29 31 30 31 35 40 40 37 35 43 45 37 35 33 37 39 41 43 47 46 42 48 42 43]; P2=[35 34 35 37 37 36 35 32 30 31 27 29 37 29 30 32 33 33 36 13 9 7 14 6 14 13 46 39 39 44 40 42 38 44 44 40 52 49 46 46 46 44 44 40 42 49 51 52 55 53 51 51 45 41 45 35 38 39 37 36 41 41 43 39 43 43 44 44 44 44 49 49 51 48 51 34 35 37 37 42 44 32 30 24 16 18 20 24 28 24 29 33 34 30 41 36 34 22 21 17 16 19 16 16 17 15 26 28 25 19 1 6 8 14 17 16 19 13 11 14 17 19 22 23 23 23 23 25 31 29 28 26 25 21 24 44 31 24 27 14 26 33 23 30 25 23 15 16 20 20 24 23 26 28 28 29 30 30 29 31 34 43 43 45 44 50]; scatter(A1,A2,'bo') %中心供水站位置 hold on; scatter(V1,V2,'k*') %一级供水站位置 hold on; scatter(U1,U2,'ks') %二级升为一级供水站位置 hold on; scatter(P1,P2,'b.') %二级供水站位置 hold on; %画线路图 xlabel('x') ylabel('y') gplot(b,C,'r-') hleg=legend('中心供水站','一级供水站','二级升为一级供水站','二级供水站','管道','Location','NorthEastOutside'); hold on;运行结果：
问题三代码：
clc; clear; A=[26 31; %1个中心供水站A 5 33;8 9;10 24;13 34;17 23;20 10;25 47;31 18;35 42;36 25;41 31;45 38]; 个一级供水站V B=[5 33;8 9;10 24;13 34;17 23;20 10;25 47;31 18;35 42;36 25;41 31;45 38; 个一级供水站V 41 35;40 34;38 35;38 37;33 37;31 36;33 35;28 32;24 30;21 31;22 27;28 29;43 37;44 39;25 27;21 29;22 30;24 32;37 33;38 33;37 36;14 13; 8个二级供水站P 16 9;14 7;18 14;12 6;15 14;20 13;13 46;16 39;21 39;26 44;28 40;27 42;29 38;29 44;36 44;41 40;39 52;27 49;23 46;20 46;16 46;22 44;40 44; 42 40;37 42;35 49;35 51;35 52;34 55;26 53;27 51;31 51;31 45;31 41;28 45;27 35;24 38;26 39;13 37;17 36;21 41;18 41;21 43;13 39;14 43;12 43; 10 44;16 44;18 44;24 44;25 49;24 49;24 51;21 48;17 51;10 34;9 35;7 37;4 37;5 42;2 44;7 32;7 30;1 24;2 16;3 18;2 20;4 24;5 28;6 24;9 29;2 33;7 34; 3 30;3 41;10 36;17 34;20 22;24 21;22 17;21 16;27 19;26 16;9 16;12 17;14 15;19 26;14 28;13 25;9 19;2 1;6 6;7 8;6 14;5 17;5 16;16 19;26 13;29 11; 31 14;28 17;20 19;17 22;15 23;21 23;24 23;26 23;25 25;15 31;15 29;10 28;38 26;37 25;33 21;40 24;44 44;41 31;33 24;32 27;40 14;42 26;45 33; 29 23;31 30;30 25;31 23;35 15;40 16;40 20;37 20;35 24;43 23;45 26;37 28;35 28;33 29;37 30;39 30;41 29;43 31;47 34;46 43;42 43;48 45;42 44;43 50]; C=[26 31; %1个中心供水站A 5 33;8 9;10 24;13 34;17 23;20 10;25 47;31 18;35 42;36 25;41 31;45 38; 个一级供水站V 41 35;40 34;38 35;38 37;33 37;31 36;33 35;28 32;24 30;21 31;22 27;28 29;43 37;44 39;25 27;21 29;22 30;24 32;37 33;38 33;37 36;14 13; 8个二级供水站P 16 9;14 7;18 14;12 6;15 14;20 13;13 46;16 39;21 39;26 44;28 40;27 42;29 38;29 44;36 44;41 40;39 52;27 49;23 46;20 46;16 46;22 44;40 44; 42 40;37 42;35 49;35 51;35 52;34 55;26 53;27 51;31 51;31 45;31 41;28 45;27 35;24 38;26 39;13 37;17 36;21 41;18 41;21 43;13 39;14 43;12 43; 10 44;16 44;18 44;24 44;25 49;24 49;24 51;21 48;17 51;10 34;9 35;7 37;4 37;5 42;2 44;7 32;7 30;1 24;2 16;3 18;2 20;4 24;5 28;6 24;9 29;2 33;7 34; 3 30;3 41;10 36;17 34;20 22;24 21;22 17;21 16;27 19;26 16;9 16;12 17;14 15;19 26;14 28;13 25;9 19;2 1;6 6;7 8;6 14;5 17;5 16;16 19;26 13;29 11; 31 14;28 17;20 19;17 22;15 23;21 23;24 23;26 23;25 25;15 31;15 29;10 28;38 26;37 25;33 21;40 24;44 44;41 31;33 24;32 27;40 14;42 26;45 33; 29 23;31 30;30 25;31 23;35 15;40 16;40 20;37 20;35 24;43 23;45 26;37 28;35 28;33 29;37 30;39 30;41 29;43 31;47 34;46 43;42 43;48 45;42 44;43 50]; lm=length(A); %lm=13 ln=length(B); %ln=180 l=length(C); %l=181 a=ones(181)*inf; %带权邻接矩阵 for i=1:lm for j=i+1:lm a(i,j)=sqrt(sum((A(i,:)-A(j,:)).^2)); %中心与一级，一级之间距离 if i>1 a(j,i)=sqrt(sum((A(i,:)-A(j,:)).^2)); %一级供水站之间距离 end end end for i=1:ln for j=i+1:ln a(i+1,j+1)=sqrt(sum((B(i,:)-B(j,:)).^2)); %一级与二级，二级之间距离 if i>12 a(j+1,i+1)=sqrt(sum((B(i,:)-B(j,:)).^2)); %二级供水站之间距离 end end end n=size(a,1); %floyd算法 for i=1:n for j=1:n end end for k=1:n for i=1:n for j=1:n if a(i,j)>a(i,k)+a(k,j) a(i,j)=a(i,k)+a(k,j); end end end end %dist=a(s,e),s为起点,e为终点 flag=[]; maxn=0; %未升级覆盖二级供水站数 num=0; %升级的二级供水站数 for i=2:lm for j=14:l if a(i,j)<=40&&ismember(j-13,flag)==0 flag=[flag j-13]; maxn=maxn+1; end end end x=zeros(1,168); maxs=zeros(1,168); %需要升级的二级供水站序号 while maxn<168-num num=num+1; D=nchoosek(1:168,num); %需要升级的二级供水站组合 for s=1:length(D) change=D(s,:); for i=1:num x(i)=change(i:i)+13; end for i=14:l for k=1:num if i==x(k) %升级后更改带权邻接矩阵信息 a(1,i)=sqrt(sum((C(1,:)-C(i,:)).^2)); end end end for i=14:l for j=2:13 for k=1:num if i==x(k) a(i,j)=sqrt(sum((C(i,:)-C(j,:)).^2)); end end end end for i=14:l for j=14:l for k=1:num if i~=x(k)&&j==x(k) a(i,j)=inf; end if i==x(k)&&j~=x(k) a(j,i)=inf; end end end end count=0; flag=[]; for i=2:lm for j=14:l for k=1:num if a(i,j)<=40&&j~=x(k)&&ismember(j-13,flag)==0 flag=[flag j-13]; count=count+1; end end end end for i=14:l for j=14:l for k=1:num if a(i,j)<=40&&i==x(k)&&j~=x(k)&&ismember(j-13,flag)==0 flag=[flag j-13]; count=count+1; end end end end maxn=count; for i=1:num %更改需要升级的二级水站信息 maxs(i)=x(i); end if maxn>=168-num break; end end end num flag for i=1:num maxs(i) end问题结果 问题一：最短的总里程数为total=540.9142公里 问题二：利用第一问的思想，将168个二级供水站中任意选取两个供水站使之升级成一级供水站，列举出所有的情况，利用Prim算法求出所有方案的距离，逐一比较，发现最短的是将P14和P15升级为一级供水站点，最短距离为mindist=538.6416公里，比第一问少了2.2726公里。 问题三：不需要修改升级任何二级站点，便可以实现对所有站点的供水。 故总管道距离依旧是第一问的540.9142公里。
以上就是本人在参加学校数学建模校内选拔赛后想要分享的内容。 第一次写技术文档，还有很多不足之处请多多包涵，谢谢！
