陈根雷,龚佳丽,乐美桃,泄洪设施修建计划论文.doc

泄洪设施修建计划 位于我国南方的某个偏远贫困乡，地处山区，一旦遇到暴雨，经常发生洪涝灾害。以往下雨时，完全是依靠天然河流进行泄洪。2010年入夏以来，由于史无前例的连日大雨侵袭，加上这些天然河流泄洪不畅，造成大面积水灾，不仅夏粮颗粒无收，而且严重危害到当地群众的生命财产安全。 为此，乡政府打算立即着手解决防汛水利设施建设问题。从两方面考虑，一是在各村开挖一些排洪沟,以满足近两三年的短期防汛需要；二是从长远考虑，可以通过修建新泄洪河道的办法把洪水引出到主干河流。经测算，修建新泄洪河道的费用为（万元），其中表示泄洪河道的可泄洪量（万立方米/小时），表示泄洪河道的长度（公里）。 请你们通过数学建模方法，解决以下问题：问题1：该乡的某个村区域内原有四条天然河流，由于泥沙沉积，其泄洪能力逐年减弱。在表1中给出它们在近年来的可泄洪量（万立方米/小时）粗略统计数字。水利专家经过勘察，在该村区域内规划了8条可供开挖排洪沟的路线。由于它们的地质构造、长度不同，因而开挖的费用和预计的可泄洪量也不同，详见表2，而且预计每条排洪沟的可泄洪量还会以平均每年10%左右的速率减少。同时开始修建一段20公里长的新泄洪河道。修建工程从开工到完成需要三年时间，且每年投资修建的费用为万元的整数倍。要求完成之后，通过新泄洪河道能够达到可泄洪量100万立方米/小时的泄洪能力。 乡政府从2010年开始，连续三年，每年最多可提供60万元用于该村开挖排洪沟和修建新泄洪河道，为了保证该村从2010至2014年这五年间每年分别能至少达到可泄洪量150、160、170、180、190万立方米/小时的泄洪能力，请作出一个从2010年起三年的开挖排洪沟和修建新泄洪河道计划，以使整个方案的总开支尽量节省（不考虑利息的因素在内）。表1 现有四条天然河道在近几年的可泄洪量（万立方米/小时） 年份编号2001200220032004200520062007200820091号32.231.329.728.627.526.125.323.722.72号21.515.911.88.76.54.83.52.62.03号27.925.823.821.619.517.415.513.311.24号46.232.626.723.020.018.917.516.3表2 开挖各条排洪沟费用（万元）和预计当年可泄洪量（万立方米/小时）编号12345678开挖费用57546553当年泄洪量2536321531282212问题2：该乡共有10个村,分别标记为，下图给出了它们大致的相对地理位置，海拔高度总体上呈自西向东逐渐降低的态势。 其中村距离主干河流最近，且海拔高度最低。乡政府打算拟定一个修建在各村之间互通的新泄洪河道网络计划，将洪水先通过新泄洪河道引入村后，再经村引出到主干河流。要求完成之后，每个村通过新泄洪河道能够达到可泄洪量100万立方米/小时的泄洪能力。表3 各村之间修建新泄洪河道的距离（单位：公里）2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 98 5 9 12 14 12 16 17 229 15 17 8 11 18 14 227 9 11 7 12 12 173 17 10 7 15 188 10 6 15 159 14 8 168 6 1111 1110请你们根据表3中的数据，为该乡提供一个各村之间修建新泄洪河道网络的合理方案，使得总费用尽量节省。（说明：从村A村B的新泄洪河道，一般要求能够承载村A及上游新泄洪河道的泄洪量。）问题3：新泄洪河道网络铺设完成后，打算安排一位维护人员，每天可以从一个村到与之直接有新泄洪河道连接的相邻村进行设施维护工作，并在到达的村留宿，次日再随机地选择一个与该村直接有新泄洪河道连接的相邻村进行维护工作。试分析长此以往，他在各村留宿的概率分布是否稳定？问题4：你们是否能够为该乡提出一个更加合理的解决泄洪的办法？泄洪设施修建优化模型摘要对于防汛水利设施建设问题。从两方面考虑，一是在各村开挖一些排洪沟,以满足短期防汛需要；二是从长远考虑，可以通过修建新泄洪河道的办法把洪水引出到主干河流。本文我们建立了在达到指定条件的基础下以资金最省为目标的优化模型，求出花费最少并满足泄洪要求的最佳搭配方案，在使用不超过每年提供的资金最大量的情况下，找出我们的最佳方案从而使得总资金最少。对于模型一：使用matlab根据多项式拟合的方法可求得从2010年至2014年的河道泄洪量，再使用lingo编程分步求解出每年我们需要修建的排洪沟，找出最优解。最终我们计算可得共用资金173.2212万元。对于模型二：我们先通过prim算法求出最小生成树，使得泄洪量达到最小。然后，根据最短路径的相关知识，再进行修改得到最优网络图。根据计算最终可知总花费资金：569.2527万元。对于模型三：根据古典法可求出维护人员在各村的留宿的转移矩阵的概率。然后，根据马氏链的方法可求出维护人员在各村随机留宿的概率。村庄 A B C DE概率0.5555556E-010.5555556E-010.1666667 0.11111110.1666667村庄FGHIJ概率0.5555556E-01 0.11111110.16666670.5555556E-010.5555556E-01 关键词：最短路径，matlab，lingo，优化模型，马氏链1问题重述在进行泄洪设施修建时，解决防汛水利设施建设问题。从两方面考虑，一是在各村开挖一些排洪沟,以满足近两三年的短期防汛需要；二是从长远考虑，以通过修建新泄洪河道的办法把洪水引出到主干河流。在资金、人力和物力各种因素的限制情况下，人们常常想以最小的代价解决防汛、泄洪问题。在该村区域内规划了8条可供开挖排洪沟的路线。而且预计每条排洪沟的可泄洪量还会以平均每年10%左右的速率减少。同时利用三年的时间修建一段20公里长的新泄洪河道。对该模型进行评估后，得到了一些基本的数据。即，修建新泄洪河道的费用为（万元），其中表示泄洪河道的可泄洪量（万立方米/小时），表示泄洪河道的长度（公里）。从2010年开始，连续三年，每年最多可提供60万元用于该村开挖排洪沟和修建新泄洪河道，为了保证该村从2010至2014年这五年间每年分别能至少达到可泄洪量150、160、170、180、190万立方米/小时的泄洪能力，对于挖各条排洪沟费用（万元）和预计当年可泄洪量（万立方米/小时）如下表所示：编号12345678开挖费用57546553当年泄洪量2536321531282212 在第二三问中，我们面对的就是如何在这10个村落之间修建泄洪河道的问题，如何使我们的基金使用量达到最优解。因此我们可以使用最小生成树的方法使得新修建的河道泄洪量尽可能的小，然后我们又运用最短路径的相关知识使得修建河道的总长度尽可能的小。 本题需要我们设计一种排洪沟的开挖和资金的分配方案，使我们使用的资金尽可能的少，而且能保证泄洪工作正常进行。并给出相应的分配数据，以及一般情况的讨论。2问题分析2.1 问题一:这是一个优化问题，要决策的是在资金、人力和物力各种因素的限制情况下，人们常常想知道我们应该怎么分配资金的流向才能使我们的资金使用最小，并且能保证工作的正常进行。一般来说这两个目标是矛盾的，资金使用少，工作就不能达使指定要求达到最佳；反之亦然所以不可能给出这两个目标同时达到最优的所谓最优决策，我们追求的只能是，在保证工作顺利进行的情况下资金使用最少的决策。对于本题决策变量是明确的，我们假设开挖洪沟为事件(当=1时，表示第条排洪沟需要开挖；当=0时，表示第条排洪沟不需要开挖)。由于新建的河道总长和泄洪是固定的，因此我们只需考虑开挖洪沟所需的资金。为了简化问题，我们对开挖洪沟逐年分析。2.2 问题二: 该问题我们即要控制泄洪量在要求范围内尽可能的小，又要使得从村子之间河道的总长尽可能的短，从而使得修建新泄洪道的总费用最低。 因此我们根据各村子的之间距离，使用最小生成树的方法使得新修建的河道泄洪量尽可能的小，然后我们又运用最短路径的相关知识使得修建河道的总长度尽可能的小。2.3 问题三： 当维护人员进入村庄进行维护时，维护人员在各村留宿的转移矩阵的概率由我们修建的新泄洪河道网络唯一确定。所以，根据古典法可求出维护人员在各村的留宿的转移矩阵的概率。然后，根据马氏链的方法可求出维护人员在各村随机留宿的概率。3基本假设1、不受人力、物力等因素的影响，修建计划能够在指定的时间内完成；2、假设当天然河道的泄洪能力非常小的情况下我们可以将其忽略不计；3、假设河道和排洪沟的泄洪能力不会受到突发的自然或人为灾难的影响；4符号系统：第i条排洪沟的开挖情况（当=1时，表示该条排洪沟需要开挖；当=0时，表示该条排洪沟不需要开挖）；:第i条排洪沟开挖费用；:表示第j年修建河道的长度；：第i条排洪沟当年泄洪量；：第j年4条天然河道泄洪总泄洪量:第j年修建新泄洪河道的费用;:泄洪河道的可泄洪量（万立方米/小时）;:第j年泄洪河道的长度（公里）；:每年的流动资金60万；:分别表示1、210村子；：分别表示维护人员在各村留宿的概率。 5 模型建立5.1模型1的建立该优化模型是把在能够达到指定的要求的情况下总费用的使用值来作为该模型最优的衡量，即：在模型的建立过程中，我们必须考虑两个限制条件:一、每年最多可提供60万元用于该村开挖排洪沟和修建新泄洪河道，二、该村从2010至2014年这五年间每年分别能至少达到可泄洪量150、160、170、180、190万立方米/小时的泄洪能力。在达到这两个条件的情况下，我们把总费用=60万结余出来的钱用来修建河道，在三年内完成20公里长的新泄洪河道的修建计划。针对各种情况分析，我们将此问题逐年考虑。第一年：满足该年可泄洪量为150万立方米/小时，利用lingo求解：目标函数：约束条件：第二年：在第一年的求解出所开挖的排洪沟外，每条排洪沟的可泄洪量还会以平均每年10%左右的速率减少，为了满足该年的可泄洪量为160万立方米/小时，利用lingo求解： 目标函数： 约束条件：第三年：在第一年和第二年的结果上，为了满足该年的可泄洪量为170万立方米/小时，利用lingo求解： 目标函数： 约束条件： 第4、 五年：经过前三年，我们新修建的泄洪河道在第四年已经可以使用，通过计算我们可以得到一个结果那就是在不修建排洪沟的情况下，第四年可以达到可泄洪量为180万立方米/小时，第五年可以达到可泄洪量为190万立方米/小时.即，我们在第四年和第五年不需要再修建任何的排洪渠道。5.2模型2的建立 根据prim算法可求的最小生成树如下: 1 3 4 5 3 7 1 5 9 3 4 5 8 7 9 2 6 10 5 7 3 6 7 6 8 8 10然后根据最短路径的知识修改可得如图1。5.3模型3的建立由模型二求出的新泄洪河道网络图，可求出维护人员在各村的转移概率矩阵如下： 0 0.5 0.5 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0.5 0 0 0.5 0 0 0 0 0 0 0 0 0.5 0 0.5 0 0 0 0 0 0 0 0 0.33333333 0 0.33333333333 0 0.333333333 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0.5 0.5 0 0 0 0 0 0.333333333 0 0.33333333 0 0 0.333333333 0 0 0 0 0 0 1 0 0 00 0 0 0 0 0 0 1 0 0。然后用lingo编程求解 ,可得维护人员随机在各村留宿的概率。6 模型求解与结果分析利用Matlab和lingo软件，编程求解三个模型，程序见附录A。6.1模型1的结果分析根据4条天然河道已知的泄洪数据，用描点的方法，得到河道泄洪量变化图形如下： 根据多项式拟合的方法可求得从2010年至2014年的河道泄洪量如下表所示： 年份编号201020112012201320141号21.447220.245619.043917.842216.64062号1.0690500003号9.130567.045564.960562.875560.7905564号9.90000总和42.528.262420.717.4对模型中每年的情况分析结果如下：第一年：利用lingo求解可得，在第一年我们只需修建第2、3、6、8四个排洪沟就可以满足各种约束条件。并且利用公式得到 第一年排洪沟的开发费用为：7+5+5+3=20万 第一年可用于修建新的泄洪河道的费用为：=60-20=40万 第一年可以修建泄洪河道的长度为：=5.7879公里第二年：利用lingo求解可得，在第一年修建了第2、3、6、8四个排洪沟的基础上，我们在第二年需要修建第1、4两个排洪沟可以满足各种约束条件，并且利用公式得到： 第二年排洪沟的开发费用为：5+4=9万 第二年可用于修建新的泄洪河道的费用为：=60-9=51万 第三年可以修建泄洪河道的长度为：=7.3795公里第三年：利用lingo求解可得，在第一年修建了第2、3、6、8四个排洪沟，在第二年修建第1、4两个排洪沟的基础上，可得在第三年只需要开发第5个排洪沟就可以满足各种约束条件，并且利用公式得到： 第三年排洪沟的开发费用为：6万 第三年可用于修建新的泄洪河道的费用为：=53.2212万 第三年可以修建泄洪河道的长度为：=20-7.3795-5.7879=6.8326公里第四年和第五年：新的泄洪河道已经建好，并且已经可以使用，通过验算可得，在第四年和第五年不需要再修建排洪沟就可以满足条件规定了。综上所述可得到：在整个计划的进行过程中我们共使用的资金是：173.2212万元 6.2模型2的结果分析 根据我们分析的可求出如下的新泄洪河道网络图： 图1根据计算最终可知总花费资金：569.2527万元。6.3模型3的结果分析根据计算可得维护人员在各村子留宿的概率如下： Variable Value P( A) 0.5555556E-01 P( B) 0.5555556E-01 P( C) 0.1666667 P( D) 0.1111111 P( E) 0.1666667 P( F) 0.5555556E-01 P( G) 0.1111111 P( H) 0.1666667 P( I) 0.5555556E-01 P( J) 0.5555556E-01P( A)=P( B)=P( F)=P(I)=P(J)=0.5555556E-01，P(C)=P(E)=P(G)= 0.1666667,P(D)=P( G)=0.1111111. 所以维护人员在各村留宿的概率分布较稳定。 7 模型评价本文我们建立了在达到指定条件的基础下以资金最省为目标的优化模型、各村之间泄洪河道最小生成树模型，通过控制排泄量与长度保证费用的最宜，并使用LINGO求解，问题分析求解简捷，所得结果具有一定意义。但是本文就第一个问题是采用逐年考虑挖洪沟的约束条件可能会与三年同时考虑所有限制条件会产生所用总资金上的偏差，在第二问中我们所采用的最小生成树是利用无向，在生成树中出现不合路线，此时，分年考虑所需费用和最小生成树法未必合理。因此，将三年的情况放在一起考虑以及同时考虑流量与长度对修建泄洪河道费用影响是我们的改进方向。参考文献1赫孝良，戴永红等编著，数学建模竞赛：赛题简析与论文点评，西安：西安交通大学出版社，2002.6.2萧树铁主编，面向21世纪课程教材：大学数学数学实验，北京：高等教育出版社，1999.7.3陈叔平，谭永基，一类投资组合问题的建模与分析，数学的实践与认识，（29）7：45-49，1999.附录A模型一的程序代码：第一年：min=5*x1+7*x2+5*x3+4*x4+6*x5+5*x6+5*x7+3*x8;25*x1+36*x2+32*x3+15*x4+31*x5+28*x6+22*x7+12*x8=107.5;5*x1+7*x2+5*x3+4*x4+6*x5+5*x6+5*x7+3*x8=107.5;5*x1+4*x4+6*x5+5*x7=107.5;6*x5+5*x7=60;bin(x5);bin(x7);模型二的程序代码：clc;clear;M=1000;a(1,2)=8; a(1,3)=5;a(1,4)=9;a(1,5)=12;a(1,6)=14;a(1,7)=12;a(1,8)=16;a(1,9)=17;a(1,10)=22;a(2,3)=9; a(2,4)=15;a(2,5)=17;a(2,6)=8;a(2,7)=11;a(2,8)=18;a(2,9)=14;a(2,10)=22;a(3,4)=7;a(3,5)=9;a(3,6)=11;a(3,7)=7;a(3,8)=12;a(3,9)=12;a(3,10)=17;a(4,5)=3; a(4,6)=17;a(4,7)=10;a(4,8)=7;a(4,9)=15;a(4,10)=18;a(5,6)=8;a(5,7)=10;a(5,8)=6;a(5,9)=15;a(5,10)=15;a(6,7)=9;a(6,8)=14;a(6,9)=8;a(6,10)=16;a(7,8)=8;a(7,9)=6;a(7,10)=11;a(8,9)=11;a(8,10)=11;a(9,10)=10