运筹学-光明市的菜篮子工程

光明市的菜篮子工程,导师：石小平 学生：潘建攻,吕一峰,张 芮,contents,目,录,问题重述,1,2,3,4,符号约定与假设,问题分析,模型建立与求解,1.,问题重述,问题重述,光明,市是一个人口不到,15,万人的小城市，根据该市的蔬菜种植情况分别在,花市,(A),、,城乡,路口,(B),和,下塘,街,(C),设,三个收购点。清晨,5,点前菜农将蔬菜送至各收购点，再由各收购点分送到全市的,8,个菜市场。该市道路情况、各路段距离（单位：,100m,）及各收购点、菜市场,.,的具体位置如图：,问题重述,按,常年情况，、,和,三个收购点每天收购量分别为,200,、,170,和,160(,单位,：,100kg),，,各菜市场的每天需求量及发生供应短缺时带来的,损失,(,元,/,100kg),见,表。设从收购点至各菜市场蔬菜调运费用为,1,元,/(100kg100m),。,菜市场,每天需求,(100Kg),短缺损失,(,元,/100Kg),75,10,60,8,80,5,70,10,100,10,55,8,90,5,80,8,请你解决以下问题：,（,1,）为该市设计一个从各收购点至各菜市场的定点供应方案，使用于蔬菜调运及预期的短期损失最小。,（,2,）若规定各菜市场短缺量一律不超过需求量的,20%,，重新设计定点供应方案。,（,3,）为满足城市居民的蔬菜供应，光明市的领导规划增加蔬菜种植面积，试问增加的蔬菜每天应分别向,A,、,B,、,C,三个采购点各供应多少最经济合理。,02,2.,符号约定与假设,假设一：,只,考虑运输费用和短缺费用，不考虑装卸等其他,费用,。,假设二：,假设,运输的蔬菜路途中没有,损,。,假设三,：,假设,各市场蔬菜只来源于三个收购站，无其他来源且三个收购站所收购蔬菜全部运往,8,个菜市场。,假设四：,假设,规划增加蔬菜种植面积后，蔬菜供应总量恰好能满足,8,个菜市场的需求量。,符号,约定与假设,符号,约定与假设,符号,符号说明,x,ij,第,i,个收购点向,j,市场供给的数量,(i=1,2,3,j=1,2 8),x,4j,第,j,个市场因供给量小于需求量的单位短缺损失,(j=1,2 8),p,ij,第,i,个收购点向,j,市场供给的单位运费,b,i,第,i,个收购点供应量,(i=1,2,3,4),d,j,第,j,个市场需求量,(j=1,2 8),3.,问题分析,问题分析,这,是一个产销不平衡的规划,问题,(,产,小于,销,),，,三个收购点每天蔬菜收购,量,5,30(100kg,),，,而,8,个菜市场每天共,需,6,10(100kg),，,所以，,8,个菜市场每天将共短缺,80(100kg),。,可设一个虚拟的,D,，每天蔬菜收购量为,80(100kg,),，,正好弥补,8,个菜市场每天短缺的那部分，则如下表：但虚拟收购点,D,运往,8,个菜市场的运费无法计算。在本题中，只考虑运费及蔬菜短缺时的总费用，考虑到虚拟收购点,D,运往,8,个菜市场的路径无法确定，及,D,所运往,8,个菜市场的蔬菜均为各个菜市场短缺的，故可将,8,个菜市场短缺所造成的损失等效于,D,运往,8,个菜市场的运费。,1,2,3,4,5,6,7,8,产量,A,200,B,170,C,160,D,80,销量,75,60,80,70,100,55,90,80,610,问题分析,为了,求解模型，必须求出,系数,(p,ij,),，,其中每一 表示第,i,个收购点向,j,市场供给单位量蔬菜的运费。但因为从收购点至各菜市场单位量蔬菜单位路程的调运费用为,1,元,/(100kg*100m),，,而蔬菜的单位量为,100kg,，单位距离为,100m,，则可求出第,i,个收购点到第,j,市场每单位蔬菜的单位距离运费为,1,元,/(100m,*,100kg),*,100m*100kg=1,元。,因而,p,ij,在,数值上等于第,i,个收购点到第,j,市场的距离值，从而等价于一个求最短路的问题。,对于,x,4j,(j=1,8),因其每短缺,100kg,损失,1,元，而蔬菜的单位量为,100kg,，,故,p,4j,在,数值上等于第,j,个市场供应短缺时带来的损失值。,从,图中可以找出从第,i,个收购点到第,j,市场的最小距离值，也即单位最小运费,p,ij,。,如下,：,1,2,3,4,5,6,7,8,A,4,8,8,19,11,6,22,20,B,14,7,7,16,12,16,23,17,C,20,19,11,14,6,15,5,10,D,10,8,5,10,10,8,5,8,4.,模型建立与求解,模型,建立与求解,由上述分析，这是一道运输问题，我们建立目标函数以及给出约束条件即可求解。,目标函数的总,费用,Z,包括两项,:,蔬菜调运费、各市场供给量小于需求量的短缺损失,。由问题分析中，我们指出将短缺损失的费用等效算作运输费用。即可得下列式子：,目标函数：,约束条件：,1,：,4,个收购点的蔬菜全部供给给,8,个,市场,2,：,每个市场的蔬菜都来自,4,个收购,点,3,：,变量,非负性限制,模型建立与求解,问题,一,：,由上述关系式，给出下列式子,根据上式的,模型，利用,LINGO,软件，输入目标函数和约束条件，求解模型的最优解。,模型建立与求解,模型建立与求解,问题一的具体分配方案如下：此时为最小费用,Z=4610,元。,1,2,3,4,5,6,7,8,A,75,40,0,0,30,55,0,0,B,0,20,70,80,0,0,0,0,C,0,0,0,0,70,0,90,0,D,0,0,0,0,0,0,0,80,模型建立与求解,问题,二,：按,题中,问题规定,各菜市场短缺量一律不超过需求量的,20%,的条件，我们对需求量的约束条件进行了修改。,根据上式的,模型，利用,LINGO,软件，输入目标函数和约束条件，求解模型的最优解。,模型建立与求解,模型建立与求解,问题二的具体分配方案如下：此时为最小费用,Z=4806,元。,1,2,3,4,5,6,7,8,A,75,10,0,0,60,55,0,0,B,0,50,64,56,0,0,0,0,C,0,0,0,0,24,0,72,64,D,0,0,16,14,16,0,18,16,模型建立与求解,问题三：,为满足城市居民的蔬菜供应，光明市的领导规划增加蔬菜种植面积。此时,A B C,三个收购点应恰好能满足,8,个菜市场的需求量。因此我们对需求量的约束条件进行了修改。,根据上式的,模型，利用,LINGO,软件，输入目标函数和约束条件，求解模型的最优解。,模型建立与求解,模型建立与求解,问题,三,的具体分配方案如下：此时为最小费用,Z=4770,元。,1,2,3,4,5,6,7,8,产量,A,75,40,0,0,30,55,0,0,200,B,0,20,80,70,0,0,0,0,170,C,0,0,0,0,70,0,90,80,240,谢谢！,附录,P,roblem1:,min=4*x11+8*x12+8*x13+19*x14+11*x15+6*x16+22*x17+20*x18+14*x21+7*x22+7*x23+16*x24+12*x25+16*x26+23*x27+17*x28+20*x31+19*x32+11*x33+14*x34+6*x35+15*x36+5*x37+10*x38+10*x41+8*x42+5*x43+10*x44+10*x45+8*x46+5*x47+8*x48,;,x11+x12+x13+x14+x15+x16+x17+x18=200;,x21+x22+x23+x24+x25+x26+x27+x28=170;,x31+x32+x33+x34+x35+x36+x37+x38=160;,x41+x42+x43+x44+x45+x46+x47+x48=80;,x11+x21+x31+x41=75;,x12+x22+x32+x42=60;,x13+x23+x33+x43=80;,x14+x24+x34+x44=70;,x15+x25+x35+x45=100;,x16+x26+x36+x46=55;,x17+x27+x37+x47=90;,x18+x28+x38+x48=80;,x11=0;x12=0;x13=0;x14=0;x15=0;x16=0;x17=0;x18=0;,x21=0;x22=0;x23=0;x24=0;x25=0;x26=0;x27=0;x28=0;,x31=0;x32=0;x33=0;x34=0;x35=0;x36=0;x37=0;x38=0;,x41=0;x42=0;x43=0;x44=0;x45=0;x46=0;x47=0;x48=0,;,附录,P,roblem2:,min=4*x11+8*x12+8*x13+19*x14+11*x15+6*x16+22*x17+20*x18+14*x21+7*x22+7*x23+16*x24+12*x25+16*x26+23*x27+17*x28+20*x31+19*x32+11*x33+14*x34+6*x35+15*x36+5*x37+10*x38+10*x41+8*x42+5*x43+10*x44+10*x45+8*x46+5*x47+8*x48;,x11+x12+x13+x14+x15+x16+x17+x18=200;,x21+x22+x23+x24+x25+x26+x27+x28=170;,x31+x32+x33+x34+x35+x36+x37+x38=160;,x41+x42+x43+x44+x45+x46+x47+x48=80;,x11+x21+x31+x41=75;,x12+x22+x32+x42=60;,x13+x23+x33+x43=80;,x14+x24+x34+x44=70;,x15+x25+x35+x45=100;,x16+x26+x36+x46=55;,x17+x27+x37+x47=90;,x18+x28+x38+x48=80;,x41=75*0.2;x42=60*0.2;x43=80*0.2;x44=70*0.2;x45=100*0.2;x46=55*0.2;x47=90*0.2;x48=0;x12=0;x13=0;x14=0;x15=0;x16=0;x17=0;x18=0;,x21=0;x22=0;x23=0;x24=0;x25=0;x26=0;x27=0;x28=0;,x31=0;x32=0;x33=0;x34=0;x35=0;x36=0;x37=0;x38=0;,x41=0;x42=0;x43=0;x44=0;x45=0;x46=0;x47=0;x48=0,;,附录,P,roblem2:,min=4*x11+8*x12+8*x13+19*x14+11*x15+6*x16+22*x17+20*x18+14*x21+7*x22+7*x23+16*x24+12*x25+16*x26+23*x27+17*x28+20*x31+19*x32+11*x33+14*x34+6*x35+15*x36+5*x37+10*x38;,x11+x12+x13+x14+x15+x16+x17+x18=200+a;,x21+x22+x23+x24+x25+x26+x27+x28=170+b;,x31+x32+x33+x34+x35+x36+x37+x38=160+80-a-b;,x11+x21+x31=75;,x12+x22+x32=60;,x13+x23+x33=80;,x14+x24+x34=70;,x15+x25+x35=100;,x16+x26+x36=55;,x17+x27+x37=90;,x18+x28+x38=80;,x11=0;x12=0;x13=0;x14=0;x15=0;x16=0;x17=0;x18=0;,x21=0;x22=0;x23=0;x24=0;x25=0;x26=0;x27=0;x28=0;,x31=0;x32=0;x33=0;x34=0;x35=0;x36=0;x37=0