应急运输调度方案设计模型v2

1、2013年中央民族大学数学建模作业论文题目：应急运运输调度度方案设设计模型型参赛队员 ：姓名：吴极极 学院院：理学学院 专业：统计学学 年级级：111级姓名：刘超超 学院院：理学学院 专业：统计学学 年级级：111级姓名：夏浩浩 学院院：理学学院 专业：统计学学 年级级：111级应急运输调调度方案案设计模模型摘 要本题要求我我们求出出每个企企业和储储备库在在不同情情况下给给发放地地点运输输救灾物物资的最最优调运运方案，我我们以每每个企业业和储备备库给每每个发放放地点的的调运量量作为决决策变量量，以公公路的长长度和运运输成本本的乘积积作为单单位运费费（价值值系数）构构造目标标函数。所所求问题题即

2、转化化为最优优路径问问题和线线性规划划问题。在求解问题题（1）（22）（33）（44）之前前，我们们首先对对题目附附件2中中的图进进行预处处理。把把公路的的交点看看成顶点点，每个个点之间间的公路路看成线线段，以以公路的的长度和和运输成成本的乘乘积作为为一条线线段的权权重，做做出赋权权图。利利用MAATLAAB软件件使用FFloyyd算法法计算出出每个企企业和储储备库到到每个发发放地点点的最优优路径（最最低单位位运费和和路线）（见表4-3-1），解决最优路径问题，求出了目标函数中的价值系数。求解问题（11）时，把把时间因因素放在在第一位位考虑，首首先求得得最快运运输时间间t。然然后以运运输成本本

3、最低为为目标函函数，以以调运量量小于等等于企业业和储备备库储存存量，接接收量介介于最低低需求量量与最大大需求量量之间等等作为约约束条件件，利用用Linngo软软件求解解此线性性规划问问题的最最优解。由由此得到到物资的的最佳调调运方案案，包括括调运量量和调运运路线（见见表4-3-22）。求解问题（22）时，已已知时间间t，由由实际情情况可以以修改约约束条件件，令调调运量等等于储存存量，其其他约束束条件不不变。同同样，利利用Liingoo软件可可以求出出一个最最优解（见见表4-3-33）。求解问题（33）时，经经过计算算可知企企业的生生产能力力不能够够满足发发放地点点的实际际需求，我我们通过过企业

4、增增产来满满足实际际需求。此此时需要要新增三三个变量量，把问问题（11）中的的约束条条件增加加几个约约束条件件，利用用Linngo求求解，得得到最佳佳调运方方案（见见表4-3-44）。求解问题（44）时，主主体思路路不变。由由于道路路中断，我我们只需需要重新新利用MMATLLAB软软件求出出最优路径径和目标标函数的的价值系系数（见见表4-3-55），再利利用Liingoo软件求求解线性性规划问问题即可可（见表4-33-6、表4-3-7、表4-3-8）。最后，我们们客观地地评价了了该模型型的优缺缺点，并并且做出出了相应应的改进进和推广广。关键词：最最优路径径 Flloydd算法 MATTLABB

5、 线性性规划 Linngo 一、问题的的提出与与分析1.1 问问题重述述在某地区有有生产某某种救灾灾物质的的企业有有三家，设设置物资资发放点点八个，储储备仓库库两个。在在灾害发发生时，企企业、各各物资发发放地点点、储备备仓库的的库存情情况，及及各发放放点的最最低需求求和实际际需求情情况见附附件1。企业业、发放放点、仓仓库及道道路分布布情况见见附件22。设该该种物资资的运输输成本为为高等级级公路220元/公里百件，普普通公路路12元/公里百件。（1）预案案要求尽尽快满足足各发放放点对救救灾物质质的最低低需求，并并尽量使使运输成成本降低低。建立立数学模模型，给给出所需需要的时时间，物物资的调调运方

