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

1 防洪物资调运 肖雄波 邹胡杨 彭旭 指导老师 数模组 海军航空工程学院 烟台 264001 摘要 本文对某地区为提前做好某种防洪抗涝物资的储备工作在同时考虑最短路径和最 小费用的情况下进行了模型研究 在本题的公路运输图中 考虑到公路级别不同造成的公路运输成本的差异 将相邻 交叉点之间的权重值赋为单位物资运输成本 消除了不同公路的运费差异 将防洪物资 调运问题转化为单一的公路运输模型 再用 Floyd 算法 借助 Matlab 7 3 软件求出各 交叉点之间的最小单位物资运输成本 进行筛选 得到各运输点之间的最小单位物资运 输成本 结果见表 1 问题 2 和问题 3 是在约束条件下求最小运输费用问题 而 问题 1 已经求得了各运输点之间的最小单位物资运输成本 将问题 2 和问题 3 转化为一个线性规划问题 根据实际情况作出合理假设 对模型进行简化 借助 Lingo 9 0 软件编写程序进而求出结果 得出问题 2 结果为 最小运输费用 214512 元 调运方案 企业 1 向储备库 1 调运 600 路线为 24 26 25 15 42 41 企业 2 向储 备库 1 调运 360 路线为 41 6 40 27 企业 3 向储备库 2 调运 610 路线为 34 32 39 30 仓库 4 向储备库 1 调运 40 路线为 31 9 27 仓库 7 向储备库 2 调运 90 路线为 29 30 调运后各运输点的库存见表 2 但是随着时间天数的增加 仓库的库存 量却没有多大变化 甚至与预测值相差很大 这样改进约束条件在满足预测值的情况求 最小费用 建立线性规划模型借助 Lingo 9 0 软件编写程序进而求出结果 结果为 最 小调用费用 317076元 调运方案为 企业1向仓库2调运330 路线为24 26 19 18 23 企业 1 向储备库 1 调运 1000 路线为 24 26 27 企业 2 向仓库 1 调运 300 路线为 41 42 28 企业 2 向仓库 7 调运 110 路线为 41 42 28 29 企业 3 向仓库 4 调运 120 路线为 34 32 31 企业 2 向仓库 6 调运 20 路线为企业 2 向仓库 8 调运 100 路线为 34 32 38 企业 3 向储备库 2 调运 700 路线为 34 32 39 30 调运后各运输点的库 存见表 3 对问题 4 中断线路即为该线路运费无穷 修正问题 1 的最小运费矩 阵 利用问题 2 的线性规划模型找到最佳运输方案 求出了在中断路段情况下问题 3 的解 最小费用为 293204 元 调运方案为 企业 1 向储备库 1 调运 460 路线为 24 20 13 27 企业 2 向储备库 1 调运 360 路线为 41 6 40 27 企业 3 向储备 库 2 调运 500 路线为 34 32 29 30 仓库 1 向储备库 1 调运 100 路线为 28 42 41 6 40 27 仓库 4 向储备库 2 调运 110 路线为 31 32 39 30 仓库 6 向储备 库 1 调运 80 路线为 36 3 2 9 27 仓库 2 向储备库 2 调运 90 路线为 29 30 本文对网络优化中最短路问题和公路运输问题的常用方法的应用进行了扩展 解决 了道路差异的问题 提高了模型的可行性和普遍性 并对本文的模型作出评价和改进意 见 关键字 公路运输模型 Floyd 算法 线性规划 2 1 问题的重述 在我国 各种自然灾害频频发生 特别是每年在长江 淮河 嫩江等流域经常爆发 不同程度的洪涝灾害 给国家和人民财产带来重大损失 防洪抗涝成为各级政府的一项 重要工作 而防洪物资的调运成为做好防洪抗涝工作的关键环节 某地区为了提前做好 防洪抗涝工作 根据气象预报及历史经验 决定提前做好某种防洪抗涝物资的储备 该地区生产该物资的企业 大小物资仓库 国家级储备库的库存 需求和分布情况 附件 1 附件 2 已知 该物资的运输成本已知 假设各企业 物资仓库及国家级储 备库之间的物资可以通过公路运输互相调运 根据以上信息 我们研究如下问题 1 根据附件 2 提供的信息建立该地区公路交通网的数学模型 2 设计该物资合理的调运方案 包括调运量及调运线路 在重点保证国家储备 库的情况下 为给该地区有关部门做出科学决策提供依据 3 根据所设计的调运方案 求 20 天后各库的库存量是多少 4 如果汛期下列路段 附件 3 因洪水交通中断 能否用问题二的模型解决紧急 调运的问题 如果不能 修改模型 2 模型假设 1 假设只考虑该物资的调运情况 不考虑其它物资的调用情况 并且假设其它物 资的调用情况对该物资的调用没有影响 2 假设只考虑调运过程中的运输费用 不考虑该物资的库存费用 装卸费用等其 它费用 3 假设运输成本只与公路级别有关 与运输量 运输次数 运输日期等无关 并 且运输成本价格保持不变 4 假设将企业 仓库 国家储备库看成一个个运输点 该物资的调运即在这些点 之间的调运 5 假设所运输的物资在当天到达 即统计物资数量时路途中没有物资 6 假设题目中所给的信息都准确无误 3 符号说明 i S 企业 1 企业 2 仓库 1 仓库 8 储备库 1 储备库 2 13 2 1L i i s i S的现有库存 j y j S的预测库存 13 5 4L j j l j S的最低库存 i m i S的最大库存 k c 企业 1 2 3 每天的产量 3 2 1 k pq t p S向 q S运输该物资的件数 13 2 1 L qp 3 pq f p S向 q S运输单位物资的最小费用 pq t p S向 q S运输该物资的数量 n 企业生产的时间天数 4 问题的分析 问题 1 要求根据根据附件 2 建立该地区公路运输网的数学模型 根据假设 把 企业 仓库以及储备库看成一个个运输点 该物资的调运就转化为在这些点之间的调运 由附件 2 可以知道 这些运输点处在公路与公路的交叉点上 于是可以根据公路各交叉 点之间的邻接关系建立公路交通网的运输模型 将问题 1 转化为求点与点之间的最 短路径问题 考虑到高等公路与普通公路运输成本的差异 将点与点之间的权值变成单 位物资在该短路径上的运输成本 最后根据 Floyd 算法 运用 Matlab 7 3 软件求出各 交叉点之间运输成本最小的路径 提取出运输点之间的最短路径 问题 2 要求在重点保证国家级储备库的情况下 设计出合理的调运方案 根据 问题 1 的结果 已经求出了各运输点之间的最优路径 问题 2 就变成了在最优路 径下求出满足题目中约束条件的合理的调运方案 运输费用等于运输量与运输成本的乘 积 所以问题就变为求合理的运输量 使运输费用最小 这样 问题 2 就转化为一 个线性规划问题 目标函数为运输量与运输点之间运输成本的乘积 线性约束条件为最 大库存 最小库存以及优先级别 优先级别即满足库存量大于预测值 问题 3 要求依据问题 2 的模型 求出 20 天后各库的库存量 我们可以将时 间代入问题 2 中的模型 运用 Lingo 9 0 软件即可求出解答 但是随着时间天数的 增加 企业的库存量增加而仓库的库存量却变化不大 与预测值相比较相差较大 于是 考虑在满足预测值的条件下建立求最小调运费用的规划模型求解 问题 4 在给出中断路段的情况下 要求改进问题 2 的模型 解决紧急调运的 问题 结合附件 2 知道 公路交叉点 14 与 23 11 与 25 26 与 27 9 与 31 之间的路段 中断 于是将中断路段的邻接值变为无穷大 改变约束条件 建立类似模型 下面我们建立求解问题的模型 首先 将附件 2 所反映的信息转化为反映公路之间 各交叉点关系的信息 建立各点之间单位物资运输费用最小模型 其次 依据要求 建 立整个运输过程运输费用的线性规划模型 将时间值代入 求解 最后 针对变化的条 件 改进模型 5 模型的建立与求解 5 1 单位物资运输费用最小模型及求解 由以上分析 我们需依据附件 2 提取信息 我们给各公路的交叉点编号为 1 2 42 假设在各点与点之间运输物资 jis表示相邻的i点与j点之间单位物资的运输成 本 jis等于i与j之间的路程乘以公路运输成本 建立如下的图的模型 0 ASVG 其中 顶点集合 42 2 1L V 对该图的边赋以权值 ij w为邻接该两点 之间的单位物资的运输费用 假设图G权的邻接矩阵为 0 A 42420 ij aA 来存放各边 4 的权值 其中 42 2 10L iaii jiaij 之间没有边 ijij wa ij w是ji 之间边的权值 42 2 1 L ji 对于问题 1 图G为无向图 A是对称矩阵 jiij aa 运行 Floyd 算法的基本思想是 递推产生一个矩阵序列 4210 AAAA k LL 其中 jiAk 表示顶点 i V到顶点 j V的路径上所经过的顶点序号不大于k的最小权值 计 算 时 min 111 jkAkiAjiAjiA kkkk k是 迭 代 次 数 42 2 1 L kji 最后 当42 k时 42 A即是各顶点之间的最短通路值 我们要求出各运输点之间的单位物资运输费用最小值和相应的路径 可以先求出图 上任意点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 2 S2 177 6 0 300 69 6 188 4387 6330 247 2303 6141 6351 6 157 6 177 6 S3 453 6 300 0 268 8 464 4147 690 502 174 196 8111 6 224 4 122 4 S4 184 8 69 6 268 8 0 195 6356 4298 8254 4373 272 320 4 227 2 146 4 S5 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 4177 60 553 2264 226 8141 6 314 4 152 4 S8 156 247 2 502 254 4 166 8610 8553 20 446 4326 4574 8 277 6 400 8 S9 410 4 303 6 174 373 2 492 321 6264 446 40 362 135 6 224 4 296 4 S10 256 8 141 6 196 8 72 267 6284 4226 8326 4362 0 248 4 216 74 4 S11 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 342 210 152 4400 8296 474 4174 220 0 5 2 1 运输费用规划模型 根据分析 问题 2 可归结为一个线性规划问题 i s 13 2 1L i 表示运输点 i S 的现有库存 i m表示 i S的最大库存 pq f 13 2 1 L qp 表示 p S与 q S之间单位物资 5 运输最小费用 pq t表示 p S向 q S运输的物资总量 r l 11 5 4L r 表示 r S的最小库 存 r y表示 r S的预测库存 n为企业生产的时间天数 要求运输费用最小 即目标函数 为 minF 13 1 13 1pq pqpqf t 约束条件为 企业的库存量约束 k q kq p pkk mtts 13 1 13 1 0 3 2 1 k 1 仓库的库存量约束 11 5 4 13 1 13 1 L rmttsl r pq rqprrr 2 国家储备库优先约束和库存量约束 L2 113 12 11 13 1 13 1 timttsy i q iq p piii 3 综上所述 所建立的模型为 min 13 1 13 1pq pqpqf t s t 13 2 1 0 13 12 11 11 5 4 3 2 1 s0 13 1 13 1 13 1 13 1 13 1 13 1 k L L qpt imttsy rmttsl kmtt pq pq iiqpiii pq rrqprrr pq kkqkp 5 2 2 模型的简化及求解 根据实际情况 在紧急情况下 为了最快和最节省费用的情况下调用该物资 就必 须按照最好的方式 尽量减少调运过程中的周转次数 即该物资被转移的次数 针对 本题目我们不难知道 应尽量减少其它运输点向企业运输该物资 尽量减少国家储备库 向其它运输点运输该物资 即 3 2 1 13 2 1 0 qptpqL 13 2 1 13 12 0L qptpq 简化的模型为 min 13 1 13 1pq pqpqf t 6 s t 13 2 1 13 120 3 2 1 13 2 10 13 2 1 0 13 12 11 115 4 3 2 1 0 13 1 13 1 13 1 13 1 L L L L qpt qpt qpt imtsy rmttsl kmts pq pq pq p ipiii pq rrqprrr k q kqk 借助 Lingo 9 0 软件 求出解为 最小运输费用 214512 元 调运方案 企业 1 向储备 库 1 调运 600 路线为 24 26 25 15 42 41 企业 2 向储备库 1 调运 360 路线为 41 6 40 27 企业 3 向储备库 2 调运 610 路线为 34 32 39 30 仓库 4 向储备 库 1 调运 40 路线为 31 9 27 仓库 7 向储备库 2 调运 90 路线为 29 30 5 3 问题 3 的模型及求解 5 3 1 不考虑预测值的最小费用模型及求解 将20 n代入上述模型 运用 Lingo 9 0 软件求得解为 最小调用费用 214512 元 路线 企业 1 向储备库 1 调运 600 路线为 24 26 25 15 42 41 企业 2 向储备库 1 调运 360 路线为 41 6 40 27 企业 3 向储备库 2 调运 610 路线为 34 32 39 30 仓库 4 向储备 1 调运 40 路线为 31 9 27 仓库 7 向储备库 2 调运 90 路线为 29 30 调运后个运输点的库存见下表 表 2 调运后各运输点的库存量 运输点 企 1 企 2企 3 仓 1 仓 2仓 3仓 4仓 5仓 6仓 7仓 8 储 1 储 2 库存量 800 600290 200 270450190800280300500 3000 2500 调运后实际库存量与预测库存量比较 0 500 1000 1500 2000 2500 3000 3500 12345678910111213 地点 库存量 百件 实际库存量 预测库存量 图1 调运后实际库存与预测库存量比较 5 3 2 满足预测值的最小费用模型及求解 上述模型在尽量减少调运费用的情况下建立的模型 但是我们发现 随着企业生产 量的增加 按照运费最小来建立模型 企业的库存量也会增加 而仓库的库存量变化会 7 很少 这样就会与预测值相差很大 于是我们考虑按照满足预测值来建立最小费用模型 来解决 模型为 min 13 1 13 1pq pqpqf t s t 13 2 1 13 120 3 2 1 13 2 10 13 2 1 0 13 12 11 115 4 2 13 2 1 0 13 1 13 1 13 1 13 1 L L L L L qpt qpt qpt imtsy rmttsy nkmtncs pq pq pq p ipiii pq rrqprrr k q kqkk 其中 3 2 1 13 2 1 0 qptpqL 13 2 1 13 12 0L qptpq 将20 n代入上述 模型 借助 Lingo 9 0 软件编制程序 得到结果为 最小调用费用 317076 元 调运方 案为 企业 1 向仓库 2 调运 330 路线为 24 26 19 18 23 企业 1 向储备库 1 调运 1000 路线为 24 26 27 企业 2 向仓库 1 调运 300 路线为 41 42 28 企业 2 向仓库 7 调运 110 路线为 41 42 28 29 企业 3 向仓库 4 调运 120 路线为 34 32 31 企业 2 向仓库 6 调运 20 路线为企业 2 向仓库 8 调运 100 路线为 34 32 38 企业 3 向储备库 2 调运 700 路线为 34 32 39 30 调运后各运输点的库存量见表 3 表 3 调运后各运输点的库存量 运输点 企 1 企 2 企 3 仓 1仓 2仓 3仓 4仓 5仓 6仓 7 仓 8 储 1 储 2 库存量 百件 70 550 20 500600450350800300500 600 30002500 调运后实际与预测库存量比较 0 500 1000 1500 2000 2500 3000 3500 123456789 10 11 12 13 地点 库存量 百件 实际库存量 预测库存量 图2 调运后实际库存与预测库存量比较 5 4 问题 4 的模型及求解 由分析知道 公路交叉点 14 与 23 11 与 25 26 与 27 9 与 31 之间的路段中断 我们将 14 与 23 11 与 25 26 与 27 9 与 31 之间的单位运输费用改为无穷大 即 8 31 9 26 27 27 26 11 25 25 11 14 23 23 14 aaaaaaa 9 31 a 然后 再依据 5 1 的模型 求出在部分路段中断的情况下 各运输点之间 单位物资运输费用最小值以及相关的路径 结果见表 4 最后 根据解决问题 2 的模 型 求出运输的最小费用和最佳调度方案 结果为 最小费用为 293204 元 调运方案 为 企业 1 向储备库 1 调运 460 路线为 24 20 13 27 企业 2 向储备库 1 调运 360 路线为 41 6 40 27 企业 3 向储备库 2 调运 500 路线为 34 32 29 30 仓库 1 向储备库 1 调运 100 路线为 28 42 41 6 40 27 仓库 4 向储备库 2 调运 110 路 线为 31 32 39 30 仓库 6 向储备库 1 调运 80 路线为 36 3 2 9 27 仓库 2 向储备库 2 调运 90 路线为 29 30 调运后各运输点的库存量见表 4 表 4 路段损坏后各地点间最小运输费用表 S1 S2 S3 S4 S5 S6 S7 S8 S9 S10 S11 S12 S13 S1 0 177 6453 6 184 8 150541 2483 6156 410 4256 8505 2 241 6 331 2 S2 177 6 0 300 69 6 188 4387 6330247 2303 6141 6351 6 157 6 177 6 S3 453 6 300 0 268 8 464 4147 690 502 174196 8111 6 224 4 122 4 S4 184 8 69 6268 8 0 195 6356 4298 8254 4373 272 320 4 227 2 146 4 S5 150 188 4464 4 195 6 0 552 494 4166 8492267 6516 331 6 342 S6 541 2 387 6147 6 356 4 5520 177 6610 8321 6284 4199 2 372 210 S7 483 6 330 90 298 8 494 4177 60 553 2264226 8141 6 314 4 152 4 S8 156 247 2502 254 4 166 8610 8553 20 446 4326 4574 8 277 6 400 8 S9 410 4 303 6174 373 2 492321 6264446 45000362 135 6 224 4 296 4 S10 256 8 141 6196 8 72 267 6284 4226 8326 43620 248 4 216 74 4 S11 505 2 351 6111 6 320 4 516199 2141 6574 8135 6248 40 330 174 S12 241 6 157 6224 4 227 2 331 6372 314 4277 6224 4216 330 0 220 S13 331 2 177 6122 4 146 4 342210 152 4400 8296 474 4174 220 0 表 5 调运后各运输点的库存量 运输点 企 1 企2 企3 仓 1仓 2仓 3仓 4仓 5仓 6仓 7 仓 8 储 1 储 2 库存量 百件 140 0 0 100270450120800200300 500 30002500 6 模型的评价及改进方向 在本文对问题 1 的解答中 我们将问题 1 转化为求最短路径的问题 由于公 路运输成本不一样 于是将权重值改为单位物资运输费用 建立了单位运输费用最小模 型 运用 Floyd 算法进行求解 在问题 2 与问题 3 中 将问题转化为一个线性规 划问题 建立规划模型 根据实际情况进行简化进而求得解答 在解决问题 4 时 根据处理问题 1 与问题 2 的方法 针对变化的情况 将模型作出相应调整 进而 求得解决实际问题的方案 对该地区进行该物资的运输具有指导作用 我们根据满足预测值所建立的线性规划模型求得的使调用费用最小的调运方案基 本与预测值相同 说明模型是满足要求具有可行性和适用性的 在改进方面 解决问题 1 时 采用 Floyd 算法 由于时间复杂度达到三次方 9 不适合计算大量数据 所以如果将模型推广 处理大量数据时效率较差 在对于本题中 的实际问题来说 由于数据量小 所以是比较适用的 当数据较大时可考虑基于 Floyd 算法的并行化 由于在假设中我们只考虑该物资的运输问题 忽略了其它物资调用对该 物资调用的影响 忽略了公路运输成本的波动 忽略运输过程对统计结果的影响 这是 一种理想情况 我们可以考虑其它物资的调运对该物资调运的影响 考虑公路运输成本 的波动 考虑运输过程对统计结果的影响等因素对模型进行改进 使模型更适合实际情 况 更具有可行性和普遍性 参考文献 1 韩中庚 数学建模方法及其应用 北京 高等教育出版社 2005 2 徐俊明 图论及其应用 合肥 中国科学技术大学出版社 1997 3 姜启源 数学模型 第二版 北京 高等教育出版社 1993 4 董肇君 系统工程与运筹学 北京 国防工业出版社 2003 附录 公路完整时最小费用流的 Floyd 算法 load data3 txt c zeros 42 邻接矩阵 c data3 c find c 0 inf c c 0 4 for i 1 42 c i i 0 end path zeros 42 n 42 for k 1 n for i 1 n for j 1 n if c i j c i k c k j c i j c i k c k j path i j k end end end end ind 24 41 34 28 23 35 31 22 36 29 38 27 30 fyzhen c ind ind fyzhen2 fyzhen fyzhen2 find fyzhen2 0 10000 dlmwrit