基于MATLAB的一类运输优化问题求解

的一类运输优化问题求解王丽娟华东交通大学交通运输与经济研究所，南昌（330013）E-mail：[e-mail]摘要：供应点的选取及调运物资数量的确定是运输决策中的关键性问题。本文通过对运输决策问题中基本情况的研究，对运力有限情况下单个需求点单一物资运输方案进行了分析，考虑运达概率、损失度对运输优化的影响，采用优化技术，以运输时间有限、每批货物运输的损失度小于规定的上限和成功运达的可能性高于规定的概率为约束条件，供应点最少、损失度最低为目标建立了运输优化数学模型。利用MATLAB编写0－1整数规划函数linprog01.m和调用其优化工具箱中非线性约束最优化函数fmincon对模型进行求解，得出了最优运输方案，验证了MATLAB强大的数值计算能力对一类运输优化问题求解的有效性。关键词：运输优化；供应点；运达概率；损失度；MATLAB中图分类号：TP18文献标识码：A0.引言在物流领域的运输决策中，供应点的选取及调运的物资数量常常是我们必须要面对的一个现实问题，人们在做运输决策时要受到当时的环境、条件以及决策的目的制约，常常是制约的因素不同，人们做出的决策也不一样[1]。多供应点对单一需求点在运力有限的情况下进行供给是运输问题中一种最基本也是较常见的情况[2]，本文力图通过对此种情况的探讨，为更复杂条件下运输问题的研究打下基础。为了解决非常状态下(如战争、自然灾害等)物资不能正常运达的问题，与以往这方面研究模型不同的是，本文在模型中考虑了运达概率、损失度对运输优化的影响。1.模型描述物资需求运输描述如下：设A为物资需求点，12......mAAA，，，为m个可提供物资的供应点，S为物资需求量，iA的最大物资供应量为(0)12......iiaaim=，，，，。Ai的单次最大运力限额为iδ(iδ0)，物资从iA运到A需要的时间为it(0)，供应量为ix，损失率为iq，成功运达的概率为ip，01in=，（0表示不由iA供应点供货，1表示由iA供应点供货），为方便表述，不妨设12......nttt，，，。决策方案可表示为：运输的决策方案[3]就是确定物资供应点及各提供的物资量，因而任一方案B可用集合的形式表示为：1122{()()......()}mmBAxAxAx=，；，；；，（1）0iixa≤≤，0iixδ≤≤且1)时间按照方案B最后物资到达时间为最终交货时间，用()TB表示方案B的最终交货时间，则()max1,2,......,iTBtim==（2）2)损失度()miiiitmiiqnxQBx==⋅⋅=∑∑1min()minmiiNBn==∑1min()minmiiNBn==∑()max1,2,......,diQBQim==每批货物的损失度[4]是指在运输过程中每批货物的损失程度，用()dQB表示，则（3）总损失度是指按照方案B，完成物资运输后整个运输过程中的损失程度，用()tQB表示，则（4）3)涉及的供应点数方案B所涉及的供应点数可表示为()iNBn=。4)运达概率按照方案B物资能够运达的概率用()PB表示，则其中ip为供应点成功将物资运达需求点的概率。2.模型的建立由上所述，模型的层次关系为：1)运输时间有限2)每批货物运输的损失度小于规定的上限3)涉及的供应点数最少4)成功运达的可能性高于规定的概率抽象成数学模型即为：目标函数：（5）约束条件：3.模型求法分析在单货种单需求点的情况下，由于有运力限制，则供应点提供的物资数量既需满足0iixa≤≤，而且还需要同时满足0iixδ≤≤。若取min(,)iiicaδ=，上述两个约束条件就可转化为0iixc≤≤。由于对任一方案B，()TB、()dQB的取值不能大于所要求限定值dTQ、，根据这点剔除不满足条件的点。则模型转化为：1）目标函数：（6）约束条件：1(1-)()0,1;1,2,......,miiiiiQcnSPBPnim=⋅⋅≥≤==∑1(1-)()()()0,1;1,2,......miiiiddiQxnSTBTPBPQBQnim=⋅⋅=≤≥≤==∑()1()12......NBiiPBpim===∏，，，－1整数规划[5]，所以编写0－1整数规划函数linprog01.m来求解。其程序代码如下所示：Function[x,fval]=linprog01(c,A,b,Aeq,beq)iVal=size(c,1);xVal=zeros(size(c));x=xVal;opt_solution=c'*xVal;fori=1:2^iVal-1strBin_i=dec2bin(i);xVal=zeros(size(c));fork=1:length(strBin_i)xVal(k)=str2num(strBin_i(k));endconstrA=A*xVal=b;constrAeq=Aeq*xVal==beq;ifall(constrA)&all(constrAeq)objVal=c'*xVal;ifobjVal=opt_solutionopt_solution=objVal;x=xVal;endendendfval=opt_solution;2）利用1）中所求得的in11minminmiiiitmiiQnxQx==⋅⋅=∑∑（7）1(1-)0miiiiiiQxnSxc=⎧⋅⋅=⎪⎨⎪≤≤⎩∑再根据总损失度最小确定ix调用MATLAB优化工具箱fmincon函数来求解非线性约束最优化问题，最终求得ix4.算例求解例：已知某地对某种货物的物资需求量25S=吨；最晚运达时间6T=天；运达概率最小0.75P=为；每批货物的最大损失度0.05dQ=，各供应点状况见表1资料来源：参考文献[2]根据例题中的已知条件并结合模型的求法分析，由()maxiTBtT=≤和()maxdidQBQQ=≤先剔除不符合条件的供应点A7、A8、A9和A10，计算列表见表2。表2计算列表供应点参数A1A2A3A4A5A6A7A8A9A10it12355678916it≤123556\\\\ia39121211151712241iδ581211916158222min(,)iiicaδ=381211915158221ip0.800.960.900.940.950.920.960.680.580.780.75ip≥0.800.960.900.940.950.92\\\\iQ0.110.020.030.050.0050.010.010.040.020.01i1-Q0.890.980.970.950.9950.990.990.960.980.99(1-)iicQ2.677.8411.6410.458.95514.8514.857.6821.560.99通过在MATLAB中编写的0－1整数规划的函数linprog01.m，得[0,0,1,0,0,1]n=和()2NB=，得选取的供应点是B={A3,A6}，再验证成功送达率()0.8280PB=满足()0.75PB≥,最后调用MATLAB优化工具箱中的非线性约束最优化函数——fmincon函数[6]求得[10.4639,15.0000]x=；()0.0182tQB=，得最优解为B={(A3,10.4639),(A6,15.0000)}，即由供应点A3、A6为该地供应货物，供应量分别为10.4639吨和15吨。5.结论本文建立了求解一类运输优化问题的模型，分析了模型解法，验证了用MATLAB求解一类运输优化问题的有效性，得到了单货种单需求点的运输问题在满足供应点最少、运达概率最大和损失率最低的最优解。为多需求点情况下优化模型的建立和求解打下了基础，这也是下一步工作要研究的内容。参考文献[1]冯耕中.现代物流与供应链管理[M].西安:西安交通大学出版社，2004.[2]黄达，王航宇.一类运输优化问题求解过程分析[J].舰船电子工程，2007，159(3)：133-135.[3]钱颂迪.运筹学[M].北京:清华大学出版社，1991.[4]刘徽.运输问题的新算法[D].成都.四川大学,2005.[5]王维强.优化技术在交通运输企业中的应用[J].汽车科技.2007,（2）：45-47.[6]飞思科技产品研发中心.Matlab6.5辅助优化计算与设计[M].电子工业出版社，2006.SolutiontoaKindofTransportOptimizationQuestionBasedontheMatlabWangLijuanInstituteofTransportationandEconomics,EastChinaJiaoTongUniversity,Nanchang,China(330013)AbstractItisthekeytoselectthesupplypointsandthenumberofthetransportmaterialsintransportationdecision.Thispaperanalyzeshowtotransportonetypegoodstoastationconsideringthelimitedtransportationabilityafterresearchingacertainbasicinstanceinthetransportdecision-makingissue,andestablishestheoptimizationmathematicalmodelusingtheoptimizationtechnologyonthegoaloftheleastsupplydepotandthelowestdamnifyingdegree.Thepaperhascompiled0-1integerprogrammingfunctionlinprog01.musingMatlab,andcallednon-linearconstrainedoptimizationfunctionfminconinMatlabOptimizationToolboxtosolvethemodel.ItprovestobeefficientbyanexamplebasedontheMatlabandconcludestheoptimizationtransportationplan.Keywords:Transportoptimizing,Supplydepot,Successfullycarryingprobability,Damnifyingdegree,Matlab