光明市的菜篮子工程.ppt

1、光明市的菜篮子工程,李伟达一、问题背景,光明市是一个人口不到15万人的小城市。根据该市的蔬菜种植情况，分别在花市（A），城乡路口（B）和下塘街（C)设三个收购点，再有个收购点分别送到全市的8个菜市场，该市道路情况，各路段距离(单位：100m)及各收购点，菜市场的具体位置见图3.2.按常年情况，A,B,C三个收购点每天收购量分别为200,170,160（单位：100kg），各菜市场的每天需求量及发生供应短缺时带来的损失（元/100kg）见表3.设从收购点至各菜市场蔬菜调运费为1元/（100kg.100m）.,（a）为该市设计一个从收购点至各个菜市场的定点供应方案，使用于

2、蔬菜调运及预期的短期损失为最小； （b）若规定各菜市场短缺量一律不超过需求量的20%，重新设计定点供应方案； （c）为满足城市居民的蔬菜供应，光明市的领导规划增加蔬菜种植面积，试问增加的蔬菜每天应分别向A、B、C三个采购点各供应多少最经济合理。,问题分析,本题旨在解决如何减少菜篮子工程的开销，即蔬菜调运费用和短缺损失两部分的费用总和。蔬菜调运费用主要取决于蔬菜调运路径的选取，这是典型的旅行商问题，采用弗洛伊德算法和蚁群算法，用MATLAB软件编程求解即可得到最路径。短缺损失主要取决于调运到各菜市场的收购量。菜篮子工程的开销取决于这两部分，对两部分的方案进行线性规划，用LINGO软件进行求解即可

3、得到最优分配方案。,1、只考虑蔬菜调运费用和短缺损失费用，不考虑装卸等其他费用； 2、假设蔬菜在调运路途中没有损耗； 3、假设各菜市场蔬菜只来源于A、B、C三个收购站，而无其他来源； 4、假设各收购站供应蔬菜质量以及单位运价相同； 5、假设各收购站可以作为中转站。,基本假设,符号说明,模型的建立,目标函数蔬菜运输和短缺损失的总费用Z包括两部分: 蔬菜调运费用P，短缺损失费用P。 Xij：第i个收购点向第j个菜市场运输蔬菜的数量（i=1,2,3;j=1,8）； Dij：调运路径中，第i个收购点到第j个菜市场的距离（i=1,2,3；j=1,8）； A：从收购点至各菜市场蔬菜调运费单价； 则蔬菜调运

4、总费用P为： ai：第i个收购点的供应量（i=1,2,3）; bj:第j个菜市场的需求量（j=1,8）; B:第j个菜市场因供给小于需求量的单位短缺损失; 则短缺损失总费用为Q： 则蔬菜运输和短缺损失的总费用Z： Z=P+Q,返回,A(i,j)=(4 8 8 19 11 6 22 20; 14 7 7 16 12 16 23 17; 20 19 11 14 6 15 5 10) 适当改变符号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-x

5、4-y4-z4）、（100-x5-y5-z5）、（55-x6-y6-z6）、（90-x7-y7-z7）、（80-x8-y8-z8）， 那么短缺损失为 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）运费为 4x1+8x2+8x3+19x4+11x5+6x6+22x7+20 x8+14y1+7y2+7y3+16y4+12y5+16y6+23y7+17y8+20z1+19z2+11z3+14z4+6z5

6、+15z6+5z7+10z8,问题（a）的模型,那么总费用即为 Z=-6x1+3x3+9x4+x5-2x6+17x7+12x8+4y1-y2+2y3+6y4+2y5+8y6+18y7+9y8+10z1+11z2+6z3+4z4-4z5+7z6+2z8+4860,约束条件表示为,结果分析： 在该题目的假设下，最经济合理的蔬菜定点供应方案是： 收购点A每天向菜市场1运送蔬菜75千克，向5运送70千克，向6运送55千克； 收购点B每天向菜市场2运送蔬菜60千克，向3运送80千克，向4运送30千克； 收购点C每天向菜市场5运送蔬菜30千克，向7运送90千克，8运送40千克； 在这种情况下使用于蔬菜调运

