论文---光明市的菜篮子

数学建模论文材料124唐甜电气125雷园微电121姚倩光明市的菜篮子工程摘要根据题设中光明村的菜篮子工程和实际生活情况，本文建立了各收购点向各个菜场供应蔬菜的方案模型。在尽可能满足周围人群蔬菜需求的前提下，使得调运费用和短缺损失达到最小，并进行了模型的优化。对于问题一，首先利用Dijkstra算法计算出各收购点到各个菜场的最短距离，从而使得调运费用达到最小。然后以实际生活经验作为约束条件，以调运费用及短缺损失之和最小为目标函数建立线性规划模型。最后利用lingo程序求解得出了最佳分配方案,并得出总费用为4610元。对于问题二，增加了一组短缺量的约束条件，模型的目标函数不变，仍利用lingo程序对模型进行了优化，给出了新的分配方案，并得出总费用为4806元。与问题一中未优化的模型相比，虽然费用稍有增加，但是短缺量明显下降，更好的满足了人们的需求，从而得出了模型优化的实际意义。对于问题三，通过增加蔬菜种植面积来满足人们的日常需求，供给量必须大于或等于需求量，增加了一组供给量的约束条件，得到了新的分配方案，并得出总费用为4770元,并与模型一进行了比较。本文还对模型的优缺点进行了分析，最后对菜场和收购点提出了建议，使该模型更加经济合理，服务于生活。关键词：线性规划Dijkstra算法最短路线运输问题一问题重述光明市是一个人口不到15万人的小城市。根据该市的蔬菜种植情况，分别在花市（A），城乡路口（B）和下塘街（C）设三个收购点，再由各收购点分送到全市的8个菜市场，该市道路情况，各路段距离（单位：100m）及各收购点，菜市场①⑧的具体位置见图3.2.按常年情况，A,B,C三个收购点每天收购量分别为200，170和160（单位：100kg）,各菜市场的每天需求量及发生供应短缺时带来的损失（元/100kg）见表3.设从收购点至各菜市场蔬菜调运费为1元①7②54837A76B⑥6855471174③/(100kg.100m).7566⑤35④86610C10⑧511⑦表3菜市场每天需求（100kg）短缺损失（元/100kg）①7510②608③805④7010⑤10010⑥558⑦905⑧808(a)为该市设计一个从收购点至个菜市场的定点供应方案，使用于蔬菜调运及预期的短缺损失为最小；(b)若规定各菜市场短缺量一律不超过需求量的20%，重新设计定点供应方案；(c)为满足城市居民的蔬菜供应，光明市的领导规划增加蔬菜种植面积，试问增产的蔬菜每天应分别向A,B,C三个采购点供应多少最经济合理。二．模型假设为了研究方便，做出以下假设：1.只考虑运输费用和短缺损失，不考虑装卸等其他费用2.假设假设运输的蔬菜路途中没有损耗3.假设在蔬菜调配的过程中无意外发生三．符号说明收购点A,B,C分别记作1，2，3；菜市场1，2，…，8；x(i,j)代表从收购点i到菜市场j运送蔬菜的数量；b(j)代表菜市场j每天对蔬菜的需求量;)c(j)代表菜市场j的短缺损失；d(i代表收购点i每天的蔬菜收购量;A(i,j)代表从收购点i到菜市场j的最短路程。P代表蔬菜调用费Q代表短缺损失费Z代表总费用四模型的建立与求解4.1问题一4.1.1问题的分析要使用于蔬菜调运及预期的短期损失最小，即调运费用P与短缺损失Q之和最小。首先利用Dijkstra算法求出三个收购点到各菜市场的最短路径A（i,j）。然后以实际情况和题目要求作为约束条件，以总费用Z最小为目标函数建立线性规划模型，利用lingo求解。4.1.2模型的建立目标函数总费用Z来表示,总费用Z包括两部分:蔬菜调运费P，短缺损失Q，即：Z=P+Q，其中P=3181),(),(ijjixjiA；市场j的短缺量为31),()(ijixjb；则Q=8131),()()(cjijixjbj所以目标函数为81313181),()()(),(),(jiijjixjbjcjixjiAZ约束条件为：（1）从收购点i运送到菜市场j的蔬菜量小于等于收购点i的收购数量，即813,2,1)(),(jiidjix　　（2）从收购点i运送到菜市场j的蔬菜量小于等于菜市场j的需求数量，即318,,2,1)(),(ijjbjix　　（3）变量非负性限制)8,2,1;3,2,1(0jixij　　。综合以上结论，得出该的模型如下：　　　　　　　　　　　8,,2,1;3,2,10),(8,,2,1)(),(3,2,1)(),(..),()()(c),(),(min318131318181jijixjjbjixiidjixtsjixjbjjixjiAZijiijj4.1.3模型求解首先利用Dijkstra算法求出最短路径A(i,j),为了叙述方便，现把收购点A记为1v，菜市场1,2，…，8依次记为239,,,vvv。首先从始点1v开始，令P（1v）=0为永久标号，其余各点赋予T标号，T（iv）=（i=2,3,…,9）第一次迭代考察以永久标号点1v为始点的弧（12vv），（13vv），（14vv），（17vv）。因2347,,,vvvv均为T标号点，所以修改这四点的T标号如下T(2v)=min[T(2v),P(1v)+12w]=min[,0+4]=4;T(3v)=min[T(3v),P(1v)+13w]=min[,0+8]=8;T(4v)=min[T(4v),P(1v)+14w]=min[,0+8]=8;T(7v)=min[T(7v),P(1v)+17w]=min[,0+6]=6;（2）在现有的T标号中，将最小的T标号改为P标号，即2()Pv=4；此为第一次迭代的结果，然后再考察以点2v为始点的弧，按照第一次迭代的方法，由此求得收购点到菜市场的最短距离如表1所示。表1：收购点到菜市场的最短距离适当改变符号x(i,j)为：x(1,j)记为xj,x(2,j)记为yj,x(3,j)记为zj，那么各菜市场的短缺量分别为（75-x1-y1-z1）、（60-x2-y2-z2）、（80-x3-y3-z3）、（70-x4-y4-z4）、（100-x5-y5-z5）、（55-x6-y6-z6）、（90-x7-y7-z7）、（80-x8-y8-z8），那么短缺损失为Q=10(75-x1-y1-z1）+8(60-x2-y2-z2）+5（80-x3-y3-z3）+10(70-x4-y4-z4）+10(100-x5-y5-z5）+8(55-x6-y6-z6）+5(90-x7-y7-z7）+8(80-x8-y8-z8），总运费为P=4x1+8x2+8x3+19x4+11x5+6x6+22x7+20x8+14y1+7y2+7y3+16y4+12y5+16y6+23y7+17y8+20z1+19z2+11z3+14z4+6z5+15z6+5z7+10z8，所以目标函数总费用即为Z=-6x1+3x3+9x4+x5-2x6+17x7+12x8+4y1-y2+2y3+6y4+2y5+8y6+18y7+9y8+10z1+11z2+6z3+4z4-4z5+7z6+2z8+4860,约束条件表示为12820012817012816011175222603338044470555100666557779088880,0,1,2,3;1,2,,8xxxyyyzzzxyzxyzxyzxyzxyzxyzxyzxyzxijij根据建立的模型，利用LINGO软件（源码及输出结果见附录），输入目标函数和约束条件，求得收购点向各市场的供应情况如表2所示。12345678A488191162220B14771612162317C20191114615510表2各收购点向市场供应量分配表12345678A14500005500B06080300000C00001000600总计费用：4460（元）4.2问题二4.2.1问题分析与模型求解要求各菜市场短缺量一律不超过需求量的20%，相比问题一，只是增加了约束条件，从而实现了模型的优化。4.2.2模型的建立与求解对模型进行优化时，增加的约束条件为%20*8088880%20*9077790%20*5566655%20*100555100%20*7044470%20*8033380%20*6022260%20*7511175zyxzyxzyxzyxzyxzyxzyxzyx仍然利用lingo软件，输入目标函数和新的约束条件，得到优化后的分配方案如表3所示：表3.优化后的各收购点向市场供应方案12345678A751000605500B05064560000C00002407264总计费用：4806（元）比较问题一所得方案，可以看出虽然总计费用稍有增加，但是可以看出菜市场3,4,5的短缺量均有显著下降，方便了人们的生活。比较问题一所得方案，主要是对3、4、7、8市场的供给量进行了优化。可以看出虽然总计费用稍有增加，但是可以看出菜市场3,4,5的短缺量均有显著下降，极大的方便了人们的生活。4.3问题三4.3.1问题分析对于问题三，通过增加蔬菜种植面积来满足人们需求,表示蔬菜的供给量必须大于或等于人们的需求量，此时模型的约束条件稍有变化。4.3.2模型的建立与求解与问题一中的原始模型相比较，增加的约束条件为：x1+x2+x3+x4+x5+x6+x7+x8200;y1+y2+y3+y4+y5+y6+y7+y8=170;z1+z2+z3+z4+z5+z6+z7+z8160;仍利用lingo程序求解，优化后的分配方案如表4所示：表4各收购点向市场供应量分配表12345678A754000305500B02080700000C00007009080总计费用：4770（元）比较问题一中的模型可以看出总计费用稍有增加，但是却满足了各个菜场人们的日常需求，方便了人们的生活。但是，该模型忽略蔬菜积压带来的损失，与实际相比也稍有不合理之处。五．模型的评价与分析5.1模型的优点本文主要使用了线性规划和Dijkstra算法，模型简单易懂易于应用，并且根据实际情况的限制对模型进行了优化，使模型更具有广泛性。5.2模型的缺点模型忽略了货品积压，蔬菜在运输过程的损耗等实际限制条件，在特殊情况下模型与实际误差可能会很大,必须在实际应用中加以变通。六.模型的实际应用该模型很好的解决了蔬菜的分配问题，简易方便，易于实施。但是在实际生活中，收购点和菜场都必须要根据天气、时令、交通、地域等外界因素的变化来优化模型，适当调整分配方案，使其更加经济合理。参考文献[1].刘淋,利用LinGo求解几种有向图最短路问题[J],襄樊职业技术学院学报，2010.8：25-27[2]姜启源.谢金星.叶俊,数学模型[M].北京：高等教育出版社，2003.8[3].徐春玲，《垃圾处理问题最短路径的Dijkstra算法》，长春大学学报[J]2011.12：21（12）附录问题一lingo源码min=-6*x1+3*x3+9*x4+x5-2*x6+17*x7+12*x8+4*y1-y2+2*y3+6*y4+2*y5+8*y6+18*y7+9*y8+10*z1+11*z2+6*z3+4*z4-4*z5+7*z6+2*z8+4860;x1+x2+x3+x4+x5+x6+x7+x8=200;y1+y2+y3+y4+y5+y6+y7+y8=170;z1+z2+z3+z4+z5+z6+z7+z8=160;x1+y1+z1=75;x2+y2+z2=60;x3+y3+z3=80;x4+y4+z4=70;x5+y5+z5=100;x6+y6+z6=55;x7+y7+z7=90;x8+y8+z8=80;输出结果如下：Globaloptimalso