防洪物资调运(肖,邹,彭)

《防洪物资调运(肖,邹,彭)》由会员分享，可在线阅读，更多相关《防洪物资调运(肖,邹,彭)（11页珍藏版）》请在金锄头文库上搜索。

1、 1防洪物资调运 肖雄波 邹胡杨 彭旭 指导老师：数模组 （海军航空工程学院，烟台，264001） 摘要： 本文对某地区为提前做好某种防洪抗涝物资的储备工作在同时考虑最短路径和最 小费用的情况下进行了模型研究。 在本题的公路运输图中，考虑到公路级别不同造成的公路运输成本的差异，将相邻 交叉点之间的权重值赋为单位物资运输成本，消除了不同公路的运费差异，将防洪物资 调运问题转化为单一的公路运输模型。再用 Floyd 算法，借助 Matlab 7.3 软件求出各 交叉点之间的最小单位物资运输成本，进行筛选，得到各运输点之间的最小单位物资运 输成本，结果见表 1。问题（2）和问题（3）是在约束条件下求

2、最小运输费用问题，而 问题（1）已经求得了各运输点之间的最小单位物资运输成本，将问题（2）和问题（3） 转化为一个线性规划问题，根据实际情况作出合理假设，对模型进行简化，借助 Lingo 9.0 软件编写程序进而求出结果。得出问题（2）结果为，最小运输费用：214512 元； 调运方案：企业 1 向储备库 1 调运 600，路线为 242625154241；企业 2 向储 备库 1 调运 360，路线为 4164027；企业 3 向储备库 2 调运 610，路线为 3432 3930；仓库 4 向储备库 1 调运 40，路线为 31927；仓库 7 向储备库 2 调运 90， 路线为 2930

3、；调运后各运输点的库存见表 2。但是随着时间天数的增加，仓库的库存 量却没有多大变化，甚至与预测值相差很大，这样改进约束条件在满足预测值的情况求 最小费用，建立线性规划模型借助 Lingo 9.0 软件编写程序进而求出结果，结果为：最 小调用费用： 317076元； 调运方案为： 企业1向仓库2调运330， 路线为24-26-19-18-23 ； 企业 1 向储备库 1 调运 1000，路线为 242627；企业 2 向仓库 1 调运 300，路线为 41-42-28；企业 2 向仓库 7 调运 110，路线为 41-42-28-29；企业 3 向仓库 4 调运 120， 路线为 34-32-

4、31；企业 2 向仓库 6 调运 20，路线为企业 2 向仓库 8 调运 100，路线为 34-32-38；企业 3 向储备库 2 调运 700，路线为 34323930。调运后各运输点的库 存见表 3。 对问题（4） ，中断线路即为该线路运费无穷，修正问题（1）的最小运费矩 阵，利用问题（2）的线性规划模型找到最佳运输方案，求出了在中断路段情况下问题 （3）的解。最小费用为 293204 元，调运方案为：企业 1 向储备库 1 调运 460，路线为 24201327；企业 2 向储备库 1 调运 360，路线为 4164027；企业 3 向储备 库 2 调运 500，路线为 34322930

5、；仓库 1 向储备库 1 调运 100，路线为 2842 4164027；仓库 4 向储备库 2 调运 110，路线为 31323930；仓库 6 向储备 库 1 调运 80，路线为 3632927；仓库 2 向储备库 2 调运 90，路线为 2930。 本文对网络优化中最短路问题和公路运输问题的常用方法的应用进行了扩展， 解决 了道路差异的问题，提高了模型的可行性和普遍性，并对本文的模型作出评价和改进意 见。 关键字：公路运输模型；Floyd 算法；线性规划。 21 问题的重述 在我国，各种自然灾害频频发生，特别是每年在长江、淮河、嫩江等流域经常爆发 不同程度的洪涝灾害，给国家和人民财产带来

