1MATLAB求解图与网络模型目的：掌握利用MATLAB求解图与网络模型的基本步骤和方法等。说明：先看一下课件“上机5_Matlab求解图与网络模型.ppt”完成下述图论相关的题目，模型求解可用MATLAB、LINGO或其它自编程序。【卫生站选址问题】某县要在其所辖的14个乡镇：V1，V2,⋯,V14，新建卫生站（建在乡镇），为14个乡镇服务，要求卫生站至最远乡镇的距离达到最小。假设该14个乡镇之间的交通网络被抽象为下图所示的无向赋权连通图，权值为乡镇之间的距离。1)如果修建一个卫生站，该卫生站应设在哪个乡镇，即哪个顶点？2)修建卫生站后，找出该卫生站到最近，最远乡镇的路径。3)如果修建两个卫生站，使最大服务距离最小，卫生站又该设在哪两乡镇，即哪两顶点？4)把14个乡镇用高压电缆连接起来建立一个电网,使所用的电缆长度之和最短,即总费用最小。图113个乡镇及交通网络示意图%以下MATLAB代码给出图的定义并绘制s=[1,1,1,1,2,2,2,3,3,4,5,6,7,7,7,8,8,8,9,10,11,11,12,13];t=[2,4,5,7,3,5,6,6,9,7,8,8,8,10,12,9,13,14,14,11,12,13,13,14];w=[13,8,12,15,8,13,10,9,16,8,10,12,12,13,6,7,14,8,10,7,7,9,10,12];G=graph(s,t,w);x=[32,40,41,24,27,32,18,19,25,7,8,14,6,15];y=[26,16,8,26,16,10,21,9,5,26,20,17,11,3];nlabels=cell(14,1);fork=1:14nlabels{k,1}=['V'num2str(k)];end;h=plot(G,'EdgeLabel',G.Edges.Weight,'NodeLabel',nlabels,'xdata',x,'ydata',y,'LineWidth',2);V1V2V3V4V5V6V7V8V9V10V11V12V13V14138121581310910916121278101412791071362参考解答：首先构建图模型：G=(V,E),其中顶点集合V={vi,i=1..14},边集合E={eij,i,j=1..14}vi表示题中第i个乡镇，eij表示题中第i和第j个乡镇的路径相连情况，eij=1表示直接相连，eij=0表示不直接相连记dij=ShortestPathDistance(vi,vj)，即dij表示vi与vj之间最短路径的距离定义最短路径距离矩阵为D=(dij)14x14（1）如果修建一个卫生站，该卫生站应设在哪个乡镇，即哪个顶点？（2）修建卫生站后，找出该卫生站到最近、最远乡镇的路径。优化目标：最大服务距离最小kjkjkdmaxminMATLAB程序：[~,k]=min(max(D));dist=D(k,:);%卫生站到其它所有乡镇的最短路距离[~,idx_far]=max(dist);dist2=dist;dist2(k)=inf;[~,idx_near]=min(dist2);[path_far,dist_far]=shortestpath(G,k,idx_far);[path_near,dist_near]=shortestpath(G,k,idx_near);fprintf('如果修建一个卫生站，该卫生站应设在乡镇:V%d\n',k);%Computethematrixofshortestpathdistancesbetweenallnodepairsinthegraph.D=distances(G)3fprintf('该卫生站到最近乡镇距离为：%d,路径为:%s\n',dist_near,num2str(path_near));fprintf('该卫生站到最远乡镇距离为：%d,路径为:%s\n',dist_far,num2str(path_far));h=plot(G,'EdgeLabel',G.Edges.Weight,'NodeLabel',nlabels,'xdata',x,'ydata',y,'LineWidth',2);highlight(h,k,'Marker','s','MarkerSize',10);highlight(h,path_near,'EdgeColor','red');highlight(h,path_far,'EdgeColor','blue');计算结果：（3）如果修建两个卫生站，使最大服务距离最小，卫生站又该设在哪两乡镇，即哪两顶点？假设两个卫生站修建在k1,k2两个乡镇优化目标：),min(maxmin212121,,jkjkkkjkkddMATLAB程序：candidates=[]fork1=1:13fork2=(k1+1):14dist1=D(k1,:);dist2=D(k2,:);dist=min([dist1;dist2],[],1);candidates=[candidates;k1k2max(dist)];4endend[~,c_idx]=min(candidates(:,3));k1=candidates(c_idx,1);k2=candidates(c_idx,2);fprintf('修建两个卫生站则应设在乡镇V%d和V%d，可使最大服务距离取得最小为%.1f\n\n',k1,k2,candidates(c_idx,3));h=plot(G,'EdgeLabel',G.Edges.Weight,'NodeLabel',nlabels,'xdata',x,'ydata',y,'LineWidth',2);highlight(h,k1,'Marker','s','MarkerSize',10,'NodeColor','red');highlight(h,k2,'Marker','s','MarkerSize',10,'NodeColor','green');fprintf('乡镇编号卫生站服务距离\n');fork=1:14ifk~=k1&&k~=k2ifD(k1,k)