6、案案，包括括调运量量和调运运路线。（2）在220天内内，按均均衡配给给的原则则，各发发放点可可以得到到多少物物资？给给出相应应的调运运方案。（3）能否否在255天内满满足各发发放点的的实际需需求？怎怎样才能能满足各各发放点点的实际际需求？并给出出相应的的调运方方案。（4）在灾灾害发生生时可能能造成交交通中断断，以中中断路段段：144-233，111-255，266-277，9-31为为例，重重新讨论论上述三三个问题题。1.2 问问题分析析1.2.11 对问题（11）的分分析要尽快满足足各发放放地点对对救灾物物资的最最低需求求，由现现有总库库存加上上企业11,2,3t天天的生产产量大于于等于88

7、个发放放点最低低需求的的不等式式，可以以解出满满足题意意的最小小时间tt为8天天。接着着在最小小时间tt=8的的情况下下，求最最小的运运输费用用，以企企业1,2,33及储存存库向88个发放放点运输输的物资资为决策策变量，建建立目标标函数.而建立立目标函函数需要要知道决决策变量量对应的的价值系系数,我我们根据据附件22, 把公路路的交点点看成顶顶点，每每个点之之间的公公路看成成线段，从从而把地地理图转转化为联联通无向向图.又又由题目目条件高高等级公公路和普普通公路路的运输输费用不不同，我我们把每每公里每每百件的的运费和和路程的的乘积作作为每条条线段的权权数，根根据图论论知识，将将求解价价值系数数

8、的问题题转化为为最优路径径问题。再再根据赋赋权图制制作权数数矩阵，然然后利用用MATTLABB使用FFloyyd算法法求出企企业1,2,33及储存存库到88个发放放点的最最优路径径，由此此计算出出价值系系数，再利用用Lingoo软件在相相关约束束下求出出目标函函数的最最优解，从从而得到到物资的的调运方方案。1.2.22 对问题（22）的分分析按照均衡配配给的原原则，求求20天天后各发发放点收收到物资资的情况况以及最最佳运输输方案，同同样是线线性规划划问题，将将模型中中的t=20，再再对约束束条件进进行修改改，使“库存+生产量量=发放放点接收收量”，得出出最优答答案。1.2.33 对问题（33）

9、的分分析要知道255天之内内能否满满足各发发放点的的实际需需求，即即计算225天的的库存和和生产量量之和，与与发放点点的最大大需求量量进行比比较，实实际上并并没有达达到需求求，解决决办法是是让企业业增产，使使之满足足各发放放点的最最高需求求，再用用线性规规划模型型求出最最优方案案即可。1.2.44 对问题（44）的分分析我们要知道道指定路路段中断断后，上上述建立立的数学学模型是是否可用用，也就就是说只只要检验验到模型型中所选选取的路路线是否否经过该该路段，如如果不经经过，则则中断路路线对模模型没有有影响，若若经过，可可将路段段中断后后的图采采用第一一步的方方式重新新处理计计算，分分别求解解出最

10、佳佳运输方方案。二、基本假假设2.1 假假设灾难难发生时时，企业业1,22,3只只向发放放点运送送物资，不不向储备备库运送物物资，而而储备库则是只只出不进进的向各各个发放放点运送送物资。2.2 假假设灾难难发生当当天企业业是生产产物资的的，即从从灾难发发生第一一天起，每每天零点点时每个个企业的的库存量量都增加加其日生生产量。2.3 假假设道路路的运输输能力足足够大，没没有运输输限制。2.4 假假设调运运过程中中没有衍衍生灾害害，各个个路段道道路通畅畅，无意意外发生生。2.5 不不考虑各各点间的的时间，假假设所有有物资瞬瞬时到达达。2.6 假假设运输输时走高高等级公公路和普普通公路路除了费费用的

11、差差别外，在在运输结结果上没没有其他他差别。2.7 假假设发放放点，企企业和储储存库与与公路的的交点处处是重合合的。三、符号说说明i=1,22,3,4,55，当ii=1,2,33时为企企业1,2,33，当ii=4,5时为为储备库库1,22j=1,22,3,4,55,6,7,88，都为为发放点点:从i运到到发放点点j的物物资量:从i到jj每百件件的运费费: 发放地地点j的的现有库库存：发放地点点j的最最低需求求：发放地点点j的最最大需求求: i的现现有库存存，i=1,22,3,4,55：企业i的的日生产产量，ii=1,2,33：企业i增增产后的的日生产产量，其其中，t:一个调调运方案案的所需需时

