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

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

2、交点看成顶点， 每个点之间的公路看成线段， 以公路的长度和运 输成本的乘积作为一条线段的权重，做出赋权图。利用MATLAB件使用Floyd算法计算出每个企业和储备库到每个发放地点的最优路径（最低单位运费和路 线）（见表 4-3-1 ），解决最优路径问题，求出了目标函数中的价值系数。求解问题（ 1）时，把时间因素放在第一位考虑，首先求得最快运输时间 t 。 然后以运输成本最低为目标函数， 以调运量小于等于企业和储备库储存量， 接收 量介于最低需求量与最大需求量之间等作为约束条件， 利用 Lingo 软件求解此线 性规划问题的最优解。 由此得到物资的最佳调运方案， 包括调运量和调运路线（见 表 4

3、-3-2 ）。求解问题（ 2）时，已知时间 t ，由实际情况可以修改约束条件，令调运量 等于储存量，其他约束条件不变。 同样，利用 Lingo 软件可以求出一个最优解 （见 表 4-3-3 ）。求解问题（ 3）时，经过计算可知企业的生产能力不能够满足发放地点的实 际需求，我们通过企业增产来满足实际需求。 此时需要新增三个变量， 把问题（1） 中的约束条件增加几个约束条件，利用 Lingo 求解，得到最佳调运方案（见表 4-3-4 ）。求解问题（4）时，主体思路不变。 由于道路中断，我们只需要重新利用 MATLAB 软件求出最优路径和目标函数的价值系数（见表 4-3-5 ），再利用 Lingo

4、软件求 解线性规划问题即可（见表 4-3-6 、表 4-3-7 、表 4-3-8 ）。最后，我们客观地评价了该模型的优缺点，并且做出了相应的改进和推广。关键词：最优路径Floyd算法MATLAB线性规划Lingo、问题的提出与分析1.1 问题重述在某地区有生产某种救灾物质的企业有三家， 设置物资发放点八个， 储备仓 库两个。在灾害发生时，企业、各物资发放地点、储备仓库的库存情况，及各发 放点的最低需求和实际需求情况见附件 1。企业、发放点、仓库及道路分布情况 见附件2。设该种物资的运输成本为高等级公路 20元/公里?百件，普通公路 12元/ 公里?百件。（1）预案要求尽快满足各发放点对救灾物质

5、的最低需求，并尽量使运输成 本降低。建立数学模型，给出所需要的时间，物资的调运方案，包括调运量和调 运路线。（2）在20天内，按均衡配给的原则，各发放点可以得到多少物资？给出相 应的调运方案。（3）能否在 25天内满足各发放点的实际需求？怎样才能满足各发放点的实 际需求？并给出相应的调运方案。（4）在灾害发生时可能造成交通中断， 以中断路段： 14-23 ，11-25 ，26-27 ， 9-31 为例，重新讨论上述三个问题。1.2 问题分析1.2.1 对问题（ 1）的分析 要尽快满足各发放地点对救灾物资的最低需求，由现有总库存加上企业1,2,3t 天的生产量大于等于 8 个发放点最低需求的不等

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

7、 及储存库到 8 个发放点的最优路径， 由此计算出价值系数， 再利用 Lingo 软件在相关约束下求出目标函数的最优解，从而得到物资的调运方案。1.2.2 对问题（ 2）的分析 按照均衡配给的原则，求 20 天后各发放点收到物资的情况以及最佳运输方 案，同样是线性规划问题，将模型中的 t=20 ，再对约束条件进行修改，使“库 存+生产量=发放点接收量”，得出最优答案。1.2.3 对问题（ 3）的分析 要知道 25天之内能否满足各发放点的实际需求， 即计算 25天的库存和生产 量之和，与发放点的最大需求量进行比较， 实际上并没有达到需求， 解决办法是 让企业增产， 使之满足各发放点的最高需求，

8、再用线性规划模型求出最优方案即 可。1.2.4 对问题（ 4）的分析 我们要知道指定路段中断后， 上述建立的数学模型是否可用， 也就是说只要 检验到模型中所选取的路线是否经过该路段， 如果不经过， 则中断路线对模型没 有影响，若经过， 可将路段中断后的图采用第一步的方式重新处理计算， 分别求 解出最佳运输方案。二、基本假设2.1 假设灾难发生时，企业 1,2,3 只向发放点运送物资，不向储备库运送物资， 而储备库则是只出不进的向各个发放点运送物资。2.2 假设灾难发生当天企业是生产物资的， 即从灾难发生第一天起， 每天零点时 每个企业的库存量都增加其日生产量。2.3 假设道路的运输能力足够大，