7、及预期的短缺损失为：4610元。 在这种供应方案下，除了菜市场4和8外，其余的菜市场的蔬菜供应都得到满足，其中菜市场4和8都短缺40千克。,若规定各菜市场短缺量一律不超过需求量的20%，重新设计定点供应方案。对于该问题，目标函数并没有任何变化，总费用仍然是调运费用以及短缺损失，该问题只是在原问题的基础上加上各菜市场短缺量一律不超过需求量的20%这一约束条件，各菜市场的短缺量在以上问题中已求出，该问题只需要在原问题的基础上加上以下约束即可，,方案b,利用Matlab实现过程：,目标函数： Z=-6x1+3x3+9x4+x5-2x6+17x7+12x8+4y1-y2+2y3+6y4+2y5+8y6

8、+18y7+9y8+10z1+11z2+6z3+4z4-4z5+7z6+2z8+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=0.8*75; x2+y2+z2=0.8*60; x3+y3+z3=0.8*80; x4+y4+z4=0.8*70; x5+y5+z5=0.8*100; x6+y6+z6=0.8*55; x7+y7+z7=0.8*90; x8+y8+z8=0.8*80;,约束条件：,返回,f= ; ; ;目标函数的系数（目标函数必须

9、求最小值） A= ; ;线性不等式约束的约束系数 b=11; -3; 线性不等式的不等号右边数字 Aeq=-2 0 1;线性等式约束的约束系数 beq=1; 线性等式的不等号右边数字 lb=0; 0; 0; 变量的边界约束，下界的约束 ub=Inf; Inf; Inf; 下界的约束由于无上界，故设ub=Inf;Inf;Inf x, fval, exitflag, output, lambda=linprog(f, A, b, Aeq, beq, lb, ub),利用Matlab实现语言：,在该题目的假设下，最经济合理的蔬菜定点供应方案是： 收购点A向菜市场1运送蔬菜75千克，向3运送10千克，

10、向5运送60千克，向6运送55千克； 收购点B向菜市场2运送蔬菜60千克，向3运送54千克，向4运送56千克； 收购点C向菜市场5运送蔬菜24千克，向7运送72千克，向8运送64千克。 在这种情况下使用于蔬菜调运及预期的短缺损失为：4806元。其中，只有菜市场1,2,6的需求得到满足，其余菜市场的短缺量分别为：市场3短缺80-（10+54）=16千克；市场4短缺70-56=14千克；市场5短缺100-（60+24）=16千克；市场7短缺90-72=18千克；市场8短缺80-64=16千克。,说明： x = linprog(c,A,b,Aeq,beq,lb,ub,x0,options) 用opt

11、ions指定的优化参数进行最小化。可以使用optimset来设置这些参数 x,fval = linprog(.) 在优化计算结束之时返回线性规划问题在解x处的目标函数值fval。 x,fval,exitflag = linprog(.) 在优化计算结束之时返回exitflag值，描述函数计算的退出条件。 x,fval,exitflag,output = linprog(.) 在优化计算结束之时返回返回结构变量output x,fval,exitflag,output,lambda = linprog(.) 在优化计算结束之时返回线性规划问题最优解x处的拉格朗日乘子lambda,为满足城市居民的

12、蔬菜供应，光明市的领导规划增加蔬菜种植面积，试问增加的蔬菜每天应分别向A、B、C三个采购点各供应多少最经济合理。 为满足城市居民的需求，增种的蔬菜量应使得菜市场1到8都达到每天的需求量，另外显然有：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;,方案C,目标函数和前两个题是一样的。 应用软件求解，在运行窗口中输入以下内容： 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+

13、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;,结果分析 增种后的定点供应方案是： 收购点A向菜市场1输送蔬菜75千克，向3输送40千克，向5输送30千克，向6输送55千克。该收购点每天共向外运送蔬菜（即每天收购量）20