蔬菜供应方案设计样本

蔬菜供应方案设计摘要由于人们生活水平发展，开始讲求天然产品，这使蔬菜产品有了辽阔市场。商业公司规定最佳销售和利润最大化，于是要设定适当蔬菜供应方案力求利润最大化和市场供应便捷性。本文运用Floyd算法求出各蔬菜采购点到每个菜市场最短运送距离，然后用lingo软件计算蔬菜调运费用及预期短缺损失最小条用方案。最优运送方案为菜市场（A）运往菜市场1蔬菜数量为8000kg，运往菜市场2蔬菜数量为4000kg，运往菜市场5蔬菜数量为6000kg，运往菜市场6蔬菜数量为7000kg；城乡路口（B）运往菜市场2蔬菜数量为30kg，运往菜市场3蔬菜数量为9000kg，运往菜市场4蔬菜数量为8000kg；南街口（C）运往菜市场5蔬菜数量为6000kg，运往菜市场7蔬菜数量为10000kg，运往菜市场8蔬菜数量为kg。用于蔬菜调运及预期短缺最小损失为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（单位：100kg）,各菜市场每天需求量及发生供应短缺时带来损失（元/100kg）见表1。设从收购点至各菜市场蔬菜调运费为2元/(100kg.100m)。图1蔬菜供应网点图表1各蔬菜市场需求量表菜市场每天需求（100kg）短缺损失（元/100kg）①8010②708③905④8010⑤12010⑥708⑦1005⑧908试为该市设计一种用于蔬菜调运及预期短缺损失为最小从收购点至各个菜市场定点供应方案；若规定各菜市场短缺量一律不超过需求量20%，重新设计定点供应方案；规划增长蔬菜种植面积后增产蔬菜每天应分别向A、B、C三个采购点供应多少最经济合理。二、问题分析求总运费最低，可以先求出各采购点到菜市场最小运费，由于单位重量运费与距离成正比。第一问可以用Floyd算法求出最短途径即求出各个采购点都菜市场最短运送距离，乘以单位重量单位距离运送费用就是单位重量各运送路线费用，然后用线性办法即可解得相应最小调运费及预期短缺损失。第二问规定各菜市场短缺量一律不超过需求量20%，只需在第一问基本上加上新设定条件，就可得到新供应方案。第三问建立新线性问题进行求解。三、问题假设1、各个收购点、中转站以及菜市场都可以做为中转点。2、各个收购点、中转站以及菜市场最大容纳量为700吨。3、假设运送路途中蔬菜没有任何损耗。4、假设只考虑运送费用和短缺费用，不考虑装卸等其她费用。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（弗洛伊德）算法。以图中每个顶点作为源点，调用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到jd(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最短途径长度，即它是从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(intk=0；k<n；k++)

for(inti=0；i<n；i++)

for(intj=0；j<n；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<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=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);fori=1:nforj=1:nifD(i,j)~=infpath(i,j)=j;end,end,endfork=1:nfori=1:nforj=1:nifD(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,endifnargin==3min1=D(start,terminal);m(1)=start;i=1;path1=[];whilepath(m(i),terminal)~=terminalk=i+1;m(k)=path(m(i),terminal);i=i+1;endm(i+1)=terminal;path1=m;end依照题目网络列出距离矩阵，在MATLAB中编写程序代码如下：a=[0488infinf6infinf7inf4infinfinf;407infinfinf5infinfinfinfinfinfinfinf;870infinfinfinfinfinf3infinfinf7inf;8infinf0inf5infinfinf5inf467inf;infinfinfinf0infinfinfinfinfinfinf5infinf;infinfinf5inf0infinfinfinf673inf6;65infinfinfinf0infinfinf75infinfinf;infinfinfinfinfinfinf011inf10infinfinf5;infinfinfinfinfinfinf110infinfinf6inf10;7inf35infinfinfinfinf0infinfinf6inf;infinfinfinfinf6710infinf0infinfinf8;4infinf4inf75infinfinfinf0infinfinf;infinfinf653infinf6infinfinf011inf;infinf77infinfinfinfinf6infinf110inf;infinfinfinfinf6inf510inf8infinfinf0]调用a,运营成果如下：七、成果分析1、菜市场收购点12345678收购量A80406070250B309080200C6010020180短缺量（100kg）70此方案通过运算成果得出用于蔬菜调运及预期短缺损失为10920元。2、菜市场收购点12345678收购量A8089270250B627464200C288072180短缺量（100kg）16162018此方案通过运算成果得出用于蔬菜调运及预期短缺损失为11128元。3、菜市场收购点12345678收购量/100kgA80406070250B309080200C6010090180由上表看出，当A，B两收购点收购和供应量相等，增收7000kg由C收购点收购，这样下来所有耗费会最小。八、参照文献[1]张志涌，杨祖樱.MATLAB教程[M].北京：北京航空航天大学出版社，.[2]《运筹学》教材编写组，运筹学，清华大学出版社，.附录1、lingo运营成果1Globaloptimalsolutionfound.Objectivevalue：10920.00Infeasibilities：0.000000Totalsolveriterations：12VariableValueReducedCostA180.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.000000A30.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.000000RowSlackorSurplusDualPrice110920.00-1.00000020.000000-16.0000030.000000-14.0000040.000000-6.00000050.000000-2.00000060.0000008.00000070.0000000.00000080.0000000.00000090.000000-18.00000100.000000-6.000000110.0000004.000000120.000000-4.000000130.000000-14.00000lingo运营成果2Globaloptimalsolutionfound.Objectivevalue：11128.00Infeasibilities：0.000000Totalsolveriterations：11VariableValueReducedCostA180.000000.000000B18.0000000.000000C10.0000000.000000D10.0000004.000000E192.000000.000000F170.000000.000000G10.00000024.00000H10.00000010.00000A20.00000022.00000B262.000000.000000C274.000000.000000D264.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.000000E0.0000004.000000F0.00000010.00000G20.000000.000000H18.000000.000000RowSlackorSurplusDualPrice111128.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.000000-4.000000130.000000-14.000001416.000000.0000001514.000000.000000162.0000000.000000170.0000008.0000001824.000000.0000001914.000000.000000200.0000004.000000210.0000008.000000lingo运营成果3Globaloptimalsolutionfound.Objectivevalue：11200.00Infeasibilities：0.000000Totalsolveriterations：12VariableValueReducedCostA180.000000.000000B140.000000.000000C10.0000000.000000D10.0000004.000000E160.000000.000000F170.000000.000000G10.00000024.00000H10.00000010.00000A20.00000022.00000B230.000000.000000C290.000000.000000D280.000000.000000