物流优化设计问题论文.doc

第三届浙江工业大学数学建模协会竞赛所选赛题： A B 我们承诺： 我们仔细阅读了浙江工业大学数学建模协会竞赛的竞赛规则。我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人研究、讨论与赛题有关的问题。 我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。 我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。物流优化设计问题摘要现代物流是以满足消费者的需要为目标，把制造、运输、销售等市场情况统一起来思考的一种战略措施。它是集现代运输、信息网络、仓储管理、营销策划等诸多业务、技术门类于一体的多学科、多领域的综合管理科学1。本文就B题所给出的物流配送系统运输路径和容量限制及扩充问题进行展开讨论,建立数学模型，得到运输成本最低的最优运输策略。通过分析可知，该问题实际上是一个最小费用最大流问题。针对该问题，我们建立了两个模型进行解答。首先，考虑包含供应商、经销商、配送中心的物流配送系统，产量与销量绝对确定，采用线性规划的方法建立数学模型一，构造包含运输费用及扩充费用的方程式，考虑扩充时间限制以及容量限制等，针对方程中的变量进行限制，当总费用取得最小值是就是该配送系统的最优解，最后利用lingo软件进行编程和求解，解得最低成本为606.20。但是，如果使总运输费用最低的代价是其中一个经销商承担大部分的运输费，则该经销商的满意度会大大下降。再者，整个配送系统中的扩容时间直接作用于物流中心的收益。因此，在求解最优运输策略时，还要满足所有经销商满意度最高以及扩容时间最小。由于以上三者的相互制约，我们所能达到的是让三者都逼近其最小值。针对该目标，对模型一进行优化，构造包含运输费用、扩充费用、经销商满意度及扩容时间的优化模型，并用lingo进行求解。最终解得的策略中，两个经销商所承担的费用分别为288.87及335.23，扩容时间为34.6，而总成本为624.10。虽然其总成本要比基本模型略微大些，但其所花的时间仅仅是模型一所需扩容时间168的20.6%，也使两经销商所承担的费用均最接近其最小值。关键字：物流配送系统 线性规划 最优运输策略 最小运输成本 满意度问题重述 物流作为“第三利润源泉”在国民经济中的地位和作用越来越重要,它对于发展经济、加强军事力量、改善人们物质和文化生活以及扩大国际技术、经济文化的交流等都具有重要意义。在一个物流配送系统中有两个产品供应商和供应产品，其供应量(产量)分别为84和116；同时有两个经销商和，其需求量(销量)分别为96和104。该物流配送网络模型中供应商和经销商之间设有两个物流配送中和，并且 和 的容量均为40，其扩张的费用均为0.35，配送中心容量进行扩充的时间限制为60，扩充一单位容量所需的时间为2，配送中心容量进行扩充的时间限制为45，扩充一单位容量所需的时间为3。运输费用3.73.5容量限制403030304030容量扩充时间限制604040406040单位扩充时间322232单位扩充费用运输费用1.6容量限制303040304030容量扩充时间限制404060406040单位扩充时间223232单位扩充费用 当物资运输的实际情况如上面所描述，请建模模型使得建立的运输路径和配送中心带容量限制及容量可扩充的物流配送网络模型就可以得到运输成本最低的最优运输策略。问题分析物流配送中心是社会物流网络中处于主要位置的结点，但不是所有物流结点都能称为物流中心。物流配送中心必须是具有较大规模的物资集散或转运地点。属于物资集散类型的如大型物资仓库，它主要在物流系统中起调节和缓冲作用，解决供需节奏或批量不平衡的矛盾。如商业连锁系统的配送中心，主要是为了降低物流系统的成本，提高服务水平，提高物资输送末端系统效率等。2。对配送中心的解释从物资运输实际情况表可以看出，通过配送中心的中转，物资从供应商到经销商所需运输费用明显降低。但是，配送中心的存在容量限制，可能无法满足经销商对供应商的产品需求。要想让配送中心能够更大的运输能力，就必须对其容量进行扩充，于此同时每个配送中心也有自身的单位扩充时间、费用、总时间限制等限制因素。而对于直接从供应商运输到经销商的产品，也必须考虑其较为昂贵的费用和本身的容量限制。因此，整个问题可以抽象成一个优化问题，要决策的是整个物资运输配送系统的最优策略，要达到的目的即是运输成本最少。建立许多实际的优化问题的数学模型都是线性规划，本题也是如此。在本题中，每个供应商的产量和每个经销商的销量是唯一确定的，而最终的配送方法虽是非明确的，但受到容量限制和容量扩充时间限制着两个约束条件的限制。这就是说，在产量、销量、容量的约束下，最优策略应是唯一的。模型假设 经销商对产品供应商没有特定的要求。 物流配送中心无中转缺失。 不考虑运输时间的影响，只考虑扩容时间。 所有运输费用由经销商承担。 所有产品单位均为如重量等之类的连续单位。符号说明 模型建立和求解供应商A1配送中心O1 经销商B1供应商A2经销商B2配送中心O2物流配送系统可以用如下图表示：模型一：只考虑运输成本最低的基本模型 该问题实际上是个最小费用最大流问题。是经济学和管理学中的一类典型问题。在一个网络中每段路径都有“容量”和“费用”两个限制的条件下，此类问题的研究试图寻找出：流量从A到B，如何选择路径、分配经过路径的流量，可以达到所用的费用最小的要求3。整个配送系统可以抽象成一个网络，在这个网络中每段路径都有“容量”和“费用”两个限制。配送系统的总体运输成本由运输费用和扩充费用组成。即：运输费用是每条路线的运输费用的叠加，因此，总体运输费用表达式为：而扩充费则是单位扩充费用和扩充量的乘积。对其中一条线路，如果运输量小于该线路的容量限制，则不需要进行扩充。因此，总体扩充费用的表达式为：其中 我们最终要达到的目的是使总运输费用达到最小值。即： （1）由于每条路径扩充时间都有一定的限制，表达式必须满足约束条件： ， （2）再者，由于每个供应商的产量与每个经销商的需求量已知，因此，以及 ， （3）两个等式必须成立。在一个物流配送系统中，配送中心只是一个中转结点，所有从经销商运输到配送中心的货物全都需要运输给供应商。即：， （4）对(1)，（2）、（3）、（4）进行综合，得以下模型：模型一的求解 对模型一编写lingo程序（见程序1）可以得到如表一结果：表一线路运输量40.0044.0050.0030.0040.0050.00线路运输量24.0050.000.000.0032.004.00总费用606.20模型二：在模型一基础上考虑经销商满意度以及扩容时间的优化模型模型一只考虑了总运输费用最低，并没有考虑经销商的满意度。假定所有运输费用都有经销商来承担，则经销商的满意度便与其承担的运输费成反比，即所付运费越少，满意度越高。如果总体运输费用达到最低，而其中一个经销商承担的单位运输成本过大，即其满意度过低，则该经销商可能无法接受模型一所得的最优策略。同时，模型一没有考虑扩充所花费的时间。每条线路的扩充都需花费一定的时间，这直接作用于物流中心的收益问题。并且当一个经销商急需货物时，他可能更在意的是所需时间而非费用。因此，要得到运输最优策略，还需综合考虑各个经销商承担的费用以及扩充花费的时间。计算时，从供应商运输到配送中心所产生的费用按供应商从配送中心所得到的货物的比例来分配。即：因此，经销商所承担的总费用表达式为： 而经销商所承担的总费用为：在整个配送系统中，扩充容量所需时间的表达式为：由于每条路径扩充时间限制不变，每个供应商的产量与经销商的需求量确定并且不变，且同样应满足所有从经销商运输到配送中心的货物全都需要运输给供应商。由以上三个约束条件，我们可以得到以两下个线性规划方程组：1规划的最小值，记规划结果为： 2规划的最大值，记规划结果为： 对以上两个线性规划编写lingo程序（见程序2），便可得到规划结果、。在同样的约束条件下，我们可以的到、以及、值（见程序3、4）。但是，我们所需要达到的目标是、以及达到最小值。当然由于三者的相互制约性，要达到这个目标是不现实的，我们所能做的，是在总运费最小的情况下尽可能的让、和逼近其最小值。为此，构造一个三维空间，分别以：、作为单位向量。 则理想点但所在的： 而目标点为： 我们要使目标点尽量接近理想点，即：当与距离最小，并满足约束条件时，我们便可以取得此模型的解。模型二的求解由程序2、3、4可得两个经销商所承担的费用的最小值及最大值及最大扩容时间。如下表：项目值275.84342.46303.69449.620248.00将、和的值以及带入模型二，并编写lingo程序（见程序5），可以得到结果如表二：表二项目值0.32288.87335.2334.60624.10且运输路线如表三所示：表三线路运输量40.0030.0030.0030.0030.0030.00线路运输量22.7037.307.306.7026.0030.00结果的分析与检验模型一从模型一所得到的结果可以看出，除了所有与配送中心相联系的线路中，除了因其运费较为昂贵没有达到其容量限制外，所有线路都达到了其容量的最大值。其中，除了、都进行了扩充。而所有直接从供应商运输到经销商的线路都没有进行扩充。这和经配送中心中转之后运费大大降低的实际情况相符合。另外，由于线路所需的单位运输费用过高，所以应尽量不要选择该线路进行运输，这和结果中线路上运输量为零相符合，线路上运输量为零的原因也是如此。因此，该模型所得的结果与题目所需结果符合很好。模型二从结果可以看出，为624.10，与基础模型相比略微大些，但是已取得其最小值，即两个经销商所承受的费用及整个配送系统的扩充时间均最接近其最小值。模型二的结果显示，只有、进行了扩容，这大大降低了配送系统的扩容时间。其次，只有、没有达到其容量的最大值，这不仅与其运输成本较高相符，也符合了配送中心能够减少运输成本的特征。比较所有线路的运输费用和扩充费用的实际情况，模型二的结果与实际相符合。进而证明了模型二的正确性。优缺点与改进方向模型一中的线性规划方程简洁明了，便于计算。只要知道整个配送系统中，所有供应商需要的产量、经销商的需求量以及每个线路的费用及限制，就可以用此模型计算出成本最低的最优路线。但是，其缺点也正是如此。如果只考虑总体的运输成本最低，就无法针对每个经销商的满意度以及扩充时间来制定运输路线，因而可能不会被某个经销商所认可。模型二针对模型一的缺点进行优化，并对此建立数学模型。最终，实现了两个经销商所承受的费用及整个配送系统的扩充时间均最接近其最小值的结果。通过计算可知，模型一所需扩容时间为168，而模型二仅需34.60，远远小于模型一。因此，虽然模型二所需成本要比模型一多了17.9，但其节省的时间可为物流中心增添更多其他收入。同时，该模型可移植性强。如果在物流配送系统中增加几个物流结点，只要知道新路线的费用和限制条件，以及增加的供应商或经销商的产量或需求量，通过在模型中增添变量并修改限制条件就可以求得最优解。但是，该模型的试用条件在于所有费用均由经销商承担。如果实际运输费用并非如此，而由供应商和经销商共同承担，则该模型无法适用。这也是该模型的缺点所在。实际运用过程中，还需考虑如油价、人员管理费用等会变化的费用，以及实际交通情况。若能将约束条件进行扩充，则能获得更加贴近现实的最佳方案，这也是两个模型的改进方向。参考文献1 陈光, 信息网络时代的现代物流我国物流业的现状与对策:2010。2中国大学生网，/html/2009-6-2/200961222847277741.htm，2009年6月2日。3维基百科，最小费用最大流问题，/wiki/%E6%9C%80%E5%B0%8F%E8%B4%B9%E7%94%A8%E6%9C%80%E5%A4%A7%E6%B5%81：2008附录注：一下所有程序均由lingo11.0实现，并选用Global Optimum进行求解。程序1：计算模型一的解model:sets:path/1.2/:aa,bb;way/1.3/:;trans(path,path):;line(way,path,path):a,v,t,s,p;endsetsdata:aa=84,116; !aa 表示A的供应量;bb=96,104; !bb 表示B的需求量;v=30,30,30,30, !v 表示容量限制; 40,30,40,30, 40,30,40,30;t=50,50,50,50, !t 表示容量扩充后的最大容量; 60,50,60,50, 60,50,60,50;s=0.3,0.3,0.3,0.3, !s表示扩充费用; 0.4,0.3,0.4,0.3, 0.4,0.3,0.4,0.3;p=1.5,1.3,1,1, !p表示表示单位运费; 1.5,1.7,1.9,1.6, 3.7,5,3.1,3.5;enddatamin=sum(line:a*p+s*(a#GT#v)*(a-v); !目标函数;!以下四条对应约束条件;for(line:a=t); for(path(i):sum(path(j):a(1,i,j)+a(3,i,j)=aa(i); for(path(j):sum(path(i):a(2,i,j)+a(3,i,j)=bb(j);for(path(i):sum(path(j):a(1,j,i)=sum(path(j):a(2,i,j);end程序2：计算的最小值（最大值仅需将min改成max）model:sets:path/1.2/:aa,bb;way/1.3/:;trans(path,path):;line(way,path,path):a,v,t,s,p;endsetsdata:aa=84,116; !aa 表示A的供应量;bb=96,104; !bb 表示B的需求量;v=30,30,30,30, !v 表示容量限制; 40,30,40,30, 40,30,40,30;t=50,50,50,50, !t 表示容量扩充后的最大容量; 60,50,60,50, 60,50,60,50;s=0.3,0.3,0.3,0.3, !s表示扩充费用; 0.4,0.3,0.4,0.3, 0.4,0.3,0.4,0.3;p=1.5,1.3,1,1, !p表示表示单位运费; 1.5,1.7,1.9,1.6, 3.7,5,3.1,3.5;enddatau=sum(path(i):a(2,i,1)/sum(trans(i,j):a(2,i,j); !在A到B的总费用中B1的分配比例;min=u*sum(trans(i,j):s(1,i,j)*(a(1,i,j)#GT#v(1,i,j)*(a(1,i,j)-v(1,i,j)+sum(path(i):s(2,i,1)*(a(2,i,1)#GT#v(2,i,1)*(a(2,i,1)-v(2,i,1)+sum(path(i):s(3,i,1)*(a(3,i,1)#GT#v(3,i,1)*(a(3,i,1)-v(3,i,1)+u*sum(trans(i,j):a(1,i,j)*p(1,i,j)+sum(path(i):a(2,i,1)*p(2,i,1)+sum(path(i):a(3,i,1)*p(3,i,1); !目标函数;!以下四条对应约束条件;for(line:a=t); for(path(i):sum(path(j):a(1,i,j)+a(3,i,j)=aa(i); for(path(j):sum(path(i):a(2,i,j)+a(3,i,j)=bb(j);for(path(i):sum(path(j):a(1,j,i)=sum(path(j):a(2,i,j); End程序3：计算的最小值（最大值仅需将min改成max）model:sets:path/1.2/:aa,bb;way/1.3/:;trans(path,path):;line(way,path,path):a,v,t,s,p;endsetsdata:aa=84,116; !aa 表示A的供应量;bb=96,104; !bb 表示B的需求量;v=30,30,30,30, !v 表示容量限制; 40,30,40,30, 40,30,40,30;t=50,50,50,50, !t 表示容量扩充后的最大容量; 60,50,60,50, 60,50,60,50;s=0.3,0.3,0.3,0.3, !s表示扩充费用; 0.4,0.3,0.4,0.3, 0.4,0.3,0.4,0.3;p=1.5,1.3,1,1, !p表示表示单位运费; 1.5,1.7,1.9,1.6, 3.7,5,3.1,3.5;enddatau=sum(path(i):a(2,i,2)/sum(trans(i,j):a(2,i,j); !在A到B的总费用中B2的分配比例;min=u*sum(trans(i,j):s(1,i,j)*(a(1,i,j)#GT#v(1,i,j)*(a(1,i,j)-v(1,i,j)+sum(path(i):s(2,i,2)*(a(2,i,2)#GT#v(2,i,2)*(a(2,i,2)-v(2,i,2)+sum(path(i):s(3,i,2)*(a(3,i,2)#GT#v(3,i,2)*(a(3,i,2)-v(3,i,2)+u*sum(trans(i,j):a(1,i,j)*p(1,i,j)+sum(path(i):a(2,i,2)*p(2,i,2)+sum(path(i):a(3,i,2)*p(3,i,2); !目标函数;!以下四条对应约束条件;for(line:a=t); for(path(i):sum(path(j):a(1,i,j)+a(3,i,j)=aa(i); for(path(j):sum(path(i):a(2,i,j)+a(3,i,j)=bb(j);for(path(i):sum(path(j):a(1,j,i)=sum(path(j):a(2,i,j); end程序4：计算的最小值（最大值仅需将min改成max）model:sets:path/1.2/:aa,bb; way/1.3/:;trans(path,path):;line(way,path,path):a,v,t,s,p,c; endsetsdata:aa=84,116; !aa 表示A的供应量;bb=96,104; !bb 表示B的需求量;v=30,30,30,30, !v 表示容量限制; 40,30,40,30, 40,30,40,30;t=50,50,50,50, !t 表示容量扩充后的最大容量; 60,50,60,50, 60,50,60,50;s=0.3,0.3,0.3,0.3, !s表示扩充费用; 0.4,0.3,0.4,0.3, 0.4,0.3,0.4,0.3;p=1.5,1.3,1,1, !p表示表示单位运费; 1.5,1.7,1.9,1.6, 3.7,5,3.1,3.5;c=2,2,2,2, !c表示单位扩充时间; 3,2,3,2, 3,2,3,2;enddatamin=sum(line:(a#GT#v)*(a-v)*c); !目标函数!以下四条对应约束条件;for(line:a=t); for(path(i):sum(path(j):a(1,i,j)+a(3,i,j)=aa(i); for(path(j):sum(path(i):a(2,i,j)+a(3,i,j)=bb(j);for(path(i):sum(path(j):a(1,j,i)=sum(path(j):a(2,i,j); end程序5：计算模型二的解model:sets:path/1.2/:aa,bb;way/1.3/:;trans(path,path):;line(way,path,path):a,v,t,s,p,c;endsetsdata:aa=84,116; !aa 表示A的供应量;bb=96,104; !bb 表示B的需求量;v=30,30,30,30, !v 表示容量限制; 40,30,40,30, 40,30,40,30;t=50,50,50,50, !t 表示容量扩充后的最大容量; 60,50,60,50, 60,50,60,50;s=0.3,0.3,0.3,0.3, !s表示扩充费用; 0.4,0.3,0.4,0.3, 0.4,0.3,0.4,0.3;p=1.5,1.3,1,1, !p表示表示单位运费; 1.5,1.7,1.9,1.6, 3.7,5,3.1,3.5;c=2,2,2,2, !c表示单位扩充时间; 3,2,3,2, 3,2,3,2;enddatau1=sum(path(i):a(2,i,1)/sum(trans(i,j):a(2,i,j); !在A到B的总费用中B1的分配比例;w1=u1*sum(trans(i,j):s(1,i,