光明市的菜篮子工程

1、光明市的菜篮子工程摘要本文研究的是蔬菜市场为满足不同条件的最优调配方案问题，用了 Froyd 算法、线性规划建立了一系列数学规划模型，并用 MATLAB和LINGO软件编 程实现。关于问题一：用Froyd算法结合MATLAB编程求出收购点至个菜市场的最 短距离，以用于蔬菜调运及预期的短缺损失为最小为目标建立线性规划模型。用LINGO编程求得日均费用最少为 4610元。关于问题二：在模型一的基础增加各菜市场短缺量一律不超过需求量的20%的约束条件，用LINGO编程求得最少日均费用以及最优供应方案。费用最 少为4806元，供应方安见正文。关于问题三：在模型一的基础上，改为以供货充足、费用最小为目标

2、，建立 模型三，用LINGO编程求得日均费用为4770元，增产的蔬菜每天应分给 C收专业资料购点 8000Kg 。关键字：蔬菜市场调配方案Froyd算法线性规划一、问题的重述海江市是一个人口不到20万人的小城市。根据该市的蔬菜种植情况，分别 在菜市场（A）,菜市场（B）和菜市场（C）设三个收购点，再由各收购点分送 到全市的8个菜市场，该市道路情况，各路段距离（单位：100m ）及各收购点, 菜市场L的具体位置见图3.2.按常年情况，A,B,C三个收购点每天收购量分 别为30000 , 25000和20000 （单位：100 kg ），各菜市场的每天需求量及发生 供应短缺时带来的损失（元/100

3、kg ）见表3.设从收购点至各菜市场蔬菜调运费 为 1 元/（100kg.100m）.754837A 76 B685547117475663510C 10511表3菜巾场每天需求（100 kg ）短缺损失（元/100kg ）15010100812051001014010100814051208（a）为该市设计一个从收购点至个菜市场的定点供应方案，使用于蔬菜调运及预期的短缺损失为最小；（b）若规定各菜市场短缺量一律不超过需求量的 20% ,重新设计定点供应方案;（c）为满足城市居民的蔬菜供应，光明市的领导规划增加蔬菜种植面积，试问增产的蔬菜每天应分别向A,B,C三个采购点供应多少最经济合理。二、

4、符号说明DAi i 1,28从A U i （各个菜市场）的最短距离DBi i 1,28从B U i （各个菜市场）的最短距离Deii1,28从C到i（各个菜市场）的最短距离SAii1,28从A到i（各个菜市场）的运货量SBii1,28从B到i（各个菜市场）的运货量&i1,28从CUi（各个菜市场）的运货量P总调运费Q短缺损失R总费用三模型假设1、假设日需求量与缺货损失费用不变。2、假设在蔬菜调配的过程中无意外发生。3、假设新增产的蔬菜能够满足缺货量。四模型的建立与求解4.1 问题一4.1.1 问题的分析：为了使用于蔬菜调运及预期的短缺损失为最小，即调运费用与缺货损失之和 最小。首先考虑

5、调运费用P, P为距离与送货量的积，因为与送货距离相关，我 们必须先求出A、B、C三个采购点至各个菜市场的最短距离。 采用Froyd算法,结合MATLAB编程实现。其次考虑缺货损失 Q,以题中要求为约束条件，损失 最低位目标建立线性规划模型，用 LINGO编程求解4.1.2 模型的建立与求解:由图和表格的信息知，建立一个线性规划模型，使得蔬菜调运及预期的短缺 损失为最小。调运总费用P为:8PSAigDAii 18SBi gDBii 18SCi gDCi i 1若使调运总费用最少，则应保证A、B、C三个收购点到8个菜市场的路程,最短路线的求解过程如图一:图一：求解过程图分析上图可知，该路线为无向

