数学建模实验报告3

桂林电子科技大学2017-2018学年第1学期数学建模实验名称实验三、利用MATLAB进行图形建模和求解检查情况：成绩教师签名：院系计算机与信息安全学院专业计算机科学与技术学号姓名同作者实验日期2017年12月24日一、实验目的使用课上讲的网络优化知识，在实验中建立模型，求解。掌握有关最短路问题的分析、建模与求解方法。掌握Dijkstra等算法，并运用算法求一些最短路径的问题二、实验内容题目11、在一个城市交通系统中取出一段如图所示，其入口为顶点v1，出口为顶点v8，每条弧段旁的数字表示通过该路段所需时间，每次转弯需要附加时间为3，求v1到v8的最短时间路径。分析：考虑到”每次转弯需要附加时间3”,所以把需要转弯的边附加上2×3时间，如果邻边已经附加转弯时间了，就不需要附加转弯时间，所以在V2和V4,V5和V7,V6和V8这三条边附加时间6。通过实验后，使用了老师所说的Matlab求最短路径的函数，功能很好用。程序：S=[1223556477];%起始节点向量W=[1831869284];%终止节点向量E=[2435768758];%终止节点向量G=sparse(S,E,W);%关联矩阵的稀疏矩阵表示G(8,8)=0;%8个节点P=biograph(G,[],'ShowWeights','on');%建立有向图对象PH=view(P);%显示各个路径权值[Dist,Path]=graphshortestpath(G,1,8,'Method','Dijkstra')%求节点1到节点8的最短路径实验结果:Dist=15Path=V1V2V3V5V62V7V8V422123163412478各个路径的权值因此最短路径为1→2→4→7→8，长度为15。题目2有四个工件等待在同一台机器上加工，若加工的先后次序可以任意，各工件之间的调整时间如下表，试确定最优加工顺序。从到ABCDA—15205B30—3015C2525—15D203510—分析模型假设：设由A,B,C,D之间的调整时间作为权值，构成邻接矩阵L。模型建立：要求出A,B，C，D之间的最优加工顺序，首先从任意选取一条路径假设为最优的，其次，依次从A，B，C，D排列循环，找到调整时间总和mi最小的路径functiony=zuhe(l)l=[015205300301525250162035100];n=length(l(1,:));%l为A,B,C,D之间构成的邻接矩阵y=zeros(1,n);mi=l(1,2)+l(2,3)+l(3,4);%假设最优顺序为A→B→C→D，mi为最短调整时间fori=1:n%从A到D依次开始forj=1:nif(i~=j)fors=1:nif(j~=s&&s~=i)fort=1:nif(t~=s&&t~=i&&t~=j)ifmil(i,j)+l(j,s)+l(s,t)mi=l(i,j)+l(j,s)+l(s,t);y(1)=i;y(2)=j;y(3)=s;y(4)=t;endendendendendendendend实验结果:Mi=40ans=1243则可知最优加工顺序为：A→B→D→C加工调整时间最小为：40三、实验总结通过本次实验，彻底的理解了Dijkstra算法，并能分析、建立模型，把实际问题变成可求解的数学问题，运用数学建模的图论知识求解实际的问题。深深的体会到分析并建模是求解的关键，也是数学建模中最难掌握，只有大量的练习才能掌握。