数学建 模课后作业

《数学建 模课后作业》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数学建模实验P.172实验二最短电缆长度问题设有九个节点，它们的坐标分别为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)任意两个节点之间的距离为：wi,j=xi-xj+

2、yi-yj

3、问：怎样连接电缆，使每个节点都连通，且所用的总电缆的长度为最短.问题分析：本题研究的是一个最优化问题。问题中给出了9个节点坐标，需要从复杂的连接方案中选出最短的电缆连接路线。要设计方案求最短电缆长度，可先求出任意两点间的距离，然后在构造边权矩阵，用prim算法求电缆线的最优连通方案。符

4、号说明：W：任意两点之间的距离矩阵X:节点的横坐标Y：节点的纵坐标解：先计算出任意两点间的距离；W=[];X=[0516203323352510];Y=[152024202511703];N=length(X);fori=1:Nforj=1:NW=[W;(abs(X(i)-X(j))+abs(Y(i)-Y(j)))]endendW'输出结果截图为：将结果整理列表如下：w(I,j)abcdefghia01025254327434340b015153327434022c081820363327d01812282527e024203321f0161329g01729h01

5、8i0用prim算法求电缆线的最优连通方案；运行结果截图为：分析结果可知：最小生成树的边集合为{（1,2），（2,3），(3,4),（4,6），（6,8），(6,7)，(3,5)，(8,9)}即用prime算法求出的最优电缆连接方案为：{（a,b），（b,c），（c,d），（d,f），（f,h），(f,g)，(c,e)，(h,i)}。P186实验一求最短路问题求图14.9所示有向网络中自点1到点6的最短有向路问题分析：用floyde算法算出任意两点之间的最短的距离。符号说明：D：任意两个点之间的最短距离n:迭代次数解：function[D,path]=floyd(a

6、)n=size(a,1);%设置D和Path的初值D=a;path=zeros(n,n);fori=1:nforj=1:nifD(i,j)~=infpath(i,j)=j;%j是i的后继点endendend%做n次迭代,每次迭代均更新D(i,j)和path(i,j)fork=1:nfori=1:nforj=1:nifD(i,k)+D(k,j)

7、infinfinf05inf;infinfinfinf02;infinfinfinfinf0];[D,path]=floyd(a)运行结果截图为：D=0593810Inf04277InfInf0243InfInfInf057InfInfInfInf02InfInfInfInfInf0path=122444023443003456000455000056000006由运行结果得：因为path(1,6)＝4，意味着顶点1的后继点为4，path(4,6)＝5，从而顶点4的后继点为5，同理，因path(5,6)＝6，从而顶点5的后继点为6，故1→4→5→6便是顶点1到顶点6

8、的最短路径。所以，顶点1到顶点6最短路径长度为D（1,6）=10：即最短路径：1—4—5—6。即：Path(1,6)/4Path(1,6)/4Path(4,6)/5Path(5,6)/6Path(6,6)/6