文档介绍：防洪物资的调运
摘要: 本文根据防洪抗涝的实际需求,探讨了防洪物资的调用问题。在对相关数据进行分析处理的基础上,首先基于Dijkstra算法,通过建立公路交通网模型,得到以路径最短和运输成本最少为指标的两种交通路线;然后建立基于成本利益的分配调运模型,利用LINGO软件求解得到了物资分配的调运方案;最后就汛期情况提出应急分配调运模型,重新规划处的物资分配得到调运量和调运线路。
关键词: 物资调运;Dijkstra算法;成本利益;LINGO;应急分配
中图分类号: O221 文献标识码: A
1 引言
我国地域辽阔,气候多变,各种自然灾害频频发生,特别是每年在长江、淮河、嫩江等流域经常爆发不同程度的洪涝灾害,给国家和人民财产带来重大损失,防洪抗涝成为各级政府的一项重要工作。某地区为做好今年的防洪抗涝工作,根据气象预报及历史经验,决定提前做好某种防洪抗涝物资的储备。
已知该地区有生产该物资的企业三家,大小物资仓库八个,国家级储备库两个,各库库存及需求情况见附件1,其分布情况见附件2。经核算该物资的运输成本为高等级公路2元/公里•百件,•百件,假设各企业、物资仓库及国家级储备库之间的物资可以通过公路运输互相调运。
2 模型的建立与求解
每年在长江、淮河、嫩江等流域经常爆发不同程度的洪涝灾害,给国家和人民财产带来重大损失,因此提前做好某种防洪抗涝物资的储备成为了防洪抗涝的关键工作。本文针对题目所给出的信息和数据,对某地区防洪物资调运问题进行详细分析。
公路交通网模型
本节主要构建从企业到仓库的公路交通网。对此,我们主要从以路径最短为指标和以运输成本最少为指标这两个方面,来构建公路交通线路。在建立以路径最短为指标的交通网模型时,主要考虑两点之间的所有路径取最短的线路;在建立以运输成本最少为指标的交通网模型时,首先将路径长度转化成运输费用,接着考虑两点之间的所有路径取运输费用最少的线路。
对于题目所给的生产企业,物资仓库及国家储备库分布图,我们应用图论的相关知识,将图中的相关信息抽象成一个带权图。其中,的每一个顶点代表一个交汇点,而交通示意图上分布着42个不同的公路交汇点,故可以把它看成是一个包含42个顶点的带权图,其中是顶点的集合,为边的集合,为边的权值。这样,该分布图就抽象为一个带权图,带权图中的权值可以根据不同的目标进行定义。
基于最短路径的公路交通网模型
针对企业到仓库,需要从企业到仓库的所有路径中找到最短的路径,那么以路程最短的指标来衡量的公路交通网,就要找到从源点到各目标点的最短路径,可用图论中的Dijkstra算法来进行求解,该算法是解决最短路径问题的一个很有效的方法。图中边的权值即为两点之间的路径。
Dijkstra算法原理
(1) 假设是的真子集且,并以记。若是从到的最短路,则显然且的节必然是最短路。所以,
(1)
并且从到的距离由公式
(2)
给出。这个公式便是Dijkstra算法的基础。
(2) 在整个算法中,每个顶点给以标号,它是的一个上界。开始时,而对,则有。在算法进行时,这些标号不断被修改:在第步结束时,
对成立(3)
并且,
对成立(4)
当算法结束时,从到的距离由标号的终值给出。
基于最短路径的公路