9、没有运输限制。2.4 假设调运过程中没有衍生灾害，各个路段道路通畅，无意外发生。2.5 不考虑各点间的时间，假设所有物资瞬时到达。2.6 假设运输时走高等级公路和普通公路除了费用的差别外， 在运输结果上没有 其他差别。2.7 假设发放点，企业和储存库与公路的交点处是重合的。三、符号说明i=1,2,3,4,5 ，当 i=1,2,3 时为企业 1,2,3 ，当 i=4,5 时为储备库 1,2 j=1,2,3,4,5,6,7,8 ，都为发放点xij : 从 i 运到发放点 j 的物资量aij : 从 i 到 j 每百件的运费bj : 发放地点 j 的现有库存，e50Cj :发放地点j的最低需求 dj

10、 :发放地点j的最大需求 mt： i 的现有库存，i=1,2,3,4,5 ni :企业i的日生产量，i=1,2,3 e :企业i增产后的日生产量，其中 t： 一个调运方案的所需时间Z： 一个调运方案的总运费四、模型的建立与求解4.1数据处理将附件2中的公路的交点看成顶点，每个点之间的公路看成线段，形成一个 联通无向图。并且以每公里每百件的运费和路程的乘积作为权重， 做出如下赋权 图：4.2根据题意，建立目标函数Z表示从企业1,2,3和储备库1,2向8个发放点运送物资的总费用，根据各个发放点的物资需求量写出其约束条件，如下：目标函数：min Z58aij xijXj0,i 1,2,3,4,5,

11、j 123,4,567,85约束条件：s.t.CjXij bj dj, j 123,4,5,6,7,8i 18Xjmi n t,i 1,2,3,4,5j 14.3模型求解4.3.1求解最优路径，确定aj :利用MATLAB件由Floyd算法（源程序见附录1、2）求出从发出地点i至U发放地点j的每百件运费aj和最优路径，其结果如下表所示:表4-3-1各发出地点与发放地点每百件运费和最优路径表企业1企业2企业3储备库1储备库2发放点1发放点2发放点3发放点4发放点5发放点6发放点7发放点81848,24,26,25,15,42,281500,24,26,19,18,234080,24,26,27,

12、9,31,32,352304,24,26,27,9,311560,24,20,223444,24,26,27,9,2,3,362568,24,26,25,15,42,28,293720,24,26,27,9,31,32,38696,41,42,281884,41,42,15,18,233672,41,6,40,9,31,32,351896,41,6,40,9,312472,41,42,15,18,19,223036,41,6,40,9,2,3,361416,41,42,28,293312,41,6,40,9,31,32,382688,34,32,39,30,29,283740,34,1,2,7

13、,27,26,19,18,231476,34,32,35900,34,32,313800,34,1,2,7,27,26,19,221740,34,1,33,361968,34,32,39,30,291116,34,32,382272,27,40,6,41,42,281980,27,26,19,18,232880,27,9,31,32,351104,27,9,312040,27,26,19,222244,27,9,2,3,362160,27,40,6,4,292520,27,9,31,32,381464,30,29,283420,30,29,28,42,15,18,232100,30,39,32

14、,351524,30,39,32,314008,30,29,28,42,15,18,19,222964,30,39,32,34,1,33,36744,30,291740,30,39,32,38*本表中符号表示数组，例如1848,24,26,25,15,42,28，第一个元素1848表示该路径的每百件运费，后面的元素24,26,25,15,42,28表示该最优路径经过的节点序号（包括起点和终点）（见图4-1-1 ） 下同4.3.2求解问题（1）由于要使物资尽快到达发放地点，则应该首先生产出满足各发放地点最低需求的物资量，再进行运输规划。此时有:8发放地点最低总需求量=Cj =3550j i发放地

15、点，企业与储备库现储存总量则有：85=bj + mi =2840j 1i 1j 1335502840 山 ti 1解得：t 7.9所以，应该取最优调运时间t 8，再将调运时间t 8代入4.2的线性规划 模型中，如下：58目标函数： mi nZaijXji 1 j 1Xij 0,i 1,2,3,4,5, j 1,2,3,4,567,85约束条件：s.t. CjXjbj dj, j 1,2,3,4,567,8i 18Xijmi ni 8,i 1,2,3,4,5j 1利用Lin go软件（源程序见附录3）对其求解，得到最优解及调运路线为:表4-3-2各发出地点向发放地点运送量和最优路径表*企业1企业

16、2企业3储备库1储备库2发放点10300( 42)00160(29)发放点2140( 26-19-18)00410( 26-19-18)0发放点30000280(39-32)发放点4000320(9)0发放点5300 (20)0000发放点6000260(9-2-3)0发放点70000470（直达）发放点800240( 32)0290(39-32)*本表中（）符号表示路径，例如 140（26-19-18），括号外140表示该路径的运送量，（26-19-18）表示该路径经过的节点序号（即表4-3-1中对应的最优路径，不包括起点和终点）。下同4.3.3求解问题（2）发放地点最低总需求量8cj =3

