蔬菜供应方案计划设计

《蔬菜供应方案计划设计》由会员分享，可在线阅读，更多相关《蔬菜供应方案计划设计（23页珍藏版）》请在装配图网上搜索。

1、蔬菜供应方案设计摘要由于人们生活水平的发展，开始讲求天然产品，这使蔬菜产品有了广阔的市场。商 业企业要求最好的销售和利润的最大化，于是要设定合适的蔬菜供应方案力求利润的最 大化和市场供应的便捷性。本文利用Floyd算法求出各蔬菜采购点到每个菜市场的最短运输距离，然后用lingo软件计算蔬菜调运费用及预期短缺损失最小的条用方案。最优运输方案为菜市场（A）运往菜市场1蔬菜数量为8000kg，运往菜市场2蔬菜数量为4000kg，运往菜 市场5蔬菜数量为6000kg，运往菜市场6蔬菜数量为7000kg ;城乡路口（ B）运往 菜市场2蔬菜数量为30kg，运往菜市场3蔬菜数量为9000kg，运往菜市场4

2、蔬菜数 量为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蔬菜数量为6400k

3、g ;南街口（ C）运往菜 市场5蔬菜数量为2800kg，运往菜市场7蔬菜数量为8000kg，运往菜市场8蔬菜数 量为7200kg。用于蔬菜调运及预期的短缺最小损失为 11128元。增加蔬菜种植面积后根据结果知增产的蔬菜向集散点C多供应70公斤最经济合关键词：最短路径；floyd算法；lingo软件;一、问题重述江平市是一个人口不到20万人的小城市。根据该市的蔬菜种植情况，分别在菜市场（A），城乡路口（ B）和南街口（ C）设三个收购点，再由各收购点分送到全市的8个菜市场，该市道路情况，各路段距离（单位： 100m ）及各收购点，菜市场到的 具体位置见图1。按常年情况，A、B、C三个收购点每天

4、收购量分别为 250，200和 180 （单位：100 kg），各菜市场的每天需求量及发生供应短缺时带来的损失（元/100kg）见表1。设从收购点至各菜市场蔬菜调运费为2元/（100kg.100m）了图1蔬菜供应网点图表1各蔬菜市场需求量表菜市场每天需求（100 kg）短缺损失（元/100kg）80107089058010120107081005908试为该市设计一个用于蔬菜调运及预期的短缺损失为最小的从收购点至各个菜市场的定点供应方案；若规定各菜市场短缺量一律不超过需求量的20%，重新设计定点供应方案；规划增加蔬菜种植面积后增产的蔬菜每天应分别向A、B、C三个采购点供应多少最经济合理。二、问

5、题分析求总的运费最低，可以先求出各采购点到菜市场的最小运费，因为单位重量的运费与距离成正比。第一问可以用Floyd算法求出最短路径即求出各个采购点都菜市场的最 短运输距离，乘以单位重量单位距离的运输费用就是单位重量各运输路线的费用，然后 用线性方法即可解得相应的最小的调运费及预期短缺损失。第二问规定各菜市场短缺量一律不超过需求量的20%，只需在第一问的基础上加上新的设定条件，就可得到新的供应方案。第三问建立新的线性问题进行求解。三、问题假设1、各个收购点、中转站以及菜市场都可以做为中转点。2、 各个收购点、中转站以及菜市场的最大容纳量为700吨。3、假设运输的路途中蔬菜没有任何损耗。4、假设只

6、考虑运输费用和短缺费用，不考虑装卸等其他费用。5、忽略从种菜地点到收购点的运输费用四、变量说明a1,b1,c1,d1,e1,f1,g1,h1A收购点分送到全市的8个菜市场的供应量a2,b2,c2,d2,e2,f2,g2,h2B收购点分送到全市的8个菜市场的供应量a3,b3,c3,d3,e3,f3,g3,h3C收购点分送到全市的8个菜市场的供应量a,b,c,d,e,f,g,h8个菜市场的短缺损失量（100kg）五、模型建立根据问题的分析，必须得求解各采购点到菜市场的最短距离。如果求图中最短路径的话则有以下两种解法：解法一：Dijkstra算法；解法二：Floyd （弗洛伊德）算法以图中的每个顶点

