防洪物资调运问题.doc

防洪物资调运问题摘要 本题所研究的是防洪物质调运问题。 在问题一中，要建立该地区公路交通网的数学模型。我们考虑到高等级公路与普通公路的运输成本的差异，通过加权，求任意两个点之间运费每一百件最少的路线。我们采用图论和网络优化的方法，借助Dijkstra算法，得到各库、企业之间的最短的加权路线，即公路交通网（见图一）。 然后是问题二，以及问题三的求解。首先问题三是问题二的承接，我们只需要得出题二的模型，便可以解决。再者考虑物资的合理调运方案，重点保证国家储备库的情况下，运用动态规划，使得在一个较短的时间内完成对各库预测库存的需要，生产过剩的将分别运往储备库1、2，具体的调运方案见（表一）。于是，20天的调运方案，得到如下的结果：仓库名仓库1仓库2仓库3仓库4仓库5仓库6仓库7仓库8储备库1储备库220天后库存量50060030035045030050060038402740 最后是问题四的紧急调运方案的修改。考虑被洪水冲断的路线，我们进行重新的图论分析，使用Dijkstra算法，得到新的公路交通网（见图二），再根据第二问的解题思路，我们可以实现模型的修改，得到了紧急调运方案（见表三）。 同时，模型的运用还可以扩展到许多的方面，如产品的分配，人员指派，最短路径、设备的合理安排以及生产与库存管理等等问题。1、问题的重述我国地域辽阔，气候多变，各种自然灾害频频发生，特别是每年在长江、淮河、嫩江等流域经常爆发不同程度的洪涝灾害，给国家和人民财产带来重大损失，防洪抗涝成为各级政府的一项重要工作。现有某地区为做好今年的防洪抗涝工作，根据气象预报及历史经验，决定提前做好某种防洪抗涝物资的储备。已知该地区有生产该物资的企业三家，大小物资仓库八个，国家级储备库两个，各库库存及需求情况见附件1，其分布情况见附件2。经核算该物资的运输成本为高等级公路2元/公里百件，普通公路1.2元/公里百件，假设各企业、物资仓库及国家级储备库之间的物资可以通过公路运输互相调运。需要求解如下的问题：（1）请根据附件2提供的信息建立该地区公路交通网的数学模型，尽量满足点与点的运输路线最短。（2）设计该物资合理的调运方案，包括调运量及调运线路，在重点保证国家级储备库的情况下，为给该地区有关部门做出科学决策提供依据。（3）根据你的调运方案，20天后各库的库存量是多少。（4）如果汛期下列路段因洪水交通中断，能否用问题二的模型解决紧急调运的问题，如果不能，请修改模型。 中断路段：1423，1125，2627，9312、基本的假设1、各企业、物资仓库及国家级储备库之间的物资可以通过公路运输互相调运；2、每一条公路满足最大时的车流量，即选择的运输路线顺利通车，不出现较长时间的路障以及断路；3、所有路线均可双向行使，即车辆往返使用同一线路；4、不考虑货物在运输过程中的损坏和遗失，货物全部安全到达目的地；5、物资调运的运输时间不计，即运输能力足够大；3、符号的说明 表示i路段为j等级的距离,i=1,2,.n;j取1(高等级公路）或者j取2（普通公路）； 表示该地区所有交点路段数目； 表示物资的运输成本为高等级公路2元/公里百件，表示普通公路1.2元/公里百件（r=1,2)；4、问题一 建立公路交通网4.1问题的分析 根据附件2提供的信息，要求建立该地区的公路交通网模型，也就是通过所给的公路长度数据，加权，采取一定的方法求解出各个点与点（企业、仓库、储备库三者）之间的加权最短路径。4.2问题的假设1、以百件为基本问题出发点，即运输物资一百件；4.3问题模型的建立与求解4.3.1模型的建立 以仓库，企业，储备库任一为出发点，余下的其中一点为终点，得到加权路线的函数表达式为 其中 表示加权路线函数，m表示虚拟的0-1变量 0 不通过此路径 m= 1 通过此路径于是可得目标函数 表示为在所有的中取最短路径，即k=1时，取中所有路线最短的一条。4.3.2模型的求解 图论是针对最短路径的一种有效的解决方法，其中比较常用的算法有Dijkstra。4.3.2.1 Dijkstra基本思想Dijkstra算法建模的基本思想如下：如果，.，.，.是某图G从到的最短路径，这它的子路，.一定是从到的最短路径.4.3.2.2 Difkstra算法的步骤该算法可求得网络中从某顶点到其他所有顶点的最短路径,算法步骤如下:(1)假设网络G有n个顶点,用带权的邻接矩阵W来表示，W(i，j）表示从顶点到的弧或边的 权值，不存在 弧或边的权值用（在MATLAB中为inf)表示。S为已求出的从已知始点出发的 最短路径的终点的集合，它的初始状态为空集。则从出发到图上其余各顶点可能达到的最短路径长度的初值为：D(k)=minW(i,k)|V-i;(2)选择，使得：D(k)=minW(i,k)|V-S;就是当前求得的一条从始点出发的 最短路径的终点。令S=Sj；（3）修改从出发到集合V-S上任一顶点可达的最短路径长度。如果D(j）+W(j,k)D(k),则修改D(k）为：D（k）=D(j）+W(j，k)；（4）重复操作（2）（3）共n-1次，并记录各最短路径经过的所有顶点。由此得到从始点到图上其余各顶点的最短路径是依路径长度递增的序列。采用Difkstra算法，求得最短路径，在使用photoshop cs工具，修改原图，得到了该地区的公路交通网图,如下库仓库35企业2企业3储备库2仓库3仓库8仓库6仓库4仓库1仓库7储备库1企业1仓库2仓库5储备库2企业2（图一）注：1312123高等级公路 普通公路 河流 等表示公路交汇点；30，50，28等表示公路区间距离，单位：公里，如 与 之间距离为80公里。 从图中可以看出在两点之间的最短距离一般的是普通公路所连接的，也就是说，在运输成本最少的情况下，尽可能的走的是普通公路，除非遇到两路段点间的高等级公路上的运输成本比普通公路的少（如2740段）。同时还可以发现，大部分路线的出发点都是以仓库或者企业为基点。于是构成了以仓库或者企业连线包裹的公路交通网。5、问题二 物资的调运方案 问题三 20天各库的库存量5.1问题的分析 通过对该地区的公路交通网模型的进一步理解，在重点保证国家级储备库的情况下，考虑各个点之间的物资互运，但运量不确定，就需要根据已经规划的交通网，保证合理运输时的成本费用最少，也就是方案的决定与时间的长短存在一定的联系较短时间达到预测库存与较长时间达到是有区别的，于是就需要分时间的阶段性进行建模。再者第三问承接第二问而来，所以只需要将数值代入问题二中的模型，即可求解。5.2 模型的建立5.2.1模型I5.2.1.1 符号的说明 表示第k天由i单位运往库j的物资的量，其中i取1，2，.13.j=1，2，.，10.储备库1和储备库2分别规定为库9和库10. 表示k天末的库存（取a,b,c,e,f,g,h,p,q,r,t,v分别代表企业1，2，3,仓库18，储备库1，2） 表示第k天的运输成本 表示第k天某单位运出的物资量（取a,b,c,e,f,g,h,p,q,r,t,v分别代表企业1，2，3,仓库18，储备库1，2） 表示第k天某单位运进的物资量（取a,b,c,e,f,g,h,p,q,r,t,v分别代表企业1，2，3,仓库18，储备库1，2）5.2.1.2目标函数 状态转移方程 约束条件 当k=8时，其库1到库10的下限改为预测库存量。通过分析附件一，发现在第8天生产完物资后，已经可以达到各库的预测值总和，于是我们采用最短时间（8天）完成预测物资的调配。所以，计算得到前8天的具体调运方案如下： 调运量（百件） 调运路线 调运费用/百件1 640.0000 企1储1 24-26-27 120 350.0000 企3库4 34-32-31 90 20.00000 企3库6 34-1-33-36 174 110.0000 企3库7 34-32-39-30-29 196.8 40.00000 企3库8 34-32-38 111.6 60.00000 库4储1 31-9-27 189.6 250.0000 库4储2 31-32-39-30 152.4 330.0000 库5库2 22-19-18-23 166.8 20.00000 库5储1 22-19-26-27 204 2 40.00000 企1储1 24-26-27 120 270.0000 企2库1 41-42-28 69.6 150.0000 企2储2 41-6-4-30 177.6 20.00000 企3库8 34-32-38 111.6 3 40.00000 企1储1 24-26-27 1204 40.00000 企1储1 24-26-27 120 60.00000 企2储2 41-6-4-30 177.6 40.00000 企3库4 34-32-31 90 5 40.00000 企1储1 24-26-27 120 30.00000 企2储2 41-6-4-30 177.6 20.00000 企3库4 34-32-31 90 6 30.00000 企2储2 41-6-4-30 177.6 7 30.00000 企2库1 41-42-28 69.6 40.00000 企3库8 34-32-38 111.6 8 120.0000 企1储1 24-26-27 120 30.00000 企2储2 41-6-4-30 177.6 20.00000 企3库4 34-32-31 90 150.0000 库3储2 35-32-39-30 210 (表一) 重点保证国家级储备库的情况下，当k（9，20）时，生产的物资按照企业1、2运往储备库1，企业3运往储备库2，于是得到20天后的各库库存情况：仓库名仓库1仓库2仓库3仓库4仓库5仓库6仓库7仓库8储备库1储备库220天后库存量50060030035045030050060038402740(表二)其总的运费成本为：506928.0元。6、问题四 模型的修改6.1问题的分析 根据问题二的调运方案中的调运路线看是否经过断桥的地方，如果不经过（2）的调运方案是可行的，如果经过那么要再考虑其它的路线，我们可以在图一的模型中进行改进，再重复（2）的步骤求解。6.2模型的建立与求解仓库2仓库5仓库1仓库3仓库8仓库6仓库4仓库7企业1企业2企业3储备库1储备库2根据第一问的解题思路，可得到修改后的公路交通网为（图二） 使用图二中的交通运输线路，避免了冲断的路径，按照最短路线的思想，根据第二问的模型，可以求解，得到紧急调运前8天的具体调运方案如下： 调运路线 调运量 企业1到储备库1 24-20-13-27 640.0000 企业2到库1 41-42-28 90.00000 企业2到库7 41-42-28-29 110.0000 企业2到储备库1 41-6-40-27 60.00000 企业2到储备库2 41-42-28-29-30 130.0000 企业3到库6 34-01-33-36 20.00000 企业3到储备库2 34-32-39-30 500.0000 库3到库4 35-32-31 120.0000 库3到储备库2 35-32-39-30 30.00000 库5到库2 22-19-18-23 330.0000 企业1到储备库1 24-20-13-27 80.00000 企业2到库1 41-42-28 60.00000 企业3到储备库2 34-32-39-30 40.00000 企业1到储备库1 24-20-13-27 40.00000 企业2到库1 41-42-28 30.00000 企业2到库1 41-42-28 30.00000 企业3到库8 34-32-38 40.00000 企业1到储备库1 24-20-13-27 80.00000 企业2到库1 41-42-28 30.00000 企业3到库8 34-32-38 20.00000 企业2到库1 41-42-28 30.00000 企业3到库8 34-32-38 20.00000 企业1到储备库1 24-20-13-27 80.00000 企业2到库1 41-42-28 30.00000 企业3到库8 34-32-38 20.00000 库5到储备库1 22-19-18-15-42-28 20.00000（表三）其总的运费成本为：460204元。7、模型的优缺点及改进 我们假设仓库与仓库之间存在调运，利用动态规划求解其它的调运路线，使得我们的调运方案具有较好的完整性，但是由于20天的数据计算，变量太多，我们简化了，采用8天，也就是所有物资满足各库的预测值，企业的基本无库存。我们考虑在调运过程中与时间无关的情况，但是在实际情况中，如果遇到紧急情况时，可能使得防洪物质短缺或者路段被冲断，从而被迫我们必须得改变调运路线，选择时间为上的原则，那样将导致运费的增加。 该模型应该做以下改进： 1、应该增加货物调运过程中的时间因素，并且为了预防某些路段因紧急情况而不能使用，则应该设有预备方案，这样才能做到临危不惧，从而确保防洪工作做得更好。 2、在现实生活中，每一次运输的运输量会有一定的限制，在某种情况还会因为运量的多少而改变运费，例如运量过少，负责运输单位会因运输过程中的物质耗费而亏本，因此负责运输单位会为确保其利益，增加本次运输费用，故无形中就会增加单位货物的运输费用。所以在模型的改进中，应该考虑这个因素，从而使该模型更具有现实性。 3、对于路线的选择应该增加对于该路段的交通流量作出分析。比如流量高峰期为避免堵车，换走其他路线。8、模型的推广本文的模型为物资调配问题，它可以用到许多领域：1、人员指派也可以应用此模型，但还需考虑人员的分布，地区的选择等等。2、此模型可以推广到商品的发放问题中。但还需要考虑更多的因素，如运输过程中商品的变质期限、商品的保鲜费用、市场变动情况等等。9、参考文献1李维铮等 运筹学 北京 清华大学出版社 20062张宏伟等 LINGO8.0及其在环境系统优化中的应用 天津大学出版社 20053梁国业 廖健平 数学建模 冶金工业出版社 20044胡良剑 孙晓君 MATLAB数学实验 高等教育出版社 2006附录一：Difkstra算法程序：function S,D=minRoute(i,m,W,opt)if nargin4,opt=0;enddd=;tt=;ss=;ss(1,1)=i;V=1:m;V(i)=;dd=0;i;kk=2;mdd,ndd=size(dd);while isempty(V) tmpd,j=min(W(i,V);tmpj=V(j); for k=2:ndd tmp1,jj=min(dd(1,k)+W(dd(2,k),V); tmp2=V(jj);tt(k-1,:)=tmp1,tmp2,jj; end tmp=tmpd,tmpj,j;tt;tmp3,tmp4=min(tmp(:,1); if tmp3=tmpd ss(1:2,kk)=i;tmp(tmp4,2); else tmp5=find(ss(:,tmp4)=0);tmp6=length(tmp5); if dd(2,tmp4)=ss(tmp6,tmp4) ss(1:tmp6+1,kk)=ss(tmp5,tmp4);tmp(tmp4,2); else,ss(1:3,kk)=i;dd(2,tmp4);tmp(tmp4,2); end;end dd=dd,tmp3;tmp(tmp4,2);V(tmp(tmp4,3)=; mdd,ndd=size(dd);kk=kk+1;end;if opt=1 tmp,t=sort(dd(2,:);S=ss(:,t);D=dd(1,t);else,S=ss;D=dd(1,:);end结果输出程序clear;w=inf*ones(42);w(1,2,34,33)=48,54,72;w(2,1,3,7,9)=48,42,60,74.4;w(3,2,36,10)=42,60,50.4;w(4,29,30,5,6)=80,84,20,36;w(5,4,6,39,40)=20,56,170,76;w(6,4,5,40,11,41)=36,56,36,64,57.6;w(7,2,10,27)=60,96,140;w(8,15,14,28)=76,72,100;w(9,2,31,40,27)=74.4,62.4,33.6,48;w(10,3,7,12)=50.4,96,62.4;w(11,6,15,25,27)=64,112,80,96;w(12,10,13)=62.4,96;w(13,12,20,27)=96,81.6,100;w(14,8,17,23)=72,112,60;w(15,8,42,18,25,11)=76 33.6 69.6 55.2 112;w(16,18,21,23)=150 69.6 78;w(17,14,23)=112 62.4;w(18,15,23,16,19,25)=69.6 54 150 26.4 60;w(19,18,22,26)=26.4 86.4 33.6;w(20,13 24 22)=81.6 60 96;w(21,16 22)=69.6 54;w(22,19 21 20)=86.4 54 96;w(23,14 17 16 18)=60 62.4 78 54;w(24,20 26)=60 36;w(25,15 18 26 11)=55.2 60 21.6 80;w(26,25 19 24 27)=21.6 33.6 36 84;w(27,9 40 11 26 13 7)=48 64 96 84 100 140;w(28,8 42 29)=100 38.4 72;w(29,28 4 30)=72 80 74.4;w(30,29 4 39)=74.4 84 18;w(31,9 32)=62.4 60;w(32,35 39 31 34 38)=117.6 74.4 60 30 81.6;w(33,1 36 37)=72 48 45.6;w(34,1 32)=54 30;w(35,39 32)=204 117.6;w(36,3 33)=60 48;w(37,33 38)=45.6 42;w(38,32 37)=81.6 42;w(39,30 32 5 35)=18 74.4 170 204;w(40,5 6 27 9)=76 36 64 33.6;w(41,6 42)=57.6 31.2;w(42,28 15 41)=38.4 33.6 31.2;s1,d1=minroute(27,42,w,1);A=s1(:, 30)B=d1(:, 30) 所得结果：A1= 28 28 28 28 28 28 28 28 28 28 28 28 42 29 42 42 42 29 29 42 42 29 42 29 15 30 41 15 41 0 30 15 41 30 41 30 18 39 6 18 6 0 39 25 0 39 6 0 23 32 40 19 40 0 32 26 0 32 40 0 0 35 9 22 9 0 38 24 0 34 27 0 0 0 31 0 2 0 0 0 0 0 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 0 36 0 0 0 0 0 0 0B1= 195.6000 356.4000 259.2000 254.4000 373.2000 72.0000 320.4000 184.8000 69.6000 268.8000 227.2000 146.4000A2= 23 23 23 23 23 23 23 23 23 23 23 18 18 18 18 18 18 18 18 18 18 1 19 19 19 19 15 19 19 15 19 19 15 26 26 22 26 42 26 26 42 26 26 42 27 27 0 27 28 27 24 41 27 27 28 9 9 0 9 29 9 0 0 9 0 29 31 31 0 2 0 31 0 0 31 0 30 32 0 0 3 0 32 0 0 32 0 0 35 0 0 36 0 38 0 0 34 0 0B2= 195.6000 486.0000 308.4000 166.8000 422.4000 267.6000 450.0000 150.0000 188.4000 398.4000 198.0000 342.0000A3= 35 35 35 35 35 35 35 35 35 35 32 32 32 32 32 32 32 32 32 32 31 31 34 39 38 31 31 34 31 39 0 9 1 30 0 9 9 0 9 30 0 27 33 29 0 27 40 0 27 0 0 26 36 0 0 26 6 0 0 0 0 19 0 0 0 24 41 0 0 0 0 22 0 0 0 0 0 0 0 0B3= 177.6000 492.0000 321.6000 284.4000 199.2000 408.0000 367.2000 147.6000 288.0000 210.0000A4= 31 31 31 31 31 31 31 31 31 9 9 32 32 9 9 32 9 32 27 2 39 38 27 40 34 27 39 26 3 30 0 26 6 0 0 30 19 36 29 0 24 41 0 0 0 22 0 0 0 0 0 0 0 0B4= 314.4000 238.8000 226.8000 141.6000 230.4000 189.6000 90.0000 110.4000 152.4000A5= 22 22 22 22 22 22 22 22 19 19 19 20 19 19 19 19 26 18 26 24 18 26 26 18 27 15 27 0 15 27 27 15 9 42 9 0 42 9 0 42 2 28 31 0 41 31 0 28 3 29 32 0 0 32 0 29 36 0 38 0 0 34 0 30B5= 428.4000 326.4000 456.0000 156.0000 247.2000 404.4000 204.0000 400.8000A6= 36 36 36 36 36 36 36 3 33 3 3 33 3 33 2 37 2 2 1 2 1 9 38 9 9 34 9 34 40 0 27 40 0 27 32 6 0 26 6 0 0 39 4 0 24 41 0 0 30 29 0 0 0 0 0 0B6= 362.0000 135.6000 344.4000 303.6000 174.0000 224.4000 296.4000A7= 29 29 29 29 29 29 30 28 28 30 4 30 39 42 42 39 6 0 32 15 41 32 40 0 38 25 0 34 27 0 0 26 0 0 0 0 0 24 0 0 0 0B7= 248.4000 256.8000 141.6000 196.8000 216.0000 74.4000A8= 38 38 38 38 38 32 32 32 32 32 31 31 34 31 39 9 9 0 9 30 27 40 0 27 0 26 6 0 0 0 24 41 0 0 0 B8= 372.0000 331.2000 111.6000 252.0000 174.0000Aa= 24 24 24 24 26 26 26 26 25 27 27 25 15 9 0 11 42 31 0 6 41 32 0 4 0 34 0 30Ba= 177.6000 320.4000 120.0000 321.6000Ab= 41 41 41 6 6 6 40 40 4 9 27 30 31 0 0 32 0 0 34 0 0 0 0 0Bb= 279.6000 157.6000 177.6000Ac= 34 34 32 32 31 39 9 30 27 0Bc=200.4000 122.4000Ak2= 27 40 6 4 30Bk2= 220附件二：问题二程序结果：Objective value: 394896.0D1 241740.0 D2 52464.00 D3 4800.000 D4 19056.00 D5 11928.00 D6 5328.000 D7 6552.000 D8 53028.00 P( 1) 0.000000 P( 2) 0.000000 P( 3) 0.000000 P( 4) 500.0000 P( 5) 600.0000 P( 6) 300.0000 P( 7) 350.0000 P( 8) 450.0000 P( 9) 300.0000 P( 10) 500.0000 P( 11) 600.0000 P( 12) 3000.000 P( 13) 2500.000 调运量 调运路线 调运费用/百件1 640.0000 企1储1 24-26-27 120 350.0000 企3库4 34-32-31 90 20.00000 企3库6 34-1-33-36 174 110.0000 企3库7 34-32-39-30-29 196.8 40.00000 企3库8 34-32-38 111.6 60.00000 库4储1