暑期建模培训初稿.doc

物资紧急调度建模摘 要本文针对防洪救灾物资调度问题，建立规划模型和图论中的Floyd算法，结合题中所给数据，给出了合理的物资调度方案。对于问题1，首先采用Floyd算法求出仓库3和仓库4以及3家企业分别到其余仓库和国家储备库的最短路径。然后建立以路程最短为目标的线性规划模型，得到紧急调运方案如下：企业1到储备库1(360百件):242627;企业1到储备库2(600百件)：242625116430;企业3到储备库1(400百件) :34323956 1127;企业3到储备库2（100百件）：34323930；仓库4到储备库2（240百件）：31323930。 对于问题2，在问题1的求解基础上以总花费时间最少为目标，建立非线性规划模型，利用Lingo编程求出完成调运任务的最小时间为852小时。具体车辆分配方案如下：企业1到储备库1（3辆) ;企业1到储备库2(6辆);企业3到储备库1(5辆);企业3到储备库2（1辆）；仓库4到储备库2（3辆）。对于问题3，考虑时间充裕的条件，为达到仓库储备量高于预测需求量的目的，首先利用Floyd算法和路费加权求得最省路径，然后以车辆数目最少为目标，建立非线性规划模型，利用Lingo编程求解出完成调运任务所需车辆最少为77辆。车辆分配方案如下：企业1到仓库2（1辆）；企业1到仓库5（2辆）；企业1到储备库1（20辆) ;企业2到仓库1(8辆);企业2到仓库2(7辆);企业3到仓库8（7辆）；企业3到储备库2（32辆）。对于问题4，在遭遇灾害的情况下，重新使用Floyd算法计算出通往16号地区的最省时间路径。然后以五天之内完成调运任务并所需车辆最小为目标，建立非线性规划模型，利用Lingo编程求出所需最少车辆为54。针对论文的实际情况，对论文的优缺点做了评价，论文最后还给出了其他的改进方向，以用于指导实际应用。关键词：Floyd算法；Lingo；非线性规划；线性规划 1问题的重述我国地域辽阔，气候多变，洪水、泥石流等各种自然灾害频频发生，给国家和人民财产带来重大损失，防洪救灾成为各级政府的一项重要工作。某地区为做好今年的防洪救灾工作，根据气象预报及历史经验，决定提前做好某种防洪救灾物资的储备工作。该地区现有3家该物资的生产企业，8个不同规模的物资储存仓库，2个国家级物资储备库，相关数据如附录表1所示，其位置分布和道路情况如附录图1所示。经测算该物资的运输费用为高等级公路2元/公里百件，普通公路1.2元/公里百件。各企业、物资仓库及国家级储备库的物资需要时可以通过公路运输相互调运。请你们研究下列问题：（1）根据未来的需求预测，在保证最低库存量和不超过最大容许库存量的情况下，还要重点保证国家级储备库的储存量，试设计给出该物资合理的紧急调运方案，包括调运线路及调运量。（2）如果用于调运这批防洪救灾物资车辆共有辆，每辆车每次能装载件，平均在高等级公路上时速为公里/小时，在普通公路上时速为公里/小时。平均装与卸一辆车的物资各需要小时，一天按小时计算。按照问题（1）的调运方案，如何来调度车辆，大约需要多少天能完成调运任务？（3）若时间容许，希望尽量地减少运输成本，请给出最佳的调运方案，最少需要多少车辆？大约需要多少天能够完成调运任务？34262511161621（4）若在调运中，正好遇到灾害使下列路段意外中断： 32252316 ， ， ， 和 。16而且 号地区严重受灾，急需向 号地区调运10万件救灾物资，请给出相应的紧急调运方案。必要时可动用国家级储备库的物资，也可以不考虑库量的最低限制。如果要求必须在5天内完成这次调运任务，那么最少需要多少辆车，并给出车辆的调度方案。2问题的分析2.1 问题（1）的分析根据未来的预测需求量，在保证最低库存与不超过最大库存量的情况下，同时要重点保证国家级储备库的存储量，要给出合理的紧急物资调运方案，首先要考虑的是时间最短，然后要保证国家级储备库的存储量。从题目所给附录中的表一可以发现所有仓库的现有存储量已经超过最低存储量，同时仓库3和仓库4的现有存储量超过了预测需求量，所以除了3家企业可以向外调运物资之外，他们也可以向外运送物资。由于紧急调运方案中，最重要的时间，而时间等效于物资源到目标的距离，因此可以采用Floyd算法计算以上五个物资源到其他仓库和储备库的最短路径。之后，重点考虑国家级储备库的存储量，以达到国家级储备库的物资存储量超过预测需求量作为约束条件，建立以时间最短，这里也就是总路程最短为目标的，同时要满足3家企业尽量运完的线性规划模型，利用Lingo软件求出最优解。2.2 问题（2）的分析问题（2）已经给定了车辆的数目，因而只需要在问题（1）的已经给出车辆运输路线基础上，以完成调运任务所需时间最少为目标函数建立数学优化模型，就可以最终给出18辆车的调运方案。2.3 问题（3）的分析根据体重所给时间充裕的条件，因此在运送物资的时候要优先考虑物资运送成本问题。那么之前Floyd计算出的最短路径不再适用与这个模型，由于高速公路和普通公路的花费不同，必须对第一问中所得到的邻接矩阵加权得到一个新的邻接矩阵，该邻接矩阵所存的是相邻两个节点之间路费加权距离。再使用Floyd算法计算五个物资源到其他的仓库和储备库的最省钱路径。然后对物资调运进行分配，分配过程以各仓库包括企业仓库不超过最大需求量，不低于预测需求量为约束条件，考虑企业生产，以花费最少为目标，建立线性规划模型，得到物资分配方案。最后以车辆数目最少为目标，建立非线性规划模型，求出最优解。2.4 问题（4）的分析问题（4）要求在毁坏一些路径的基础上向16号地区五天之内运送超过10万件物品，而且必要时可以动用国家级储备库的物资，不考虑最低的需求量。首先可以利用Floyd算法重新求解出各企业、仓库、国家级储备库分别向16号地区调运物资最省时的路径，在此基础上综合考虑上述要求建立优化模型求解出最优的车辆调运方案，并给出此时所需的车辆数。3模型的假设与符号说明3.1 模型的假设（1）假设在确定车辆的调度方案时每条调运路线上派发的车辆数是不变的；（2）任意一条调运路线上派发的所有车辆都是同时发车；（3）除装、卸车所消耗的时间外，车辆一直在调运路线上往返；（4）不考虑行车过程中因加油、故障等原因所浪费的时间；（5）企业每天生产救灾物资的行为是不间断的。（6）假设27号点为储备库1,30号点为储备库2（7）车辆满载和空载时的速度是一样的 3.2 符号的说明第个节点到第个节点的调运量路程邻接矩阵费用邻接矩阵第个发送物资节点（企业、仓库或国家级储备库）的最低库存量，单位“百件” 第个发送物资节点（企业、仓库或国家级储备库）的预测库存量，单位“百件” 第个发送物资节点（企业、仓库或国家级储备库）的现有库存量，单位“百件”第个发送物资节点（企业、仓库或国家级储备库）的最大库存量，单位“百件”第个接受物资节点（企业、仓库或国家级储备库）的最低库存量，单位“百件”第个接受物资节点（企业、仓库或国家级储备库）的预测需求量，单位“百件”第个接受物资节点（企业、仓库或国家级储备库）的现有库存量，单位“百件”第个接受物资节点（企业、仓库或国家级储备库）的最大库存量，单位“百件”第个发送物资节点到第个接受物资节点运输为1，不运输为04 模型的建立与求解4.1问题（1）的模型建立与求解由题中图1所示的各节点之间的相邻情况，以相邻两点之间距离为权重，建立邻接矩阵：这个矩阵中表示两点之间的距离，inf表示为这两点不相邻，采用Floyd算法计算3家企业与仓库3、4到其他仓库与储备库的最短路径，如表（1-1）：表（1-1）：五个物资源到其他仓库和储备库的最短路径仓库1仓库2仓库5仓库6仓库7仓库8储备库1储备库2企业11311124218331021企业2513183611261114企业321323514158259仓库32334372517152711仓库42435382125172812因为是紧急调运方案，所以考虑以距离之和最短为目标，建立线性规划模型如下：目标函数：约束条件：约束条件（1.2），（1.3）表示国家储备库现有存储量加上调运量要大于预测需求量，约束条件（1.4）表示仓库和储备库存储量加上调运量不超过最大库存量，约束条件（1.7）表示从企业的调运量不超过现有库存量，约束条件（1.8），（1.9）表示从仓库3、4的调运量不超过现有库存量与预测需求量之差。目标函数表示总路程最短。该模型是一个线性规划模型，采用Lingo求解，其结果为：共需要5条调运路线，总调运量为1700，具体调运量分配如表（1-2）所示。（程序见附录二程序1）表（1-2）紧急调运分配方案路径路径具体节点调运量（百件）路线1企业1到储备库124-26-27360路线2企业2到储备库241-6-4-30600路线3企业3到储备库134-32-39-5-6-11-27400路线4企业3到储备库234-32-39-30100路线5仓库4到储备库131-32-39-5-6-11-272404.2问题（2）的模型建立4.2.1车辆调度问题的模型建立由问题（1）可以得到运输路线共有五条并计算出气单程所需时间，如表（2-1）：表（2-1）紧急调运分配方案各路线时间路径路径具体节点调运量（百件）时间路线1企业1到储备库124-26-273602路线2企业2到储备库241-6-4-306002.8路线3企业3到储备库134-32-39-5-6-11-274003.725路线4企业3到储备库234-32-39-301001.8路线5仓库4到储备库131-32-39-5-6-11-272404.325在第一问已经给出车辆路线的情况下，结合题中给定的车辆数，以完成调运任务所需的时间最短为目标函数，建立优化模型。目标函数如下：其中（其中是第条线路上调运量）是第线路上所需要的最大运输车次，是每条线路上一辆车完成撞在、运送、卸货并返回的周期（是第条线路单程所需要时间）。约束条件如下：其中是第条线路所分配的车辆数。4.2.2模型的求解对于该模型，实际上是一个非线性的规划模型。利用第一问中得出的路线以及各线路所需时间，以完成调运任务时间最少为目标函数，利用Lingo编写相关的程序，可以解得最终的结果。对应问题（1）中求出的路线的调运方案的车辆分配具体如表（2-2）（程序见附录二程序2）：表（2-2）紧急调运方案车辆分配情况路径车辆数路线1企业1到储备库13路线2企业2到储备库26路线3企业3到储备库15路线4企业3到储备库21路线5仓库4到储备库13最终的总花费时间为852小时，约为35.5天。 4.3问题（3）的模型建立与求解由于时间充裕，优先考虑成本，那么之前的路程加权邻接矩阵不再适用于该模型，而建立一个新的以路费加权的邻接矩阵：采用Floyd算法计算出五个物资源到其他仓库和储备库的最省钱路径，如下表：表（3-1）路费加权的最省钱路径仓库1仓库2仓库5仓库6仓库7仓库8储备库1储备库2企业115.613.214.45422.845.61230企业2615.621.644.413.232.418.816.8企业325.2424816.8189.636.810.8仓库333.650.456.43026.41845.219.2仓库428.845.651.625.221.613.240.414.4之后对物资源向其他仓库和储备库的调运量进行分配，建立以路费最少为目标的非线性规划模型如下：目标函数：约束条件：其中约束条件（3.2），（3.3），（3.4）为3家企业调运完之后不低于零，不超过最大库存；约束条件（3.5）为接受物资仓库及储备库不超过最大库存，同时不低于预测需求量；约束条件（3.8）为时间不超过所有库存达到最大的时间；约束条件（3.9），（3.10）为仓库3、4调运完之后不低于预测需求量。这是一个非线性规划模型，采用Lingo求解，得到具体分配方案表（3-2）。（程序见附录二程序3-1）表（3-2）最省钱调运方案具体路线调运量路线具体节点路线1企业1到仓库221124-26-19-18-23路线2企业1到仓库512024-26-19-22路线3企业1到储备库1100024-26-27路线4企业2到仓库130041-9-28路线5企业2到仓库211941-9-15-18-23路线6企业3到仓库817035-32-38路线7企业3储备库270035-39-30路线8企业2到仓库711041-6-4-29由这个模型同时可以解出运满最后一个仓库所需要的时间为24.275天，即最后以车辆数目最少为目标，建立非线性规划模型如下：目标函数：约束条件：使用Lingo解这个非线性规划模型，其结果如下：共需要76辆汽车运送，在25天内完成运送目标，车辆具体分配方案如表（3-3)。（程序见附录二程序3-2）表（3-3）最省钱调运方案车辆分配情况路线车辆分配路线1企业1到仓库21路线2企业1到仓库52路线3企业1到储备库120路线4企业2到仓库14路线5企业2到仓库27路线6企业3到仓库87路线7企业3储备库232路线8企业2到仓库734.4问题（4）的模型建立与求解4.4.1最省时路径的确定在紧急情况下，可以将所有仓库、企业、国家级储备库都作为物资提供点。首先利用Floyd算法计算的在题中给定路线断了之后所有物资提供点向16号地区最省时间的路径，结果如表（4-1）：表（4-1）紧急情况各仓库到16号节点的最短路径调运路线具体节点时间路线1企业124-26-19-18-162.275路线2企业241-9-15-18-162.675路线3企业334-1-2-3-10-7-27-26-19-18-167.45路线4仓库128-9-15-18-162.875路线5仓库223-18-161.675路线6仓库335-39-5-6-11-15-18-165.4路线7仓库431-32-39-5-6-11-15-18-165.95路线8仓库522-19-18-162.675路线9仓库636-33-1-2-3-10-7-27-26-19-18-168.675路线10仓库729-28-9-15-18-164.075路线11仓库838-32-39-5-6-11-15-18-166.525路线12储备库127-26-19-18-163.075路线13储备库230-29-28-9-15-18-165.5254.4.2问题（4）模型的建立（1）目标函数的确定假设分配给企业1、2、3，仓库1、2、3、4、5、6、7、8，国家储备库1、2的车辆数分别为（1，2，3，13），则目标函数为：（2）约束条件的确定根据题中的要求必须在五天之内往16号地区运送超过10万件的物资，则有约束条件如下：其中是第个物资提供点向16号地区的运货量，是第天路线单程所花费的时间，M是完成整个调运任务的天数。在运输过程中还需要考虑企业的生产，因而有以下的约束条件：其中是仓库1，2,3,4,5,6,7,8以及国家及储备库1,2的现有库存量。（3）问题（4）的模型求解在确定目标函数以及相关的约束条件之后，利用lingo软件编写相关程序，求解出具体的车辆方案如表（4-2）。（程序见附录二程序4）表（4-2）紧急情况向16号灾区运资车辆分配物资提供点企业1企业2仓库3仓库1仓库2仓库3仓库42820111200物资提供点仓库4仓库5仓库6仓库7储备库1储备库21000005模型的推广与改进方向此模型即是一个优化模型，也可用于日常物流问题如n 个供应商与m 个顾客，知道各供应商到顾客的距离后，以顾客的需求与供应商的量为约束条件，以运费最少为目标函数建立数学模型。同时在这个防洪物资调用问题中还需要考虑运送物资的实际情况，例如：在非汛期间防洪物资的安全抵运问题。对于这个问题我们重新建立模型，如下：假设在这种情况下运输公司除了收取原有的运输成本外，还因存在危险性收取额外的费用：额外的费用单位货物运输成本危险系数危险系数我们用h表示，则收取的额外费用为所以：运输代价Z=运输成本+单位货物运输成本危险系数运输成本，建立运输代价最少，仓库最大和最小储备量为约束条件的线性规划模型则目标函数为：对于上文中某地区的情况，运输过程中发生事故的几率和运输距离、运输货物量有直接的关系，运输路程越长，运输货物量越多，发生事故的几率约大，因此可以假定危险系数用运输路程和运输量的乘积来衡量，而为了使危险系数更加符合实际，使它的数值在（0，1）区间内，对数据进行归一化处理：其中：修改后目标为：约束条件：采用Lingo求解得到结果如表（5-1）：表（5-1）：考虑危险因素的调运方案路径调运量路径具体节点企业1到仓库23302426191823企业1到仓库50企业1到储备库1100041928企业2到储备库10企业2到仓库1300242627企业2到仓库71104192829企业3到仓库4120343231企业3到储备库270034323930企业3到仓库30企业3到仓库8100343238企业3到仓库6203413336企业2到储备库206模型的优缺点6.1模型的优点（1）本文采用了线性规划模型和非线性规划模型，针对题中不同的条件和要求建立了不同的模型。每个模型有自己的侧重点，能使得模型得出的结果更具有说服力。（2）模型具有实用性强的特点能够针对突发事件做出快速的调整（3）该模型具有将强的推广性，能够应用到其他很多方面。（4）模型的推广里结合实际情况对本文所建立的模型进行了修改，是模型更具有实际意义。6.2模型的缺点（1）在车辆调度的模型中没有考虑车辆可以从一条路线调到另一条路线的情况，导致所得到的结果并不是最优的。（2）问题（3）的模型只考虑了起始和结束的状态并没有考虑运输过程的状态，即可能在运输过程中会超过企业的最大库存量。参考文献1 姜启源. 数学模型（第三版）M. 北京：高等教育出版社，1999.2 韩中庚. 数学建模方法及其应用（第二版）M. 北京：高等教育出版社，2009.3 张国辉，赵丽红.紧急物资调运问题的数学模型研究J. 湖 南 城 市 学 院 学 报，2011,2（2）附录附录一：表1：各库库存及需求情况（单位：百件）库存单位现有库存量最大容许库存量最低需求库存量预测需求量产量（/天）企业136060040企业260080030企业350060020仓库1200800100500仓库2270900200600仓库3450600200300仓库48001000300400仓库5230400100350仓库6280500200450仓库7390600300500仓库8500800200600储备库12000400020003000储备库21800300015002500企业1仓库5企业2企业3仓库2仓库4储备库1储备库2仓库3仓库1仓库6仓库7仓库875655258457280452250302830186870508078404870324028303832301048562826325846505636385060406270851510252625048425235504050456040380356898622825202116171819131415121011427689543122524232922282730263132333435363738394041企业1仓库5企业2企业3仓库2仓库4储备库1储备库2仓库3仓库1仓库6仓库7仓库875655258457280452250302830186870508078404870324028303832301048562826325846505636385060406270851510252625048425235504050456040380356898622825202116171819131415121011427689543122524232922282730263132333435363738394041注：1312123高等级公路 普通公路 河流 等表示公路交汇点；数字30，50，28等表示公路区间距离，单位：公里，如与之间距离为80公里。图1：生产企业，物资仓库及国家级储备库分布图附录二：Floyd算法matlab代码：function d,path=floyd(a,sp,ep)% floyd - 最短路问题% Syntax: d,path=floyd(a,sp,ep)% 输入：% a - 距离矩阵是指i到j之间的距离，可以是有向的% sp - 起点的标号% ep - 终点的标号% 输出:% d - 最短路的距离% path - 最短路的路径n=size(a,1);D=a;path=zeros(n,n);for i=1:nfor j=1:nif D(i,j)=infpath(i,j)=j; %j是i的后续点endendendfor k=1:nfor i=1:nfor j=1:nif D(i,j)D(i,k)+D(k,j)D(i,j)=D(i,k)+D(k,j);path(i,j)=path(i,k);endendendendp=sp;mp=sp;for k=1:nif mp=epd=path(mp,ep);p=p,d;mp=d;endendd=D(sp,ep);path=p;程序1：model:sets:arrange/1.5/:t;row/1.8/:yuce,now,zuidi,zuigao;links(arrange,row):x,w,d;endsetsdata:t= 360 600 500 150 400;yuce= 500 600 350 450 500 600 3000 2500;now= 200 270 230 280 390 500 2000 1800;zuigao= 800 900 400 500 600 800 4000 3000;zuidi=100 200 100 200 300 200 2000 1500;d=13 11 12 42 18 33 10 95 13 18 36 11 26 11 1421 32 35 14 15 8 25 923 34 37 25 17 15 27 1124 35 38 21 18 11 28 12;enddatamin=sum(arrange(i):(sum(row(j):w(i,j)*d(i,j);sum(arrange(i):x(i,7)+20003000;sum(arrange(i):x(i,8)+18002500;for(row(j):(sum(arrange(i):(x(i,j)+now(j)zuigao(j); for(arrange(i):(sum(row(j):(x(i,j)0);end程序2：model:sets:arrange/1.5/:t,x,b,a;endsetsdata:t=2 2.8 3.725 1.8 2.4;b=360 600 400 100 240;enddatamin=max(arrange:a);for(arrange(i):a(i)=(b(i)*(2*t(i)+2)/x(i);sum(arrange(i):x(i)=18;for(arrange(i):x(i)0);for(arrange(i):gin(x(i);End程序3-1：model:sets:arrange/1.5/;row/1.8/;links(arrange,row):x,newdistance;endsetsdata:newdistance= 156 132 144 540 228 156 120 300 60 156 216 444 132 324 188 168 252 420 480 168 180 96 368 108 336 504 564 300 264 180 452 192 288 456 516 252 216 132 404 144;enddatamin=sum(arrange(i):(sum(row(j):x(i,j)*newdistance(i,j);sum(row(j):x(1,j)-40*t=-240;sum(row(j):x(2,j)-30*t=-200;sum(row(j):x(3,j)-20*t=-100;sum(arrange(i):x(i,1)=300;sum(arrange(i):x(i,1)=330;sum(arrange(i):x(i,2)=120;sum(arrange(i):x(i,3)=170;sum(arrange(i):x(i,4)=110;sum(arrange(i):x(i,5)=100;sum(arrange(i):x(i,6)=1000;sum(arrange(i):