7、作为源点，调用Dijkstra算法。Dijkstra算法是从一个顶点到其余各顶点的最短路径算法，主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法简明，可是由于它遍历计算的点太多了，所说效率很低，占用运算空间大。 这里只需要求解图中任意两点之间的最短距离，所以可以使用网络各点之间的矩阵计算法即Floyd算法。Floyd算法的基本思想：可以将问题分解，先找出最短的距离，然后在考虑如何找出对应的行进路线。如何找出最短路径呢，这里还是用到动态规划的知识， 对于任何一个城市而言，i至叮的最短 距离不外乎存在经过i与j之间的k和不经过k两种可能，所以可以令k=1，2，3，,

8、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至叮距 离短，自然把i到j的d(ij)重写为d(ik)+d(kj)，每当一个k查完了，d(ij)就是目前的i 到j的最短距离。重复这一过程，最后当查完所有的 k时，d(ij)里面存放的就是i到j 之间的最短距离了。Floyd算法的基本步骤：定义nxn的方阵序列D-1，D0，Dn 1。初始化：D-1 = C

9、。D-1ij=边<i,j>的长度，表示初始的从i到j的最短路径长度，即它是从i到j的中间不经过其他 中间点的最短路径。迭代：设 Dk-1已求出，如何得到Dk (0<k <n-1 )。Dk-1ij表示从i到j的中间点不大于k-1的最短路径p : i-j，考虑将顶点k加入路径 p得到顶点序列q : ik，若q不是路径，则当前的最短路径仍是上一步结果：Dkij= Dk 1ij;否则若q的长度小于p的长度，则用q取代p作为从i至叮的最短路径。 因为q的两条子路径ik和k皆是中间点不大于k 1的最短路径，所以从i到j中间点不大于 k 的最短路径长度为：Dkij = min Dk-

10、1ij, Dk-1ik +Dk-1kj Floyd算法实现:可以用三个for循环把问题搞定了，但是有一个问题需要注意，那就是for循环的嵌套的顺序。for(i nt k=0; k< n; k+)for(i nt i=0; i<n; i+)for(i nt j=0; j< n; j+)这样作的意义在于固定了k,把所有i到j而经过k的距离找出来，然后象开头所提到的那样进行比较和重写，因为k是在最外层的，所以会把所有的i至叮都处理完后， 才会移动到下一个k，这样就不会有问题了，看来多层循环的时候，我们一定要当心， 否则很容易就弄错了。接下来就要看一看如何找出最短路径所行经的城市了，

11、这里要用到另一个矩阵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

12、->t，就会的到答案了，i至叮的最短行 径为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

13、的上一个城市正好 是 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

14、+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

15、*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

16、+f=70;g1+g2+g3+g=100;h1+h2+h3+h=90;a<16;b<14;c<18;d<16;e<24;f<14;g<20;h<18;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)*2;a1+a2+a3=80;b1+b2+b3=7

17、0;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代码如下：fun cti on D,path,mi n1,path1=floyd(a,start,termi nal)D=a;n=size(D,1)path=zeros( n,n);for i=1: nfor j=1

18、: nif D(i,j)=i nfpath(i,j)=j;end ,end ,endfor k=1: nfor i=1: nfor j=1: nif D(i,k)+D(k,j)<D(i,j)D(i,j)=D(i,k)+D(k,j);path(i,j)=path(i,k);end ,end ,end ,endif nargin=3min 1=D(start,termi nal);m(1)=start;i=1;path1=;while path(m(i),termi nal)=termi nalk=i+1;m(k)=path(m(i),termi nal);i=i+1;endm(i+1)=t

19、ermi nal;path仁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 i

20、nf;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

21、 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,运行结果如下:>> ID, pathZ'f lcyd(a)n =16D 二048S1911 6222071341413174D712231552224

22、1012SIS14208Q8191312242031912141198128011g1612511461119231911&8201911161415516141115135801211910673126551292012017211375151615222Z241619111701121101314230202420121192111017151661710f103516101321170169116161312191114si'101516012gIE84S124157rIS16512010111214IS14巧&3Id14611910c1191314g-16121

23、6231761811li0IE17201911US151016813g180path =1234412i12410*124101212311113c113712310101021010102110U101110413612613106121314613131313131313131313131313131212441331.2151341112134Id1221212121Lt1211112121?11131.1!15151511S9151115Id15131313131313131339131313131315133444144104斗斗U41I666jS6611i!6&IS1114

