《物资紧急调运问题的优化模型》由会员分享，可在线阅读，更多相关《物资紧急调运问题的优化模型（30页珍藏版）》请在金锄头文库上搜索。
1、物资紧急调运问题的优化模型摘要本文就物资的紧急调运问题，运用图论和线性规划的理论和方法建立数学模 型，针对防洪救灾物资的调运问题设计了合理的调运方案。在问题（1）中，将工作量（运输路程 调运量）作为衡量调运方案的标准。 利用Floyd算法（Matlab程序代码见附录二）得到各重要节点（企业、仓库、国 家级储备库）之间的最短路线（详见表1）。由于要求重点保证国家级储备库的 库存量，我们将调运过程分为两个阶段：（1）企业和现有库存量超过预测需求 量的仓库向国家级储备库调运；（2）企业向现有库存量小于预测需求量的仓库 调运。据此建立线性规划模型，用LINGO进行求解，得到最佳的紧急调运方案。（详见表
2、3、表4）。在问题（2）中，在问题（1）所确定的调运方案的基础上，建立以时间最省 为目标的线性规划模型。利用LING O软件求解得到18辆车的最佳调度方案（见表7）,所用的时间为68.2天。在问题（3）中，因为时间充裕，我们认为各仓库及国家级储备库均要达到 其最大库存量才能应对灾害，为降低运输成本,在建立Floyd算法的邻接矩阵时, 应以运费为权重，找到费用最省的路线后，调运救灾物资时必定沿费用最省的路 径调运，据此建立线性规划模型求出使运输费用最省的调运方案（见表10）。确 定调运量后即可确定使车辆数最小的车辆调度方案（见表11），共需要32辆车。 最终得到最低运输成本为724253元。在问
3、题（4）中，由于16号地区灾情紧急，急需10万件救灾物资。此时应 在保证在5天内完成调运任务的前提下，使所需车辆尽量少。首先在路段一Q, 16Q25 ,2526和32中断的情况下求出各企业、仓库、 国家级储备库向16号地区调运救灾物资的时间最省路径；其次建立以所需车辆 最少为目标，5天内完成调运任务等为约束条件的线性规划模型。通过LINGO求 解得到最少需要60辆车（详见表13）。关键词：救灾物资调运；Floyd算法；线性规划；LINGO1. 问题的重述我国地域辽阔，气候多变，洪水、泥石流等各种自然灾害频频发生，给国 家和人民财产带来重大损失，防洪救灾成为各级政府的一项重要工作。某地区为 做好
4、今年的防洪救灾工作，根据气象预报及历史经验，决定提前做好某种防洪救 灾物资的储备工作。该地区现有3家该物资的生产企业，8个不同规模的物资储存仓库，2个国家 级物资储备库，相关数据如表14（见附录一）所示，其位置分布和道路情况如图2 （见附录一）所示。经测算该物资的运输费用为高等级公路2元/公里百件，普 通公路1.2元/公里百件。各企业、物资仓库及国家级储备库的物资需要时可以 通过公路运输相互调运。请你们研究下列问题：（1）根据未来的需求预测，在保证最低库存量和不超过最大容许库存量的 情况下，还要重点保证国家级储备库的储存量，试设计给出该物资合理的紧急调 运方案，包括调运线路及调运量。（2）如果
5、用于调运这批防洪救灾物资车辆共有18辆，每辆车每次能装载100 件,平均在高等级公路上时速为80公里/小时,在普通公路上时速为50公里/小时。 平均装与卸一车救灾物资各需要1小时，一天按24小时计算。按照问题（1）的调 运方案，如何来调度车辆，大约需要多少天能完成调运任务？（3）若时间容许，希望尽量地减少运输成本，请给出最佳的调运方案，最 少需要多少车辆？大约需要多少天能够完成调运任务？（4）若在调运中，正好遇到灾害使下列路段意外中断：16Q , , Q,和而且16号地区严重受灾，急需向16号地区调运10万件救灾物资，请给出相应的 紧急调运方案。必要时可动用国家级储备库的物资，也可以不考虑库存
6、量的最低 限制。如果要求必须在5天内完成这次调运任务，那么最少需要多少辆车，并 给出车辆的调度方案2. 问题的分析2.1问题（1）的分析该问题要求根据未来预测需求，在保证最低库存量和不超过最大库存量的情 况下，还要重点保证国家级储备库的储存量，设计合理的紧急调运方案，包括调 运线路及调运量。在紧急情况下，应保证调运的路径最短，所需调运的救灾物资 最少。故可先利用Floyd算法求出各节点（企业、仓库、储备库）间的最短线路。 调运时救灾物资沿两个节点间的最短路径调运。根据重点保证国家级储备库的库存量的要求和各仓库现有库存量及预测需 求情况，在调运时分两个阶段进行。第一阶段从企业1、2、3和仓库3、
7、4调运救 灾物资满足国家级储备库的预测需求量，第二阶段从企业1、2、3调运救灾物资 以满足仓库1、2、5、6、7、8的预测需求量，如图1所示：第一阶段第二阶段图1调运时的两个阶段由于现有库存量总和无法满足各个仓库的预测需求量之和，故3个企业还要 再进行生产。由此以min（路程 调运物资数量）为目标函数,库存量为约束条件建 立线性规划模型，利用Ling o软件求出最佳的调运方案。2.2问题（2）的分析该问题要求在问题（1）所确定的紧急调运方案的基础上，确定车辆的调度 方案，给定用于调运救灾物资的车辆为18辆，并给出车辆在高等级公路和普通公 路上的时速分别为80公里/小时、50公里/小时。在紧急调
8、运方案中，应考虑尽量 减少完成调运任务的时间，故应计算出问题（1）紧急调运方案中所用到的调运 线路对应消耗的时间，以完成调运任务的时间最短为目标函数，用于调运任务的 车辆数、各货源地向目的地的调运量等为约束条件建立线性规划模型并用Lingo 进行求解。2.3问题（3）的分析该问题在给出时间充裕的条件下，要求设计最佳的调运方案使运输成本最 低，并确定完成调运任务所需的最少车辆和大概时间，已知救灾物资在高等级公 路和普通公路上的运输费用分别为2元/公里百件、1.2元/公里百件。由于时 间充裕，即可认为灾害在较短的时间内不会发生，因此不再重点保证国家级储备 库的库存量。同时，我们认为每个仓库、国家级
9、储备库要达到其最大库存量才能 应对灾情。对问题的研究分三个步骤进行，首先利用Floyd算法确定三个企业到 仓库和国家储备库运输费用最省的路径；其次以总运输费用最省为目标建立线性 规划模型求解3个企业往仓库和国家级储备库的调运量，得到最佳调运方案；最 后根据已确定的路径和调运量分配车辆，使得所需车辆尽量少。2.4问题（4）的分析该问题要求向受灾的16号地鼻紧急调运尹万件救灾物资，已知因为灾害路段 16 3 3 矽,3 如,如一（26和如一Z意外中断。要求设计使所需 车辆最少的车辆调度方案和调运方案，保证能够在5天内完成调运任务，必要时 可动用国家级储备库的物资，也可以不考虑库存量的最低限制。首先
10、运用Floyd 算法确定由各企业、仓库、国家级储备库分别向16号地区调运救灾物资的时间最 省路径，在此基础上综合考虑上述要求建立线性规划模型求出最佳的车辆调度方 案。3. 问题的假设与符号说明3.1问题的假设1假设在确定车辆的调度方案时每条调运路线上派发的车辆数是不变的；2任意一条调运路线上派发的所有车辆都是同时发车；3除装、卸车所消耗的时间外，车辆一直在调运路线上往返；4. 不考虑行车过程中因加油、故障等原因所浪费的时间；5. 企业每天生产救灾物资的行为是不间断的。3.2符号说明x :第i个货源地到第j个目的地的运货量，单位“百件”（/b :第i个节点（企业、仓库或国家级储备库）的预测需求量
11、，单位“百件”ic :第i个节点（企业、仓库或国家级储备库）的现有库存量，单位“百件”iB :第i个节点（企业、仓库或国家级储备库）的最大库存量，单位“百件”ia :第i个节点（企业、仓库或国家级储备库）的最低库存量，单位“百件”imi :第i个企业救灾物资的日产量，单位“天/百件”d :任意两相邻的节点i、j之间的运费D :第i个货源地到第j个目的地的总运费（/ s :任意两相邻的节点i、j之间的路程（/S :第i个货源地到第j个目的地的总路程ijA :以任意两相邻节点i、j之间的路程为权重建立的邻接矩阵B :以任意两相邻节点i、j之间的运费为权重建立的邻接矩阵C :以任意两相邻节点i、j之
12、间的单程运输时间为权重建立的邻接矩阵 其它符号将在文中另作说明。4 模型的建立与求解4.1问题（1）的模型建立与求解4.1.1求节点（企业、仓库、国家级储备库）间的最短路线根据企业、仓库及国家级储备库的分布图，以任意两相邻节点i、j之间的 路程为权重，建立各节点的邻接矩阵:040infinf - inf40035inf - infinf350inf - infinfinfinf0 - infinfinfinfinf 0这是个对称矩阵，数字代表相邻两节点的距离，inf代表两节点不相邻。利用 Floyd算法，求出部分重要节点（企业、仓库、储备库）间的最短路线如下表:表1各货源地到目的地的最短线路企
13、业1企业2企业3仓库3仓库4仓 库124-26-25-15-9-2841-9-2834-32-39-30-292835-39-30-29-2831-42-40-641-9-28仓 库224-26-25T41-9-15-18-34-32-31-42-27-35-39-5-6-11-31-42-27-118-232311-25-18-2325-18-23-25-18-23仓24-20-2241-9-15-18-34-32-31-42-27-35-39-5-6-11-31-42-27-26192226-19-2225261922-19-2224-26-27-42-2-3-3624-26-25-11-
14、6-4-2924-26-27-42-31-32-3841-6-40-42-2-3-3641-6-4-2941-6-40-42-31-32-3834-1-33-3635-32-34-1-33-3631-42-2-3-334-32-39-30-2935-39-30-2931-42-40-5-4-2934-32-3835-32-3831-32-38储备库1储备库224-26-2724-26-25-11-6-4-3041-6-40-2741-6-4-3034-32-31-42-2335-32-31-42-231-42-2734-32-39-3035-39-3031-32-39-30注：表中阿拉伯数字为分布图中各节点的编号。表2各货源地到目的地的最短线路对应的最短路程企业1企业2企业3仓库3仓库4仓库114258224239216仓库2123157330362255仓库5130206337405262仓库6287253145268199仓库7190118164179168仓库831027693166118储备库110011016724092储备库2220148102117127注：表中数字单位为“公里”4.1.2求货源地的调运量为便于讨论，将企业1、企业2、企业3、仓库1、仓库2 仓库8、储备库1、储备库2分别编号为1,2,312，13