17、550;8发放地点实际总需求量=dj=5600;j i3而当 t 20 时，有 3550 2840ni t 4640 5600 ;i 1即当t 20时，企业和储备库的物资总量肯定能够满足各个发放地点的最低 需求，而且不超过各个发放点的最高需求。从实际情况出发，不可能让物资堆积在企业之中，所以按照均匀配给的原则，将企业1, 2,3和储备库1,2以及发放点原来所存的所有物资全部发放，得到新的规划模型如下：58目标函数：min Zaij xiji 1 j 1Xij 0,i 1,2,3,4,5, j 123,4,5,6,7,85约束条件：s.t.CjXij bj dj, j 1,2,3,4,5,6,7

18、,8i 18Xj 二mi ni 20, i 1,2,3, 4,5j 1利用Lin go软件（源程序见附录4）解出此时的最优解以及各个发放点所得 到的物资和调运方案。表4-3-3 20天内各发出地点向发放地点运送量和最优路径表*企业1企业2企业3储备库1储备库2发放点10660 (42)00100(29)发放点2480( 26-19-18)00370( 26-19-18)0发放点300280 (32)00发放点4000370(9)0发放点5440 (20)0000发放点6000260(9-2-3)0发放点70000570（直达）发放点800200 (32)0530(39-32)434求解问题（3

19、）要知道25天之内能否满足各发放点的实际需求，即计算25天的库存和生产 量之和，与发放点的实际需求量进行比较。由题意：8发放地点实际总需求量=d j =5600;j 185发放地点，企业与储备库现储存总量=bj + mi =2840;j 1i 125天企业1,2,3的总产量=nj t =2250;i 1由于2250+2840D(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);p

20、ath=p;%=floyd.m 文件结束 =2. 问题( 1)利用 Floyd 算法给出系数和各点间最优路径的 Matlab 程序%=run01.m 文件开始 =load( lines0.mat ); %“lines0.mat ”为事先录入的 42*42 的权数矩阵，包含每点的 距离 *单位 路费 数据i1=1;j1=1;result=cell(5,8);for i=24,41,34,27,30for j=28,23,35,31,22,36,29,38d,path=floyd(lines0,i,j);%从“ floyd.m ”调用 floyd 算法resulti1,j1=d,path;j1=j

21、1+1;endi1=i1+1;j1=1;end%=run01.m 文件结束 =3. 问题( 1)计算最低成本运输方案的model :!5 发点 8收点运输问题 ;sets :warehouses/wh1.wh5/:capacity; vendors/v1.v8/:demand1,demand2; links(warehouses,vendors):cost,volume; endsetsLingo 命令! 企业 1,2,3 与储备库 1,2 的储存量 ;! 发放地点的最低需求量和最高需求量! 权数矩阵和决策变量 ;! 目标函数 ;min = sum(links:cost*volume);! 需

22、求约束(储存量在最低需求量和最高需求量之间)for (vendors(J):sum(warehouses(I):volume(I,J)=demand1(J);sum(warehouses(I):volume(I,J)=demand2(J););! 产量约束(发放量不超过储存量) ;for (warehouses(I):sum(vendors(J):volume(I,J)=demand1(J);sum(warehouses(I):volume(I,J)=demand2(J););! 产量约束(发放量等于储存量) ;for (warehouses(I):sum(vendors(J):volume(

23、I,J)=capacity(I);! 这里是数据 ;data :capacity=920 660 480 1000 1200;demand1=460 550 280 320 300 260 470 530;demand2=760 850 580 370 900 460 570 730;cost=1848 1500 4080 2304 1560 3444 2568 3720696 1884 3672 1896 2472 3036 1416 33122688 3984 1476 900 4044 1740 1968 11162272 1980 2880 1104 2040 2244 2160 25

24、201464 3420 2100 1524 4008 2676 744 1740;enddataend最佳调运方案：Global optimal solution found.Objective value:5719440.Total solver iterations:17VariableValue Reduced CostCAPACITY( WH1)920.00000.000000CAPACITY( WH2)660.00000.000000CAPACITY( WH3)480.00000.000000CAPACITY( WH4)1000.0000.000000CAPACITY( WH5)12

25、00.0000.00000DEMAND1( V1)460.00000.000000DEMAND1( V2)550.00000.000000DEMAND1( V3)280.00000.000000DEMAND1( V4)320.00000.000000DEMAND1( V5)300.00000.000000DEMAND1( V6)260.00000.000000DEMAND1( V7)470.00000.000000DEMAND1( V8)530.00000.000000DEMAND2( V1)760.00000.000000DEMAND2( V2)850.00000.000000DEMAND2( V3)580.00000.000000DEMAND2( V4)370.00000.000000DEMAND2( V5)900.00000.000000DEMAND2( V6)460.00000.000000DEMAND2( V7)570.00000.000000DEMAND2( V8)730.00000.000000COST( WH1, V1)1848.0000.000000COST( WH1, V2)1500.0000.000000COST( WH1, V3)4080.0000.000000COST( WH1, V4)2304.0000.000000COST( W