精品文档

。 1欢迎下载 蔬菜运输问题

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） 短缺损失（元/100kg）

① 75 10

② 60 8

③ 80 5

④ 70 10

⑤ 100 10

⑥ 55 8

⑦ 90 5

⑧ 80 8

(a)为该市设计一个从收购点至个菜市场的定点供应方案，使用于蔬菜调运及预精品文档

。 2欢迎下载 期的短缺损失为最小；

(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)重写为精品文档

。 3欢迎下载 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 i=1:n

ins=0;

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; 精品文档

。 4欢迎下载 end, end, end

v1=0;

k=inf;

for i=1:n

ins=0;

for j=1:length(s)

if i==s(j)

ins=1;

end, end

if ins==0

v=i;

if k>label(v)

k=label(v); v1=v;

end, end, end

s(length(s)+1)=v1;

u=v1;

end

min=label(terminal); path(1)=terminal;

i=1;

while path(i)~=start

path(i+1)=f(path(i));

i=i+1 ;

end

path(i)=start;

L=length(path);

path=path(L:-1:1); 精品文档

。 5欢迎下载

图2 Dijkstra算法的MATLAB运行图

如图2，红色框内的是Dijkstra算法的脚本程序，蓝色框内的试运行结果，根据程序显示s点到j点的最短路就是4百米。在程序中显示所走的路线为path=1 2，对应点即为直接从A点到达①点。但是由于运用dijkstra编程每次都要修改起始点和终点，所以在大部分情况下效率都不高。

由于dijkstra算法较为复杂，所以可用Floyd算法用于求最短路径。Floyd算法思路本质很简单，即用三个for循环的嵌套，代码思路如下：

for ( int i = 0; i < 节点个数; ++i )

{

for ( int j = 0; j < 节点个数; ++j )

{

for ( int k = 0; k < 节点个数; ++k )

{

if ( Dis[i][k] + Dis[k][j] < Dis[i][j] )

{

// 找到更短路径 精品文档

。 6欢迎下载 Dis[i][j] = Dis[i][k] + Dis[k][j];

}

}

}

}

但是这里我们要注意循环的嵌套顺序，如果把检查所有节点X放在最内层，那么结果将是不正确的，因为这样便过早的把i到j的最短路径确定下来了，所以正确的应该是这样的：

for ( k = 0; k < 节点个数; ++k )

{

for ( i = 0; i < 节点个数; ++i )

{

for ( j = 0; j < 节点个数; ++j )

{

if ( Dis[i][k] + Dis[k][j] < Dis[i][j] )

{

％ 找到更短路径

Dis[i][j] = Dis[i][k] + Dis[k][j];

}

}

}.

}

那么接下来的问题就是，我们如何找出最短路径.这里需要借助一个辅助数组Path，它是这样使用的：Path(AB)的值如果为P，则表示A节点到B节点的最短路径是A->...->P->B。这样一来，假设我们要找A->B的最短路径，那么就依次查找，假设Path(AB)的值为P，那么接着查找Path(AP)，假设Path(AP)的值为L，那么接着查找Path(AL)，假设Path(AL)的值为A，则查找结束，最短路径为A->L->P->B。那么，如何填充Path的值呢？很简单，当我们发现Dis(AX) +

Dis(XB) < Dis(AB)成立时，就要把最短路径改为A->...->X->...->B，而此时，Path(XB)的值是已知的，所以，Path(AB) = Path(XB)。Floyd算法直接在图的带权邻接矩阵中用插入顶点的方法依次递推地构造出n个矩阵D(1), D(2), …,

D(n), D(n)是图的距离矩阵, 同时引入一个后继点矩阵记录两点间的最短路径。d(i,j) : i到j的距离; path(i,j): i到j的路径上i的后继点;输入带权邻接矩阵a(i,j)。赋初值，对所有i,j, d(i,j)a(i,j) , path(i,j)j,k=l。然后更新d(i,j) , path(i,j)对所有i,j,若d(i,k)+d(k,j)

接下来就是代入具体的数据了，这里的图以及邻接矩阵依旧是修改后的图1及表2。

Floyd算法的MATLAB代码如下：

M程序

function [D,path,min1,path1]=floyd(a,start,terminal)

D=a;n=size(D,1);path=zeros(n,n);

for i=1:n