24、46h64i7124464444亍4&&4&413140103341344i13104413144611u66S11S9611e6e13七、结果分析收购点12345678收购量A80406070250B309080200C6010020180短缺量（100 kg）70此方案通过运算结果得出用于蔬菜调运及预期的短缺损失为10920元2、菜市场收购点12345678收购量A8089270250B627464200C288072180短缺量（100 kg）16162018此方案通过运算结果得出用于蔬菜调运及预期的短缺损失为11128元3、菜市&收购点12345678收

25、购量/100kgA80406070250B309080200C6010090180由上表看出，当A，B两收购点收购和供应量相等，增收的 7000kg由C收购点收购，这样下来所有的花费会最小八、参考文献,2011.1 张志涌，杨祖樱 MATLAB教程M.北京：北京航空航天大学出版社2 运筹学教材编写组，运筹学，清华大学出版社，2011.九、附录1、lingo运行结果1Global optimal soluti on found.Objective value:10920.00In feasibilities:0.000000Total solver iterati ons:12VariableV

26、alueReduced CostA180.000000.000000B140.000000.000000C10.0000000.000000D10.0000004.000000E160.000000.000000F170.000000.000000G10.00000024.00000H10.00000010.00000A20.00000022.00000B230.000000.000000C290.000000.000000D280.000000.000000E20.0000004.000000F20.00000022.00000G20.00000028.00000H20.0000006.00

27、0000A30.00000042.00000B30.00000032.00000C30.00000016.00000D30.0000004.000000E360.000000.000000F30.00000028.00000G3100.00000.000000H320.000000.000000A0.00000026.00000B0.00000014.00000C0.0000008.000000D0.0000000.000000E0.00000012.00000F0.00000018.00000G0.0000004.000000H70.000000.000000RowSlack or Surp

28、lusDual Price-1.000000-16.00000-14.00000-6.000000-2.0000008.0000000.0000000.000000-18.00000-6.0000004.000000-4.000000-14.000001 10920.002 0.0000003 0.0000004 0.0000005 0.0000006 0.0000007 0.0000008 0.0000009 0.00000010 0.00000011 0.00000012 0.00000013 0.0000002、lingo运行结果2Global optimal soluti on fou

29、nd.Objective value:11128.00In feasibilities:0.000000Total solver iterati ons:11VariableValueReduced CostA180.000000.000000B18.0000000.000000C10.0000000.000000D10.0000004.000000E192.000000.000000F170.000000.000000G10.00000024.00000H10.00000010.00000A20.00000022.00000B262.000000.000000C274.000000.0000

30、00D264.000000.000000E20.0000004.000000F20.00000022.00000G20.00000028.00000H20.0000006.000000A30.00000042.00000B30.00000032.00000C30.00000016.00000D30.0000004.000000E328.000000.000000F30.00000028.00000G380.000000.000000H372.000000.000000A0.00000018.00000B0.0000006.000000C16.000000.000000D16.000000.00

31、0000E0.0000004.000000F0.00000010.00000G20.000000.000000H18.000000.000000RowSlack or SurplusDual Price111128.00-1.00000020.000000-16.0000030.000000-14.0000040.000000-6.00000050.000000-10.0000060.0000008.00000070.0000000.00000080.0000000.00000090.000000-18.00000100.000000-6.000000110.0000004.000000120

32、.000000-4.000000130.000000-14.000001416.000000.0000001514.000000.000000162.0000000.000000170.0000008.0000001824.000000.0000001914.000000.000000200.0000004.000000210.0000008.0000003、lingo运行结果3Global optimal soluti on found.Objective value:11200.00In feasibilities:0.000000Total solver iterati ons:12Va

33、riableValueReduced CostA180.000000.000000B140.000000.000000C10.0000000.000000D10.0000004.000000E160.000000.000000F170.000000.000000G10.00000024.00000H10.00000010.00000A20.00000022.00000B230.000000.000000C290.000000.000000D280.000000.000000E20.0000004.000000F20.00000022.00000G20.00000028.00000H20.000

34、0006.000000A30.00000042.00000B30.00000032.00000C30.00000016.00000D30.0000004.000000E360.000000.000000F30.00000028.00000G3100.00000.000000H390.000000.000000RowSlack or SurplusDual Price111200.00-1.00000020.0000002.00000030.000000-6.00000040.000000-6.00000050.000000-24.0000060.000000-12.0000070.000000-2.00000080.000000-10.0000090.000000-20.00000100.000000-10.00000110.000000-8.0000001270.000000.000000