数学模型实验报告

《数学模型实验报告》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数学模型实验报告数学建模实验报告最短路问题及其算法最短路问题及其算法一.实验目的：1、了解与掌握图论的基本概念、相关MATLAB知识和最短路径算法；2、学会使用MATLAB编写Dijkstra算法和Floyd算法程序求最短路径.二.实验内容：要铺设一条A1→A2→…→A15的输送天然气的主管道，如图所示.经筛选后可以生产这种主管道的钢厂有S1，S2,…,S7.图中粗线表示铁路，单细线表示公路，双细线表示要铺设的管道（假设沿管道或者原来有公路，或者建有施工公路），圆圈表示火车站，每段铁路、公路和管道旁的阿拉伯数字表示里程（单位：km）

2、.为方便计，1km主管道钢管称为1单位钢管.一个钢厂如果承担制造这种钢管，至少需要生产500单位钢厂Si在指定期限内能生产刚钢管的最大数量为si个单位.钢管出厂销价1单位钢管为pi万元，如下表：1单位钢管的铁路运价如下表：1000km以上每增加1至100km运价增加5万元.公路运输费用为1单位钢管0.1万元每千米（不足整千米部分按整千米计算）.假设从钢厂S2订购钢管运输到铺设地点A5和A6.钢厂S2在指定期间内能生产该钢管的最大数量为s2?800个单位，钢管出厂销价1单位钢管为155万元.wilyes11收集博客(与学习无关)：ht

3、tp://blog.sina.com.cn/u/1810231802S2A5试制定一个从钢厂S2到铺设地点A5和A6的钢管的订购与运输计划，使总费用最小.三.模型建立设S2为V1,将上图按从上到下，从右到左的顺序依次命名如下.将上图改为如下赋权图形G：V10V8V5V3V2利用Dijkstra算法和Floyd算法：求G中从顶点V1到其余顶点的最短路.而求钢厂S2到铺设地点A5和A6的最短距离，即为V1到V10和V8的最短距离1解：先写出带权邻接矩阵：1200??????????0?1200?012202??????????120?2

4、01?????????202?03120?????????20131010?205???M??????20100195???????????19505306???????205?50?194??????????306?010??????????194100????后分别用Dijkstra算法和Floyd算法步骤，求出V1到V10和V8的最短路的权l(V)以及V的父亲点标记z(V).四.模型求解（含经调试后正确的源程序）(1)Dijkstra算法road1.m文件源程序：w=[01200infinfinfinfinfinfinfinf

5、;1200012202infinfinfinfinfinf;inf120inf201infinfinfinfinf;inf202inf03120infinfinfinf;infinf20131010inf205infinf;infinfinf20100195infinfinf;infinfinfinfinf19505306inf;infinfinfinf205inf50inf194;infinfinfinfinfinf306inf010;infinfinfinfinfinfinf194100];n=size(w,1);w1=w(1,

6、:);fori=1:nl(i)=w1(i);z(i)=1;ends=[];s(1)=1;u=s(1);k=1;l;z;whileknfori=1:n2forj=1:kifi~=s(j)ifl(i)l(u)+w(u,i);l(i)=l(u)+w(u,i);z(i)=u;endendendendl;z;ll=l;fori=1:nforj=1:kifi~=s(j)ll(i)=ll(i);elsell(i)=inf;endendendlv=inf;fori=1:nifll(i)lvlv=ll(i);v=i;endendlv;v;s(k+1)

7、=v;k=k+1;u=s(k);endlz(2)Floyd算法road2.m文件源程序：a=[01200infinfinfinfinfinfinfinf;1200012202infinfinfinfinfinf;inf120inf201infinfinfinfinf;inf202inf03120infinfinfinf;infinf20131010inf205infinf;infinfinf20100195infinfinf;3infinfinfinfinf19505306inf;infinfinfinf205inf50inf194

8、;infinfinfinfinfinf306inf010;infinfinfinfinfinfinf194100];[D,R]=floyd(a)floyd.m文件源程序：function[D,R]=floyd(a)n=size(a,1