光明市的菜篮子工程

1光明市的菜篮子工程摘要本文研究的是蔬菜市场为满足不同条件的最优调配方案问题，用了Froyd算法、线性规划建立了一系列数学规划模型，并用MATLAB和LINGO软件编程实现。关于问题一：用Froyd算法结合MATLAB编程求出收购点至个菜市场的最短距离，以用于蔬菜调运及预期的短缺损失为最小为目标建立线性规划模型。用LINGO编程求得日均费用最少为4610元。关于问题二：在模型一的基础增加各菜市场短缺量一律不超过需求量的20%的约束条件，用LINGO编程求得最少日均费用以及最优供应方案。费用最少为4806元，供应方安见正文。关于问题三：在模型一的基础上，改为以供货充足、费用最小为目标，建立模型三，用LINGO编程求得日均费用为4770元，增产的蔬菜每天应分给C收购点8000Kg。关键字：蔬菜市场调配方案Froyd算法线性规划2一、问题的重述海江市是一个人口不到20万人的小城市。根据该市的蔬菜种植情况，分别在菜市场（A），菜市场（B）和菜市场（C）设三个收购点，再由各收购点分送到全市的8个菜市场，该市道路情况，各路段距离（单位：100m）及各收购点，菜市场①⑧的具体位置见图3.2.按常年情况，A,B,C三个收购点每天收购量分别为30000，25000和20000（单位：100kg）,各菜市场的每天需求量及发生供应短缺时带来的损失（元/100kg）见表3.设从收购点至各菜市场蔬菜调运费为1元/(100kg.100m).①7②54837A76B⑥6855471174③7566⑤35④86610C10⑧511⑦表3菜市场每天需求（100kg）短缺损失（元/100kg）①15010②1008③1205④10010⑤14010⑥1008⑦1405⑧1208(a)为该市设计一个从收购点至个菜市场的定点供应方案，使用于蔬菜调运及预期的短缺损失为最小；(b)若规定各菜市场短缺量一律不超过需求量的20%，重新设计定点供应方案；(c)为满足城市居民的蔬菜供应，光明市的领导规划增加蔬菜种植面积，试问增3产的蔬菜每天应分别向A,B,C三个采购点供应多少最经济合理。二、符号说明1,28AiDi……从A到i（各个菜市场）的最短距离1,28BiDi……从B到i（各个菜市场）的最短距离1,28CiDi……从C到i（各个菜市场）的最短距离1,28AiSi……从A到i（各个菜市场）的运货量1,28BiSi……从B到i（各个菜市场）的运货量1,28CiSi……从C到i（各个菜市场）的运货量P总调运费Q短缺损失R总费用三模型假设1、假设日需求量与缺货损失费用不变。2、假设在蔬菜调配的过程中无意外发生。3、假设新增产的蔬菜能够满足缺货量。四模型的建立与求解4.1问题一4.1.1问题的分析：为了使用于蔬菜调运及预期的短缺损失为最小，即调运费用与缺货损失之和最小。首先考虑调运费用P，P为距离与送货量的积，因为与送货距离相关，我们必须先求出A、B、C三个采购点至各个菜市场的最短距离。采用Froyd算法，结合MATLAB编程实现。其次考虑缺货损失Q，以题中要求为约束条件，损失最低位目标建立线性规划模型，用LINGO编程求解。4.1.2模型的建立与求解：由图和表格的信息知，建立一个线性规划模型，使得蔬菜调运及预期的短缺4损失为最小。调运总费用P为：888111AiAiBiBiCiCiiiiPSDSDSD若使调运总费用最少，则应保证A、B、C三个收购点到8个菜市场的路程最短，最短路线的求解过程如图一：图一：求解过程图分析上图可知，该路线为无向网络，就该图而言，网络弧集为：E=[(v1,v2),(v1,v4),(v1,v5),(v2,v1),(v2,v3),(v2,v5),(v2,v6),(v3,v2),.(v3,v6),(v3,v8),(v3,v9),(v4,v1),(v4,v5).(v4,v7),(v4,v10),(v5,v1),(v5,v2),(v5,v4),(v5,v6),(v5,v7),(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,v11),(v9,v3),(v9,v8),(v9,v11),(v9,v13),(v9,v15),(v10,v4),(v10,v11),(v10,v12),(v10,v14),(v11,v7),(v11,v8),(v11,v9)(v11,v10),(v11,v12),(v12,v10),(v12,v11),(v12,v13),(v12,v14),(v13,v9),(v13,v12),(v13,v14),(v14,v10),(v14,v12),(v14,v13),(v15,v9)]下面来确定网络权矩阵：W=()nnijw其中iiw=ijl，当（iv,jv）属于E时，ijl为弧（iv,jv）的权iiw=0，i=1,2,3……nijw=inf,当（iv,jv）不属于E时。（inf为无穷大，n为网络结点个数）5按上述规定，该网络的权矩阵为：07inf54infinfinfinfinfinfinfinfinfinf707inf83infinfinfinfinfinfinfinfinfinf70infinf6inf711infinfinfinfinfinf5infinf06inf5infinf7infinfinfinfinf48inf60748infinfinfinfinfinfinfinf36inf70inf5infinfinfinfinfinfinfinfinfinf54inf04infinf7infinfinfinfinfinf7inf85406inf5infinfinfinfinfinf11infinfinfinf60inf3inf6inf5infinfinf7infinfinfinfinf068inf10infinfinfinfinfinfinf753606infinfinfinfinfinfinfinfinfinfinfinf860105infinfinfinfinfinfinfinfinf6infinf10011infinfinfinfinfinfinfinfinfinf10inf5110infinfinfinfinfinfinfinfinf5infinfinfinfinf0因为上述网络有15个结点，故网络的权矩阵均为15阶矩阵。现在给出网络最短路线的Froyd算法：（1）d1=w.(w为所给网络的n阶权矩阵)（2）dk=()ijnndk,k=2,3,…,p.其中ijdk=min[(1)isdk+(1)sjdk,i,j=1,2,…,n.计算次数的确定：当ijw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=(fld(15,d3),算的d4为：07145410812181215202422237071283128141913192024191470161361171118121817231651216061359157121521172048136074814131117202219103613709511161016176211681211549041012713161815128798540611511121611181411151411106093961451219187131612119068151014151312121110753606911820191815171613119860105142420172120171612615910011112224231722211816141011511019231916201916151151481411190d4即为该网络的距离矩阵，距离矩阵的第i行指明了iv到其他各点的最短距离。根据上述矩阵，分别找出A,B,C到①、②、③、④、⑤、⑥、⑦、⑧的最短距离，见表一：表一：收购点到菜市场的最短距离最短距离（单位：100千米）①②③④⑤⑥⑦⑧A488191162220B14771612162317C20191114615510调运量的限制：7短缺损失费为：1112223334445556667778881075860580107010100855590880ABCABCABCABCABCABCABCABCQSSSSSSSSSSSSSSSSSSSSSSSS总费用为：RPQ由以上约束条件，用LINGO软件进行线性规划求解（源程序及完整运行结果见附录），部分运行结果如下：Globaloptimalsolutionfound.Objectivevalue:4610.000Infeasibilities:0.000000Totalsolveriterations:10ModelClass:LPTotalvariables:26Nonlinearvariables:0Integervariables:0Totalconstraints:22Nonlinearconstraints:0Totalnonzeros:124Nonlinearnonzeros:0VariableValueReducedCostP3890.0000.000000Q720.00000.000000SA175.000000.000000SA20.0000000.000000SA30.0000000.0000008SA40.0000002.000000SA570.000000.000000SA655.000000.000000SA70.00000012.00000SA80.0000005.000000SB10.00000011.00000SB260.000000.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从上述运行结果中可以得出调运方案为：收购点A菜市场①，运量为75菜市场⑤，运量为70菜市场⑥，运量为55收购点B菜市场②，运量为60菜市场③，运量为80菜市场④，运量为309在此种方案下，蔬菜调运及预期的短缺损失为最小，最小金额为4610元。4.1.3模型的评价与分析：本模型用Froyd算法快捷的求出了A、B、C三个收购点到8个菜市场的最短路程，用线性规划模型使得费用最低，并给出了上图所示的调配方案。在所得方案中每日只需4610元。4.2问题二4.2.1问题的分析：若按规定各菜市场短缺量一律不超过需求量的20%，则只需要在模型一的基础上在增加一个约束条件：每个菜市场的供应量必须不低于需求量的80%即可。即得到满足条件的模型二。4.2.2模型的建立与求解：各菜市场短缺量一律不超过需求量的20%，为满足这一条件，现对方案一进行调整。只需在方案一中加一限制条件：111222333444555666777888750.860600.848800.864700.8561000.880550.844900.872800.8