6、网络，就该图而言，网络弧集为:E=(v1,v2),(v1,v4),(v1,v5),(v2,v1),(v2,v3),(v2,v5),(v2,v6),(v3,v2),.(v3,v6),(v3,v 8),(v3,v9),(v4,v1),(v4,v5).(v4,v7),(v4,v10),(v5,v1),(v5,v2),(v5,v4),(v5,v6),(v5,v 7),(v5,v8),(v6,v2),(v6,v3),(v6,v5),(v6,v8),(v7,v4),(v7,v5),(v7,v8),(v7,v11),(v8,v3),(v8,v5),(v8,v6),(v8,v7),(v8,v9), (v8,v

7、11),(v9,v3),(v9,v8),(v9,v11),(v9,v13),(v9,v15),(v10,v4),(v10,v11),(v10,v12),(v10,v14),(v1 1,v7),(v11,v8),(v11,v9)(v11,v10),(v11,v12),(v12,v10),(v12,v11),(v12,v13),(v1 2,v14),(v13,v9),(v13,v12),(v13,v14),(v14,v10),(v14,v12),(v14,v13),(v15,v9)下面来确定网络权矩阵：W= (wij )n n其中Wi = lij ,当(Vi ,Vj )属于 E 时，lij 为弧(

8、Vi ,Vj )的权Wi =0 , i=1,2,3n明=inf,当(v ,Vj)不属于E时。(inf为无穷大，n为网络结点个数) 按上述规定，该网络的权矩阵为：7 infinf inf inf inf inf inf inf infinf inf707inf705infinfinf8inf inf063 inf inf6inf7inf 5infinf inf11 infinf 7infinfinfinfinfinfinfinfinfinfinfinfinfinfinf48 inf 6048 inf inf inf inf infinf infinf36inf70inf5infinfinfinf

9、infinfinfinfinfinf54inf04infinf7infinfinfinfinfinf7inf85406inf5infinfinfinfinfinf11infinfinfinf60inf3inf6inf5infinfinf7infinfinfinfinf068inf10infinfinfinfinfinfinf753606infinfinfinfinfinfinfinfinfinfinfinf860105infinfinfinfinfinfinfinfinf6infinf10011infinfinfinfinfinfinfinfinfinf10inf5110infinfinfin

