数学建模第六次179.doc

数学建模 第四篇 网络图论建模作业段承承 20131060179 通信工程十三章实验二 最短电缆长度问题一、问题重述：设有9个节点，它们的坐标分别为a(0,15)、b(5,20)、c(16,24)、d(20,20)、e(33,25)、f(23,11)、g(35,7)、h(25,0)、i(10,3)。任意两个节点之间的电缆长度为w(i,j)=|xi-xj|+|yi-yj|问：怎样连接电缆，使每个节点都连通，且所用的总电缆长度为最短？二、模型假设三、变量说明4、 分析五、模型的建立十四章实验二 剧场设置问题一、问题重述：准备在v1,v2,v7七个居民点中设置一个剧场。各个居民点之间距离和连接关系如图14.10所示。问剧场应该设置在哪一个居民点，使各点到剧场的距离之和为最小？若要设置两个售票处，问应该设在哪两个点？2、 模型假设1、 忽略建造费用在各个点处的不同带来的影响2、 忽略居民点人口密度和人口流量对剧场设置的影响三、分析问题1：计算各列之和，表示各点到第点之和。 计算。则点可作为剧场。计算得各列和为 34.6, 20.6, 25, 27.0, 37.2,23.2, 18.1, 29.1, 32.1显然选作剧场最好，各居民点到剧场的最小距离为18.1。问题2：计算任意点到两点的距离， 则各点到点距离为 所求点容易求得所求两点为4或6，各点到该两点最小距离为13.30四、代码及结果：由于第一点位置不容易看出与其他点的最短路径，因此我先用Dijkstra算法算出点到其余各点的最短路径。MATLAB代码：w= 0 3 inf inf inf inf inf; 3 0 2 inf inf 1.5 inf; inf 2 0 6 4 2.5 inf; inf inf 6 0 3 inf inf; inf inf 4 3 0 1.8 inf; inf 1.5 2.5 inf 1.8 0 3;n=size(w,1);w1=w(1,:);%赋初值for i=1:n dist(i)=w1(i); path(i)=1;ends=;s(1)=1;u=s(1);k=1distpathwhile kdist(u)+w(u,i) dist(i)=dist(u)+w(u,i); path(i)=u; end end endend distpath%求v*distdist=dist;for i=1:n for j=1:k if i=s(j) distdist(i)=distdist(i); else distdist(i)=inf; path(i)=u; end endend distv=inf;for i=1:n if distdist(i)distv distv=distdist(i); v=i; endenddistvvs(k+1)=vk=k+1u=s(k)enddistpath输出结果：k =1dist =0 3 Inf Inf Inf Inf Infpath =1 1 1 1 1 1 1dist =0 3 Inf Inf Inf Inf Infpath = 1 1 1 1 1 1 1distv =3v =2s =1 2k = 2u =2dist =0 3.0000 5.0000 Inf Inf 4.5000 Infpath =1 1 2 1 1 2 1distv =4.5000v =6s =1 2 6k = 3u = 6dist = 0 3.0000 5.0000 Inf 6.3000 4.5000 7.5000path =2 2 2 1 6 2 6distv =5v =3s = 1 2 6 3k =4u = 3dist =0 3.0000 5.0000 11.0000 6.3000 4.5000 7.5000path =6 6 2 3 6 6 6distv =6.3000v =5s =1 2 6 3 5k = 5u =5dist =0 3.0000 5.0000 9.3000 6.3000 4.5000 7.5000path = 3 3 3 5 6 3 6distv = 7.5000v =7s = 1 2 6 3 5 7k =6u = 7dist =0 3.0000 5.0000 9.3000 6.3000 4.5000 7.5000path =5 5 5 5 5 5 6distv =9.3000v = 4s =1 2 6 3 5 7 4k =7u = 4dist =0 3.0000 5.0000 9.3000 6.3000 4.5000 7.5000path =7 7 7 5 7 7 7知：dist = 0 3.0000 5.0000 9.3000 6.3000 4.5000 7.5000为到其余各点的最短路径。接下来开始进入正式计算：%剧场选址问题%剧场选址问题D=0 3 5 9.3 6.3 4.5 6.5; 3 0 2 6.3 3.3 1.5 4.5; 5 2 0 6 4 2.5 5.5; 9.3 6.3 6 0 3 4.8 7.8; 6.3 3.3 4 3 0 1.8 4.8; 4.5 1.5 2.5 4.8 1.8 0 3 ; 6.5 4.5 5.5 7.8 4.8 3 0 ; %问题1S=sum(D);d,v=min(S);fprintf(剧场为%2d点,最短距离为%6.2fn,v,d); %问题2(求两售票处位置) V=;for i=1:6 for j=i+1:7 s=sum(min(D(:,i),D(:,j); V=V;i,j,s;%获得各点到(i,j)的最小距离 end;end;d