泄洪设施修建计划

数学建模论文 论文题目 泄洪设施修建计划泄洪设施修建计划 姓名 胡益共 学号 08053328 专业 化工 姓名 尧志邦 学号 08053325 专业 化工 姓名 王威 学号 08053314 专业 化工 2010 年 7 月 31 日 摘要 本文建立了泄洪相关问题的最优化模型 问题一 首先估算出四条天然河道在 2010 到 2012 三年内的泄洪量 得出 剩下每年排洪沟应承担的泄洪量 然后根据约束条件建立 0 1 规划模型 求出 的在 2010 年修建排洪沟 2 3 6 8 2011 年修建排洪沟 5 2012 年修建排洪沟 9 总费用为万元35 Y 问题二 本问题采用prim算法求出图 各村之间的预修建网络图 的最G 小生成树 建立最少总长度河道网络图 计算求得洪河道最少总长度62 最少km 费用为万元 428 5 P 问题三 假设维修人员在各村的留宿概率是稳定的 把问题转换成一个离 散动态随机过程 也就是马氏链 利用转移概率矩阵 计算得到维修人员留宿 每个村的稳定概率 问题四 从短期和长期两方面考虑 解决泄洪问题 关键字 0 1 规划 prim 算法 马氏链 一 问题重述 某个偏远贫困乡 乡政府打算解决防汛水利设施建设问题 从两方面考虑 一是在各村开挖一些排洪沟 以满足近两三年的短期防汛需要 二是从长远考虑 可以通过修建新泄洪河道的办法把洪水引出到主干河流 经测算 修建新泄洪 河道的费用为 LQP 51 0 66 0 万元 其中Q表示泄洪河道的可泄洪量 万立 方米 小时 L表示泄洪河道的长度 公里 请你们通过数学建模方法 解决以下问题 问题 1 该乡的某个村区域内原有四条天然河流 由于泥沙沉积 其泄洪 能力逐年减弱 在表 1 中给出它们在近年来的可泄洪量 万立方米 小时 粗略 统计数字 水利专家经过勘察 在该村区域内规划了 8 条可供开挖排洪沟的路 线 由于它们的地质构造 长度不同 因而开挖的费用和预计的可泄洪量也不 同 详见表 2 而且预计每条排洪沟的可泄洪量还会以平均每年 10 左右的速率 减少 同时开始修建一段 20 公里长的新泄洪河道 修建工程从开工到完成需要 三年时间 且每年投资修建的费用为万元的整数倍 要求完成之后 通过新泄 洪河道能够达到可泄洪量 100 万立方米 小时的泄洪能力 乡政府从 2010 年开始 连续三年 每年最多可提供 60 万元用于该村 开挖排洪沟和修建新泄洪河道 为了保证该村从 2010 至 2014 年这五年间每年 分别能至少达到可泄洪量 150 160 170 180 190 万立方米 小时的泄洪能力 请作出一个从 2010 年起三年的开挖排洪沟和修建新泄洪河道计划 以使整个方 案的总开支尽量节省 不考虑利息的因素在内 表表 1 1 现有四条天然河道在近几年的可泄洪量 万立方米现有四条天然河道在近几年的可泄洪量 万立方米 小时 小时 4 4 号号 46 232 626 723 020 018 917 516 3 表表 2 2 开挖各条排洪沟费用 万元 和预计当年可泄洪量 万立方米开挖各条排洪沟费用 万元 和预计当年可泄洪量 万立方米 小时 小时 编号编号 1 12 23 34 45 56 67 78 8 开挖费用开挖费用 57546553 当年泄洪当年泄洪 量量 2536321531282212 问题 2 该乡共有 10 个村 分别标记为 下图给出了它们大致的相 对地理位置 海拔高度总体上呈自西向东逐渐降低的态势 其中村 距离主干河流最近 且海拔高度最低 乡政府打算拟定一个修建 在各村之间互通的新泄洪河道网络计划 将洪水先通过新泄洪河道引入村 后 再经村 引出到主干河流 要求完成之后 每个村通过新泄洪河道能够达到可 泄洪量 100 万立方米 小时的泄洪能力 表 3 各村之间修建新泄洪河道的距离 单位 公里 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 8 5 9 12 14 12 16 17 22 9 15 17 8 11 18 14 22 7 9 11 7 12 12 17 3 17 10 7 15 18 8 10 6 15 15 9 14 8 16 8 6 11 11 11 10 请你们根据表 3 中的数据 为该乡提供一个各村之间修建新泄洪河道网络 的合理方案 使得总费用尽量节省 说明 从村 A 村 B 的新泄洪河道 一般 要求能够承载村 A 及上游新泄洪河道的泄洪量 问题 3 新泄洪河道网络铺设完成后 打算安排一位维护人员 每天可以 从一个村到与之直接有新泄洪河道连接的相邻村进行设施维护工作 并在到达 的村留宿 次日再随机地选择一个与该村直接有新泄洪河道连接的相邻村进行 维护工作 试分析长此以往 他在各村留宿的概率分布是否稳定 问题 4 你们是否能够为该乡提出一个更加合理的解决泄洪的办法 二 模型的合理假设 1 修建的新泄洪河道在三年内维持可泄洪量 100 万立方米 小时的泄洪能 力 2 每条排洪沟的可泄洪量以平均每年 10 左右的速率减少 3 从村 A 村 B 的新泄洪河道 能够承载村 A 及上游新泄洪河道的泄洪量 4 维修人员在各村的留宿概率是稳定的 5 假设疏通和维护天然河流的费用少于修建河道的费用 km20 三 符号说明 1 2 8 1 2 3 ij 第年第 条排洪沟开挖情况 当时表示该排洪沟开挖 当 ijx ji1 ijx 时表示该排洪沟不开挖 0 ijx 开挖第 条排洪沟的费用 万元 ic i 第年所需要的费用 万元 j y j 开挖第 条排洪沟当年的泄洪量 万立方米 小时 ib i 第年用于修建新泄洪河道的费用 万元 j pj 第年四条天然河道的总泄洪量 万立方米 小时 jm j 泄洪河道的可泄洪量 万立方米 小时 Q 泄洪河道的长度 公里 L 三年用于修建新泄洪河道的总费用 万元 P 从 2010 年起三年的开挖排洪沟和修建新泄洪河道的总开支 万元 Y 各村的代号 i v 8 3 2 1 i 表示维修人员在第 村留宿的概率 iGi 10 3 2 1 i 表示维修人员从第 村转移到邻近第村的迁移概率 jiTij 10 3 2 1 10 3 2 1 ji 三 问题分析 问题一 首先根据四条天然河道在近几年的可泄洪量 运用拟合的方法估算 出四条天然河道从 2010 至 2014 年五年间的可泄洪量 对于剩余的泄洪量在 2010 到 2012 这三年内完全由修建的排洪沟承担 2013 到 2014 年分别由排洪沟 和泄洪道共同承担 从而保证该村从 2010 至 2014 年这五年间每年分别能至少 达到可泄洪量 150 160 170 180 190 万立方米 小时的泄洪能力 在 2010 到 2012 这三年内 至于如何开挖排洪沟 则根据排洪沟应承担的泄 洪量和开挖排洪沟的最少开支原则 建立 0 1 规划模型求得最优解 决定开挖 哪条排洪沟 问题二 要使费用最少 必须使得修建新泄洪河道网络总长度最少 可以绘 出各村之间的河道网络图 用 prim 算法求出图的最小生成树 河道总长度最少 总开支最少 问题三 假设维修人员在各村的留宿概率是稳定的 这样问题是一个离散动 态随机过程 也就是马氏链 利用转移概率矩阵 计算稳定状态下留宿每个村 的概率 问题四 解决泄洪问题 从短期和长期两方面考虑 短期计划中 很大程度 上考虑使用天然河道进行泄洪 无疑是使得开支最少的方案 这样可以结合疏 通天然河道和修建排洪沟和河道的方案解决泄洪问题 四 模型的建立与求解 4 1 问题一 模型的建立与求解 运用拟合的方法估算出四条天然河道从 2010 至 2014 年这五年间的可泄洪量 四条天然河道在近几年的可泄洪量 y 1 2017x 33 464 R2 0 9977 y 2 085x 29 981 R2 0 9999 y 0 0311x3 0 7966x2 7 5771x 28 236 R2 0 9998 y 0 1773x3 3 7333x2 27 044x 86 21 R2 0 9955 60 40 20 0 20 40 60 80 0246810121416 年份 可泄洪量 万立方米 小时 编号 1号 2号 3号 年份年份 编号编号 2010201020112011201220122013201320142014 1 1 号号 21 420 21917 816 6 2 2 号号 1 0 0 0 0 0 0 0 0 0 3 3 号号 9 1 7 0 5 0 2 9 0 8 4 4 号号 11 8 4 5 0 0 0 0 0 0 天然河流泄洪天然河流泄洪 量量 43 4 31 8 24 0 20 7 17 4 由上表得 4 条天然河道 2010 到 2014 年的总泄洪量 jm 目标函数是总开支 它包含三年开挖排洪沟的费用 和三年修建新Y 1 y 2 y 3 y 泄洪河道的总费用 即 PPyyyY 321 其中 8 1 11 i iix cy 8 2 2 1 ii i y c x 8 3 3 1 ii i y c x LQpppP 51 0 321 66 0 目标函数为 min 888 0 51 123 111 0 66 iiiiii iii yL Q c xc xc x 约束条件为 s t 1 2 8 1 2 3ij 1 0 ijijxx 每年乡政府提供的资金限制 8 1 1 1 60 ii i p c x 8 2 2 1 60 ii i p c x 8 3 3 1 60 ii i p c x 每年该村排洪量的限制 8 11 1 150 ii i b xm 88 122 11 0 9160 iiii ii b xb xm 888 1233 111 0 810 9170 iiiiii iii b xb xb xm 每条排洪沟开挖限制 3 1 1 ij j X 根据程序运行结果得出下表 年份 编号 20102011201220132014 1 号 21 420 219 017 816 6 2 号 1 00 00 00 00 0 3 号 9 17 05 02 90 8 4 号 11 84 50 00 00 0 天然河流泄洪量 43 431 824 020 717 4 修建排洪沟 2 3 6 851 4 不修建不修建 修建排洪沟费用 206900 本年修建洪沟泄泄洪量 108314000 原排洪沟泄洪量 0 097 2115 4139 8125 9 修建新河道泄洪量 000100100 实际可泄洪量 151 4160 0179 4260 6243 3 要求可泄洪量 150 0160 0170 0180 0190 0 4 2 问题二 模型的建立与求解 各村之间的预修建网络图 设 置两个集合和 其中用于存放的最小生成树中的顶点 集合存放PQPGQ 的最小生成树中的边 令集合的初值为 假设构造最小生成树时 GP 8 vP 从顶点出发 集合的初值为 从自东向西 依次经过 8 vQ Q 8 v 5 v 10 v 所有 的边中 选取具有最小 4 v 7 v 3 v 9 v 1 v 2 v 6 vPp PVv 权值的边 将顶点 加入集合中 将边加入集合中 如此不断重复 pvvPpvQ 直到时 最小生成树构造完毕 这时集合中包含了最小生成树的所有VP Q 边 运用手工求解得到如下图 计算的泄洪河道最少总长度 62 最少费用为万元km428 5 P 4 3 问题三 模型的建立与求解 假设维修人员在各村的留宿概率是稳定的 则应该有 10 1 jiTjGiG j 维修人员在各村留宿的概率之和为 1 则应该有 10 1 1 i iG 运用 LINGO 软件求解得 村留宿概率 G 1 0 1100000 G 2 0 5500000E 01 G 3 0 1100000 G 4 0 1100000 G 5 0 1100000 G 6 0 5666667E 01 G 7 0 1133333 G 8 0 1666667 G 9 0 1133333 G 10 0 5500000E 01 4 4 问题四 本问题需要从短期与长期两个角度考虑 1 短期计划 1 疏通天然河道 2 开挖排洪沟 3 加固原有水坝与河道 2 长期计划 1 改造 修建截污管道 2 修建蓄水水库 水坝及拦水闸 3 对河道两边进行绿化 防止水土流失堵塞河道 4 乡政府加强环境保护措施 加强全乡绿化 短期计划中疏通天然河流尤为重要 原因如下 预测四条天然河道在 1998 2000 年的可泄洪量 预测四条天然河道在1998 2000年的可泄洪量 y 1 24x 33 55 R2 0 9894 y 2 09x 30 R2 0 9997 y 4 25x 25 1 R2 0 9829 y 9 75x 64 417 R2 0 9506 40 20 0 20 40 60 80 100 120 6 4 20246810 年份 可泄洪量 万立方米 小时 编号 1号 2号 3号 4号 预测结果如下 年份 编号 1998199920002001200220032004 1 号 36 0334 7933 5532 3131 0729 8328 59 2 号 33 629 3525 120 8516 612 358 1 3 号 34 232 130 027 925 823 721 6 4 号 83 974 264 454 744 935 225 4 天然河流泄洪 量 187 727170 397153 067135 737118 407101 07783 747 因为数据较少 所以只预测 1998 到 2000 年三年内天然河道的泄洪量 从 表中可以看出如果天然河道疏通后能够达到 1999 年的状况 其泄洪量完全可以 可泄洪量 150 万立方米 小时的泄洪能力 在短期计划内可以按疏通河道 修建 排洪沟 修建河道从主到次的顺序方案 解决泄洪问题 五 模型评价 1 本问题一中采用 0 1 规划方法运用 MATLAB 软件进行求解 这样使得模 型的计算结果更加准确 2 本问题二构采用的 prim 模型算法较简单 得到了符合要求的结果 3 本问题四中预测 1998 2000 年天然河流泄洪量由于数据较少 缺乏相关 经验 不能确定预测结果与实际情况的差距 4 模型改进 在实际情况可以根据天然河道和排洪沟的位置以及各村之间的地质条件 建立模型 拟定一个修建在各村之间由新泄洪河道和排洪沟 天然河道互通的 网络计划 解决泄洪问题 参考文献 1 赵静 但琦等编著 数学建模与数学实验 高等教育出版社 2000 1 17 2 赫孝良 戴永红等编著 数学建模竞赛 赛题简析与论文点评 西安 西安 交通大学出版社 2002 6 附录 AMatlab 程序 问题一 2010年修建排洪沟 f 5 7 5 4 6 5 5 3 A 5 7 5 4 6 5 5 3 25 36 32 15 31 28 22 12 b 60 103 9 x f bintprog f A b 2011年修建排洪沟 f 5 0 0 4 6 0 5 0 A 5 0 0 4 6 0 5 0 25 0 0 15 31 0 22 0 b 60 31 x f bintprog f A b 2012年修建排洪沟 f 5 0 0 4 0 0 5 0 A 5 0 0 4 0 0 5 0 25 0 0 15 0 0 22 0 b 60 30 62 x f bintprog f A