应急运输调度方案设计模型v精编版Word格式文档下载.docx
《应急运输调度方案设计模型v精编版Word格式文档下载.docx》由会员分享，可在线阅读，更多相关《应急运输调度方案设计模型v精编版Word格式文档下载.docx（36页珍藏版）》请在冰点文库上搜索。
最优路径Floyd算法MATLAB线性规划Lingo
一、问题的提出与分析
问题重述
在某地区有生产某种救灾物质的企业有三家，设置物资发放点八个，储备仓库两个。
在灾害发生时，企业、各物资发放地点、储备仓库的库存情况，及各发放点的最低需求和实际需求情况见附件1。
企业、发放点、仓库及道路分布情况见附件2。
设该种物资的运输成本为高等级公路20元/公里?
百件，普通公路12元/公里?
百件。
（1）预案要求尽快满足各发放点对救灾物质的最低需求，并尽量使运输成本降低。
建立数学模型，给出所需要的时间，物资的调运方案，包括调运量和调运路线。
（2）在20天内，按均衡配给的原则，各发放点可以得到多少物资给出相应的调运方案。
（3）能否在25天内满足各发放点的实际需求怎样才能满足各发放点的实际需求并给出相应的调运方案。
（4）在灾害发生时可能造成交通中断，以中断路段：
14-23，11-25，26-27，9-31为例，重新讨论上述三个问题。
问题分析
对问题
（1）的分析
要尽快满足各发放地点对救灾物资的最低需求，由现有总库存加上企业1,2,3t天的生产量大于等于8个发放点最低需求的不等式，可以解出满足题意的最小时间t为8天。
接着在最小时间t=8的情况下，求最小的运输费用，以企业1,2,3及储存库向8个发放点运输的物资为决策变量，建立目标函数.而建立目标函数需要知道决策变量对应的价值系数,我们根据附件2,把公路的交点看成顶点，每个点之间的公路看成线段，从而把地理图转化为联通无向图.又由题目条件高等级公路和普通公路的运输费用不同，我们把每公里每百件的运费和路程的乘积作为每条线段的权数，根据图论知识，将求解价值系数的问题转化为最优路径问题。
再根据赋权图制作权数矩阵，然后利用MATLAB使用Floyd算法求出企业1,2,3及储存库到8个发放点的最优路径，由此计算出价值系数，再利用Lingo软件在相关约束下求出目标函数的最优解，从而得到物资的调运方案。
对问题
（2）的分析
按照均衡配给的原则，求20天后各发放点收到物资的情况以及最佳运输方案，同样是线性规划问题，将模型中的t=20，再对约束条件进行修改，使“库存+生产量=发放点接收量”，得出最优答案。
对问题（3）的分析
要知道25天之内能否满足各发放点的实际需求，即计算25天的库存和生产量之和，与发放点的最大需求量进行比较，实际上并没有达到需求，解决办法是让企业增产，使之满足各发放点的最高需求，再用线性规划模型求出最优方案即可。
对问题（4）的分析
我们要知道指定路段中断后，上述建立的数学模型是否可用，也就是说只要检验到模型中所选取的路线是否经过该路段，如果不经过，则中断路线对模型没有影响，若经过，可将路段中断后的图采用第一步的方式重新处理计算，分别求解出最佳运输方案。
二、基本假设
假设灾难发生时，企业1,2,3只向发放点运送物资，不向储备库运送物资，而储备库则是只出不进的向各个发放点运送物资。
假设灾难发生当天企业是生产物资的，即从灾难发生第一天起，每天零点时每个企业的库存量都增加其日生产量。
假设道路的运输能力足够大，没有运输限制。
假设调运过程中没有衍生灾害，各个路段道路通畅，无意外发生。
不考虑各点间的时间，假设所有物资瞬时到达。
假设运输时走高等级公路和普通公路除了费用的差别外，在运输结果上没有其他差别。
假设发放点，企业和储存库与公路的交点处是重合的。
三、符号说明
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，都为发放点
:
从i运到发放点j的物资量
从i到j每百件的运费
发放地点j的现有库存
：
发放地点j的最低需求
发放地点j的最大需求
i的现有库存，i=1,2,3,4,5
企业i的日生产量，i=1,2,3
企业i增产后的日生产量，其中
，
t:
一个调运方案的所需时间
Z:
一个调运方案的总运费
四、模型的建立与求解
数据处理
将附件2中的公路的交点看成顶点，每个点之间的公路看成线段，形成一个联通无向图。
并且以每公里每百件的运费和路程的乘积作为权重，做出如下赋权图：
图4-1-1赋权图
模型建立
根据题意，建立目标函数Z表示从企业1,2,3和储备库1,2向8个发放点运送物资的总费用，根据各个发放点的物资需求量写出其约束条件，如下：
目标函数：
约束条件：
.
模型求解
4.3.1求解最优路径，确定
利用MATLAB软件由Floyd算法（源程序见附录1、2）求出从发出地点i到发放地点j的每百件运费
和最优路径，其结果如下表所示：
表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）。
下同。
求解问题
（1）
由于要使物资尽快到达发放地点，则应该首先生产出满足各发放地点最低需求的物资量，再进行运输规划。
此时有：
发放地点最低总需求量=
=3550
发放地点，企业与储备库现储存总量=
+
=2840
则有：
解得：
所以，应该取最优调运时间
，再将调运时间
代入的线性规划模型中，如下：
利用Lingo软件（源程序见附录3）对其求解，得到最优解及调运路线为：
表4-3-2各发出地点向发放地点运送量和最优路径表*
300（42）
160（29）
140（26-19-18）
410（26-19-18）
280（39-32）
320（9）
300（20）
260（9-2-3）
470（直达）
240（32）
290（39-32）
*本表中（）符号表示路径，例如140（26-19-18），括号外140表示该路径的运送量，（26-19-18）表示该路径经过的节点序号（即表4-3-1中对应的最优路径，不包括起点和终点）。
求解问题
（2）
=3550；
发放地点实际总需求量=
=5600；
而当
时，有
；
即当
时，企业和储备库的物资总量肯定能够满足各个发放地点的最低需求，而且不超过各个发放点的最高需求。
从实际情况出发，不可能让物资堆积在企业之中，所以按照均匀配给的原则，将企业1，2,3和储备库1,2以及发放点原来所存的所有物资全部发放，得到新的规划模型如下：
利用Lingo软件（源程序见附录4）解出此时的最优解以及各个发放点所得到的物资和调运方案。
表4-3-320天内各发出地点向发放地点运送量和最优路径表*
660（42）
100（29）
480（26-19-18）
370（26-19-18）
280（32）
370（9）
440（20）
570（直达）
200（32）
530（39-32）
求解问题（3）
要知道25天之内能否满足各发放点的实际需求，即计算25天的库存和生产量之和，与发放点的实际需求量进行比较。
由题意：
=2840；
25天企业1,2,3的总产量=
=2250；
由于2250+2840<
5600，故25天之内无法满足各个发放点的实际需求。
解决方案为让企业增产，使之满足各发放点的实际需求。
现将各企业的增产后的现生产量设为新增变量,重新建立数学模型如下：
由Lingo软件（源程序见附录5）解出最优产量解为企业1的产量为40（百件/天），企业2的产量为30（百件/天），企业1的产量为（百件/天）。
此时得到相应的调运方案如下。
表4-3-425天内各发出地点向发放地点运送量和最优路径表
现产量
40
30
-
求解问题（4）
由于灾害发生导致14-23，11-25，26-27，9-31路段中断，检验到26,9两个路段是上述模型最优解的调运方案，所以再次利用Matlab软件由Floyd算法（源程序见附录6）求出从i到发放地点j的最小单位运费
，其结果如下表所示：
表4-3-5部分路段中断后各发出地点与发放地点每百件运费和最优路径表
[2376,24,26,19,18,15,42,28]
[464434323930292842151823]
[3460,27,40,6,41,42,15,18,23]
[5940242619181542282930393235]
[3876,41,6,4,30,39,32,35]
[4216,27,40,9,2,1,34,32,35]
[5364242619181542282930393231]
[3300,41,6,4,30,39,32,31]
[3640,27,40,9,2,1,34,32,31]
[4536,34,1,2,7,27,13,20,22]
[2776,27,13,20,22]
[4104,24,20,13,12,10,3,36]
[2740,27,40,9,2,3,36]
[3096,24,26,19,18,15,42,28,29]
[54602420131210336333738]
[3516,41,6,4,30,39,32,38]
[3796,27,40,9,2,1,33,37,38]
在此最小单位运费的基础上，其他算法同前三问，使用Lingo软件（源程序见附录7、8、9）得到此时的最优解如下。
对于问题
（1）的最佳调运方案为：
表4-3-6部分路段中断后各发出地点向发放地点运送量和最优路径表
160（40-6-41-42）
440（26-19-18）
110（40-6-41-42-15-18）
80（39-32）
300（13-20）
260（40-9-2-3）
160（40-6-4）
310（直达）
对于问题
（2）的最佳调运方案为：
表4-3-720天内各发出地点向发放地点运送量和最优路径表
100（40-6-41-42）
850（26-19-18）
160（32）
120（39-32）
320（32）
70（20）
420（13-20）
460（40-9-2-3）
20（40-6-4）
550（直达）
对于问题（3）的最佳调运方案为：
表4-3-825天内各发出地点向发放地点运送量和最优路径表
760（42）
800（26-19-18）
50（42-15-18）
580（39-32）
370（32）
360（20）
540（13-20）
680（32）
50（39-32）
五、模型分析
模型评价
5.1.1模型的优点
1、利用图论知识将复杂的交通路线图转化为赋权图，巧妙精确的将实际问题转化为数学模型，是模型求解的关键。
2、利用MATLAB和Lingo软件求解保证了效率和精度。
利用Floyd算法详细计算了企业1,2,3和储备库1,2到8个发放点的最优相对距离，利用Lingo更为细致的解出线性规划模型的最优解。
3、本文的解题思路是根据实际情况以及优化问题的思想来设计调运方案，既有理论依据，又符合现实规律。
5.1.2模型的缺点
1、我们假设了没有其他自然因素的影响，而在实际情况中，由于灾害的发生，道路，车辆等问题都可能发生突发状况，使之无法达到我们所要求的最优解。
2、在本文所设计的最优调运过程中，我们没有考虑高等级公路和普通公路在速度，安全性等方面的优势，只考虑了两者的运费差别。
而两种运输途径必然存在着差异，这种差异也会对我们本文所解出的最优解有所影响。
3、由于此模型中时间最小和运费最少是无法同时达到的，本论文中优先考虑了运费最优模型，而在实际问题中，灾害发生时，最重要的因素应该是时间最小，所以实际问题解决可能与此论文的最优解有差别。
4、在模型的求解过程中，我们只考虑了运费，而没有考虑企业的生产费用以及储存费用等其他费用，单方面的追求运费最少并不一定是实际问题中总花费最少的最优解。
5.1.3模型的改进
1、突出高等级公路与普通公路的区别，将高等级公路和普通公路分别乘以一定的权重，体现出高等级公路在速度和安全性等方面的优越性。
2、实际问题中我们应该考虑到天气，交通等自然因素的影响，并且，在运费最低方案中，还应该结合实际的生产费用，储存费用来求得救灾过程的总花费最低为最优方案。
模型的推广及应用
本模型为物资调运模型，它可以应用到很多领域：
如可以推广到一般商品的发放和运输，但要综合考虑商品的生产费用，运输费用，储存费用等多种因素，以期获得商品最大利润。
参考文献
[1]姜启源、谢金星、叶俊，数学模型（第四版），北京，高等出版社，2011年1月第四版
[2]Frank等着、叶其孝等译，数学建模（原书第四版），北京，机械工业出版社，2009年8月
[3]《运筹学》教材编写组，运筹学，北京，清华大学出版社，2005年6月
[4]郭晶，MATLAB辅助优化计算与设计，北京，电子工业出版社，2003年1月
[5]XiaoyongRen，基于matlab的floyd算法，Xi'
anUniversityofTechnology，，2013年4月
附录
1.计算最优路径的Floyd算法在Matlab中的实现程序
%======="
"
文件开始=========
function[d,path]=floyd（a,sp,ep）
%使用格式：
[d,path]=floyd（a,sp,ep），d为权数矩阵，sp为起点编号，ep为终点编号
n=size（a,1）;
D=a;
path=zeros（n,n）;
fori=1:
n
forj=1:
ifD（i,j）~=inf
path（i,j）=j;
%j是i的后续点
end
end
fork=1:
fori=1:
ifD（i,j）>
D（i,k）+D（k,j）
D（i,j）=D（i,k）
升级会员 