12、间Z:一个调调运方案案的总运运费四、模型的的建立与与求解4.1 数数据处理理 将将附件22中的公公路的交交点看成成顶点，每每个点之之间的公公路看成成线段，形成一个联通无向图。并且以每公里每百件的运费和路程的乘积作为权重，做出如下赋权图：图4-1-1 赋赋权图4.2 模模型建立立根据题意，建建立目标标函数ZZ表示从从企业11,2,3和储储备库11,2向向8个发发放点运运送物资资的总费费用，根据各各个发放放点的物物资需求求量写出出其约束束条件，如下：目标函数：约束条件：s.tt.4.3 模模型求解解4.3.11 求解解最优路径径，确定定：利用MATTLABB软件由由Flooyd算算法(源程序序见附

13、录录1、22)求出从发出地地点i到到发放地地点j的的每百件件运费和和最优路路径，其其结果如如下表所所示：表4-3-1 各发出出地点与与发放地地点每百件件运费和和最优路径表 *企业1企业2企业3储备库1储备库2发放点118488,244,266,255,155,422,288696,41,42,2826888,344,322,399,300,299,28822722,277,400,6,41,42,2814644,300,299,288发放点215000,244,266,199,188,23318844,411,422,155,188,23337400,344,1,2,77,277,266,19

14、9,188,23319800,277,266,199,188,23334200,300,299,288,422,155,188,233发放点340800,244,266,277,9,31,32,3536722,411,6,40,9,331,332,33514766,344,322,35528800,277,9,31,32,3521000,300,399,322,355发放点423044,244,266,277,9,3118966,411,6,40,9,331900,34,32,3111044,277,9,3115244,300,399,322,311发放点515600,244,200,2222

15、4722,411,422,155,188,199,22238000,344,1,2,77,277,266,199,22220400,277,266,199,22240088,300,299,288,422,155,188,199,222发放点634444,244,266,277,9,2,33,36630366,411,6,40,9,22,3,3617400,344,1,33,3622444,277,9,2,33,36629644,300,399,322,344,1,33,36发放点725688,244,266,255,155,422,288,29914166,411,422,288,29919

16、688,344,322,399,300,29921600,277,400,6,4,229744,30,29发放点837200,244,266,277,9,31,32,3833122,411,6,40,9,331,332,33811166,344,322,38825200,277,9,31,32,3817400,300,399,322,388* 本表中中 符号表示示数组，例例如118488,244,266,255,155,422,288，第一个个元素118488表示该该路径的的每百件件运费，后后面的元元素244,266,255,155,422,288表示该该最优路路径经过过的节点点序号（包包括起

17、点点和终点点）（见图4-1-1）。下同。4.3.22 求解问问题（11）由于要使物物资尽快快到达发发放地点点，则应应该首先先生产出出满足各各发放地地点最低低需求的的物资量量，再进进行运输输规划。此此时有：发放地点最最低总需需求量=35550发放地点，企企业与储储备库现现储存总总量=+=28840则有：解得：所以，应该该取最优优调运时时间，再再将调运运时间代代入4.2的线线性规划划模型中中，如下下：目标函数：约束条件：s.tt.利用Linngo软软件（源源程序见见附录33）对其其求解，得得到最优优解及调调运路线线为：表4-3-2 各各发出地点点向发放放地点运运送量和和最优路径径表 *企业1企业2

18、企业3储备库1储备库2发放点10300（442）00160(229)发放点2140（226-119-118）00410（226-119-118）0发放点30000280(339-332)发放点4000320(99)0发放点5300（220）0000发放点6000260(99-2-3)0发放点70000470(直直达)发放点800240（332）0290(339-332)* 本表中中（）符符号表示示路径，例如1440（226-119-118），括括号外1400表示该路路径的运运送量，（26-19-18）表示该路径经过的节点序号（即表4-3-1中对应的最优路径，不包括起点和终点）。下同。4.3.3

