泄洪设施修建计划2.doc
《泄洪设施修建计划2.doc》由会员分享，可在线阅读，更多相关《泄洪设施修建计划2.doc（25页珍藏版）》请在冰点文库上搜索。
数学建模第三次论文
队号：
198
题目：
A题
队员：
孙团伟
杨刚
张端正
2010年8月17日
泄洪设施修建计划
摘要
修建泄洪设施时，如何在满足安全泄洪的情况下使总费用最少，是政府部门十分关注的问题。
针对本题提出的如何修建泄洪河道使总费用最省以及维护人员在各村留宿的概率的问题，分别建立了线性规划模型、最小生成树模型、马氏链模型、基于天然河道的最优泄洪基本模型，并运用MATLAB7.0和LINGO8.0数学软件，对模型进行求解，得出修建河道的最省方案和维护人员在各村留宿的概率。
最后还对原来建立的模型进行了评价，并加以推广。
问题一，开挖排洪沟和修建新泄洪河道计划按照以下五步骤进行求解（见图1）：
1、拟合出四条天然河道的泄洪量与时间的关系式；2、根据拟合的关系式，预测未来五年四条天然河道的泄洪量；3、确定开挖排洪沟的费用和预计的可泄洪量以及要达到的泄洪要求；4、建立线性规划模型，进行求解；5、检验第四、第五年是否满足泄洪要求。
计算得到整个方案的总开支最省为172万元。
问题二，在最短路径和泄洪量的要求下，建立了最小生成树模型。
先编写MATLAB程序代码（见附录17）,通过prim算法求出最小生成树，使得泄洪量达到最小。
然后根据最短路径的要求，再进行修改得到最优网络图（见图6）。
通过计算最终得出修建新泄洪河道网络最省总花费资金为593万元。
问题三，维护人员是在问题二中解得的新泄洪河道网络上移动的，从一个村移动到与之相连的一个村，符合马氏链，所以建立了马氏链模型。
通过分析得出，该马氏链是正则链。
根据正则链的性质可知，正则链存在唯一的极限状态概率，所以维护人员在各村留宿的概率分布是稳定的。
联立关系式（见③式），求解出维护人员在各村留宿的稳态概率（见表3）。
问题四，考虑到天然河道有着很大的泄洪潜力，如果能够及时的对天然河道清淤以及在天然河道的基础上建立泄洪河道网络，可以显著地减少泄洪工程的花费，所以建立了基于天然河道的最优泄洪基本模型。
首先找出模型的影响因素：
天然河道的曲折；不同地方土质的不同造成修建泄洪河道的成本不同；有的村可能没有天然河道流过；天然河道还要定期进行清淤；根据地貌，修建人工湖或者水库。
这些因素都会对泄洪方案的花费造成影响。
因此，以这些影响因素建立约束函数，以工程的总花费建立目标函数（见关系式④）。
对这些影响因素进行分别讨论，找出约束函数最小和最大的修建方案，此时目标函数取最小值，则此时的方案是最优的，也是最合理的。
关键词：
线性规划模型最小生成树马氏链最优泄洪基本模型
1问题重述
位于我国南方的某个偏远贫困乡，地处山区，一旦遇到暴雨，经常发生洪涝灾害。
造成大面积水灾，不仅夏粮颗粒无收，而且严重危害到当地群众的生命财产安全。
为此，乡政府打算立即着手解决防汛水利设施建设问题。
从两方面考虑，一是在各村开挖一些排洪沟,以满足近两三年的短期防汛需要；二是从长远考虑，可以通过修建新泄洪河道的办法把洪水引出到主干河流。
经测算，修建新泄洪河道的费用为（万元），其中表示泄洪河道的可泄洪量（万立方米/小时），表示泄洪河道的长度（公里）。
要求通过数学建模方法，解决以下问题：
（1）该乡的某个村区域内原有四条天然河流，由于泥沙沉积，其泄洪能力逐年减弱。
在附录1中给出它们在近年来的可泄洪量（万立方米/小时）粗略统计数字。
水利专家经过勘察，在该村区域内规划了8条可供开挖排洪沟的路线。
由于它们的地质构造、长度不同，因而开挖的费用和预计的可泄洪量也不同（详见附录2），而且预计每条排洪沟的可泄洪量还会以平均每年10%左右的速率减少。
同时开始修建一段20公里长的新泄洪河道。
修建工程从开工到完成需要三年时间，且每年投资修建的费用为万元的整数倍。
要求完成之后，通过新泄洪河道能够达到可泄洪量100万立方米/小时的泄洪能力。
乡政府从2010年开始，连续三年，每年最多可提供60万元用于该村开挖排洪沟和修建新泄洪河道，为了保证该村从2010至2014年这五年间每年分别能至少达到可泄洪量150、160、170、180、190万立方米/小时的泄洪能力，请作出一个从2010年起三年的开挖排洪沟和修建新泄洪河道计划，以使整个方案的总开支出尽量节省（不考虑利息的因素在内）。
（2）该乡共有10个村,分别标记为①—⑩，它们大致的相对地理位置（见附录3），海拔高度总体上呈自西向东逐渐降低的态势。
其中村⑧距离主干河流最近，且海拔高度最低。
乡政府打算拟定一个修建在各村之间互通的新泄洪河道网络计划，将洪水先通过新泄洪河道引入村⑧后，再经村⑧引出到主干河流。
要求完成之后，每个村通过新泄洪河道能够达到可泄洪量100万立方米/小时的泄洪能力。
根据附录4中的数据，为该乡提供一个各村之间修建新泄洪河道网络的合理方案，使得总费用尽量节省。
（说明：
从村A→村B的新泄洪河道，一般要求能够承载村A及上游新泄洪河道的泄洪量。
）
（3）新泄洪河道网络铺设完成后，打算安排一位维护人员，每天可以从一个村到与之直接有新泄洪河道连接的相邻村进行设施维护工作，并在到达的村留宿，次日再随机地选择一个与该村直接有新泄洪河道连接的相邻村进行维护工作。
试分析长此以往，他在各村留宿的概率分布是否稳定？
（4）是否能够为该乡提出一个更加合理的解决泄洪的办法？
2基本假设
1、新泄洪河道在三年完工后，才能用于泄洪；
2、不受人力、物力等因素的影响，修建计划能够在指定的时间内完成；
3、在天然河道的泄洪能力非常小的情况下，认为其泄洪量为零。
3符号说明
：
第i条排洪沟的开挖情况（当=1时，表示该条排洪沟需要开挖；当=0时，表示该条排洪沟不需要开挖）；
：
第i条排洪沟开挖费用；
：
第i条排洪沟当年泄洪量；
：
第j年4条天然河道泄洪总泄洪量；
：
第j年修建新泄洪河道的费用；
：
每年的流动资金60万；
：
维护员从村子到相邻村子的概率（）；
：
在i村留宿的概率（）
4开挖排洪沟和修建新泄洪河道计划
4.1问题分析
整个开挖排洪沟和修建新泄洪河道计划应包括五个环节：
1、拟合出四条天然河道的泄洪量与时间的关系式；2、根据拟合的关系式，预测未来五年四条天然河道的泄洪量；3、确定开挖排洪沟的费用和预计的可泄洪量以及要达到的泄洪要求；4、建立线性规划的数学模型，进行求解；5、检验第四、第五年是否满足泄洪要求。
可用下面的流程图（图1）来表示，其中环节1、2、4、5是本文要做的工作，即应用拟合方法，预测出未来五年四条天然河道的泄洪量，建立数学模型进行求解出最佳方案，对第四、第五年进行检验是否满足泄洪要求。
开始
拟合出四条天然河道的
泄洪量与时间的关系式
根据拟合的关系式，预测未来
五年四条天然河道的泄洪量
已知开挖排洪沟的费用和预计的可泄洪量
已知要达到的泄洪要求
建立线性规划的数学模型，进行求解
检验第四、第五年
是否满足泄洪要求
结束
图1开挖排洪沟和修建新泄洪河道计划的流程图
4.2拟合并预测未来五年四条天然河道的泄洪量
（1）由附录一中表格所给的数据对每条河道进行拟合，得到各条河道泄洪量随时间变化的关系式，然后对各河道未来五年的泄洪量进行预测。
当天然河道的泄洪量很低时，认为其泄洪量为零。
1号天然河道泄洪量随时间的变化近似为直线关系，所以使用MATLAB7.0对天然河道1号进行一次拟合（源程序见附录5）得到：
P=-1.201733.4639
Y=32.262231.060629.858928.657227.455626.253925.052223.850622.6489
拟合的图像为：
图21号天然河道泄洪量随时间变化的拟合图
则拟合的直线方程为：
使用MATLAB7.0对未来五年该天然河道的泄洪量进行预测（源程序见附录6），得到：
y=21.446920.245219.043517.841816.6401
则未来五年1号天然河道的泄洪量分别为：
21.4469万立方米/小时、20.2452万立方米/小时、19.0435万立方米/小时、17.8418万立方米/小时、16.6401万立方米/小时。
（2）2号天然河道泄洪量随时间的变化近似为三次曲线关系，所以使用MATLAB7.0对天然河道2号进行三次拟合（源程序见附录7）得到：
P=-0.03110.7966-7.577128.2357
Y=21.424216.019711.83578.68596.38404.74353.57812.70151.9273
拟合的图像为：
图32号天然河道泄洪量随时间变化的拟合图
则拟合的直线方程为：
使用MATLAB7.0对未来五年该天然河道的泄洪量进行预测（源程序见附录8），得到：
y=1.0247-0.1179-1.7199-3.9679-7.048
从计算结果中可以看出，第二年以后结果为负数，则第二年以后2号天然河道的泄洪量已经变得很小，可以认为其泄洪量为0
则未来五年2号天然河道的泄洪量分别为：
1.0247万立方米/小时、0、0、0、0。
（3）3号天然河道泄洪量随时间的变化近似为一次直线关系，所以使用MATLAB7.0对天然河道2号进行一次拟合（源程序见附录9）得到：
P=-2.085029.9806
Y=27.895625.810623.725621.640619.555617.470615.385613.300611.2156
拟合的图像为：
图43号天然河道泄洪量随时间变化的拟合图
则拟合的直线方程为：
使用MATLAB7.0对未来五年该天然河道的泄洪量进行预测（源程序见附录10），得到：
y=9.13067.04564.96062.87560.7906
则未来五年3号天然河道的泄洪量分别为：
9.1306万立方米/小时、7.0456万立方米/小时、4.9606万立方米/小时、2.8756万立方米/小时、0.7906万立方米/小时。
（4）4号天然河道泄洪量随时间的变化近似为三次曲线关系，所以使用MATLAB7.0对天然河道4号进行三次拟合（源程序见附录11）得到：
P=-0.11362.5333-19.907873.0095
Y=42.418233.018026.639022.599420.217318.811017.698716.1985
拟合的图像为：
图54号天然河道泄洪量随时间变化的拟合图
则拟合的直线方程为：
使用MATLAB7.0对未来五年该天然河道的泄洪量进行预测（源程序见附录12），得到：
y=13.66159.35142.6103-7.2434-20.8913
由计算结果可知：
第四、第五年时，河道的泄洪量已经很小，可以认为其泄洪量为0。
则未来五年4号天然河道的泄洪量分别为：
13.6615万立方米/小时、9.3514万立方米/小时、2.6103万立方米/小时、0、0。
（5）、根据以上的计算结果，可以列出未来五年四条天然河道的泄洪量情况：
表1未来五年四条天然河道的泄洪量（万立方米/小时）预测表
年份
编号
2010
2011
2012
2013
2014
1号
21.4
20.2
19.0
17.8
16.6
2号
1.0
0
0
0
0
3号
9.1
7.0
5.0
2.9
0.8
4号
13.7
9.4
2.6
0
0
所以可以得到未来五年4条天然河道泄洪总泄洪量分别为
表2未来五年4条天然河道泄洪总泄洪量表
年份
总泄洪量
2010
2011
2012
2013
2014
（万立方米/小时）
45.2
36.6
26.6
20.7
17.4
4.3线性规划模型的建立与求解
分析可知，本题研究的是，如何在资金使用最省的情况下，建立泄洪方案，达到每年的泄洪要求。
所以，应先建立线性规划模型，找出目标函数和约束函数，然后根据题目中的数据，进行求解。
再用第四、第五年的数据进行检验该方案是否满足该年的泄洪量。
影响最优泄洪方案的主要因素有两个，一是泄洪要求，一是资金花费。
泄洪的方式有：
天然河道泄洪、挖排洪沟泄洪、新泄洪河道泄洪（三年完工后，方可用于泄洪）。
费用被使用的途径：
挖排洪沟、建新泄洪河道。
则根据泄洪要求和资金花费可以建立约束函数。
而前两年是在修建的排洪沟满足当年的泄洪量要求时，剩下的资金全部用来修建新泄洪河道，只有在第三年时，修建的排洪沟满足当年的泄洪量要求时，剩下的资金部分用于修建新泄洪河道，因为新泄洪河道的泄洪量要求是确定的，所以修建新泄洪河道时，应该先按照最低的泄洪量要求进行修建，然后用第四、第五年的泄洪量要求进行检验。
若是满足，则可以按照最低的泄洪量要求进行修建新泄洪河道；若不满足，则要增加排洪沟或者增大新泄洪河道的泄洪量。
所以建立线性规划模型中，新泄洪河道先按照最低的泄洪量来修建。
修建新泄洪河道的费用为（万元），其中表示泄洪河道的可泄洪量（万立方米/小时），表示泄洪河道的长度（公里）。
新泄洪河道能够达到可泄洪量100万立方米/小时的泄洪能力，长为20公里。
则求解可得,因为要求每年投入到修建新泄洪河道的资金为万元的整数倍，则修建新泄洪河道的钱最少为139万元。
该方案追求的是如何在达到泄洪量的要求下使资金费用最省，则如何选择开挖排洪沟是影响资金使用的关键因素。
首先建立开挖排洪沟资金使用的函数，该函数就是建立的线性规划模型的目标函数；接着分阶段进行计算。
建立第一年的线性规划模型
目标函数：
设每年的开挖排洪沟的费用为z,则
约束条件
泄洪要求：
资金约束：
非约束：
综上可得
第一年线性规划模型的求解：
带入数据，使用LINGO8.0求解（见附录13）可得
即在第一年，只需挖1、3、6、7条排洪沟。
挖排洪沟的花费为20万，即投入到建新泄洪河道的资金为40万。
建立第二年的线性规划模型
第二年线性规划模型的求解：
带入数据，使用LINGO8.0求解（见附录14）可得，，那么在第二年，只需挖第5条排洪沟。
挖排洪沟的花费为6万元，则有54万元被用来挖新泄洪河道。
建立第三年的线性规划模型
第三年线性规划模型的求解：
带入数据，使用LINGO8.0求解（见附录15）可得，，那么在第三年，只需挖第2条排洪沟。
挖排洪沟的花费为7万元，剩余的资金为53万元。
139-（40+54）=45
则第三年被用来修建新泄洪河道的资金为45万。
4.4模型的检验
使用LINGO8.0进行检验（见附录16），结果输出为：
则能满足第四、第五年的泄洪要求，则第四、第五年不用再挖排洪沟。
所以该模型符合泄洪量的要求，该方案能达到最省钱的目的。
资金花费总额为：
139+5+7+5+6+5+5=172万元。
5修建新泄洪河道网络的合理方案
根据修建新泄洪河道的费用为（万元），要使费用P最小，即泄洪量尽量的小，且泄洪河道的长度尽量的短。
根据prim算法得到最小生成树算法，根据图的基本定义，一个有n个点的图，它的最小生成树必定含有n个点，（n-1）条边，运用MATLAB7.0软件编程（源程序见附录17）求得：
result=
134537159
3458792610
5736768810
根据以上的结果，再结合从西向东流和最短路径的方法，可以得到如下图所示的各村之间互通的新泄洪河道网络（图6）
①
②③④
⑤
⑥⑦⑧
⑨
⑩
图6.各村之间互通的新泄洪河道网络
泄洪量按照100万立方米/小时的倍数计算，得到：
则最终得出修建新泄洪河道网络最省总花费资金为593万元。
6在各村留宿的概率
6.1建立马氏链模型
维护人员从一个村到与之直接有新泄洪河道连接的相邻村进行设施维护工作，并在到达的村留宿，次日再随机地选择一个与该村直接有新泄洪河道连接的相邻村进行维护工作，那么维护人员的转移路线就是问题二中建立的新泄洪河道网络。
为求维护人员在各村留宿的概率分布以及是否稳定，所以要建立马氏链模型。
则维护人员留宿的十个村就是建立的马氏链模型的十个状态，用随机变量表示维护人员所处的状态，则可以取10个离散值，记，即状态概率，维护人员处在村的概率。
从到的概率记为，即转移概率，维护人员从村转移到村的概率。
p=
由马氏链的性质可知：
的取值只取决于的取值及转移概率，而与的取值无关。
由状态转移的无后效性和全概率公式可以写出马氏链的基本方程为
①
并且和应满足
则状态概率向量（行向量）和转移概率矩阵
则基本方程
（1）可以表示为
由该递推关系式还可以得到
6.2判断该马氏链是否是正则链
正则链的定义为：
一个有个状态的马氏链如果存在正整数，使从任意状态经次转移，都以大于零的概率到达状态，则这样的马氏链称为正则链。
因为修建的新泄洪河道网络连接着这十个村，当维护人员沿着新泄洪河道网络转移时，每个村都有可能到达。
即假设维护人员在村，一定可以经过正整数次转移到任意村即都以大于零的概率到达状态。
由正则链的定义可以知道，本问题中建立的马氏链模型是正则链。
6.3求解极限状态概率
由定理可知，正则链存在唯一的极限状态频率，使得当时状态概率，与初始状态概率无关。
满足
②
所以，长此以往，维护人员在各村留宿的概率就是极限状态频率，则由正则链的性质可知，维护人员在各村留宿的概率是稳定的。
由②式可得：
③
联立可解得极限状态概率为（MATLAB源程序见附录18）：
x=0.05560.05560.16670.11110.16670.05560.11110.16670.05560.0556
表3即可得维护人员随机在各村留宿的稳态概率
村庄
概率p
村庄
概率p
7提出一个更加合理的解决泄洪的办法
7.1问题的分析
在求解问题一时，该乡的某个村区域内原有四条天然河流，由于泥沙沉积，其泄洪能力逐年减弱。
这四条天然河流在2002年的总泄洪量达到31.3+15.9+25.8+46.2=119.2万立方米/小时，可以看出，天然河道有着很大的泄洪潜力，如果充分利用天然河道的天然优势，则可以大大减少修建新泄洪河道花费的资金。
问题一中，该乡的某个村区域内有四条天然河道，按照这种情况，该乡的十个村之间以及流过各村的河流应该很多，只是由于时间的推移，泥沙的沉积，造成这些天然河道的泄洪能力逐年下降，以至于近几年来，每当夏季连日大雨时，不能及时把大量的雨水排出，造成洪灾。
在这种情况下，可以在拓宽拓深天然河道的基础上，辅助修建一些泄洪河道，连接成河道网络，从而解决该乡的泄洪问题。
即建立基于天然河道的最优泄洪模型。
7.2模型建立
7.2.1模型的影响因素
但是考虑到天然河道有些地段可能会过于曲折，拓宽拓深河道时会损耗大量的人力物力，为此可以修建新的河道绕过这段天然河道；不同地方土质的不同造成修建泄洪河道的成本不同，为此可以拓宽拓深该地区的天然河道，进行泄洪，减少成本；并不一定所有的村都有天然河道流过，对此，不论该地区的修建泄洪河道的成本高低，都要修建泄洪河道；由于泥沙的逐年沉积，天然河道还要定期进行清淤，以维持其泄洪量，所以每年还要投入一部分费用用于清淤。
由于此处是山区，可以利用山区的地貌优势，在低洼的地段，选择在河流交汇处建立人工湖或者水库，这样既能减小成本，又能达到很好的蓄水防洪效果。
根据上面分析可知，影响基于天然河道的最优泄洪基本模型的因素为：
、天然河道的曲折
、不同地方土质的不同造成修建泄洪河道的成本不同
、有的村可能没有天然河道流过
、天然河道还要定期进行清淤
、根据地貌，修建人工湖或者水库
7.2.2建立基于天然河道的最优泄洪基本模型
综合这些主要影响因素，可以建立基于天然河道的最优泄洪模型。
由于这些因素都会关系到最终的修建成本，所以最省的资金花费就是最合理的泄洪方案应该达到的要求。
可以用各因素花费的资金来表示各因素，由于因素会造成拓深拓宽天然河道花费增多，根据情况可能要辅助修建泄洪河道，
中建立人工湖或者水库，可以起到蓄水防洪的效果，减小河流的泄洪工作量，则可以减少拓深拓宽天然河道的花费。
因素造成的花费分别设为
因素节省的费用设为建立表示修建泄洪河道网络的资金花费的目标函数，即
对这些影响因素进行分别讨论，找出最小和最大的修建方案，然后把各因素最节省的修建方案综合起来，此时目标函数取最小值，则此时的方案是最优的，也是最合理的。
综上可得基于天然河道的最优泄洪基本模型函数表达式为
④
7.3模型求解
对于因素，当天然河道过于曲折时，会造成拓深拓宽天然河道的成本增加。
若在此段距离修建新的河道费用小于拓深拓宽天然河道的花费，则可以修建新的河道绕过这段天然河道，那么此时的费用为最小。
对于因素，不同地方土质的不同造成修建新泄洪河道的成本不同，为此可以拓宽拓深该地区的天然河道，进行泄洪，减少成本。
则拓宽拓深天然河道的花费小于修建新泄洪河道的花费时，选择拓宽拓深天然河道的费用是最小的。
对于因素，有的村可
升级会员 