内容发布更新时间 : 2024/11/17 17:25:57星期一 下面是文章的全部内容请认真阅读。

蔬菜运输问题

2012年8月22日

摘要

本文运用floyd算法求出各蔬菜采购点到每个菜市场的最短运输距离，然后用lingo软件计算蔬菜调运费用及预期短缺损失最小的调运方案，紧接着根据题目要求对算法加以修改得出每个市场短缺率都小于20%的最优调运方案，并求出了最佳的供应改进方案。

关键词

最短路问题 floyd算法 运输问题

一、问题重述

光明市是一个人口不到15万人的小城市。根据该市的蔬菜种植情况，分别在花市（A），城乡路口（B）和下塘街（C）设三个收购点，再由各收购点分送到全市的8个菜市场，该市道路情况，各路段距离（单位：100m）及各收购点，菜市场①⑧的具体位置见图1，按常年情况，A,B,C三个收购点每天收购量分别为200，170和160（单位：100 kg）,各菜市场的每天需求量及发生供应短缺时带来的损失（元/100kg）见表1.设从收购点至各菜市场蔬菜调运费为1元/(100kg.100m).

① 7 ②

5 4 8 3 7 A 7 ⑼ 6 B ⑥ 6 8 5 5 4 7 11 7 ⑾ 4 ③ 7 5 6

6 ⑤ 3 ⑿ 5 ④ ⑽ 8 6 6

10 C 10 ⑧ 5 11 ⑦ 图1

表1

菜市场 ① ② ③ ④ ⑤ ⑥ ⑦ ⑧ 每天需求（100 kg） 75 60 80 70 100 55 90 80 短缺损失（元/100kg） 10 8 5 10 10 8 5 8 (a)为该市设计一个从收购点至个菜市场的定点供应方案，使用于蔬菜调运及预期的短缺损失为最小；

(b)若规定各菜市场短缺量一律不超过需求量的20%，重新设计定点供应方案 (c)为满足城市居民的蔬菜供应，光明市的领导规划增加蔬菜种植面积，试问增产的蔬菜每天应分别向A,B,C三个采购点供应多少最经济合理。

二、问题分析

求总的运费最低，可以先求出各采购点到菜市场的最小运费，由于单位重量运费和距离成正比，题目所给的图1里包含了部分菜市场、中转点以及收购点之间的距离，（a）题可以用求最短路的方法求出各采购点到菜市场的最短路径，乘上单位重量单位距离费用就是单位重量各运输线路的费用，然后用线性方法即可解得相应的最小调运费用及预期短缺损失。

第二问规定各菜市场短缺量一律不超过需求量的20%，只需要在上题基础上加上新的限制条件，即可得出新的调运方案。

第三问可以在第二问的基础上用灵敏度分析进行求解，也可以建立新的线性问题进行求解。

三、模型假设

1、各个菜市场、中转点以及收购点都可以作为中转点；

2、各个菜市场、中转点以及收购点都可以的最大容纳量为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)。

五、模型的建立和求解

按照问题的分析，首先就要求解各采购点到菜市场的最短距离，在图论里面关于最短路问题比较常用的是Dijkstra算法，Dijkstra算法提供了从网络图中某一点到其他点的最短距离。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。但由于它遍历计算的节点很多，所以效率较低，实际问题中往往要求网络中任意两点之间的最短路距离。如果仍然采用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)的值；在此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法进行计算了。

表2 各点的邻接矩阵图

首先对图1中的4个纯中转点进行编号，为（9）~（12），并标注在图1中，A、B、C的编号分别为1、14、15，其余点在矩阵中的编号如表1第一行所示。

由于数据比较复杂，用普通的计算很困难，所以我们可以用MATLAB软件来编程求解。

算法思路：采用标号作业法,每次迭代产生一个永久标号, 从而生长一颗以V0为根的最短路树,在这颗树上每个顶点和根节点之间的路径皆为最短路径。当然此问题也需要表2的各点邻接矩阵。

接下来可以得到Dijkstra法的MATLAB语言。 M程序如下：

function [min,path]=dijkstra(w,start,terminal) n=size(w,1); label(start)=0; f(start)=start; for i=1:n

if i~=start

label(i)=inf; end, end

s(1)=start; u=start; while length(s)

for j=1:length(s) if i==s(j) ins=1; end, end if ins==0 v=i;

if label(v)>(label(u)+w(u,v))

label(v)=(label(u)+w(u,v)); f(v)=u;