19、3 求解问问题（22）发放地点最最低总需需求量=35550；发放地点实实际总需需求量=56600；而当时，有有；即当时，企企业和储储备库的的物资总总量肯定定能够满满足各个个发放地地点的最最低需求求，而且且不超过过各个发发放点的的最高需需求。从从实际情情况出发发，不可可能让物物资堆积积在企业业之中，所所以按照照均匀配配给的原原则，将将企业11，2,3和储储备库11,2以以及发放放点原来来所存的的所有物物资全部部发放，得到新的规划模型如下：目标函数：约束条件：s.tt. 利用Linngo软软件（源源程序见见附录44）解出出此时的的最优解解以及各各个发放放点所得得到的物物资和调调运方案案。表4-3-

20、3 220天内各发出出地点向发发放地点点运送量量和最优路径径表 *企业1企业2企业3储备库1储备库2发放点10660（442）00100(229)发放点2480（226-119-118）00370（226-119-118）0发放点300280（332）00发放点4000370(99)0发放点5440（220）0000发放点6000260(99-2-3)0发放点70000570(直直达)发放点800200（332）0530(339-332)4.3.44 求解问问题（33）要知道255天之内内能否满满足各发发放点的的实际需需求，即即计算225天的的库存和和生产量量之和，与与发放点点的实际际需求量量

21、进行比比较。由由题意：发放地点实实际总需需求量=56600；发放地点，企企业与储储备库现现储存总总量=+=28840；25天企业业1,22,3的的总产量量=222500；由于22550+228400DD(i,k)+D(kk,j) D(i,jj)=DD(i,k)+D(kk,j); paath(i,jj)=ppathh(i,k); ennd ennd enndend p=spp;mp=spp;for kk=1:n iif mmp=ep d=ppathh(mpp,epp); p=p,dd; mp=d; eendendd=D(ssp,eep);path=p;%=flloydd.m文件结结束=2. 问题

22、题（1）利利用Flloydd算法给给出系数数和各点点间最优优路径的的Mattlabb程序%=ruun011.m文件开开始=load(liiness0.mmat);%“linnes00.maat”为事先先录入的的42*42的的权数矩矩阵，包包含每点点的 距距离*单单位路费费 数据据i1=1;j1=1;resullt=ccelll(5,8);for ii=224,441,334,227,330 ffor j=28,23,35,31,22,36,29,38 d,patth=flooyd(linnes00,i,j); %从“flooyd.m”调用ffloyyd算法法 ressultti11,j11=d

23、,ppathh; j1=j1+1; eend ii1=ii1+11;j11=1;end%=ruun011.m文件结结束=3. 问题题（1）计计算最低低成本运运输方案案的Liingoo命令modell:!5发点88收点运运输问题题;sets:warehhousses/wh11.wwh5/:caapaccityy;!企业1,2,33与储备备库1,2的储储存量;vendoors/v1.v88/:ddemaand11,deemannd2;!发放地地点的最最低需求求量和最最高需求求量;linkss(waarehhousses,venndorrs):cosst,vvoluume;!权数矩矩阵和决决策变量量

