数学模型课程设计.doc

【精品文档】如有侵权，请联系网站删除，仅供学习与交流数学模型课程设计.精品文档.课程设计（论文）任务书学 院理 学 院专 业信息与计算科学学生姓名杨阳班级学号0609010224课程名称数学模型课程设计课 程 设 计（论文）题目垃圾运输问题设计要求（技术参数）：1. 建模：要求思路清晰、处理恰当、构思新颖。2. 分析：数学应用合理恰当，应用知识综合，内容丰富。3. 结论：要有一定的广度、深度、实用程度。4. 表达：文字通顺、语言流畅、论述简洁、推理严谨。设计任务：用所学过的数学建模知识，上网查阅相关资料，对现实生活中的某一个实际问题，建立数学模型，分析并解决提出的问题。（可结合自己解决的问题展开）并以MATLAB或者其他数学软件为工具，对所建模型进行求解，程序源码要在附录中给出。论文篇幅要在15页以上。计划与进度安排：第一周：第一阶段：上网查阅相关资料第二阶段：建立模型第二周：第三阶段：模型求解及优化第四阶段：撰写论文指导教师（签字）：年 月 日专业负责人（签字）：年 月 日主管院长（签字） 年 月 日摘要该题我们的主要解题思路分三阶段：第一阶段，我们先根据题设条件和基本假设画出该题的图。第二阶段，我们根据图和点的位置关系结合题设，归纳出一些最基本的确定路线的原则：在仔细分析该题后，我们认为该题为一个单目标规划题。我们先抛开空载费用，若要把所有的垃圾运回垃圾处理站，这部分有效工的费用为1.8|Xi|Yi(|Xi|为垃圾点Xi到原点的距离,Yi为垃圾点的垃圾量)，是恒定不变的。只要我们能保证空载路线最小，则所花的时间和费用都最小。因此解题的关键在于找出一个调度方案，使空载行驶的线路最小。第三阶段则是编制程序阶段，采用计算机模拟搜索的计算方法，搜索出运输车投入辆数以及运输车最佳调配方案，使得在不考虑铲车的情况下运营费用最低。总运营费用为运输车空载费与实际运输费之和。问题的解答如下：第一问，求得所需总费用为2345.4元，所需总时间为22.5小时，路线分配图见正文；第二问，求得需3辆铲车，铲车费用为81.6元，分配图及运输车调度表见正文；第三问，运营总费用为：2325.8，其中8吨、6吨、4吨载重量的运输车各需5、2、3辆，路线分配图见正文。关键词 单目标优化 计算机搜索目录一、问题重述1二、问题分析1三、名词解释2四、模型建立与求解341、模型假设342、参数说明343、模型的建立444、模型的求解5五、模型评价与推广2051、模型评价2052、模型推广20六、参考文献20七、附件21一、问题重述某城区有 36 个垃圾集中点，每天都要从垃圾处理厂（第 37 号节点）出发将垃圾运回。现有一种载重 6 吨的运输车。每个垃圾点需要用 10 分钟的时间装车，运输车平均速度为 40 公里小时（夜里运输，不考虑塞车现象）；每台车每日平均工作 4 小时。运输车重载运费 1.8 元 / 吨公里；运输车和装垃圾用的铲车空载费用 0.4 元 / 公里；并且假定街道方向均平行于坐标轴。请你给出满意的运输调度方案以及计算程序。问题：1. 运输车应如何调度（需要投入多少台运输车，每台车的调度方案，运营费用）2. 铲车应如何调度（需要多少台铲车，每台铲车的行走路线，运营费用）3. 如果有载重量为 4 吨、 6 吨、 8 吨三种运输车，又如何调度？ （垃圾点地理坐标数据表见附录一）二、问题分析 垃圾运输问题最终可以归结为最优路径搜索问题，但注意到此图为森林而不是树，不能直接套用Krusal，Prim等现成算法，于是根据具体问题设计出随机下山法，用计算模拟搜索，可以搜寻到令人满意的可行解。先注意到两点的情况，设两点分别为A(x1,y1),B(x2,y2)。主要有以下两种情况：一 A,B明显有先后次序。-递减状态（如图1）不妨设x1>x2, y1>y2,不难看出A在B的后方,即A比B远。对于前方参考点O,要将A,B对应垃圾点的垃圾全部取回再返回O,一共有三种方式：1 OàAàO, OàBàO单独运输。这种情况下，总的路程消费等于空载运行费用(0.4元/公里)与装载时运行费用（1.8元/公里吨）的总和。所需的总时间等于车辆所走过的总路程与速度（40公里/小时）的比值再加上在A,B两点停留的时间(每个垃圾点上停留了10分钟，1/6小时)，于是有：2. OàAàBàO 先远点再近点，即先空载至最远处，装完A点垃圾后再返回至B,再回O点，有：3. OàBàAàO 先近点在远点，即先装B点垃圾，然后载着B点的垃圾奔至A点，再回O点，有：比较以上三种情况，远近点的遍历顺序，可以看出，“先远后近”绝对比“先近后远”在花费钱的数量上要少的多，省出1.8*|A-B|*2*Tb这部分的钱主要是车载着B点的垃圾奔到A点再返回B点。而又注意到两者的时间花费是相等的。所以在其余同等的情况下选择“先远后近”。考虑到时间上单独运输比其余的两种运输要大的多，多一一倍，而且花费的钱仍不比“先远后近”省，还多了0.4*|B|，所以一般情况下，不采用单独运输。三、名词解释|A| 表示A点到原点的距离，恒正|B| 表示B点到原点的距离，恒正|A-B| 表示A,B两点之间的距离,恒正Ta 表示A点所在地的垃圾量cost：运费；time：时间消耗；装的足够多 运输车当前的载重离限载不大于0.55吨(垃圾点的最小垃圾量)序数号 所在点的编号四、模型建立与求解41、模型假设1车辆在拐弯时的时间损耗忽略。2车辆在任意两站点中途不停车，保持稳定的速率。3只要平行于坐标轴即有街道存在。4无论垃圾量多少，都能在十分钟内装上运输车。5 每个垃圾站点的垃圾只能由一辆运输车运载。6. 假设运输车、铲车从A垃圾站到B垃圾站总走最短路线。7. 任意两垃圾站间的最短路线为以两垃圾站连线为斜边的直角三角形的两直角边之和。8. 建设在运输垃圾过程中没有新垃圾入站。9. 假设铲车、运输车载工作途中不发生意外也不遇到意外；10. 各垃圾站每天的垃圾量相对稳定。42、参数说明|A| 表示A点到原点的距离，恒正|B| 表示B点到原点的距离，恒正|A-B| 表示A,B两点之间的距离,恒正Ta 表示A点所在地的垃圾量43、模型的建立先注意到两点的情况，设两点分别为A(x1,y1),B(x2,y2)。主要有以下两种情况：二 A,B明显有先后次序。-递减状态（如图1）图 一不妨设x1>x2, y1>y2,不难看出A在B的后方,即A比B远。对于前方参考点O,要将A,B对应垃圾点的垃圾全部取回再返回O,一共有三种方式：1 OàAàO, OàBàO单独运输。这种情况下，总的路程消费等于空载运行费用(0.4元/公里)与装载时运行费用（1.8元/公里吨）的总和。所需的总时间等于车辆所走过的总路程与速度（40公里/小时）的比值再加上在A,B两点停留的时间(每个垃圾点上停留了10分钟，1/6小时)，于是有： （1） （2）2. OàAàBàO 先远点再近点，即先空载至最远处，装完A点垃圾后再返回至B,再回O点，有： （3） （4）3. OàBàAàO 先近点在远点，即先装B点垃圾，然后载着B点的垃圾奔至A点，再回O点，有： （5） （6）比较以上三种情况，远近点的遍历顺序，可以看出，“先远后近”绝对比“先近后远”在花费钱的数量上要少的多，省出1.8*|A-B|*2*Tb这部分的钱主要是车载着B点的垃圾奔到A点再返回B点。而又注意到两者的时间花费是相等的。所以在其余同等的情况下选择“先远后近”。考虑到时间上单独运输比其余的两种运输要大的多，多一一倍，而且花费的钱仍不比“先远后近”省，还多了0.4*|B|，所以一般情况下，不采用单独运输。二A，B两点没有明显先后顺序。 -并邻状态（如图2）图 二还是一共有三种情况： 1 OàAàO, OàBàO单独运输。这种情况下，跟A,B两点有先后顺序中的情况完全相同，即有： （7） （8） 2 OàAàBàO （9） （10）3.OàBàAàO （11） （12）相比之下，清晰可见并邻状态下的单独运输所花的费用最少，所以在不要求时间的情况下对于并邻两点，采用单独运输的方式最节约钱。用<1>式与<2>式相减除以1.8， 得到如下判断式：上式 < 0时， 选 0àAàBàO;上式 > 0时， 选 OàBàAàO;上式 = 0时， 任意选上述两路线。三 两点选择趋势的讨论。 （如图3）图 三由图中看到B,C两点没有明显的先后顺序，属于并邻点。因为当运输车载重行驶时费用会成倍的增长，比其空载时所花费用要大的多，所以排除AàBàC或AàCàB这样的一次经过3点的往返路线，仅选择B,C中的某一点与A完成此次运输，将另一点留到下次。那么A点选择B还是C呢？不妨假设|B|>|C|,即B点离原点的距离比C点的更远，因为A在B,C之后，所以也就是B点离A点更近。这样，此次的运输我们更趋向于选择AàB,因为就这三点而论，A无论是选B还是C，三点的垃圾总要运完，所以花费的钱是一样的。但选择AàB后，下次运输车运C点垃圾时就无需跑的更远。四 关于垃圾点的垃圾是否一次清除的讨论（以6吨车例）由假设2知，每天的垃圾必须清除完毕，全部运往37点。这里说的一次清除问题不是指一天，而是指当一辆运输车已经装载了足够多的垃圾，不能完全清理下一个垃圾点的时候，车在下一个站点“停还是不停”的问题。例如，一辆运输车选择了30à26à18à35à20的路线（即先将空车开往30，清理装载30点的垃圾，然后依次到26，18，35，20），它从20返回时车已经装载了5.8吨垃圾，仍可以装0.2吨(小于垃圾点垃圾量的最小值0.5，称这种情况为“装的足够多”)。在20点下方仍有不少的点，但肯定不能将下面的任意点的垃圾装完，那么此车是直接返回37点呢，还是继续装直至车装满为止呢？我们判断前者更好，就是车在装的足够多的情况下应该直接返回原点（37点）。这是因为对于下一垃圾点(假设为A点)内的垃圾而言，无论是一次装完还是分两次装完，将它们运回所花费用是恒定的，等于1.8*Ta*|A|。整体而言，两者花费的钱是相等的，但分两次装要多花10分钟的装车时间，所以选择前者。综上所述，得出搜索的基本原则：1 在两点递减的情况下，不采用单独运输；2 在其余同等的情况下选择“先远后近”；3 不要求时间的情况下对于并邻两点，采用单独运输的方式最节约钱；一般情况下用式<3作判断；4 车在装的足够多的情况下应该直接返回原点（37点）；每一次布局和每条线路的搜索不妨由剩下未搜点中的最大值开始。44、模型的求解问题一在不考虑铲车的情况下首先根据题所给的数据画出散点图：图 四求得总运营费用为2345.4元,总时间为22.5小时，求解程序如附录二，运输车的最优路线如下图所示：图 五站点序号空载费用所花时间一号线0-30-29-27-3-018.42.3+2/3二号线0-28-26-32-25-5-017.62.2+5/6三号线0-36-23-33-21-016.82.1+2/3四号线0-24-18-35-15-013.61.7+2/3五号线0-34-17-16-2-0121.45+2/3六号线0-20-11-10-011.21.4+1/2七号线0-19-13-8-010.81.35+1/2八号线0-14-7-4-1-08.81.1+1/2九号线0-22-08.41.05+1/6十号线0-12-9-081+1/3十一号线0-31-6-06.80.85+1/3图表 1问题二.铲车加入后的讨论 当加入铲车后,我们应该让铲车将就运输车,因为铲车的空载费用为0.4元/小时.铲车加入垃圾后为1.8元/公里小时.若改变一条线,则会造成几公里的误差,甚至十几公里的误差,这一项的数目就很大.若是铲车将就运输车,则即使路线误差大一点,但所需费用也不会变得很大.故我们以第一个方案的路线为准.这时我们只要保证前一条线路的末节点,与后一条线路的首节点的路程差分别相加之和最小即可.根据这一思路.我们设一个结构数组变量,他有11个元素(代表11条元素).其中每个元素里面有两个结构成员,这样一个元素就代表一条线路.对这11个元素进行排列,这样每一个排列就是一个线路方案.这样便能通过排列,遍历每种方案.就求出最优解.再考虑了最短路径的情况下，由于要考虑和各车在时间地衔接，以及尽量要在规定的时间内作完，我们进行相应的调整。这部分由于考虑到计算复杂性，我们用手工调整，由于前面有最短路径的保证，我们调整的结果接近最优解。程序代码如附录三【源码】程序运行结果见附录三【结果】 图 六线路时间0-30-29-27-3-0 2.3+4/60-28-26-32-25-5-02.2+5/60-36-23-33-21-02.1+4/60-24-18-35-15-0 1.7+4/60-34-17-16-2-01.45+2/30-19-13-8-01.35+1/20-20-12-9-01.0+1/20-11-10-0 0.7+1/30-31-6-00.7+1/30-14-7-4-1-00.55+4/613.5小时图表 2根据总时间和个线路的耗时，依平均工作6小时为条件得出需要三量铲车，三辆铲车的起始点分别为36 ，31 ，28；因为运输车时速为40km/h,则铲车速度无须大于40km/h.若速度小于40km/h,则至少要多买一辆铲车,这样造成重复,故最好多花点钱买大功率的铲车.为了保证能在晚上干完，我们可以多条路同时干，但考虑到新加铲车费用，我们只让三辆铲车同时工作，就能在规定时间干完。总费用为81.6元。问题三： 存在4吨，6吨，8吨三种运输车时的调度 若存在4吨,6吨,8吨三种,我们应把握的原则是:尽量让8吨的车,拉远处的垃圾,远处垃圾拉得越多,以后车的空载路程就越少,而不考虑空载费用,只把垃圾运回垃圾处理厂,它的这部分费用不变.同时，我们考虑到8吨,6吨,4吨的运输车费用问题,故8吨的车不宜太多.我们在分析过程中,发现主要是第15点比较难处理,因此8吨的车应将这一点在30那条线上一并处理.而象第2点,用6吨车单独拉一次太浪费,应用4吨车还有11,22这两条线也可改用4吨车.图 七运营总费用为：2325.8 其中运输费用是2213.4 空载费用为112.4求解程序如附录四：线路时间垃圾量30-29-27-20-11-0 2.3+5/67.828-26-32-25-14-7-02.2+17.936-23-33-21-22-02.1+5/6724-18-35-15-31-5-0 1.7+17.9534-17-16-2-01.45+2/3519-13-8-3-1-01.35+5/66.9512-9-01.0+1/34.110-0 0.7+1/61.56-00.7+1/61.34-00.55+1/61.2图表 3运输车数量8吨56吨24吨3图表 4铲车路线：铲车跟随运输厂车行驶，先行驶到远点、伴随运输车网回路行驶，铲完一趟后就寻找该离铲车最近的另外一条运输线的起始点（运输车远端），然后再跟着运输车行驶。五、模型评价与推广 5.1、模型评价然而，该问题在站点众多，运输半径较大的前提下，缺点就会显得尤为突出。首先是运输车载重的不足，当运输车的载重不能满足其中任一点的垃圾量时，模型就可能不能适用了，该模型优点是算法简单容易实现,精度特别是后两个模型的精度不是很高.前两问只要进行穷举就能得出最优解.第三问的处理原则不算很精确,有待改进5.2、模型推广该模型可以应用在很多方面，比如说货物运输、车辆分配等六、参考文献全国大学生数学建模竞赛 优秀论文汇编。中国物价出版社，2002宋兆基，徐流美等。MATLAB6.5在科学计算中的应用。清华大学出版社，2005七、附件附录一：垃圾点地理坐标数据表序号 站点编号 垃圾量T 坐标 (km) 序号 站点编号 垃圾量 T 坐标 (km) x y x y 1 1 1.50 3 2 20 15 1.40 19 9 2 2 1.50 1 5 21 32 1.20 22 5 3 3 0.55 5 4 22 22 1.80 21 0 4 4 1.20 4 7 23 23 1.40 27 9 5 6 0.85 0 8 24 24 1.60 15 19 6 5 1.30 3 11 25 25 1.60 15 14 7 7 1.20 7 9 26 26 1.00 20 17 8 8 2.30 9 6 27 27 2.00 21 13 9 9 1.40 10 2 28 28 1.00 24 20 10 10 1.50 14 0 29 29 2.10 25 16 11 11 1.10 17 3 30 30 1.20 28 18 12 12 2.70 14 6 31 31 1.90 5 12 13 13 1.80 12 9 32 21 1.30 17 16 14 14 1.80 10 12 33 33 1.60 25 7 15 20 0.60 7 14 34 34 1.20 9 20 16 16 1.50 2 16 35 35 1.50 9 15 17 17 0.80 6 18 36 36 1.30 30 12 18 18 1.50 11 17 37 37 0.00 0 0 19 19 0.80 15 12 附录二【源码】 codeclearx=3 1 5 4 0 3 7 9 10 14 17 14 12 10 7 2 6 11 15 19 22 21 27 15 15 20 21 24 25 28 5 17 25 9 9 30 0;y=2 5 4 7 8 11 9 6 2 0 3 6 9 12 14 16 18 17 12 9 5 0 9 19 14 17 13 20 16 18 12 16 7 20 15 12 0;t=1.50 1.50 0.55 1.20 0.85 1.30 1.20 2.30 1.40 1.50 1.10 2.70 1.80 1.80 0.60 1.50 0.80 1.50 0.80 1.40 1.20 1.80 1.40 1.60 1.60 1.00 2.00 1.00 2.10 1.20 1.90 1.30 1.60 1.20 1.50 1.30 0.00;i=1:37;a=1:37;plot(x,y,'*r')for ii=1:37 k=int2str(ii); k=strcat('P',k); text(x(ii),y(ii),k);endw=i;x;y;t;a;w(5,:)=0;jg=zeros(11,11);%´æ·Å11Ìõ·¾¶for i=1:20 sum=0; j1=1; s=0; m=37; i3=37; for j=1:36 if(w(2,j)+w(3,j)>s&w(5,j)=0) s=w(2,j)+w(3,j); jg(i,j1)=w(1,j); sum=w(4,j); m=j; else continue; end end w(5,m)=1; j1=j1+1; while 1 js=0; q=40; for k=1:36 if(q>w(2,m)-w(2,k)+w(3,m)-w(3,k)&w(2,m)>w(2,k)&w(3,m)>w(3,k)&(6-sum)>w(4,k)&w(5,k)=0 q=w(2,m)+w(3,m)-w(2,k)-w(3,k); js=1; jg(i,j1)=w(1,k); i3=k; else continue; end end w(5,i3)=1; sum=sum+w(4,i3); j1=j1+1; m=i3; if(w(2,i3)=0&w(3,i3)=0|js=0) break end endendkcost=0;zcost=0;allcost=0;n=0;for u1=1:11 for u2=1:11 if jg(u1,u2)=0 n=jg(u1,u2); else continue end zcost=zcost+w(4,n)*1.8*(w(2,n)+w(3,n); end n=jg(u1,1); kcost=kcost+0.4*(w(2,n)+w(3,n);endallcost=zcost+kcostzcostkcosti=1:11;time=i;time(1,:)=0;n1=0;n2=0;n3=0;for u4=1:11 for u5=1:11 if jg(u4,u5)=0 n1=jg(u4,u5); n2=n2+1; else continue end end n3=jg(u4,1); time(1,u4)=(w(2,n3)+w(3,n3)*2)/40;endn2 time 附录三源码clearx=3 1 5 4 0 3 7 9 10 14 17 14 12 10 7 2 6 11 15 19 22 21 27 15 15 20 21 24 25 28 5 17 25 9 9 30 0;y=2 5 4 7 8 11 9 6 2 0 3 6 9 12 14 16 18 17 12 9 5 0 9 19 14 17 13 20 16 18 12 16 7 20 15 12 0;t=1.50 1.50 0.55 1.20 0.85 1.30 1.20 2.30 1.40 1.50 1.10 2.70 1.80 1.80 0.60 1.50 0.80 1.50 0.80 1.40 1.20 1.80 1.40 1.60 1.60 1.00 2.00 1.00 2.10 1.20 1.90 1.30 1.60 1.20 1.50 1.30 0.00;r=1:37;%plot(x,y,'*r');%for ii=1:37 % k=int2str(ii); % k=strcat('P',k); % text(x(ii),y(ii),k);%endw=r;x;y;t;a=1:11;point=30 28 36 24 34 20 19 14 22 11 31; 3 5 21 15 2 9 8 1 22 10 6;a;point(3,:)=0;s=80;p=80;k=2;j1=0;j2=0;m=1;b=1:11;pai=b;pai(1,:)=0; for j=1:11 if s>=w(2,point(1,j)+w(3,point(1,j)&point(3,j)=0 s=w(2,point(1,j)+w(3,point(1,j); else continue end end j1=j; point(3,j1)=1; pai(1)=point(1,j1); while m<40 for i=1:11 if (p>=w(2,point(1,i)+w(3,point(1,i)-w(2,point(2,j1)-w(3,point(2,j1)&point(3,i)=0 p=w(2,point(1,i)+w(3,point(1,i)-w(2,point(2,j1)-w(3,point(2,j1); else continue end j2=i; point(3,j2)=1; pai(k)=point(1,j2); k=k+1; end j1=j2; m=m+1; end pai 附录三结果pai = 31 30 28 36 24 34 20 19 14 22 11 附录四：clearx=3 1 5 4 0 3 7 9 10 14 17 14 12 10 7 2 6 11 15 19 22 21 27 15 15 20 21 24 25 28 5 17 25 9 9 30 0;y=2 5 4 7 8 11 9 6 2 0 3 6 9 12 14 16 18 17 12 9 5 0 9 19 14 17 13 20 16 18 12 16 7 20 15 12 0;t=1.50 1.50 0.55 1.20 0.85 1.30 1.20 2.30 1.40 1.50 1.10 2.70 1.80 1.80 0.60 1.50 0.80 1.50 0.80 1.40 1.20 1.80 1.40 1.60 1.60 1.00 2.00 1.00 2.10 1.20 1.90 1.30 1.60 1.20 1.50 1.30 0.00;i=1:37;a=1:37;plot(x,y,'*r')for ii=1:37 k=int2str(ii); k=strcat('P',k); text(x(ii),y(ii),k);endw=i;x;y;t;a;w(5,:)=0;jg=zeros(10,10);%´æ·Å11Ìõ·¾¶for i=1:20 sum=0; j1=1; s=0; m=37; i3=37; for j=1:36 if(w(2,j)+w(3,j)>=s&w(5,j)=0) s=w(2,j)+w(3,j); jg(i,j1)=w(1,j); sum=w(4,j); m=j; else continue; end end w(5,m)=1; j1=j1+1; while 1 js=0; q=40; for k=1:36 if(q>=w(2,m)-w(2,k)+w(3,m)-w(3,k)&w(2,m)>w(2,k)&w(3,m)>w(3,k)&(8-sum)>=w(4,k)&w(5,k)=0 q=w(2,m)+w(3,m)-w(2,k)-w(3,k); js=1; jg(i,j1)=w(1,k); i3=k; else continue; end end w(5,i3)=1; sum=sum+w(4,i3); j1=j1+1; m=i3; if(w(2,i3)=0&w(3,i3)=0|js=0) break end endendkcost=0;zcost=0;allcost=0;n=1;for u1=1:10 for u2=1:10 if jg(u1,u2)=0 n=jg(u1,u2); else continue end zcost=zcost+w(4,n)*1.8*(w(2,n)+w(3,n); end n=jg(u1,1); kcost=kcost+0.4*(w(2,n)+w(3,n);endallcost=zcost+kcostzcostkcosti=1:10;time=i;time(1,:)=0;n1=0;n2=0;n3=0;for u4=1:10 for u5=1:10 if jg(u4,u5)=0 n1=jg(u4,u5); n2=n2+1; else continue end end n3=jg(u4,1); time(1,u4)=(w(2,n3)+w(3,n3)*2)/40;endn2 time jg