蔬菜供应方案设计
蔬菜供应方案设计
摘 要
由于人们生活水平的发展，开始讲求天然产品，这使蔬菜产品有了广阔的市场。商业企业要求最好的销售和利润的最大化，于是要设定合适的蔬菜供应方案力求利润的最大化和市场供应的便捷性。
本文利用Floyd算法求出各蔬菜采购点到每个菜市场的最短运输距离，然后用lingo软件计算蔬菜调运费用及预期短缺损失最小的条用方案。最优运输方案为菜市场（A）运往菜市场1蔬菜数量为8000kg，运往菜市场2蔬菜数量为4000kg，运往菜市场5蔬菜数量为6000kg，运往菜市场6蔬菜数量为7000kg；城乡路口（B）运往菜市场2蔬菜数量为30kg，运往菜市场3蔬菜数量为9000kg，运往菜市场4蔬菜数量为8000kg；南街口（C）运往菜市场5蔬菜数量为6000kg，运往菜市场7蔬菜数量为10000kg，运往菜市场8蔬菜数量为2000kg。用于蔬菜调运及预期的短缺最小损失为10920元。
根据题目要求对算法加以修改得出每个市场短缺率都小于20%的最优调运方案，并求出了最佳的供应改进方案。最优运输方案为菜市场（A）运往菜市场1蔬菜数量为8000kg，运往菜市场2蔬菜数量为800kg，运往菜市5蔬菜数量为9200kg，运往菜市6蔬菜数量为7000kg；城乡路口（B）运往菜市场2蔬菜数量为6200kg，运往菜市场3蔬菜数量为7400kg，运往菜市场4蔬菜数量为6400kg；南街口（C）运往菜市场5蔬菜数量为2800kg，运往菜市场7蔬菜数量为8000kg，运往菜市场8蔬菜数量为7200kg。用于蔬菜调运及预期的短缺最小损失为11128元。
增加蔬菜种植面积后根据结果知增产的蔬菜向集散点C多供应70公斤最经济合理。
关键词：最短路径；floyd算法；lingo软件；
一、问题重述
江平市是一个人口不到20万人的小城市。根据该市的蔬菜种植情况，分别在菜市场（A），城乡路口（B）和南街口（C）设三个收购点，再由各收购点分送到全市的8个菜市场，该市道路情况，各路段距离（单位：100m）及各收购点，菜市场①到⑧的具体位置见图1。按常年情况，A、B、C三个收购点每天收购量分别为250，200和180（单位：100 kg）,各菜市场的每天需求量及发生供应短缺时带来的损失（元/100kg）见表1。设从收购点至各菜市场蔬菜调运费为2元/(100kg.100m)。
图1 蔬菜供应网点图
试为该市设计一个用于蔬菜调运及预期的短缺损失为最小的从收购点至各个菜市场的定点供应方案；若规定各菜市场短缺量一律不超过需求量的20%，重新设计定点供应方案；规划增加蔬菜种植面积后增产的蔬菜每天应分别向A、B、C三个采购点供应
多少最经济合理。
二、问题分析
求总的运费最低，可以先求出各采购点到菜市场的最小运费，因为单位重量的运费与距离成正比。第一问可以用Floyd算法求出最短路径即求出各个采购点都菜市场的最短运输距离，乘以单位重量单位距离的运输费用就是单位重量各运输路线的费用，然后用线性方法即可解得相应的最小的调运费及预期短缺损失。
第二问规定各菜市场短缺量一律不超过需求量的20%，只需在第一问的基础上加上新的设定条件，就可得到新的供应方案。
第三问建立新的线性问题进行求解。
三、问题假设
1、各个收购点、中转站以及菜市场都可以做为中转点。
2、各个收购点、中转站以及菜市场的最大容纳量为700吨。
3、假设运输的路途中蔬菜没有任何损耗。
4、假设只考虑运输费用和短缺费用，不考虑装卸等其他费用。
5、忽略从种菜地点到收购点的运输费用。
四、变量说明
五、模型建立
根据问题的分析，必须得求解各采购点到菜市场的最短距离。如果求图中最短路径的话则有以下两种解法：解法一：Dijkstra算法；解法二：Floyd（弗洛伊德）算法。以图中的每个顶点作为源点，调用Dijkstra算法。Dijkstra算法是从一个顶点到其余各顶点的最短路径算法，主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法简明，可是由于它遍历计算的点太多了，所说效率很低，占用运算空间大。这里只需要求解图中任意两点之间的最短距离，所以可以使用网络各点之间的矩阵计算法即Floyd算法。
Floyd算法的基本思想：
可以将问题分解，先找出最短的距离，然后在考虑如何找出对应的行进路线。如何找出最短路径呢，这里还是用到动态规划的知识，对于任何一个城市而言，i到j的最短距离不外乎存在经过i与j之间的k和不经过k两种可能，所以可以令k=1，2，3，...，n(n是城市的数目)，在检查d(ij)与d(ik)+d(kj)的值；在此d(ik)与d(kj)分别是目前为止所
知道的i到k与k到j的最短距离，因此d(ik)+d(kj)就是i到j经过k的最短距离。所以，若有d(ij)>d(ik)+d(kj)，就表示从i出发经过k再到j的距离要比原来的i到j距离短，自然把i到j的d(ij)重写为d(ik)+d(kj)，每当一个k查完了，d(ij)就是目前的i到j的最短距离。重复这一过程，最后当查完所有的k时，d(ij)里面存放的就是i到j之间的最短距离了。
Floyd算法的基本步骤：
定义n×n的方阵序列D-1，D0， … Dn－1。初始化： D-1＝C。D-1[i][j]＝边的长度，表示初始的从i到j的最短路径长度，即它是从i到j的中间不经过其他中间点的最短路径。迭代：设Dk-1已求出，如何得到Dk（0≤k≤n-1）。
Dk-1[i][j]表示从i到j的中间点不大于k-1的最短路径p：i…j，考虑将顶点k加入路径p得到顶点序列q：i…k…j，若q不是路径，则当前的最短路径仍是上一步结果：Dk[i][j]= Dk－1[i][j]；否则若q的长度小于p的长度，则用q取代p作为从i到j的最短路径。因为q的两条子路径i…k和k…j皆是中间点不大于k－1的最短路径，所以从i到j中间点不大于k的最短路径长度为：Dk[i][j]＝min{ Dk-1[i][j], Dk-1[i][k] +Dk-1[k][j] }。
Floyd算法实现：
可以用三个for循环把问题搞定了，但是有一个问题需要注意，那就是for循环的嵌套的顺序。
for(int k=0; k
for(int i=0; i
for(int j=0; j
这样作的意义在于固定了k，把所有i到j而经过k的距离找出来，然后象开头所提到的那样进行比较和重写，因为k是在最外层的，所以会把所有的i到j都处理完后，才会移动到下一个k，这样就不会有问题了，看来多层循环的时候，我们一定要当心，否则很容易就弄错了。
接下来就要看一看如何找出最短路径所行经的城市了，这里要用到另一个矩阵P，它的定义是这样的：p(ij)的值如果为p，就表示i到j的最短路径为i->...->p->j，也就是说p是i到j的最短行径中的j之前的最后一个城市。P矩阵的初值为p(ij)=i。有了这个矩阵之后，要找最短路径就轻而易举了。对于i到j而言找出p(ij)，令为p，就知道了路径i->...->p->j；再去找p(ip)，如果值为q，i到p的最短路径为i->...->q->p；再去找p(iq)，如果值为r，i到q的最短路径为i->...->r->q；所以一再反复，到了某个p(it)的值为i时，就表示i到t的最短路径为i->t，就会的到答案了，i到j的最短行径为i->t->...->q->p->j。因为上述的算法是从终点到起点的顺序找出来的，所以输出的时候要把它倒过来。但是，如何动态的回填P矩阵的值呢？当d(ij)>d(ik)+d(kj)时，就要让i到j的最短路径改为走i->...->k->...->j这一条路，但是d(kj)的值是已知的，换句话说，就是k->...->j这条路是已知的，所以k->...->j这条路上j的上一个城市(即p(kj))也是已知的，当然，因为要改走i->...->k->...->j这一条路，j的上一个城市正好是p(kj)。所以一旦发现d(ij)>d(ik)+d(kj)，
就把p(kj)存入p(ij)。
在利用Floyd算法求出最短路径以后，对于问题一可以建立以下lingo程序下的线性规划模型：
MIN=(4*a1+8*b1+8*c1+19*d1+11*e1+6*f1+22*g1+20*h1+14*a2+7*b2+7*c2+16*d2+12*e2+16*f2+23*g2+17*h2+20*a3+19*b3+11*c3+14*d3+6*e3+15*f3+5*g3+10*h3+ 10*a+8*b+5*c+10*d+10*e+8*f+5*g+8*h)*2;
a1+b1+c1+d1+e1+f1+g1+h1=250;
a2+b2+c2+d2+e2+f2+g2+h2=200;
a3+b3+c3+d3+e3+f3+g3+h3=180;
a+b+c+d+e+f+g+h=70;
a1+a2+a3+a=80;
b1+b2+b3+b=70;
c1+c2+c3+c=90;
d1+d2+d3+d=80;
e1+e2+e3+e=120;
f1+f2+f3+f=70;
g1+g2+g3+g=100;
h1+h2+h3+h=90;
End
对于问题二可以建立以下lingo程序下的线性规划模型：
MIN=(4*a1+8*b1+8*c1+19*d1+11*e1+6*f1+22*g1+20*h1+14*a2+7*b2+7*c2+16*d2+12*e2+16*f2+23*g2+17*h2+20*a3+19*b3+11*c3+14*d3+6*e3+15*f3+5*g3+10*h3+ 10*a+8*b+5*c+10*d+10*e+8*f+5*g+8*h)*2;
a1+b1+c1+d1+e1+f1+g1+h1=250;
a2+b2+c2+d2+e2+f2+g2+h2=200;
a3+b3+c3+d3+e3+f3+g3+h3=180;
a+b+c+d+e+f+g+h=70;
a1+a2+a3+a=80;
b1+b2+b3+b=70;
c1+c2+c3+c=90;
d1+d2+d3+d=80;
e1+e2+e3+e=120;
f1+f2+f3+f=70;
g1+g2+g3+g=100;
h1+h2+h3+h=90;
a
b
c
d
e
f
g
h
End
对于问题三可以建立以下lingo程序下的线性规划模型：
就把p(kj)存入p(ij)。
在利用Floyd算法求出最短路径以后，对于问题一可以建立以下lingo程序下的线性规划模型：
MIN=(4*a1+8*b1+8*c1+19*d1+11*e1+6*f1+22*g1+20*h1+14*a2+7*b2+7*c2+16*d2+12*e2+16*f2+23*g2+17*h2+20*a3+19*b3+11*c3+14*d3+6*e3+15*f3+5*g3+10*h3+ 10*a+8*b+5*c+10*d+10*e+8*f+5*g+8*h)*2; a1+b1+c1+d1+e1+f1+g1+h1=250; a2+b2+c2+d2+e2+f2+g2+h2=200; a3+b3+c3+d3+e3+f3+g3+h3=180; a+b+c+d+e+f+g+h=70; a1+a2+a3+a=80; b1+b2+b3+b=70; c1+c2+c3+c=90; d1+d2+d3+d=80; e1+e2+e3+e=120; f1+f2+f3+f=70; g1+g2+g3+g=100; h1+h2+h3+h=90; End
对于问题二可以建立以下lingo程序下的线性规划模型：
MIN=(4*a1+8*b1+8*c1+19*d1+11*e1+6*f1+22*g1+20*h1+14*a2+7*b2+7*c2+16*d2+12*e2+16*f2+23*g2+17*h2+20*a3+19*b3+11*c3+14*d3+6*e3+15*f3+5*g3+10*h3+ 10*a+8*b+5*c+10*d+10*e+8*f+5*g+8*h)*2; a1+b1+c1+d1+e1+f1+g1+h1=250; a2+b2+c2+d2+e2+f2+g2+h2=200; a3+b3+c3+d3+e3+f3+g3+h3=180; a+b+c+d+e+f+g+h=70; a1+a2+a3+a=80; b1+b2+b3+b=70; c1+c2+c3+c=90; d1+d2+d3+d=80; e1+e2+e3+e=120; f1+f2+f3+f=70; g1+g2+g3+g=100; h1+h2+h3+h=90; a
对于问题三可以建立以下lingo程序下的线性规划模型：
MIN=(4*a1+8*b1+8*c1+19*d1+11*e1+6*f1+22*g1+20*h1+14*a2+7*b2+7*c2+16*d2+12*e2+16*f2+23*g2+17*h2+20*a3+19*b3+11*c3+14*d3+6*e3+15*f3+5*g3 +10*h3)*2; a1+a2+a3=80; b1+b2+b3=70; c1+c2+c3=90; d1+d2+d3=80; e1+e2+e3=120; f1+f2+f3=70; g1+g2+g3=100; h1+h2+h3=90;
a1+b1+c1+d1+e1+f1+g1+h1>250; a2+b2+c2+d2+e2+f2+g2+h2>200; a3+b3+c3+d3+e3+f3+g3+h3>180; End
六、模型求解
Floyd算法的MATLAB代码如下：
function [D,path,min1,path1]=floyd(a,start,terminal) D=a; n=size(D,1) path=zeros(n,n); for i=1:n for j=1:n
if D(i,j)~=inf path(i,j)=j; end,end,end for k=1:n for i=1:n for j=1:n
if D(i,k)+D(k,j)
min1=D(start,terminal); m(1)=start; i=1; path1=[];
while path(m(i),terminal)~=terminal k=i+1;
m(k)=path(m(i),terminal); i=i+1; end
m(i+1)=terminal; path1=m;
end
根据题目网络列出距离的矩阵，在MATLAB中编写的程序代码如下： a=[0 4 8 8 inf inf 6 inf inf 7 inf 4 inf inf inf;
4 0 7 inf inf inf 5 inf inf inf inf inf inf inf inf; 8 7 0 inf inf inf inf inf inf 3 inf inf inf 7 inf; 8 inf inf 0 inf 5 inf inf inf 5 inf 4 6 7 inf;
inf inf inf inf 0 inf inf inf inf inf inf inf 5 inf inf; inf inf inf 5 inf 0 inf inf inf inf 6 7 3 inf 6; 6 5 inf inf inf inf 0 inf inf inf 7 5 inf inf inf; inf inf inf inf inf inf inf 0 11 inf 10 inf inf inf 5; inf inf inf inf inf inf inf 11 0 inf inf inf 6 inf 10; 7 inf 3 5 inf inf inf inf inf 0 inf inf inf 6 inf; inf inf inf inf inf 6 7 10 inf inf 0 inf inf inf 8; 4 inf inf 4 inf 7 5 inf inf inf inf 0 inf inf inf; inf inf inf 6 5 3 inf inf 6 inf inf inf 0 11 inf; inf inf 7 7 inf inf inf inf inf 6 inf inf 11 0 inf; inf inf inf inf inf 6 inf 5 10 inf 8 inf inf inf 0] 调用a,运行结果如下：
七、结果分析
1、
此方案通过运算结果得出用于蔬菜调运及预期的短缺损失为10920元。 2、 此方案通过运算结果得出用于蔬菜调运及预期的短缺损失为11128元。 3、
由上表看出，当A，B两收购点收购和供应量相等，增收的7000kg由C收购点收购，这样下来所有的花费会最小。
八、参考文献
[1] 张志涌，杨祖樱. MATLAB教程[M]. 北京：北京航空航天大学出版社, 2011. [2] 《运筹学》教材编写组，运筹学，清华大学出版社，2011.
九、附录
1、lingo运行结果1
Global optimal solution found.
Objective value: 10920.00 Infeasibilities: 0.000000 Total solver iterations: 12
Variable Value Reduced Cost A1 80.00000 0.000000 B1 40.00000 0.000000 C1 0.000000 0.000000 D1 0.000000 4.000000 E1 60.00000 0.000000 F1 70.00000 0.000000 G1 0.000000 24.00000 H1 0.000000 10.00000 A2 0.000000 22.00000 B2 30.00000 0.000000 C2 90.00000 0.000000 D2 80.00000 0.000000 E2 0.000000 4.000000 F2 0.000000 22.00000 G2 0.000000 28.00000 H2 0.000000 6.000000 A3 0.000000 42.00000 B3 0.000000 32.00000 C3 0.000000 16.00000 D3 0.000000 4.000000 E3 60.00000 0.000000
H3 20.00000 0.000000
A 0.000000 26.00000
B 0.000000 14.00000
C 0.000000 8.000000
D 0.000000 0.000000 E 0.000000 12.00000 F 0.000000 18.00000 G 0.000000 4.000000 H 70.00000 0.000000
Row Slack or Surplus Dual Price 1 10920.00 -1.000000 2 0.000000 -16.00000 3 0.000000 -14.00000 4 0.000000 -6.000000 5 0.000000 -2.000000 6 0.000000 8.000000 7 0.000000 0.000000 8 0.000000 0.000000 9 0.000000 -18.00000 10 0.000000 -6.000000 11 0.000000 4.000000 12 0.000000 -4.000000 13 0.000000 -14.00000
2、lingo运行结果2
Global optimal solution found.
Objective value: 11128.00
Infeasibilities: 0.000000
Total solver iterations: 11
Variable Value Reduced Cost A1 80.00000 0.000000 B1 8.000000 0.000000 C1 0.000000 0.000000 D1 0.000000 4.000000 E1 92.00000 0.000000 F1 70.00000 0.000000 G1 0.000000 24.00000 H1 0.000000 10.00000 A2 0.000000 22.00000 B2 62.00000 0.000000 C2 74.00000 0.000000
F2 0.000000 22.00000 G2 0.000000 28.00000 H2 0.000000 6.000000 A3 0.000000 42.00000 B3 0.000000 32.00000 C3 0.000000 16.00000 D3 0.000000 4.000000 E3 28.00000 0.000000 F3 0.000000 28.00000 G3 80.00000 0.000000 H3 72.00000 0.000000
A 0.000000 18.00000
B 0.000000 6.000000
C 16.00000 0.000000
D 16.00000 0.000000 E 0.000000 4.000000 F 0.000000 10.00000 G 20.00000 0.000000 H 18.00000 0.000000
Row Slack or Surplus Dual Price 1 11128.00 -1.000000 2 0.000000 -16.00000 3 0.000000 -14.00000 4 0.000000 -6.000000 5 0.000000 -10.00000 6 0.000000 8.000000 7 0.000000 0.000000 8 0.000000 0.000000 9 0.000000 -18.00000 10 0.000000 -6.000000 11 0.000000 4.000000 12 0.000000 -4.000000 13 0.000000 -14.00000 14 16.00000 0.000000 15 14.00000 0.000000 16 2.000000 0.000000 17 0.000000 8.000000 18 24.00000 0.000000 19 14.00000 0.000000 20 0.000000 4.000000 21 0.000000 8.000000
3、lingo运行结果3
Global optimal solution found.
Objective value: 11200.00
Infeasibilities: 0.000000
Total solver iterations: 12
Variable Value Reduced Cost A1 80.00000 0.000000 B1 40.00000 0.000000 C1 0.000000 0.000000 D1 0.000000 4.000000 E1 60.00000 0.000000 F1 70.00000 0.000000 G1 0.000000 24.00000 H1 0.000000 10.00000 A2 0.000000 22.00000 B2 30.00000 0.000000 C2 90.00000 0.000000 D2 80.00000 0.000000 E2 0.000000 4.000000 F2 0.000000 22.00000 G2 0.000000 28.00000 H2 0.000000 6.000000 A3 0.000000 42.00000 B3 0.000000 32.00000 C3 0.000000 16.00000 D3 0.000000 4.000000 E3 60.00000 0.000000 F3 0.000000 28.00000 G3 100.0000 0.000000 H3 90.00000 0.000000
Row Slack or Surplus Dual Price 1 11200.00 -1.000000 2 0.000000 2.000000 3 0.000000 -6.000000 4 0.000000 -6.000000 5 0.000000 -24.00000 6 0.000000 -12.00000 7 0.000000 -2.000000 8 0.000000 -10.00000 9 0.000000 -20.00000 10 0.000000 -10.00000 11 0.000000 -8.000000 12 70.00000 0.000000