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

2013年中央民族大学数学建模作业论文题目：应急运输调度方案设计模型参赛队员：姓名：吴极学院：理学院专业：统计学年级：11级姓名：刘超学院：理学院专业：统计学年级：11级姓名：夏浩学院：理学院专业：统计学年级：11级1应急运输调度方案设计模型摘要本题要求我们求出每个企业和储备库在不同情况下给发放地点运输救灾物资的最优调运方案，我们以每个企业和储备库给每个发放地点的调运量作为决策变量，以公路的长度和运输成本的乘积作为单位运费（价值系数）构造目标函数。所求问题即转化为最优路径问题和线性规划问题。在求解问题（1）（2）（3）（4）之前，我们首先对题目附件2中的图进行预处理。把公路的交点看成顶点，每个点之间的公路看成线段，以公路的长度和运输成本的乘积作为一条线段的权重，做出赋权图。利用MATLAB软件使用Floyd算法计算出每个企业和储备库到每个发放地点的最优路径（最低单位运费和路线）（见表4-3-1），解决最优路径问题，求出了目标函数中的价值系数。求解问题（1）时，把时间因素放在第一位考虑，首先求得最快运输时间t。然后以运输成本最低为目标函数，以调运量小于等于企业和储备库储存量，接收量介于最低需求量与最大需求量之间等作为约束条件，利用Lingo软件求解此线性规划问题的最优解。由此得到物资的最佳调运方案，包括调运量和调运路线（见表4-3-2）。求解问题（2）时，已知时间t，由实际情况可以修改约束条件，令调运量等于储存量，其他约束条件不变。同样，利用Lingo软件可以求出一个最优解（见表4-3-3）。求解问题（3）时，经过计算可知企业的生产能力不能够满足发放地点的实际需求，我们通过企业增产来满足实际需求。此时需要新增三个变量，把问题（1）中的约束条件增加几个约束条件，利用Lingo求解，得到最佳调运方案（见表4-3-4）。求解问题（4）时，主体思路不变。由于道路中断，我们只需要重新利用MATLAB软件求出最优路径和目标函数的价值系数（见表4-3-5），再利用Lingo软件求解线性规划问题即可（见表4-3-6、表4-3-7、表4-3-8）。最后，我们客观地评价了该模型的优缺点，并且做出了相应的改进和推广。关键词：最优路径Floyd算法MATLAB线性规划Lingo2一、问题的提出与分析1.1问题重述在某地区有生产某种救灾物质的企业有三家，设置物资发放点八个，储备仓库两个。在灾害发生时，企业、各物资发放地点、储备仓库的库存情况，及各发放点的最低需求和实际需求情况见附件1。企业、发放点、仓库及道路分布情况见附件2。设该种物资的运输成本为高等级公路20元/公里•百件，普通公路12元/公里•百件。（1）预案要求尽快满足各发放点对救灾物质的最低需求，并尽量使运输成本降低。建立数学模型，给出所需要的时间，物资的调运方案，包括调运量和调运路线。（2）在20天内，按均衡配给的原则，各发放点可以得到多少物资？给出相应的调运方案。（3）能否在25天内满足各发放点的实际需求？怎样才能满足各发放点的实际需求？并给出相应的调运方案。（4）在灾害发生时可能造成交通中断，以中断路段：14-23，11-25，26-27，9-31为例，重新讨论上述三个问题。1.2问题分析1.2.1对问题（1）的分析要尽快满足各发放地点对救灾物资的最低需求，由现有总库存加上企业1,2,3t天的生产量大于等于8个发放点最低需求的不等式，可以解出满足题意的最小时间t为8天。接着在最小时间t=8的情况下，求最小的运输费用，以企业1,2,3及储存库向8个发放点运输的物资为决策变量，建立目标函数.而建立目标函数需要知道决策变量对应的价值系数,我们根据附件2,把公路的交点看成顶点，每个点之间的公路看成线段，从而把地理图转化为联通无向图.又由题目条件高等级公路和普通公路的运输费用不同，我们把每公里每百件的运费和路程的乘积作为每条线段的权数，根据图论知识，将求解价值系数的问题转化为最优路径问题。再根据赋权图制作权数矩阵，然后利用MATLAB使用Floyd算法求出企业1,2,3及储存库到8个发放点的最优路径，由此计算出价值系数，再利用Lingo软件在相关约束下求出目标函数的最优解，从而得到物资的调运方案。1.2.2对问题（2）的分析按照均衡配给的原则，求20天后各发放点收到物资的情况以及最佳运输方3案，同样是线性规划问题，将模型中的t=20，再对约束条件进行修改，使“库存+生产量=发放点接收量”，得出最优答案。1.2.3对问题（3）的分析要知道25天之内能否满足各发放点的实际需求，即计算25天的库存和生产量之和，与发放点的最大需求量进行比较，实际上并没有达到需求，解决办法是让企业增产，使之满足各发放点的最高需求，再用线性规划模型求出最优方案即可。1.2.4对问题（4）的分析我们要知道指定路段中断后，上述建立的数学模型是否可用，也就是说只要检验到模型中所选取的路线是否经过该路段，如果不经过，则中断路线对模型没有影响，若经过，可将路段中断后的图采用第一步的方式重新处理计算，分别求解出最佳运输方案。二、基本假设2.1假设灾难发生时，企业1,2,3只向发放点运送物资，不向储备库运送物资，而储备库则是只出不进的向各个发放点运送物资。2.2假设灾难发生当天企业是生产物资的，即从灾难发生第一天起，每天零点时每个企业的库存量都增加其日生产量。2.3假设道路的运输能力足够大，没有运输限制。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,2j=1,2,3,4,5,6,7,8，都为发放点ijx:从i运到发放点j的物资量ija:从i到j每百件的运费jb:发放地点j的现有库存4jc：发放地点j的最低需求jd：发放地点j的最大需求tm:i的现有库存，i=1,2,3,4,5in：企业i的日生产量，i=1,2,3ie：企业i增产后的日生产量，其中40e，50et:一个调运方案的所需时间Z:一个调运方案的总运费四、模型的建立与求解4.1数据处理将附件2中的公路的交点看成顶点，每个点之间的公路看成线段，形成一个联通无向图。并且以每公里每百件的运费和路程的乘积作为权重，做出如下赋权图：480420600480456504624420816300540720117620407446006247441808402001700760336480640140060096096010008166003608402168009606403609605406967805401500984864336600696552336312576384720744800100072076060011206245601120360储备库2储备库1发放8发放7发放6发放5发放4发放3发放2发放1企业3企业2企业1123363337101238323435393193045402771320242625116222116231819154228412981417图4-1-1赋权图4.2模型建立根据题意，建立目标函数Z表示从企业1,2,3和储备库1,2向8个发放点运送物资的总费用，根据各个发放点的物资需求量写出其约束条件，如下：目标函数：5811minijijijZax5约束条件：s.t.51810,1,2,3,4,5,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,8,1,2,3,4,5ijjijjjiijiijxijcxbdjxmnti4.3模型求解4.3.1求解最优路径，确定ija：利用MATLAB软件由Floyd算法(源程序见附录1、2)求出从发出地点i到发放地点j的每百件运费ija和最优路径，其结果如下表所示：表4-3-1各发出地点与发放地点每百件运费和最优路径表*企业1企业2企业3储备库1储备库2发放点1[1848,24,26,25,15,42,28][696,41,42,28][2688,34,32,39,30,29,28][2272,27,40,6,41,42,28][1464,30,29,28]发放点2[1500,24,26,19,18,23][1884,41,42,15,18,23][3740,34,1,2,7,27,26,19,18,23][1980,27,26,19,18,23][3420,30,29,28,42,15,18,23]发放点3[4080,24,26,27,9,31,32,35][3672,41,6,40,9,31,32,35][1476,34,32,35][2880,27,9,31,32,35][2100,30,39,32,35]发放点4[2304,24,26,27,9,31][1896,41,6,40,9,31][900,34,32,31][1104,27,9,31][1524,30,39,32,31]发放点5[1560,24,20,22][2472,41,42,15,18,19,22][3800,34,1,2,7,27,26,19,22][2040,27,26,19,22][4008,30,29,28,42,15,18,19,22]发放点6[3444,24,26,27,9,2,3,36][3036,41,6,40,9,2,3,36][1740,34,1,33,36][2244,27,9,2,3,36][2964,30,39,32,34,1,33,36]发放点7[2568,24,26,25,15,42,28,29][1416,41,42,28,29][1968,34,32,39,30,29][2160,27,40,6,4,29][744,30,29]发放点8[3720,24,26,27,9,31,32,38][3312,41,6,40,9,31,32,38][1116,34,32,38][2520,27,9,31,32,38][1740,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）由于要使物资尽快到达发放地点，则应该首先生产出满足各发放地点最低需6求的物资量，再进行运输规划。此时有：发放地点最低总需求量=81jjc=3550发放地点，企业与储备库现储存总量=81jjb+51iim=2840则有：tnii3128403550解得：9.7t所以，应该取最优调运时间8t，再将调运时间8t代入4.2的线性规划模型中，如下：目标函数：5811minijijijZax约束条件：s.t.51810,1,2,3,4,5,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,88,1,2,3,4,5ijjijjjiijiijxijcxbdjxmni利用Lingo软件（源程序见附录3）对其求解，得到最优解及调运路线为：表4-3-2各发出地点向发放地点运送量和最优路径表*企业1企业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）表示该路径经过的节点序号（即