10、finfinfinfinfinf5infinfinfinfinf0因为上述网络有15个结点，故网络的权矩阵均为15阶矩阵。现在给出网络最短路线的Froyd算法：(1) d1=w.(w为所给网络的n阶权矩阵)(2) dk= (dkj)n n,k=2,3,p.其中 dkj =min d(k 1h+d(k 1%浦=1,2,n.计算次数的确定：当Wj 0时，p由下式确定：p ln(n-1)/ln2 ,这样的dp就确定了网络各点间的最短距离。此处 n=15,解出p 3.8074故只需要取p=4即可，即算到d4即可。按照Froyd算法：d1=d,d2=fld(15,d1),d3=fld(15,d2),d4

11、=(fld(15,d3), 算的 d4 为:071454108121812152024222370712831281419131920241914701613611711181218172316512160613591571215211720481360748141311172022191036137095111610161721168121154904101271316181512879854061151112161118141115141110609396145121918713161211906815101415131212111075360620102422112311d4111918

12、1415171613112017212017161215101111242317222118161410111919191620191615111414即为该网络的距离矩阵，距离矩阵的第i行指明了 Vi到其他各点的最短距离。根据上述矩阵，分别找出A,B,C到、的最短距离,见表表一：收购点到菜市场的最短距离最短距离（单位：100千米）A488191162220B14771612162317C20191114615510调运量的限制:Q 10 75 SA1 SB1SC1860SA2 SB2SC2580 SA3SB3 SC3A3 B3 C 310 70Sa4 Sb4 Sc4短缺损失费为：810 10

13、0SA5 SB5 SC555SA6SB6SC 690Sa7Sb7Sc780 Sa8Sb8 Sc8总费用为：R P Q由以上约束条件，用LINGO软件进行线性规划求解（源程序及完整运行结果见附录），部分运行结果如下:Global optimal solution found.Objective value:4610.000Infeasibilities:0.000000Total solver iterations:10Model Class:LPTotal variables:26Nonlinear variables:Integer variables:Total constraints:2

14、2Nonlinear constraints:Total nonzeros:124Nonlinear nonzeros:VariableValueReduced CostP3890.0000.000000Q720.00000.000000SA175.000000.000000SA20.0000000.000000SA30.0000000.000000SA40.0000002.000000SA570.000000.000000SA655.000000.000000SA70.00000012.00000SA80.0000005.000000SB10.00000011.00000SB260.0000

15、00.000000SB380.000000.000000SB430.000000.000000SB50.0000002.000000SB60.00000011.00000SB70.00000014.00000SB80.0000003.000000SC10.00000021.00000SC20.00000016.00000SC30.0000008.000000SC40.0000002.000000SC530.000000.000000SC60.00000014.00000SC790.000000.000000SC840.000000.000000从上述运行结果中可以得出调运方案为:在此种方案下，

16、蔬菜调运及预期的短缺损失为最小，最小金额为4610元。4.1.3模型的评价与分析：本模型用Froyd算法快捷的求出了 A、B、C三个收购点到8个菜市场的最 短路程，用线性规划模型使得费用最低， 并给出了上图所示的调配方案。 在所得 方案中每日只需4610元。4.2 问题二4.2.1 问题的分析：若按规定各菜市场短缺量律不超过需求量的 20% ,则只需要在模型一的基础上在增加一个约束条件：每个菜市场的供应量必须不低于需求量的80%即可。即得到满足条件的模型二。4.2.2模型的建立与求解：各菜市场短缺量一律不超过需求量的 20%,为满足这一条件，现对方案一进行调整。只需在方案 一中加一限制条件：S

17、B1SC1750.860SB2SC2600.848SB3SC3800.864SB4SC4700.856SB5 SC5 100 0.8 80Sb6Sc6550.844SB7SC7900.872SB8SC8800.864B 8C 8SA4SA5SA6SA7同理可用LINGO编程（源程序及完整运行结果见附录），部分运行结果如下:Global optimal solution found.Objective value:4806.000Infeasibilities:0.000000Total solver iterations:13LPModel Class:Total variables:26No

18、nlinear variables:0Integer variables:0Total constraints:30Nonlinear constraints:0Total nonzeros:148Nonlinear nonzeros:0VariableValueReduced CostP4208.0000.000000Q598.00000.000000SA175.000000.000000SA210.000000.000000SA30.0000000.000000SA40.0000002.000000SA560.000000.000000SA655.000000.000000SA70.000

19、00012.00000SA80.0000005.000000SB10.00000011.00000SB250.000000.000000SB364.000000.000000SB456.000000.000000SB50.0000002.000000SB60.00000011.00000SB70.00000014.00000SB80.0000003.000000SC10.00000021.00000SC20.00000016.00000SC30.0000008.000000SC40.0000002.000000SC524.000000.000000SC60.00000014.00000SC77

20、2.000000.000000SC864.000000.000000从上述运行结果得知调整后的方案为:调整后的总损失为：4806元4.2.3 模型的评价与分析：在增加了供货量的限制条件后，只需在模型一的基础上再增加约束条件即得到模型二。在本模型下日均花费最低为 4806元。新的调配方案如上图所示。4.3 问题三4.3.1 问题的分析：本题的目标有二：一、要满足每个菜市场的供货量充足；二、要使得总费用最低。所以我们在模型一的基础上增加了上述两个限制条件，即得到模型三。使得在供货量充足的情况下最小化日均费用。4.3.2 模型的建立与求解:要足城市居民的蔬菜供应，增加蔬菜种植面积，则需要保证所有的菜

21、市场都 满足日需求量，在问题一得基础上作出以下调整:SB3Sci 75SC2 6070100Sc3 80SA4SB 4SC4SA5SB 5SC5SB6SC655SB7SB8B8Sc7 90Sc8 80同理，用LINGO编程求解（源程序及完整运行结果见附录），部分运行结果如下：Global optimal solution found.Objective value:4770.000Infeasibilities:0.000000专业资料Total solver iterations:Model Class:Total variables:Nonlinear variables:Integer

22、variables:Total constraints:Nonlinear constraints:12LP2600220Total nonzeros:Nonlinear nonzeros:1240VariableValueReduced CostP4770.0000.000000Q0.0000000.6250000SA175.000000.000000SA240.000000.000000SA30.0000000.000000SA40.0000002.000000SA530.000000.000000SA655.000000.000000SA70.00000012.00000SA80.000

23、0005.000000SB10.00000011.00000SB220.000000.000000SB380.000000.000000SB470.000000.000000SB50.0000002.000000SB60.00000011.00000SB70.00000014.00000SB80.0000003.000000SC10.00000021.00000SC20.00000016.00000SC30.0000008.000000SC40.0000002.000000SC570.000000.000000SC60.00000014.00000SC790.000000.000000SC88

24、0.000000.000000专业资料从结果中可以的知:SA1SA2SA5Sa6 200SB2SB3 SB4 170SC5Sc7 Sc8240故新增的蔬菜8000Kg全部运向C地，这样既能满足城市居民的蔬菜供应， 又能使总损失最小，最小为：4770元。4.3.3 模型的评价与分析：本模型以供货充足和费用最低为目标， 利用题中的约束条件解得：在供货量 充足的情况下日均花费最低为 4770元。并得到了全新的调配方案如上图所示， 而且新增蔬菜8000Kg ,且全部运向C地。五模型的及评价与改进5.1 模型的评价5.1.1 模型的优点：模型简单易懂,主要用了 Froyd算法与线性规划，使问题的求解变得

25、十分 方便，能适应更重新的要求。5.1.2 模型的缺点：上述模型第三问只考虑了运输费用最小，却没有考虑到供过于求造成的货物积压问题。5.2 模型的改进：由于上述模型第三问只考虑了运输费用最小，却没有考虑到供过于求造成的 货物积压问题。可将存货损失计算进去，这样会使这个模型更加完善。六参考文献1姜启源，数学模型，北京，高等教育出版社，20032黄雍检、赖明勇，MATLAB语言在运筹学中的应用，大学出版社，2005七附件问题一：MATLAB新建m文件：function y=fld(n,x)for r=1:nfor i=1:nfor j=1:np(j)=x(i,j)+x(j,r);endy(r,i尸

26、min(p);end end输入命令：d=0 7 inf 5 4 inf inf inf inf inf inf inf inf inf inf;7 0 7 inf 8 3 inf inf inf inf inf inf inf inf inf;inf 7 0 inf inf 6 inf 7 11 inf inf inf inf inf inf;5 inf inf 0 6 inf 5 inf inf 7 inf inf inf inf inf;4 8 inf 6 0 7 4 8 inf inf inf inf inf inf inf;inf 3 6 inf 7 0 inf 5 inf inf

27、inf inf inf inf inf;inf inf inf 5 4 inf 0 4 inf inf 7 inf inf inf inf;inf inf 7 inf 8 5 4 0 6 inf 5 inf inf inf inf;inf inf 11 inf inf inf inf 6 0 inf 3 inf 6 inf 5;inf inf inf 7 inf inf inf inf inf 0 6 8 inf 10 inf;inf inf inf inf inf inf 7 5 3 6 0 6 inf inf inf;inf inf inf inf inf inf inf inf inf

28、8 6 0 10 5 inf;inf inf inf inf inf inf inf inf 6 inf inf 10 0 11 inf;inf inf inf inf inf inf inf inf inf 10 inf 5 11 0 inf;inf inf inf inf inf inf inf inf 5 inf inf inf inf inf 0d1=dd2=fld(15,d1)d3=fld(15,d2) d4=fld(15,d3)运行结果:Columns 1 through 1407 Inf 54 Inf Inf Inf Inf Inf Inf Inf InfInf707 Inf 8

29、3 Inf Inf Inf Inf Inf Inf InfInfInf 70 Inf Inf 6 Inf 711 Inf Inf Inf InfInf5 Inf Inf 06 Inf 5 Inf Inf 7 Inf Inf InfInf48 Inf 60748 Inf Inf Inf Inf InfInfInf 36 Inf 70 Inf 5 Inf Inf Inf Inf InfInfInf Inf Inf 54 Inf 04 Inf Inf 7 Inf InfInfInf Inf 7 Inf 85406 Inf 5 Inf InfInfInf Inf 11 Inf Inf Inf Inf

30、60 Inf 3 Inf 6InfInf Inf Inf 7 Inf Inf Inf Inf Inf 068 Inf10Inf Inf Inf Inf Inf Inf 753606 InfInfInf Inf Inf Inf Inf Inf Inf Inf Inf 860105Inf Inf Inf Inf Inf Inf Inf Inf 6 Inf Inf 10011Inf Inf Inf Inf Inf Inf Inf Inf Inf 10 Inf 5110Inf Inf Inf Inf Inf Inf Inf Inf 5 Inf Inf Inf Inf InfColumn 15InfIn

31、fInfInfInfInfInf5InfInfInfInfInf0di =InfInfColumns 1 through 1407 Inf 54 Inf Inf Inf Inf Inf Inf InfInf707 Inf 83 Inf Inf Inf Inf Inf InfInf专业资料11Inf 70 Inf Inf 6 Inf 711 Inf Inf Inf InfInf5 Inf Inf 06 Inf 5 Inf Inf 7 Inf Inf InfInf48 Inf 60748 Inf Inf Inf Inf InfInfInf 36 Inf 70 Inf 5 Inf Inf Inf I

32、nf InfInfInf Inf Inf 54 Inf 04 Inf Inf 7 Inf InfInfInf Inf 7 Inf 85406 Inf 5 Inf InfInfInf Inf 11 Inf Inf Inf Inf 60 Inf 3 Inf 6InfInf Inf Inf 7 Inf Inf Inf Inf Inf 068 Inf10Inf Inf Inf Inf Inf Inf 753606 InfInfInf Inf Inf Inf Inf Inf Inf Inf Inf 860105Inf Inf Inf Inf Inf Inf Inf Inf 6 Inf Inf 10011

33、专业资料Inf Inf Inf Inf Inf Inf Inf Inf Inf 10 Inf 5 0InfInf Inf Inf Inf Inf Inf Inf Inf 5 Inf Inf Inf InfColumn 15InfInfInfInfInfInfInfInf 5InfInfInfInfInf 0d2 =Columns 1 through 1407145410812 Inf 12 Inf Inf InfInf707128312818 Inf Inf Inf InfInf1470 Inf 13611711 Inf 12 Inf17 Inf512 Inf 061359 Inf 71215

34、 Inf17481360748141311 InfInf Inf103613709511 Inf 10 Inf InfInf81211549041012713Inf Inf12879854061151112 InfInf 1811 Inf1712 Inf Inf 713 Inf 121190681810Inf Inf 12121110753606911Inf Inf Inf 15 Inf Infnf Inf 17 Inf Inf Inf Inf 12618910011Inf Inf Inf 17 Inf Inf Inf Inf 1710115

35、110Inf Inf 16 Inf Inf Inf Inf 115 Inf 8 Inf 11InfColumn 15InfInf16InfInfInf专业资料Inf专业资料115Inf8Inf11Inf0d3 =Columns 1 through 14071454108121812152024227071283128141913192029147016136117111812181723512166135915712152117709511161016172116481360202210361371721812115416181287981216181411151461412191871315

36、10151312121191120191815171052420172120011222923172211023191620194814131117951116101604101271340611511106093912119068753606131198601612615910181614101151511514814专业资料1119Column 15231916201916151151481411190d4 =专业资料1 through 14Columns02422720241417235211742022101721816181212161861412714541081218121520

37、0712831281419131970161361171118121812160613591571215813607481413111736137095111610161211549041012713专业资料87985406115111411151411106093919187131612119068151011专业资料1011111513121211101120241122231919181517161311202419Column 1523191620191615172120171612151023161720222118161410111916151114145148141119 0LI

38、NGO程序:min=P+Q;DA1=4;DA2=8;DA3=8;DA4=19;DA5=11;DA6=6;DA7=22;DA8=20;DB1=14;DB2=7;DB3=7;专业资料DB4=16;DB5=12;DB6=16;DB7=23;DB8=17;DC1=20;DC2=19;DC3=11;DC4=14;DC5=6;DC6=15;DC7=5;DC8=10;SA1+SA2+SA3+SA4+SA5+SA6+SA7+SA8=200;SB1+SB2+SB3+SB4+SB5+SB6+SB7+SB8=170;SC1+SC2+SC3+SC4+SC5+SC6+SC7+SC8=160;p=(SA1*DA1+SA2

39、*DA2+SA3*DA3+SA4*DA4+SA5*DA5+SA6*DA6+SA7*DA7+SA8 *DA8)+(SB1*DB1+SB2*DB2+SB3*DB3+SB4*DB4+SB5*DB5+SB6*DB6+SB7*DB7+SB8*DB8)+(SC1*DC1+SC2*DC2+SC3*DC3+SC4*DC4+SC5*DC5+SC6*DC6+SC7*DC 7+SC8*DC8);Q=10*(75-(SA1+SB1+SC1)+8*(60-(SA2+SB2+SC2)+5*(80-(SA3+SB3+SC3)+10*( 70-(SA4+SB4+SC4)+10*(100-(SA5+SB5+SC5)+8*(55

40、-(SA6+SB6+SC6)+5*(90-(SA7+SB7+SC7)+8*(80-(SA8+SB8+SC8);10*(75-(SA1+SB1+SC1)>=0;8*(60-(SA2+SB2+SC2)>=0;5*(80-(SA3+SB3+SC3)>=0;10*(70-(SA4+SB4+SC4)>=0;10*(100-(SA5+SB5+SC5)>=0;8*(55-(SA6+SB6+SC6)>=0;5*(90-(SA7+SB7+SC7)>=0;8*(80-(SA8+SB8+SC8)>=0;SA1+SB1+SC1<=75;SA2+SB2+SC2<

41、;=60;SA3+SB3+SC3<=80;SA4+SB4+SC4<=70;SA5+SB5+SC5<=100;SA6+SB6+SC6<=55;SA7+SB7+SC7<=90;SA8+SB8+SC8<=80;end运行结果：Global optimal solution found.专业资料Objective value:4610.000Infeasibilities:Total solver iterations:Model Class:Total variables:Nonlinear variables:Integer variables:Total co

42、nstraints:Nonlinear constraints:Total nonzeros:Nonlinear nonzeros:0.00000010LP26002201240VariableValueReduced CostP3890.0000.000000Q720.00000.000000DA14.0000000.000000DA28.0000000.000000DA38.0000000.000000DA419.000000.000000DA511.000000.000000DA66.0000000.000000DA722.000000.000000DA820.000000.000000

43、DB114.000000.000000DB27.0000000.000000DB37.0000000.000000DB416.000000.000000DB512.000000.000000DB616.000000.000000DB723.000000.000000DB817.000000.000000DC120.000000.000000DC219.000000.000000DC311.000000.000000DC414.000000.000000DC56.0000000.000000DC615.000000.000000DC75.0000000.000000DC810.000000.000000SA175.000000.000000SA20.0000000.000000SA30.0000000.000000SA40.0000002.000000SA570.000000.000000SA655.000000.000000SA70.00000012.00000SA80.0000005.000000SB10.00000011.00000SB260.000000.000000SB380.000000.000000SB430.000000.000000SB50.0000002.