您好,欢迎访问三七文档
1/22数学软件与数学实验实训报告学生姓名1邱振涛年级学号12010级218学生姓名2陈玲年级学号22010级205完成日期2011-12-162/22一、实训内容1、求最短路的迪克斯特拉算法matlab实现所求任意一段都是最短路。2、穿越荒漠一探险家计划独身徒步穿越荒漠,探险家每天可步行40km,除行装,最多可携带总量为20kg的食物和水,探险家每天消耗1.5kg水和1kg食物。问题(1):根据已有资料,穿越荒漠的行程为480km,问探险家如何在中途建立食物和水的储藏点以确保探险家尽快安全穿越荒漠,给出探险家的日程计划。问题(2):根据最新资料,在距离终点200km处有可饮用泉水,如何修改原计划,给出新的日程计划。二、第1题解题思路看到这一幅图,我们可以直观的知道相邻两点之间的距离,现在我们要求的是每一点和u1的最短距离。首先我们要把我们输入的下标和他们的直接距离转换成带权邻接矩阵,这个不难实现,只要生成相对应的零矩阵,在将直接距离赋值到相对应的位置,没有直接距离的赋值为无穷大。在通过邻接矩阵,我们通过for循环我们依次求出每个点和u1的最短距离。将无穷大看作1u2u3u4u7u5u8u9u6u219987436355216153/22是很大的数,比如1000或者10000,第一个循环先计算出每一个点与u1通过一个点作为中转点这条路的距离和两点的直接距离比较,取较小值记录赋值并记录前驱顶点。接着是第二个循环,我们要到的终点通过两个中转站从u1到达,通过for比较这条路径的距离和上一个循环所保留的数据相对应比较,留下较小的,在记录数据和前驱顶点。依次类推,循环n-2次,n为顶点的个数。最后我们可以得出个顶点之间的最短距离和前驱顶点。三、第1题程序清单和测试结果functionroute=sroute1(A)%文件名n1=size(A,1);%求A的行数n2=size(A,2);%求A的列数fori=1:n1forj=1:(n2-1)n3=max(A(i,j));%求顶点数endendW=zeros(n3,n3);%生成一个对应的零矩阵fori=1:n1W(A(i,1),A(i,2))=A(i,3);W(A(i,2),A(i,1))=A(i,3);%将对应顶点间的距离放在矩阵对应的位置endfori=1:n3forj=1:n3if(i~=j)ifW(i,j)==0W(i,j)=1000;%生成对应的带权连接矩阵endendendendn=size(W,1);%计算W的行数W1=W(1,:);fori=1:nl(i)=W1(i);%将W的第一行赋值于各顶点的起始最短距离z(i)=1;%将前驱顶点起始的赋值为1endfori=1:nforu=1:nifl(i)l(u)+W(u,i)%判断两顶点之间直接距离和通过另一个顶点作为枢纽到达的距离谁更小l(i)=l(u)+W(u,i);%取更小的那一条路线z(i)=u;%前驱顶点在此改变endforj=2:n4/22ifl(i)W(u,j)+W(j,i)+l(u)%判断两顶点之间直接距离和通过另外两个顶点作为枢纽到达的距离谁更小l(i)=W(u,j)+W(j,i)+l(u);%取更小的那一条路线z(i)=j;%前驱顶点在此改变endforq=1:nifl(i)l(u)+W(u,j)+W(j,q)+W(q,i)%判断两顶点之间直接距离和通过另外三个顶点作为枢纽到达的距离谁更小l(i)=l(u)+W(u,j)+W(j,q)+W(q,i);%取更小的那一条路线z(i)=q;%前驱顶点在此改变endendendendendl%输出最短距离z%输出前驱顶点A=[122;138;141;236;251;347;355;361;372;479;563;589;674;686;695;785;793;895];sroute1(A)l=02713691211z=116125356四、第2题解题思路拿到题目,我们就有个概念!480千米的路程由于所带食物和水有限,不可能一次到达!又得考虑到探险家的身体状况,保持健康的状态。接着我们考虑设定中转站,来回反复才能到达我们的目的地!但要求出如何设定储藏点才能更节省时间呢?于是可列出公式:问题(1):(1)设置一个储藏点:探险家每次最多可携带总量为20千克的食物,每公里消耗食物1/16千克,ABCn1x2x5/22则每次携带的食物可供走320千米。最后一段最多可走320千米,于是设置一个储藏点最近只能是在距离终点320千米的地方,可若是这样,则x1最小是160千米,我们可设想在160千米出设置一个储藏点,那他所带的粮食只够他与这个储藏点来回走而不能储藏粮食,所以不能走出沙漠!1x+2x=480;andxdxn21)12(n为非负整数21,xx0;(2)设置两个储藏点:第一段路上的消耗量+第二段将要运送量第一段实际运送量;第二段路上的消耗量+第三段将要消耗量第二段实际运送量;可以此列出函数式并建立模型:min32211)12()12(xxnxnf,s.t.480321xxx,anandxn1211)12(,andxdxn2322)12(,,0,,321xxx21,nn取非负整数。(3)设置三个储藏点:ABC1n1x2xD2n3x6/22第一段路上的消耗量+第二段将要运送量第一段实际运送量;第二段路上的消耗量+第三段将要运送量第二段实际运送量;第三段路上的消耗量+第四段将要消耗的量第三段实际运送量;min4332211)1(2)12()12(xxnxnxnf,s.t.4804321xxxx,anandxn1211)12(,anandxn2322)12(andxdxn3433)12(,,0,,,4321xxxx21,nn3n取非负整数(4)设置四个储藏点:第一段路上的消耗量+第二段将要运送量第一段实际运送量;第二段路上的消耗量+第三段将要运送量第二段实际运送量;第三段路上的消耗量+第四段将要运送量第三段实际运送量;3nABC1n1x2xD2n3xE3nF4n4x5xABC1n1x2xD2n3xE3n7/22第四段路上的消耗量+第五段将要消耗量第三段实际运送量;min543332211)12()1(2)12()12(xxnxnxnxnf,s.t.48054321xxxxx,anandxn1211)12(,anandxn2322)12(anandxn3433)12(,andxdxn4544)12(,,0,,,,54321xxxxx21,nn3n4n取非负整数。接着我们一一运行程序,先观察这些程序有什么共同点。若有共同点则较容易得多,若没有我们在加大程序的实践量!接着就运行程序,看结果。问题(2):(1)设置两个储藏点:考虑到在DB段有饮用水,且需消耗5kg食物,我们可以设在D点之后无再须水源。探险家平均每公里消耗水量w=1.5/40,平均每公里消耗食物量f=1/40;第一段路上的耗水量+第二段将要运送水量第一段实际运送水量;第二段路上的耗水量第二段实际运送水量;第一段路上的耗食物量+第二段将要运送食物量第一段实际运送食物量;第二段路上的耗食物量+第三段消耗食物量第二段实际运送食物量;每次背的食物和水量都不能超过20kg。可建立模型列出公式:min200)12()12(2211xnxnfABC1n1x2xD2n3x8/22s.t.28021xx,wnwnwxn12211)12(,2222)12(wnwxn112211)12(fnfnfxn,22225)12(fnfxn,,2011fw2022fw,0,,,,,212121ffwwxx21,nn取非负整数。(2)设置三个储藏点:根据人体饥饿情况和路上消耗的食物,保证探险家保持健康状态穿越荒漠,可列出条件:第一段路上的耗水量+第二段将要运送水量第一段实际运送水量;第二段路上的耗水量+第三段将要运送水量第二段实际运送水量;第三段路上的耗水量第二段实际运送水量;第一段路上的耗食物量+第二段将要运送食物量第一段实际运送食物量;第二段路上的耗食物量+第三段将要运送食物量第二段实际运送食物量;第三段路上的耗食物量+第四段消耗食物量(5)第三段实际运送食物量;每次背的食物和水量都不能超过20kg。可建立模型列出公式:ABC1n1x2xD2n3xE3n9/22min200)12()12()12(332211xnxnxnfs.t.280321xxx,112211)12(wnwnwxn,223322)12(wnwnwxn3333)12(wnwxn112211)12(fnfnfxn,223322)12(fnfnfxn33335)12(fnfxn,,2011fw2022fw2033fw,0,,,,,,,,321321321fff取非负整数。五、第2题程序清单和测试结果fmincon:找到最小值问题1:(1)设置一个储藏点:探险家每次最多可携带总量为20千克的食物,每公里消耗食物1/16千克,则每次携带的食物可供走320千米。最后一段最多可走320千米,于是设置一个储藏点最近只能是在距离终点320千米的地方,可若是这样,则x1最小是160千米,我们可设想在160千米出设置一个储藏点,那他所带的粮食只够他与这个储藏点来回走而不能储藏粮食,所以不能走出沙漠!1x+2x=480;2x/1620-1x/16+(20-1x/8)×n20n为非负整数1x0;10/22(2)设置两个储藏点function[c,cep]=myconl(x)%文件名l=480;a=20;d=2.5/40;%已知条件c=[(2*x(4)-1)*x(1)*d+x(5)*a-x(4)*a;(2*x(5)-1)*x(2)*d+x(3)*d-x(5)*a];%非线性不等式条件约束cep=[];%无非线性等式条件x0=[100,100,280,10,5]';%给你个较合适的初值条件A=[];%无线性不等式约束b=[];Aeq=[11100];%线性等式约束beq=[480];lb=[0016022]';%下界ub=[1601603202010]';%上界(由于x1和x2需要来回走动,所以上节是160)[x,fval]=fmincon('(2*x(4)-1)*x(1)+(2*x(5)-1)*x(2)+x(3)',x0,A,b,Aeq,beq,lb,ub,@myconl)%求解最优解Warning:Large-scale(trustregion)methoddoesnotcurrentlysolvethistypeofproblem,switchingtomedium-scale(linesearch).Infminconat271Optimizationterminated:first-orderoptimalitymeasurelessthanoptions.TolFunandmaximumconstraintviolationislessthanoptions.TolCon.Activeinequalities(towithinoptions.TolCon=1e-006):lowerupperineqlinineqnonlin5312x=53.3333106.6667320.00002.75002.0000fval=880.0000由于趟次是没有小数的,所以n1应取大于它的整数,增加两个约束条件.31n优化:x0=[100,
本文标题:数学建模案例
链接地址:https://www.777doc.com/doc-6915951 .html