剧团选址问题.docVIP

剧团选址问题 准备在八个居民点中设置一个剧场,各个居民点之间的距离和连接关系如下图,问剧场应设在哪一个居民点，使各点到剧场的距离和最小?若要设置两个售票处，应设在哪两个点？三个售票处呢？ 图1 居民点分布图 解：作距离矩阵，表示和之间的距离。 容易得到： 问题1：计算各列之和，表示各点到第点之和。 计算。则点可作为剧场。 计算得各列和为 [39.1, 21.1, 27.5, 27.0, 44.0, 20.1, 29.1, 33.1] 显然选作剧场最好，各居民点到剧场的最小距离为20.1。 问题2：到两点的距离， 则各点到点距离为 所求点 容易求得所求两点为(2,4)或(2,5)，各点到该两点最小距离为14.5 问题3：同理可得所求三点为(2,5,6)，各点到该三点最小距离为10.3。 计算的Matalb程序: %剧场选址问题 %剧场选址问题 D=[0,3,5,6.3,9.3,4.5,6,5; 3,0,2,3.3,6.3,1.5,3,2; 5,2,0,4,6,2.5,4,4; 6.3,3.3,4,0,3,1.8,3.3,5.3; 9.3,6.3,6,3,0,4.8,6.3,8.3; 4.5,1.5,2.5,1.8,4.8,0,1.5,3.5; 6,3,4,3.3,6.3,1.5,0,5; 5,2,4,5.3,8.3,3.5,5,0]; %问题1 S=sum(D); [d,v]=min(S); fprintf(剧场为%2d点,最短距离为%6.2f\n,v,d); %问题2(求两售票处位置) V=[]; for i=1:7 for j=i+1:8 s=sum(min(D(:,i),D(:,j))); V=[V;i,j,s;];%获得各点到(i,j)的最小距离 end; end; [d,n]=min(V(:,3));%求最小值所在行 fprintf(两售票处为(%2d,%2d),最小距离为%5.2f\n,V(n,1),V(n,2),V(n,3)); %问题3(求三售票处位置) VV=[]; for i=1:6 for j=i+1:7 for k=j+1:8 s=sum(min(D(:,i),min(D(:,j),D(:,k)))); VV=[VV;i,j,k,s;];%获得各点到(i,j,k)的最小距离 end; end; end; [d,n]=min(VV(:,4));%求最小值所在行 fprintf(三售票处为(%2d,%2d,%2d),最小距离为%5.2f,... VV(n,1),VV(n,2),VV(n,3),VV(n,4));