6、重大损失，防洪抗涝成为各级政府的一项 重要工作，而防洪物资的调运成为做好防洪抗涝工作的关键环节。某地区为了提前做好 防洪抗涝工作，根据气象预报及历史经验，决定提前做好某种防洪抗涝物资的储备。 该地区生产该物资的企业、大小物资仓库、国家级储备库的库存、需求和分布情况 （附件 1，附件 2）已知，该物资的运输成本已知，假设各企业、物资仓库及国家级储 备库之间的物资可以通过公路运输互相调运 。根据以上信息，我们研究如下问题： （1）根据附件 2 提供的信息建立该地区公路交通网的数学模型； （2）设计该物资合理的调运方案，包括调运量及调运线路，在重点保证国家储备 库的情况下，为给该地区有关部门做出科学

7、决策提供依据； （3）根据所设计的调运方案，求 20 天后各库的库存量是多少； （4）如果汛期下列路段（附件 3）因洪水交通中断，能否用问题二的模型解决紧急 调运的问题，如果不能，修改模型。 2 模型假设 （1）假设只考虑该物资的调运情况，不考虑其它物资的调用情况，并且假设其它物 资的调用情况对该物资的调用没有影响。 （2）假设只考虑调运过程中的运输费用，不考虑该物资的库存费用、装卸费用等其 它费用。 （3）假设运输成本只与公路级别有关，与运输量、运输次数、运输日期等无关，并 且运输成本价格保持不变。 （4）假设将企业、仓库、国家储备库看成一个个运输点，该物资的调运即在这些点 之间的调运。 （

8、5）假设所运输的物资在当天到达，即统计物资数量时路途中没有物资。 （6）假设题目中所给的信息都准确无误。 3 符号说明 iS :企业 1，企业 2，仓库 1，仓库 8，储备库 1，储备库 2，13, 2 , 1L=i ; is:iS的现有库存； jy：jS的预测库存，13, 5 , 4L=j； jl：jS的最低库存； im：iS的最大库存； kc：企业 1，2，3 每天的产量，3 , 2 , 1=k； pqt：pS向qS运输该物资的件数，13, 2 , 1,L=qp； 3pqf：pS向qS运输单位物资的最小费用； pqt：pS向qS运输该物资的数量； n：企业生产的时间天数。 4 问题的分析

9、问题（1）要求根据根据附件 2 建立该地区公路运输网的数学模型。根据假设，把 企业、 仓库以及储备库看成一个个运输点， 该物资的调运就转化为在这些点之间的调运。 由附件 2 可以知道，这些运输点处在公路与公路的交叉点上，于是可以根据公路各交叉 点之间的邻接关系建立公路交通网的运输模型，将问题（1）转化为求点与点之间的最 短路径问题。考虑到高等公路与普通公路运输成本的差异，将点与点之间的权值变成单 位物资在该短路径上的运输成本。最后根据 Floyd 算法，运用 Matlab 7.3 软件求出各 交叉点之间运输成本最小的路径，提取出运输点之间的最短路径。 问题（2）要求在重点保证国家级储备库的情况

10、下，设计出合理的调运方案。根据 问题（1）的结果，已经求出了各运输点之间的最优路径，问题（2）就变成了在最优路 径下求出满足题目中约束条件的合理的调运方案。 运输费用等于运输量与运输成本的乘 积，所以问题就变为求合理的运输量，使运输费用最小。这样，问题（2）就转化为一 个线性规划问题，目标函数为运输量与运输点之间运输成本的乘积，线性约束条件为最 大库存、最小库存以及优先级别，优先级别即满足库存量大于预测值。 问题（3）要求依据问题（2）的模型，求出 20 天后各库的库存量。我们可以将时 间代入问题（2）中的模型，运用 Lingo 9.0 软件即可求出解答。但是随着时间天数的 增加，企业的库存量

