泄洪设施修建计划组队：第十组组员：曹智敏胡思文宋佩泄洪设施修建计划摘要本文是利用数学建模的方法解决泄洪设施修建计划的问题，从而减轻经常发生的洪涝所带来的灾害。
要使得开挖排洪沟的费用最节省，先拟合出四条天然河道未来五年的可泄洪量，然后从每年要求的泄洪量出发，构造以总费用尽量少为目标的优化模型，利用lingo软件计算出花费了171万元，比预期投入资金节省了9万元，而且每年都达到了可泄洪量。
通过修建各村之间新泄洪道的办法，考虑求出这10个村的最短距离，Dijkstra算法，编写MATLAB软件程序，可得出最短距离，有三种情况，但要满足每个村通过新泄洪河道能够达到可泄洪量，只有情况一是最佳方案，图形为求出的总费用为578.43万元。
由第二问中可知路线为情况一，利用马尔代夫链算法，将维护人员去每个村的概率列成为转移矩阵，用MATLAB软件便可以求出，当时间为无穷大时，维护人员在村①到村⑩的留宿概率分别为：1/18，1/18，1/6，1/9，1/6，1/18，1/9，1/6，1/18，1/18。
所以他在各村的留宿概率分布是稳定的。
提出更加合理的解决泄洪的办法，可考虑对四天天然河流中的泥沙进行处理，前三年中，不仅要开挖各条排洪沟和修建新泄洪道，而且还要用经费来处理泥沙沉积，利用lingo软件求出，比实际计划节省了23.5万元。
关键词：拟合泄洪量优化模型 Dijkstra算法马尔代夫链算法一、问题的重述位于我国南方的某个偏远贫困乡，地处山区，一旦遇到暴雨，经常发生洪涝灾害。
以往下雨时，完全是依靠天然河流进行泄洪。
2010年入夏以来，由于史无前例的连日大雨侵袭，加上这些天然河流泄洪不畅，造成大面积水灾，不仅夏粮颗粒无收，而且严重危害到当地群众的生命财产安全。
为此，乡政府打算立即着手解决防汛水利设施建设问题。
从两方面考虑，一是在各村开挖一些排洪沟,以满足近两三年的短期防汛需要；二是从长远考虑，可以通过修建新泄洪河道的办法把洪水引出到主干河流。
经测算，修建新泄洪河道的费用为L.0（万元），其中Q表示泄洪河道的可泄洪量（万立方米/ 66P51.0Q小时），L表示泄洪河道的长度（公里）。
请你们通过数学建模方法，解决以下问题：问题1：该乡的某个村区域内原有四条天然河流，由于泥沙沉积，其泄洪能力逐年减弱。
在表1中给出它们在近年来的可泄洪量（万立方米/小时）粗略统计数字。
水利专家经过勘察，在该村区域内规划了8条可供开挖排洪沟的路线。
由于它们的地质构造、长度不同，因而开挖的费用和预计的可泄洪量也不同，详见表2，而且预计每条排洪沟的可泄洪量还会以平均每年10%左右的速率减少。
同时开始修建一段20公里长的新泄洪河道。
修建工程从开工到完成需要三年时间，且每年投资修建的费用为万元的整数倍。
要求完成之后，通过新泄洪河道能够达到可泄洪量100万立方米/小时的泄洪能力。
乡政府从2010年开始，连续三年，每年最多可提供60万元用于该村开挖排洪沟和修建新泄洪河道，为了保证该村从2010至2014年这五年间每年分别能至少达到可泄洪量150、160、170、180、190万立方米/小时的泄洪能力，请作出一个从2010年起三年的开挖排洪沟和修建新泄洪河道计划，以使整个方案的总开支尽量节省（不考虑利息的因素在内）。
表1 现有四条天然河道在近几年的可泄洪量（万立方米/小时）表2 开挖各条排洪沟费用（万元）和预计当年可泄洪量（万立方米/小时）问题2：该乡共有10个村,分别标记为①—⑩，下图给出了它们大致的相对地理位置，海拔高度总体上呈自西向东逐渐降低的态势。
其中村⑧距离主干河流最近，且海拔高度最低。
乡政府打算拟定一个修建在各村之间互通的新泄洪河道网络计划，将洪水先通过新泄洪河道引入村⑧后，再经村⑧引出到主干河流。
要求完成之后，每个村通过新泄洪河道能够达到可泄洪量100万立方米/小时的泄洪能力。
表3 各村之间修建新泄洪河道的距离（单位：公里）请你们根据表3中的数据，为该乡提供一个各村之间修建新泄洪河道网络的合理方案，使得总费用尽量节省。
（说明：从村A→村B的新泄洪河道，一般要求能够承载村A及上游新泄洪河道的泄洪量。
）问题3：新泄洪河道网络铺设完成后，打算安排一位维护人员，每天可以从一个村到与之直接有新泄洪河道连接的相邻村进行设施维护工作，并在到达的村留宿，次日再随机地选择一个与该村直接有新泄洪河道连接的相邻村进行维护工作。
试分析长此以往，他在各村留宿的概率分布是否稳定？问题4：你们是否能够为该乡提出一个更加合理的解决泄洪的办法？二、问题的分析问题一：在考虑该地区泄洪设施修建计划时，数据中提供了四条天然河道近几年的可泄洪量，8条可供开挖排洪沟开挖费用和当年泄洪量以及一条20公里的新泄洪河道的数据，要求设置出在每年满足一定的泄洪量的前提下，使总开支尽量节省的修建方案。
我们先拟合出四条天然河道未来五年的可泄洪量，然后从每年要求的泄洪量出发，构造以总费用尽量少为目标的优化模型。
由于修建20公里长的新泄洪河道的总费用为定值，所以要求找出修建排洪沟的费用最少的方案。
问题二：对该乡10个村修建一个互通的新泄洪网络，考虑到10个村的相对海拔高度，各村之间修建新泄洪河道的距离，我们采用图论的有关知识，利用了Dijkstra 算法，并结合实际情况，得出一条最优的网络布局。
从而计算出总是费用。
问题三：由于每天维护人员在进行河道维护时，可从一个村到与之直接有新泄洪河道的村进行维护工作，所以由新泄洪河道网络铺设情况计算出每一点到其他点的概率，10点构成一个转移矩阵，由马尔代夫链算法，得出其在各个村的留宿的概率，进而说明他在各村的留宿的概率分布是否稳定。
问题四：提供更加合理的解决泄洪的办法，我们通过分析原有修建方案，再对河流中的泥沙沉积进行了处理，可使得泄洪量达到最佳，而费用不增多。
三、模型的假设(1)河道和排洪沟的修建不会因人，自然等外界因素而导致中途停止； (2)排洪沟在当年修建好之后，即可投入使用进行泄洪；(3)题目所提供的数据真实有效,且在一定的时间内保持不变； (4)每年投入的修建开支所产生的利息因素不考虑在内； (5)将每个村都作为一个质点考虑；(6)不考虑突发自然灾害对河道，排洪沟的堵塞，从而无法进行泄洪的情况； (7)新泄洪河道修建好之后，每个村都可达到可泄洪量100万立方米/小时的泄洪能力；(8)在一定的时间内，这10个村的大致的地理位置和海拔高度不发生改变； (9)每一条排洪沟的可泄量会以平均每年10%左右的速率减少四、符号说明i b ：编号)8,,2,1( =i i 条排洪沟是否开挖，即0=i b 或1；i m ：开挖编号为i 的排洪沟所需费用，单位为万元，83,2,1 =i ； L ：新建泄洪河道的长度，公里20=L ； j L ：第j 年修建河道的长度，3,2,1=j ；)(t q i ：编号为i 的排洪沟在第t 年的泄洪量，83,2,1 =i ；)(t Q ： 第t 年原有四条天然河道的总泄洪量，5,4,3,2,1=t ;)(t Q con ：第t 年新建泄洪河道的泄洪量；)0(i q :开挖编号为i 的排洪沟当年预计的可泄洪量；i τ：需要开挖的排洪沟开挖的时间（14=τ表示编号为4的排洪沟需要在第一年开挖）；M :修建泄洪河道网络的总费用（单位：万元）； P :修建20公里新的排洪河道的总费用五、模型的准备根据表1中的四条天然河流的可泄洪量，可用MATLAB 软件可拟合出这四条河未来五年的泄洪量。
其中，为简化数据，将2001年至2009年的年份表示为1-9，最后拟合出各天然河流的函数图形和方程为：一号（深蓝）：9,,1,4639.332017.11 =+-=x x y 二号（绿色）：9,,1, 0217.293004.02 ==-x e y x 三号（红色）：9,,1, 9806.290850.23 =+-=x x y 四号（浅绿色）：9,,1, 6335.44122.04 ==-x e y x六、模型的建立与求解6.1问题一由于修建新泄洪河道的总费用为定值，所以要求整个方案的总开支尽量少，就是求怎样修建排洪沟，且新泄洪河道能够达到可泄洪量100万立方米每小时的泄洪能力，使得修建排洪沟总开支尽量少。
从2010年到2014年每年主要有以下河道或排洪沟进行泄洪：（1）四条天然河道，第一年需修建的排洪沟；（2）四条天然河道，第一年已修建的排洪沟，第二年需修建的排洪沟； （3）四条天然河道，第一，二已修建，第三年需修建的排洪沟；（4）四条天然河道，第一，二，三的年修建的排洪沟，新建泄洪河道； （5）四条天然河道，第一，二，三的年修建的排洪沟，新建泄洪河道；每年每条需修建的排洪沟可泄洪的量为:⎩⎨⎧≥-=-其他0%)101)(0()(i t i i t q t q iττ新建泄洪河道第四年，第五年可泄洪都为：⎩⎨⎧<==4054100)(t t t Q con 或四条天然河道的泄洪量，我们通过拟合得到每条天然河道的泄洪量与时间的关系函数，进而知道将来每年的预测可泄洪量：tt e t e t t Q 122.03004.06335.44)9806.290850.2(0217.294639.332017.1)(--++-+++-=每年可泄洪量的总和为：)()()()(81t Q b t q t Q t Q con i i i sum ++=∑=该优化模型是把在能够达到指定的要求的情况的泄洪量总费用的使用值来作为该模型最优的衡量，即：目标函数：P t q b Min i i i +⋅=∑=)(81，..t s 3,2,1;83,2,1,60==≤⎥⎥⎤⎢⎢⎡+j i P L L m b j i i31≤≤i τ,150)1(≥sum Q,160)2(≥sum Q ,170)3(≥sum Q ,180)4(≥sum Q ,190)5(≥sum Q由于每年投入修建新泄洪河道的费用为万元的整数倍，修建每个条排洪沟的费用也为万元的整数倍，所以该问题是一个整数优化模型。
用LINGO 求解（程序见附件），得到每年需修建的排洪沟和泄洪河道长度的计划安排需要三年时间，乡政府也只能从2010年开始连续三年每年可提供资金最大值为60万，所以每年修建完排洪沟剩余的资金修建排洪河道，直到排洪河道修建完成。
第一年修建完3,4,5,6号排洪沟沟，剩余40万元，该资金用于修建排洪河道，可修建的长度为 7878.5)100(66.04051.01=⋅=L （公里）第二年修建完1好排洪沟，剩余55万元，该资金用于修建排洪河道，可修建的长度为 9583.7)100(66.05551.02==L （公里） 第三年修建完2号排洪沟，剩余53万元，但第三年需修建排洪河道的长度为2539.620213=+-=L L L （公里） 所以修建费用为2210.432539.6)100(66.051.0=⨯⨯(万元) 取整为44万元； 总开支为：1714455407520=+++++（万元）与预期投入资金少了 9万元；6.2问题二该乡有十个村，要使得费用尽量节省，依据新泄洪河道费用的公式，要使得它最少，则考虑泄洪河道的可泄洪量和泄洪河道的长度最小，但是泄洪河道的可泄洪量只要满足下一村的能够承载上一村的泄洪量就可以，所以问题转化为只要将泄洪河道的长度最小就可以得出费用最少，我们考虑用图论中最短路径的Dijkstra算法求出。
