文档介绍：关于防洪物资调运的优化模型
摘要
在充分理解题意的基础上,我们将这个运输问题归结为先求最短路再进行线性规划的问题,并给出运输费用等价转换和运输地位等价转换两个转化法则,,我们采用了Dijkstra和Floyd两种算法,并利用Matlab软件进行计算.
分析我们的线性规划模型,由于变量和约束条件较少,,我们向当地有关部门提出的调运方案为16天达到各库预测库存,总运费为335330元.
在问题二解决的基础上,又对模型作了推广,即在满足预测库存量后,继续调运。那么20天后各库库存量为
库名
仓库1
仓库2
仓库3
仓库4
仓库5
仓库6
仓库7
仓库8
储备库1
储备库2
库存量
500
600
450
350
800
300
500
600
3480
2600
模型的适应度良好,在遇到如问题四的紧急情况时,模型仍然适用,从而大大拓广了模型的适用范围.
在论文中,我们还对所建立的模型的优缺点和需要改进的方向进行了讨论.
一、问题重述(略)
二、基本符号说明与基本假设
基本符号说明
:提供物资的点
:需要物资的点
:从运往的运量()
:可以提供的物资量
:处接收的物资量
:单位距离单位百件数的运价
:和之间的最短路()
:总运费
基本假设
假定天气情况对公路运输的影响不大,可以忽略不计;
从分布图上可以看出最远的两个运输点之间的距离也不过是几百公里,按照现在的交通运输水平,我们可以绝对保证物资在一天内运到,这样库存就不再受到最大容量的约束;
假定无论运多少物资,我们都有足够的车辆保证运输量;
假定提前储备的时间充分,无需在短时间内完成;
假设各库达到预测库存后,企业就不再生产.
三、问题分析和基本思路
问题分析和建模思路
考虑问题的题设和要求,我们要解决的是防洪物资调运优化配置问题.
对题目仔细地分析后,,难点是图中有两种不同的公路,,根据运输费用等价转换法则,将高等级公路转化为普通公路,这样模型得到了统一.
、仓库及储备库之间的最短路,,我们根据运输地位等价转化法则,将现有库存量多余的仓库转化为企业,,我们分别从时间和费用两方面考虑,给出优化方案,并进行了比较.
由于数据量较大,我们借助计算机对模型进行最优求解.
思路流程图
下面的思路流程图是我们文章结构的一个缩影,它完整而形象地反映了我们文章的建模思路.
图1:建模思路流程图
运输费用等价转换法则
公路交通网数学模型
最短路问题
Dijkstra算法
Floyd算法
线性规划模型
最终调运方案
Lingo软件
运输地位等价转换法则
模型优缺点评价
四、模型的准备
运输费用等价转换法则:对于高等级公路线上的任意两点、之间的长度
,根据高等级公路单位运费(2元/公里•百件)求得对应的总运费为;设与等费用的普通公路的长度为,又根据普通公路单位运费(•百件),我们得到如下等式: .
从而有.
由此,我们把两种公路的交通网化归为普通公路交通网,使模型得到了统一.
运输地位等价转换法则:按照我们的调运方案,仓库3和仓库5的地位和企业其实是一样的,我们可以把它们看成是一种特殊的企业(产量为0),,我们就把运输问题化为有5个提供物资的点,8个接收物资的点.
五、模型的建立与求解
问题一:建立该地区公路交通网的数学模型
我们把离散的各交汇点以邻接矩阵的模式在计算机中存储(主程序见附件2),其中0表示两节点无边直接相连,非0表示有边直接相连,,且其仅作为解决后续问题的一个铺垫,在此我们不再给出具体的表示,仅将统一后的交通网络图附上(说明见图注).
生产企业、物资仓库及国家级储备库分布图
问题二
考虑问题的题设和要求,为了给调运方案做个铺垫,我们首先要解决的是最短调运路线问题,,,我们很容易得到一张赋权图,因此,我们可以直接利用以下两种算法求解最短路问题.
方法一:Dijk