#蔬菜运输问题--数学建模.doc

#蔬菜运输问题--数学建模.doc

ID:48431964

大小:253.00 KB

页数:19页

时间:2020-01-26

#蔬菜运输问题--数学建模.doc_第1页
#蔬菜运输问题--数学建模.doc_第2页
#蔬菜运输问题--数学建模.doc_第3页
#蔬菜运输问题--数学建模.doc_第4页
#蔬菜运输问题--数学建模.doc_第5页
资源描述:

《#蔬菜运输问题--数学建模.doc》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库

1、蔬菜运输问题2012年8月22日摘要本文运用floyd算法求出各蔬菜采购点到每个菜市场的最短运输距离,然后用lingo软件计算蔬菜调运费用及预期短缺损失最小的调运方案,紧接着根据题目要求对算法加以修改得出每个市场短缺率都小于20%的最优调运方案,并求出了最佳的供应改进方案。关键词最短路问题floyd算法运输问题一、问题重述光明市是一个人口不到15万人的小城市。根据该市的蔬菜种植情况,分别在花市(A),城乡路口(B)和下塘街(C)设三个收购点,再由各收购点分送到全市的8个菜市场,该市道路情况,各路段距离(单位:100m)及各收购点,

2、菜市场①⑧的具体位置见图1,按常年情况,A,B,C三个收购点每天收购量分别为200,170和160(单位:100kg),各菜市场的每天需求量及发生供应短缺时带来的损失(元/100kg)见表1.设从收购点至各菜市场蔬菜调运费为1元/(100kg.100m).①7②54837A7⑼6B⑥685547117⑾4③7566⑤3⑿5④⑽86610C10⑧511⑦图1表1菜市场每天需求(100kg)短缺损失(元/100kg)①7510②608③805④7010⑤10010⑥558⑦905⑧808(a)为该市设计一个从收购点至个菜市场的定点供应

3、方案,使用于蔬菜调运及预期的短缺损失为最小;(a)若规定各菜市场短缺量一律不超过需求量的20%,重新设计定点供应方案(b)为满足城市居民的蔬菜供应,光明市的领导规划增加蔬菜种植面积,试问增产的蔬菜每天应分别向A,B,C三个采购点供应多少最经济合理。二、问题分析求总的运费最低,可以先求出各采购点到菜市场的最小运费,由于单位重量运费和距离成正比,题目所给的图1里包含了部分菜市场、中转点以及收购点之间的距离,(a)题可以用求最短路的方法求出各采购点到菜市场的最短路径,乘上单位重量单位距离费用就是单位重量各运输线路的费用,然后用线性方法即

4、可解得相应的最小调运费用及预期短缺损失。第二问规定各菜市场短缺量一律不超过需求量的20%,只需要在上题基础上加上新的限制条件,即可得出新的调运方案。第三问可以在第二问的基础上用灵敏度分析进行求解,也可以建立新的线性问题进行求解。三、模型假设1、各个菜市场、中转点以及收购点都可以作为中转点;2、各个菜市场、中转点以及收购点都可以的最大容纳量为610吨;3、假设只考虑运输费用和短缺费用,不考虑装卸等其它费用;4、假设运输的蔬菜路途中没有损耗;5、忽略从种菜场地到收购点的运输费用。四、符号说明A收购点分送到全市的8个菜市场的供应量分别为

5、a1,b1,c1,d1,e1,f1,g1,h1,B收购点分送到全市的8个菜市场的供应量分别为a2,b2,c2,d2,e2,f2,g2,h2,C收购点分送到全市的8个菜市场的供应量分别为a3,b3,c3,d3,e3,f3,g3,h3,8个菜市场的短缺损失量分别为a,b,c,d,e,f,g,h(单位均为100kg)。五、模型的建立和求解按照问题的分析,首先就要求解各采购点到菜市场的最短距离,在图论里面关于最短路问题比较常用的是Dijkstra算法,Dijkstra算法提供了从网络图中某一点到其他点的最短距离。主要特点是以起始点为中心向

6、外层层扩展,直到扩展到终点为止。但由于它遍历计算的节点很多,所以效率较低,实际问题中往往要求网络中任意两点之间的最短路距离。如果仍然采用Dijkstra算法对各点分别计算,就显得很麻烦。所以就可以使用网络各点之间的矩阵计算法,即Floyd算法。Floyd算法的基本是:从任意节点i到任意节点j的最短路径不外乎2种可能,1是直接从i到j,2是从i经过若干个节点k到j。i到j的最短距离不外乎存在经过i和j之间的k和不经过k两种可能,所以可以令k=1,2,3,...,n(n是城市的数目),在检查d(i,j)和d(i,k)+d(k,j)的值

7、;在此d(i,k)和d(k,j)分别是目前为止所知道的i到k和k到j的最短距离。因此d(i,k)+d(k,j)就是i到j经过k的最短距离。所以,若有d(i,j)>d(i,k)+d(k,j),就表示从i出发经过k再到j的距离要比原来的i到j距离短,自然把i到j的d(i,j)重写为d(i,k)+d(k,j),每当一个k查完了,d(i,j)就是目前的i到j的最短距离。重复这一过程,最后当查完所有的k时,d(i,j)里面存放的就是i到j之间的最短距离了。对于上面的问题,只要能列出它的距离的邻接矩阵,如表2所示。便能用floyd法进行计算了

8、。表2各点的邻接矩阵图首先对图1中的4个纯中转点进行编号,为(9)~(12),并标注在图1中,A、B、C的编号分别为1、14、15,其余点在矩阵中的编号如表1第一行所示。由于数据比较复杂,用普通的计算很困难,所以我们可以用MATLAB软件来编程求解

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。