物资紧急调运优化模型
摘要
本文就物资紧急调运问题，在合理的假设下，采用了规划的理论和方法建立数学模型，针对实际问题给出了合理的调度方案。
在问题1中，将工作量（运输路程与运输量的乘积）作为衡量合理调度的标准。利用Floyd算法得到企业、仓库、储备库之间的最短路线。考虑到重点保证国家级储备，分两步建立模型：（1）、建立所有企业和仓库向国家级储备库进行调运的线性规划模型；（2）、建立3个企业向8个仓库进行调运的线性规划模型。最后对以上模型分别用LINGO软件包进行求解，实现最小工作量为295520公里·百件调运方案，具体调运量见表4-3、4-4。
在问题2中，根据问题1已得到的调运方案，建立以时间最少的优化模型，利用LINGO软件求解确定了18辆车的最佳调度方案所用的时间为64天。18辆车调度如下： 仓库1 仓库2 仓库5 仓库6 仓库7 仓库8 储备库1 储备库2 企业1 0 2 1 0 0 0 2 0 企业2 1 1 0 0 1 0 1 2 企业3 0 0 0 1 0 1 0 2 仓库3 0 0 0 0 0 1 0 0 仓库4 0 0 0 0 0 0 2 0 在问题3中，因为时间允许，首先在使得企业，仓库及国家级储备达到最大储备量基础上，建立物资调运运费线性规划模型，得出调运方案；再建立车辆的线性规划模型，利用LINGO软件求解得出最少需要33辆车，调度方案见表4-11 。
16 号地，此时在问题4中，属于紧急调运问题，任务是将物资尽快调运到 16 不再优先考虑费用资金问题。在5天期限内，建立仓库和储备库到 号地的最优调运模型，从而实现车辆调度最少的目标。通过LINGO软件求解得到最少需要58辆车，调度方案如下： 企业1 车辆数 33
仓库2 11 仓库5 11 仓库7 33 关键词 Floyd算法 线性规划 LINGO
1 问题重述
当前我国自然灾害频频发生，因此各项预防工作成为了国家和地方各级部门的一项重要工作。
某地区现有3家物资生产企业，8个不同规模的物资储存仓库，2个国家级物资储备库，他们的相关数据及其位置分布和道路情况分别见附表1和附图1。又已知该物资的运输费用为高等级公路2元/公里·百件，普通公路1.2元/公里·百件。各企业、物资仓库及国家级储备库的物资需要时可以通过公路运输相互调运。在此基础上研究以下问题：
（1）根据未来的需求预测，在保证最低库存量和不超过最大容许库存量的情况下，还要重点保证国家级储备库的储存量，试设计给出该物资合理的紧急调运方案，包括调运线路及调运量。
（2）如果用于调运这批防洪救灾物资车辆共有18辆，每辆车每次能装载100件，平均在高等级公路上时速为80公里/小时，在普通公路上时速为50公里/小时。平均装与卸一车物资各需要1小时，一天按24小时计算。按照问题（1）的调运方案，如何来调度车辆，大约需要多少天能完成调运任务？
（3）若时间容许，希望尽量地减少运输成本，请给出最佳的调运方案，最少需要多少车辆？大约需要多少天能够完成调运任务？
（4）若在调运中，正好遇到灾害使下列路段意外中断： 16 — 21 16 — 23 ，11 25 ，25 26 ， -- 32 34 ， ， — — 而且○16号地区严重受灾，急需向○16号地区调运10万件救灾物资，请给出相应的紧急调运方案。必要时可动用国家级储备库的物资，也可以不考虑库量的最低限制。如果要求必须在5天内完成这次调运任务，那么最少需要多少辆车，并给出车辆的调度方案。
2 问题分析
对于问题一，要求利用三家生产企业与8个不同规模的物资储存仓库，2个国家级物资储备库之间物资调运关系，在保证最低库存量和不超过最大容许库存量，还要重点保证国家级储备库的储存量的情况下，设计出该物资合理的紧急调运方案。
考虑到目前正在进行提前储备工作，我们用调运过程的总工作量（运输路程*运输量）大小来衡量调运方案的合理性。先做准备工作：通过图论中Floyd算法列出所有企业、仓库、储备库之间的最短路线图。
再由题目所要求重点保证国家级储备，因此首先考虑国家级储备，将3个企 业和8个仓库中多余预测需求量的物资用来支援国家级储备，如下图
企业1—企业3 仓库1—仓库8 调运 国家级储备1—国家级储备2 让国家级储备库首先达到预测值，并对此建立线性规划模型；再对其余8个仓库进行储备，物资主要来源于3个企业，如下图
企业1 企业2 企业3 调运 仓库1—仓库8
在此基础上建立线性规划模型，得到最小工作量的调运方案以及调运路线和调运量。
对于问题二，根据问题1的调运方案，以达到时间最省的目标来调度现有车辆。在满足约束条件的情况下，建立关于时间最短的线性规划模型，求得到最佳的调度方案。
对于问题三，根据最少运费确定企业与仓库之间的最小运费路径，再以费用最少为目标，在满足各仓库的最大贮存量的约束下，建立最少费用的规划模型，得到具体的调运计划，再以车辆最少为目标建立优化模型，得到最优的车辆调度方案。
对于问题四，现要向16 号地区紧急调运物资，考虑到情况紧急，所以必要时
16 号地区调运。16 号可以将企业，仓库，储备库的物资都向 因此先确定各仓库到 16 地区的最短路径，再以最少车辆为目标，满足在5天内向 号地区运送10万件
物资，各仓库的运送量在自身的现有库存量范围内的约束下，建立车辆最少的线性规划模型，求得最佳调运方案。
3 模型假设和符号设定
3.1模型假设
（1）调运过程中不会出现意外情况，例如交通堵塞影响调运时间； （2）问题四中灾情发生时，运输工作还没有进行； （3）物资运输为双向收费，即来回收取相同费用；
（4）车辆除装卸货时花费了2小时，不存在排队等待现象； （5）为了方便分析我们将储存库1、2视为仓库9、10。 3.2符号设定
dij 第i个企业与第j个仓库之间的最短路径 sij 第i个企业与第j个仓库之间的最短路径值
xij 第i个企业运往第j个仓库的调运量
p 企业和仓库的最大储存量
a 企业和仓库的现有储存量 zi 仓库i的预需求量
qi 仓库i的最低库存量
yij 第i个企业派往第j个仓库的车辆数 tij 车辆从第i个企业到第j个仓库所需要的时间
4.模型建立与求解
4. 1问题一的模型建立与求解
根据未来预测需求量的要求，考虑到要重点保证国家级储备库的储存量，将仓库3、4看成企业4、5。这里我们将该过程分为两个阶段，第一阶段指的是生产企业1，2，3和仓库3、4先只向2个国家级物资储备库调运物资，使其达到预测需求量；第二阶段向其余仓库调运物资，使剩下仓库的现有库存量都达到预测需求值。
4.1.1问题一的数据预处理
分析附表1所提供的各库存数据及需求情况可以看出不仅三家生产企业可以向其他物资储存仓库和2个国家级物资储备库运送物资，而且仓库3、4也可以提供。根据附图所提供的各条路径的长度，建立点与点之间的距离矩阵（见附录2），运用Floyd算法，在matlab7.0上编程（程序见附录D?(dij)43?433）计算得到生产企业1、2、3和仓库3、4到其他不同规模的物资储存仓库与2
个国家级物资储备库的最短路径，如下表4-1所示，
表4-1 最短路径 企业编号 仓库编号 路径编号 路径 仓库1 1 24-26-25-15-9-28 仓库2 2 24-26-25-18-23 仓库5 3 24-20-22 仓库6 4 24-26-27-42-2-3-36 仓库7 5 24-26-25-11-6-4-29 仓库8 6 24-26-27-42-31-32-38 储备库1 7 24-26-27 企业1 储备库2 8 24-26-25-11-6-4-30 仓库1 9 1941-9-28 仓库2 10 41-9-15-18-23 企业2 仓库5 11 41-9-15-18-19-22
12 41-6-40-42-2-3-36 13 41-6-4-29 14 41-6-40-42-31-32-38 15 41-6-40-27 16 41-6-4-30 17 34-32-39-30-29-28 18 34-32-31-42-27-11-25-18-23 19 34-32-31-42-27-26-19-22 20 34-1-33-36 21 34-32-39-30-29 22 34-32-38 23 34-32-31-42-27 企业3 24 34-32-39-30 25 35-39-30-29-28 26 35-39-5-6-11-25-18-23 27 35-39-5-6-11-25-26-19-22 28 35-32-34-1-33-36 29 35-39-30-29 30 35-32-38 31 35-32-31-42-27 仓库3 32 35-39-30 33 31-42-40-6-41-9-28 34 31-42-27-11-25-18-23 35 31-42-27-26-19-22 36 31-42-2-3-36 37 31-42-40-5-4-29 38 31-32-38 39 31-42-27 仓库4 40 31-32-39-30 同时我们还得到与上表4-1相对应的三个生产企业1、2、3和仓库3、4到其他不同规模的物资储存仓库与2个国家级物资储备库的最短路径值，如下表4-2所示，
表4-2 最短路径值sij（单位：公里）
仓库1 仓库2 仓库5 仓库6 仓库7 仓库8 储备库1 储存库2 企业1 154 123 130 287 190 310 100 220 企业2 58 157 206 253 118 276 110 148 企业3 224 330 337 145 164 93 167 102 仓库3 239 362 405 268 179 166 240 117 仓库4 216 255 262 199 168 118 92 127
仓库6 仓库7 仓库8 储备库1 储备库2 仓库1 仓库2 仓库5 仓库6 仓库7 仓库8 储备库1 储备库2 仓库1 仓库2 仓库5 仓库6 仓库7 仓库8 储备库1 储备库2 仓库1 仓库2 仓库5 仓库6 仓库7 仓库8 储备库1 储备库2
物资紧急调运优化模型