24、;endseets!目标函数数;min=summ(liinkss:coost*vollumee);!需求约束束（储存存量在最最低需求求量和最最高需求求量之间间）;for(venndorrs(JJ): suum(wwareehouusess(I):voolumme(II,J)=demmandd1(JJ); suum(wwareehouusess(I):voolumme(II,J)=demmandd2(JJ); );!产量约束束（发放放量不超超过储存存量）;for(warrehoousees(II): suum(vvenddorss(J):voolumme(II,J)=demmandd1(JJ);

25、 suum(wwareehouusess(I):voolumme(II,J)=440;extraa(2)=330;extraa(3)=220;!产量约束束（发放放量等于于储存量量）;for(warrehoousees(II): suum(vvenddorss(J):voolumme(II,J)=ccapaacitty(II)+225*eextrra(II); );!这里是数数据;data: cappaciity=1200 600 800 10000 12000; demmandd=7660 8850 5800 3770 9900 4600 5770 7730; cosst=118488 155

26、00 40880 223044 15560 34444 225688 37720 6966 18884 36772 118966 24472 30336 114166 33312 226888 39984 14776 9000 40044 17440 119688 11116 222722 19980 28880 111044 20040 22444 221600 25520 114644 34420 21000 115244 40008 26776 7444 17740;enddaataend最佳调运方方案： Glooball opptimmal sollutiion fouund. Obj

27、jecttivee vaaluee: 722276600. Tottal sollverr itteraatioons: 155 Varriabble Vaaluee RReduucedd Coost CAPPACIITY( WHH1) 1220.000000 0.00000000 CAPPACIITY( WHH2) 600.0000000 0.00000000 CAPPACIITY( WHH3) 800.0000000 0.00000000 CAPPACIITY( WHH4) 10000.0000 0.00000000 CAPPACIITY( WHH5) 12200.0000 0.00000

28、000 DEMMANDD( VV1) 7660.000000 0.00000000 DEMMANDD( VV2) 8550.000000 0.00000000 DEMMANDD( VV3) 5880.000000 0.00000000 DEMMANDD( VV4) 3770.000000 0.00000000 DEMMANDD( VV5) 9000.000000 0.00000000 DEMMANDD( VV6) 4660.000000 0.00000000 DEMMANDD( VV7) 5770.000000 0.00000000 DEMMANDD( VV8) 7330.000000 0.0

29、0000000 EXXTRAA( EE1) 400.0000000 0.00000000 EXXTRAA( EE2) 300.0000000 0.00000000 EXXTRAA( EE3) 400.4000000 0.00000000 EXXTRAA( EE4) 0.00000000 0.00000000 EXXTRAA( EE5) 0.00000000 0.00000000 COSST( WH11, VV1) 18848.0000 0.00000000 COSST( WH11, VV2) 15500.0000 0.00000000 COSST( WH11, VV3) 40080.0000

30、0.00000000 COSST( WH11, VV4) 23304.0000 0.00000000 COSST( WH11, VV5) 15560.0000 0.00000000 COSST( WH11, VV6) 34444.0000 0.00000000 COSST( WH11, VV7) 25568.0000 0.00000000 COSST( WH11, VV8) 37720.0000 0.00000000 COSST( WH22, VV1) 6996.000000 0.00000000 COSST( WH22, VV2) 18884.0000 0.00000000 COSST( W

31、H22, VV3) 36672.0000 0.00000000 COSST( WH22, VV4) 18896.0000 0.00000000 COSST( WH22, VV5) 24472.0000 0.00000000 COSST( WH22, VV6) 30036.0000 0.00000000 COSST( WH22, VV7) 14416.0000 0.00000000 COSST( WH22, VV8) 33312.0000 0.00000000 COSST( WH33, VV1) 26688.0000 0.00000000 COSST( WH33, VV2) 39984.0000

32、 0.00000000 COSST( WH33, VV3) 14476.0000 0.00000000 COSST( WH33, VV4) 9000.000000 0.00000000 COSST( WH33, VV5) 40044.0000 0.00000000 COSST( WH33, VV6) 17740.0000 0.00000000 COSST( WH33, VV7) 19968.0000 0.00000000 COSST( WH33, VV8) 11116.0000 0.00000000 COSST( WH44, VV1) 22272.0000 0.00000000 COSST(

33、WH44, VV2) 19980.0000 0.00000000 COSST( WH44, VV3) 28880.0000 0.00000000 COSST( WH44, VV4) 11104.0000 0.00000000 COSST( WH44, VV5) 20040.0000 0.00000000 COSST( WH44, VV6) 22244.0000 0.00000000 COSST( WH44, VV7) 21160.0000 0.00000000 COSST( WH44, VV8) 25520.0000 0.00000000 COSST( WH55, VV1) 14464.000

34、0 0.00000000 COSST( WH55, VV2) 34420.0000 0.00000000 COSST( WH55, VV3) 21100.0000 0.00000000 COSST( WH55, VV4) 15524.0000 0.00000000 COSST( WH55, VV5) 40008.0000 0.00000000 COSST( WH55, VV6) 26676.0000 0.00000000 COSST( WH55, VV7) 7444.000000 0.00000000 COSST( WH55, VV8) 17740.0000 0.00000000 VOOLUM

35、ME( WH11, VV1) 0.00000000 15336.0000 VOOLUMME( WH11, VV2) 8000.000000 0.00000000 VOOLUMME( WH11, VV3) 0.00000000 25880.0000 VOOLUMME( WH11, VV4) 0.00000000 16880.0000 VOOLUMME( WH11, VV5) 3220.000000 0.00000000 VOOLUMME( WH11, VV6) 0.00000000 16880.0000 VOOLUMME( WH11, VV7) 0.00000000 24224.0000 VOO

36、LUMME( WH11, VV8) 0.00000000 25880.0000 VOOLUMME( WH22, VV1) 7660.000000 0.00000000 VOOLUMME( WH22, VV2) 500.0000000 0.00000000 VOOLUMME( WH22, VV3) 0.00000000 17888.0000 VOOLUMME( WH22, VV4) 0.00000000 8888.00000 VOOLUMME( WH22, VV5) 0.00000000 5288.00000 VOOLUMME( WH22, VV6) 0.00000000 8888.00000

37、VOOLUMME( WH22, VV7) 0.00000000 8888.00000 VOOLUMME( WH22, VV8) 0.00000000 17888.0000 VOOLUMME( WH33, VV1) 0.00000000 24000.0000 VOOLUMME( WH33, VV2) 0.00000000 25008.0000 VOOLUMME( WH33, VV3) 5880.000000 0.00000000 VOOLUMME( WH33, VV4) 0.00000000 3000.00000 VOOLUMME( WH33, VV5) 0.00000000 25008.000

38、0 VOOLUMME( WH33, VV6) 4110.000000 0.00000000 VOOLUMME( WH33, VV7) 0.00000000 18448.0000 VOOLUMME( WH33, VV8) 1000.000000 0.00000000 VOOLUMME( WH44, VV1) 0.00000000 14880.0000 VOOLUMME( WH44, VV2) 0.00000000 0.00000000 VOOLUMME( WH44, VV3) 0.00000000 9000.00000 VOOLUMME( WH44, VV4) 3770.000000 0.000

39、00000 VOOLUMME( WH44, VV5) 5880.000000 0.00000000 VOOLUMME( WH44, VV6) 500.0000000 0.00000000 VOOLUMME( WH44, VV7) 0.00000000 15336.0000 VOOLUMME( WH44, VV8) 0.00000000 9000.00000 VOOLUMME( WH55, VV1) 0.00000000 5522.00000 VOOLUMME( WH55, VV2) 0.00000000 13220.0000 VOOLUMME( WH55, VV3) 0.00000000 0.

40、00000000 VOOLUMME( WH55, VV4) 0.00000000 3000.00000 VOOLUMME( WH55, VV5) 0.00000000 18448.0000 VOOLUMME( WH55, VV6) 0.00000000 3122.00000 VOOLUMME( WH55, VV7) 5770.000000 0.00000000 VOOLUMME( WH55, VV8) 6330.000000 0.00000000 RRow Slaack or Surrpluus Duual Priice 1 722276600. -1.00000000 2 0.0000000

41、0 -2888.00000 3 0.00000000 -14776.0000 4 0.00000000 -14776.0000 5 0.00000000 -6000.00000 6 0.00000000 -15336.0000 7 0.00000000 -17440.0000 8 0.00000000 -1200.00000 9 0.00000000 -11116.0000 10 0.00000000 -126600.00 11 0.00000000 -156600.00 12 0.00000000 -6000.00000 13 0.00000000 -102200.00 14 200.4000000 0.00000000 15 0.00000000 -24.000000 16 0.00000000 -4088.00000 17 0.00000000 0.00000000 18 0.00000000 -5044.00000 19 0.00000000 -6244.000006. 问题题（4）修修改权数数矩阵重重新计算算系数和和各点间间最优路径径的Maatlaab程序序%=ruun044.m文件开开始=load(liiness0.