11、增加而仓库的库存量却变化不大，与预测值相比较相差较大，于是 考虑在满足预测值的条件下建立求最小调运费用的规划模型求解。 问题（4）在给出中断路段的情况下，要求改进问题（2）的模型，解决紧急调运的 问题。结合附件 2 知道，公路交叉点 14 与 23、11 与 25、26 与 27、9 与 31 之间的路段 中断，于是将中断路段的邻接值变为无穷大，改变约束条件，建立类似模型。 下面我们建立求解问题的模型。首先，将附件 2 所反映的信息转化为反映公路之间 各交叉点关系的信息，建立各点之间单位物资运输费用最小模型；其次，依据要求，建 立整个运输过程运输费用的线性规划模型，将时间值代入，求解；最后，针

12、对变化的条 件，改进模型。 5 模型的建立与求解 5.1 单位物资运输费用最小模型及求解 由以上分析， 我们需依据附件 2 提取信息。 我们给各公路的交叉点编号为 1， 2， ，42，假设在各点与点之间运输物资。),(jis表示相邻的i点与j点之间单位物资的运输成本（),(jis等于i与j之间的路程乘以公路运输成本） 。建立如下的图的模型),(0ASVG=，其中，顶点集合42, 2 , 1L=V。对该图的边赋以权值ijw为邻接该两点之间的单位物资的运输费用。假设图G权的邻接矩阵为0A，42420)(=ijaA 来存放各边4的权值，其中： 42, 2 , 10L=iaii； jiaij,=之间没

13、有边； ijijwa= ijw是ji,之间边的权值，42, 2 , 1,L=ji。 对于问题（1） ，图G为无向图，A是对称矩阵，jiijaa=。 运行 Floyd 算法的基本思想是：递推产生一个矩阵序列4210,AAAAkLL ，其中),(jiAk 表示顶点iV到顶点jV的路径上所经过的顶点序号不大于k的最小权值。 计 算 时),(),(),(min(),(111jkAkiAjiAjiAkkkk+=。k是 迭 代 次 数 ，42, 2 , 1,L=kji。 最后，当42=k时，42A即是各顶点之间的最短通路值。 我们要求出各运输点之间的单位物资运输费用最小值和相应的路径， 可以先求出图 上任

14、意点m与n之间的单位物资运输费用最小值和相应的路径，然后提取出于各运输点 之间的单位物资运输费用最小值和相应的路径。根据所建立的模型，运用 Floyd 算法， 借助 Matlab 7.3 软件，编写程序，即可求得解答。解见表 1。 表 1 各运输点之间最小运输费用表 S1 S2 S3 S4 S5 S6 S7 S8 S9 S10 S11 S12 S13 S1 0 177.6 453.6 184.8 150 541.2483.6156 410.4256.8505.2 241.6 331.2S2 177.6 0 300 69.6 188.4387.6330 247.2303.6141.6351.6

15、157.6 177.6S3 453.6 300 0 268.8 464.4147.690 502 174 196.8111.6 224.4 122.4S4 184.8 69.6 268.8 0 195.6356.4298.8254.4373.272 320.4 227.2 146.4S5 150 188.4 464.4 195.6 0 552 494.4166.8492 267.6516 331.6 342 S6 541.2 387.6 147.6 356.4 552 0 177.6610.8321.6284.4199.2 372 210 S7 483.6 330 90 298.8 494.4

16、177.60 553.2264 226.8141.6 314.4 152.4S8 156 247.2 502 254.4 166.8610.8553.20 446.4326.4574.8 277.6 400.8S9 410.4 303.6 174 373.2 492 321.6264 446.40 362 135.6 224.4 296.4S10 256.8 141.6 196.8 72 267.6284.4226.8326.4362 0 248.4 216 74.4S11 505.2 351.6 111.6 320.4 516 199.2141.6574.8135.6248.40 330 174 S12 241.6 157.6 224.4 227.2 331.6372 314.4277.6224.4216 330 0 220 S13 331.2 177.6 122.4 146.4