资源描述：
《蔬菜运输问题--数学建模》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、蔬菜运输问题22摘要本文运用floyd算法求出各蔬菜采购点到每个菜市场的最短运输距离，然后用lingo软件计算蔬菜调运费用及预期短缺损失最小的调运方案，紧接着根据题目要求对算法加以修改得出每个市场短缺率都小于20%的最优调运方案，并求出了最佳的供应改进方案。求解各采购点到菜市场的最短距离，在图论里面关于最短路问题比较常用的是Dijkstra算法，Dijkstra算法提供了从网络图中某一点到其他点的最短距离。关键词最短路问题floyd算法运输问题一、问题重述F市是一个人口不到15万人的小城市。根据该市的蔬菜种植情况，分
2、别在花市（A），城乡路口（B）和下塘街（C）设三个收购点，再由各收购点分送到全市的8个菜市场，该市道路情况，各路段距离（单位：100m）及各收购点，菜市场①⑧的具体位置见图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菜市场每天需
3、求（100kg）短缺损失（元/100kg）①7510②608③805④7010⑤10010⑥55822⑦905⑧808(a)为该市设计一个从收购点至个菜市场的定点供应方案，使用于蔬菜调运及预期的短缺损失为最小；(b)若规定各菜市场短缺量一律不超过需求量的20%，重新设计定点供应方案(c)为满足城市居民的蔬菜供应，光明市的领导规划增加蔬菜种植面积，试问增产的蔬菜每天应分别向A,B,C三个采购点供应多少最经济合理。二、问题分析求总的运费最低，可以先求出各采购点到菜市场的最小运费，由于单位重量运费与距离成正比，题目所给的图
4、1里包含了部分菜市场、中转点以及收购点之间的距离，（a）题可以用求最短路的方法求出各采购点到菜市场的最短路径，乘上单位重量单位距离费用就是单位重量各运输线路的费用，然后用线性方法即可解得相应的最小调运费用及预期短缺损失。第二问规定各菜市场短缺量一律不超过需求量的20%，只需要在上题基础上加上新的限制条件，即可得出新的调运方案。第三问可以在第二问的基础上用灵敏度分析进行求解，也可以建立新的线性问题进行求解。三、模型假设1、各个菜市场、中转点以及收购点都可以作为中转点；2、各个菜市场、中转点以及收购点都可以的最大容纳量为
5、610吨；3、假设只考虑运输费用和短缺费用，不考虑装卸等其它费用；4、假设运输的蔬菜路途中没有损耗；5、忽略从种菜场地到收购点的运输费用。四、符号说明A收购点分送到全市的8个菜市场的供应量分别为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)。五、模型的建立
6、与求解22按照问题的分析，首先就要求解各采购点到菜市场的最短距离，在图论里面关于最短路问题比较常用的是Dijkstra算法，Dijkstra算法提供了从网络图中某一点到其他点的最短距离。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。但由于它遍历计算的节点很多，所以效率较低，实际问题中往往要求网络中任意两点之间的最短路距离。如果仍然采用Dijkstra算法对各点分别计算，就显得很麻烦。所以就可以使用网络各点之间的矩阵计算法，即Floyd算法。Floyd算法的基本是：从任意节点i到任意节点j的最短路径不外乎2
7、种可能，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)的值；在此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(
8、k,j)，每当一个k查完了，d(i,j)就是目前的i到j的最短距离。重复这一过程，最后当查完所有的k时，d(i,j)里面存放的就是i到j之间的最短距离了。对于上面的问题，只要能列出它的距离的邻接矩阵，如表2所示。便能用floyd法进行计算了。表2各点的邻接矩阵图首先对图1中的4个纯中转点进行编号，为（9）~（12），并标注在图1中，A、B、C的
