洪水排险问题解决方案.docx

1、洪水排险问题解决方案队号：08队员：谢文婷 陈商龙 戴翔洪水排险问题解决方案摘要本题主要讨论了洪水排险的优化问题。文章通过三个问题由浅入深的展开，对洪水排险的最佳方案进行了深入的探讨。首先，问题一第一小问探讨了使所有区域都遭受损失的最小洪水量的问题，是一个典型的规划求解问题。本文根据具体情况，设计了合理的假设，并通过建立规划模型，引入0-1变量，得到了最优解。本问的第二个小题探讨了简单题设条件下的规划问题，本题的关键在于利用图论的相关知识得到限制条件，本文根据题设条件得到邻接矩阵，再引入0-1变量，根据Floyd-Warshall算法和矩阵的运算设计限制条件进行筛选，得到可行解，最后比较目标函

2、数大小，得到最优解，即损失最小的泄洪方案和损失金额。在第一题的基础上，问题二进一步拓展，讨论了复杂条件情况下的规划问题。问题二的第一小题探讨了在海拔高度不同的条件下使所有区域都遭受损失的最小洪水量的问题，本文通过逻辑判断，找到了使得所有区域都遭到损失的必要条件，并通过计算得出了使其实现的最小值，从而得出了最优解。本问的第二小问对第一问的第二小问进行了拓展，题设条件更加复杂，本文通过整理题中各区域的单位体积损失率,对其进行排序，并判断最优路径能否实现，若不能则使用次优路径，得到各个区域遭受洪水袭击损失的优先级，最后得到最佳泄洪方案。问题三探讨了在第二题情况下，对给定的条件进行修改，从而设计出一个

3、损失更小的最优泄洪方案的问题。本文对该问题暂未作具体解答。本文主要通过规划求解和逻辑判断的方法，解决题目中所要求的不同情况下使得所有区域遭受损失的最小洪水量，以及给定洪水量的情况下，遭受损失最小的泄洪方案和损失金额等问题。思路明确，答案精准。略显不足的是算法较为复杂，导致运行时间长，纠错困难。在讨论了本文的优缺点以及改进措施之后，我们认为本文还有很大的拓展和优化空间，在改进和拓展之后，可以用于解决类似的调度问题，具有一定的普适性。关键词 洪水排险 0-1变量 Floyd-Warshall算法 最优路径一、问题重述近段时间以来，由于我国南方地区遭受持续的强暴雨袭击，许多江河流域出现百年不遇的险情

4、。为减少损失，将采取破堤的方法排除险情，而泄洪必然影响下游沿岸区域。位于广西某区域三面环山，山很高，一面是河流，用堤坝隔离，使该区域成为封闭区域。当上游发生泄洪时，极易破堤淹没区域，造成人员和财产的损失。为减少总的损失，人们采取破堤排除险情。该区域内又分成20个矩形小区，已知小区域的分布示意图。该区域与河流之间有大堤隔离，各小区域之间有高度为1.2m的小堤相互隔离，假设决堤口可选在大堤或小堤的任何地方，决堤口数目不受限制。但一经决口，就不能再补合。从河流经大堤决口流入小区域的洪水量按决口数成比例分配。如在小区域之间小堤开一决口，则假设该两小区域之间的这段才小堤不复存在。若水位高于小堤，则将自动

5、向邻近最低的一个小区泄洪。若这样的小区有几块时，则平均泄洪。已知各小区域被完全淹没时土地、房屋和财产等损失总数k，当洪水淹没一个小区域且水位高于该小区域高度p（单位m）时，该小区域的损失为该小区域的k和p的函数。问题一 1、在海拔高度相同的假设下，首先求出整个区域全部受损失的最小洪水量。2、当洪水量为20106m3，40106m3时，分别制定泄洪方案，使总损失最小（在一种方案中，决堤同时进行），须计算出该方案的损失数。问题二 1、在海拔高度不同的假设下，根据已知的各区域的海拔高度求出整个区域全部受损失的最小洪水量。2、当洪水量为40106m3，80106m3时，分别制定泄洪方案，使总损失最小。

6、问题三 在海拔高度不同的假设下，可以对小堤增高加固，增高加固的费用（不计厚度）为1（百元/平方米），最高可将原有小堤提高0.5（m），制定泄洪、增高加固方案，使总损失最小。二、问题分析问题一的第一小题要求得到所有区域受到损失所需的最小洪水量，是规划求解问题，首先通过设计0-1变量来判断某区域是否被完全淹没，然后通过完全淹没区域的位置及水位和未被完全淹没区域的位置对变量进行约束，最后以总洪水量最小建立目标函数，解得最小值。问题一的第二小题要求在给定洪水量的情况下，制定使损失达到最小的泄洪方案，是典型的规划求解问题。本题可以利用上一小题关于完全淹没区域位置关系的限制条件，并添加关于总洪水量的限制条

7、件对变量进行限制。最后以总损失最小建立目标函数，解得最小值，并得到最佳泄洪方案。问题二的第一小题要求得到在各区域海拔高度不同的情况下使所有区域受到损失最小的洪水量。通过逻辑判断找到所有区域都受损失的充分必要条件，并计算得出使该条件得到满足的最小洪水量，即可解决问题。问题二的第二小题要求在给定洪水量且海拔不同的情况下，制定使损失达到最小的泄洪方案。通过对各个区域的损失率进行排序，并判断洪水高于小堤溢出与挖开小区的损失差异，对各小区受到损失的优先级进行排序，最后得到结果。问题三是典型的规划求解问题，问题的关键在于目标函数的设计。通过完全淹没区域的位置与顺序以及总洪水量设计限制条件，使用0-1变量来

8、判断是否要加固堤坝，最后以总损失最小建立目标函数，解得最小值，并得到最佳泄洪方案。三、模型假设与符号系统3.1模型假设1. 在第一问第一小问与第二问第一小问中，某区域必须被完全淹没才能向下一个区域泄洪。2. 某区域的水位极低（趋近于0）时，该区域也算作遭受损失。3. 在第一题第二小问与第二题第二小问中，决堤同时进行。4. 小堤决堤视作该小堤不再存在。5. 不考虑挖通堤坝的时间。6. 假设水的流速极大，从一个区域流动另一个区域的时间为0。7. 水位符合连通器原理，即连同的区域，水面相对于海平面的高度相等。8. 洪水不会回流到河流中。9. 所有数据真实可靠且具有代表性。3.2 符号系统ki 第i个

9、小区域被完全淹没时土地、房屋和财产等损失总数p 当洪水淹没一个小区域且水位高于该小区域高度mji 第i个小区域的面积shli 第i个小区域被完全淹没时的面积损失率s(i) 0-1变量构成的行向量，表示该区域是否属于覆盖区域ai,j 根据已知图形求得的无权邻接矩阵bi,j 路径覆盖区域可到达的其它区域的矩阵di,j 路径覆盖区域是互相连接的矩阵zshl 总面积损失率sunshi 总损失hi 第i区域的海拔V 最小洪水量四、模型的建立与求解4.1问题一4.1.1模型的建立1、第一小问假设某区域受损失是指只要有一点洪水淹没该区域即表示该区域受损失，我们称被洪水完全淹没的小区域为覆盖区域，未完全被洪水

10、淹没的区域为邻近区域。因此使整个区域全部受损失的最小洪水量应满足的条件为：被选出的覆盖区域应与所有邻近区域相邻，只有这样才能保证当洪水刚好淹没覆盖区域时，只要再多一点水就可以使所有邻近区域受损，此时满足整个区域全部受损。若把覆盖区域连通，看成一条路径，则该路径应满足的条件为：第一，路径的起点应包含区域1、2、3、4、5中至少一个区域；第二，该路径覆盖区域和该路径的邻近区域包含所有20个小区域；第三，该路径是连通的，即路径覆盖区域是相邻的。当选出满足以上条件的路径后，只要找到能被最小洪水量淹没的路径即可。2、第二小问本题已知具体洪水量，要求分别制订泄洪方案使损失最小。已知各小区域被完全淹没时土地

11、、房屋和财产等损失总数为ki，各区域面积为mji。首先各区域被完全淹没时的面积损失率为shli=kimji通过计算可得各区域的面积损失率分别为下图所示：接下来我们要考虑的是在满足可以容纳全部洪水的情况下遭受损失最小的条件。首先，洪水必须至少经过区域1、2、3、4、5中的一个才能到达其它区域，而在这五个小区域中，面积损失率最小的区域为1和4且这两个区域可以和区域2、3、5相连，因此我们设定洪水经过的路径起点必须为区域1或区域4。其次，洪水经过的路径必须是相连通的，这与第一小问中的第三个条件相同，不再赘述。最后，当我们找出符合上述条件的路径后，需要通过规划求解得出损失最小的路径，具体思路为：以区域

12、1与区域4为起点的路径覆盖区域的总体积应不小于洪水总量；而后比较以区域1与区域4为起点的路径覆盖区域的总面积损失率，洪水应首先流入总面积损失率较小的路径区域，若洪水总量小于该区域总体积；若洪水总量大于该区域总体积，则多余的洪水量流入总面积损失率较大的那条路径覆盖区域，进而则可求出在不同情况下的损失。4.1.2 模型的求解1、第一小问算法描述s(i)：0-1变量构成的行向量，表示该区域是否属于覆盖区域a(i,j)：根据已知图形求得的无权邻接矩阵，该矩阵主对角线所有元素均为1，所有无法到达的点用20表示，以便后续分析。第一步 通过0-1循环构造由0-1变量组成的s向量。将矩阵a的第i行所有元素与s

13、向量中第i个元素对应相乘，得到矩阵b，矩阵b表示路径覆盖区域可到达的其它区域的矩阵。第二步 将矩阵b的每一列相加，得行向量c，c中的每个元素被20除所得的余数不为0时，可满足上述条件二，即此路径覆盖区域和该路径的邻近区域包含所有20个小区域。第三步 将矩阵b第j列的所有元素分别与s向量中的第j个元素相乘，得到矩阵d，矩阵d表示路径覆盖区域是互相连接的矩阵。第四步 从第20列开始，将矩阵d第j列的前j-1个元素相加，所得到的和需满足等于0或被20除所得余数不为0这两个条件中的一个。第五步 计算并记录此s向量所代表的路径覆盖区域的总体积，从第二次循环开始每一次都与前一次求得的总体积相比较，若新的体

14、积小于旧的体积，则用新求出的总体积值覆盖之前求得的总体积值。全部循环完毕后，最终得到可使全部区域受损失的最小洪水量。使用MATLAB编程求解，可得使全部区域受损失的最小洪水量为39.192106m3，洪水覆盖的区域为1、4、7、9、12、14、17，即当洪水完全淹没上述区域时，再多一点洪水即可使20个区域全部受损失。2、第二小问算法描述s(i)：0-1变量构成的行向量，表示该区域是否属于覆盖区域a(i,j)：根据已知图形求得的无权邻接矩阵，该矩阵主对角线所有元素均为1，所有无法到达的点用20表示，以便后续分析。第一步 通过0-1循环构造由0-1变量组成的s向量。将矩阵a的第i行所有元素与s向量

15、中第i个元素对应相乘，得到矩阵b，矩阵b表示路径覆盖区域可到达的其它区域的矩阵。第二步将矩阵b第j列的所有元素分别与s向量中的第j个元素相乘，得到矩阵d，矩阵d表示路径覆盖区域是互相连接的矩阵。第三步 通过Floyd-Warshall算法找到以区域1和区域4为起点的不同路径，具体过程如下：设Di,j,k为从i到j的只以(1k)集合中的节点为中间节点的最短路径的长度。若最短路径经过点k，则Di,j,k=Di,k,k-1+Dk,j,k-1；若最短路径不经过点k，则Di,j,k=Di,j,k-1。因此，Di,j,k=min（Di,k,k-1+Dk,j,k-1，Di,j,k-1）。第四步 在保证两条路

16、径的覆盖区域的总体积不小于一直洪水量的前提下，比较两条路径的总面积损失率zshl。若zshl1zshl2，与上述情况类似。第五步 将每一次循环求得的损失结果sunshi与某一极大值jieguo进行比较，若sunshi=1; b1=s1*a1;b2=s2*a2;b3=s3*a3;b4=s4*a4;b5=s5*a5;b6=s6*a6;b7=s7*a7;b8=s8*a8;b9=s9*a9;b10=s10*a10;b11=s11*a11;b12=s12*a12;b13=s13*a13;b14=s14*a14;b15=s15*a15;b16=s16*a16;b17=s17*a17;b18=s18*a18

17、;b19=s19*a19;b20=s20*a20;for i=1:20;c(i)=b1(i)+b2(i)+b3(i)+b4(i)+b5(i)+b6(i)+b7(i)+b8(i)+b9(i)+b10(i)+b11(i)+b12(i)+b13(i)+b14(i)+b15(i)+b16(i)+b17(i)+b18(i)+b19(i)+b20(i);endif mod(c(1),20)0 & mod(c(2),20)0 &mod(c(3),20)0 &mod(c(4),20)0 &mod(c(5),20)0 &mod(c(6),20)0 &mod(c(7),20)0 &. mod(c(8),20)0

18、&mod(c(9),20)0 &mod(c(10),20)0 &mod(c(11),20)0 &mod(c(12),20)0 &mod(c(13),20)0 &mod(c(14),20)0 &. mod(c(15),20)0 &mod(c(16),20)0 &mod(c(17),20)0 &mod(c(18),20)0 &mod(c(19),20)0 &mod(c(20),20)0 ; dd=b1;b2;b3;b4;b5;b6;b7;b8;b9;b10;b11;b12;b13;b14;b15;b16;b17;b18;b19;b20; ddins=dd; for p=1:20; for q=1:

19、20; ee(p,q)=ddins(p,q)*ss(1,p); end end f=zeros(1,20);g=zeros(1,20); for m=20:-1:1; for n=1:(m-1); f(m)=ee(n,m)+f(m); end end for t=1:20; for u=1:20; g(t)=ee(u,t)+g(t); end end l=0; for k=20:-1:6; if mod(f(k),20)0.9 |g(k)=0 ; l=l+1; end end if l=15 & sum(ss.*mianji)=1; b1=s1*a1;b2=s2*a2;b3=s3*a3;b4=

20、s4*a4;b5=s5*a5;b6=s6*a6;b7=s7*a7;b8=s8*a8;b9=s9*a9;b10=s10*a10;b11=s11*a11;b12=s12*a12;b13=s13*a13;b14=s14*a14;b15=s15*a15;b16=s16*a16;b17=s17*a17;b18=s18*a18;b19=s19*a19;b20=s20*a20; dd=b1;b2;b3;b4;b5;b6;b7;b8;b9;b10;b11;b12;b13;b14;b15;b16;b17;b18;b19;b20; ddins=dd; for p=1:20; for q=1:20; ee(p,q)

21、=ddins(p,q)*ss(1,p); end end f=zeros(1,20);g=zeros(1,20); for m=20:-1:1; for n=1:(m-1); f(m)=ee(n,m)+f(m); end end for t=1:20; for u=1:20; g(t)=ee(u,t)+g(t); end end l=0; for kk=20:-1:6; if mod(f(kk),20)0.9 |g(kk)=0 ; l=l+1; end end sstiji=sum(ss.*tiji); if l=15 ;%? %zuiduanlu n=20; d=ee; %赋初值for(i=

22、1:n) for(j=1:n) r(i,j)=j; %赋路径初值 endendfor(k=1:n) for(i=1:n) for(j=1:n) if(d(i,k)+d(k,j)d(i,j) d(i,j)=d(i,k)+d(k,j); %更新距离 r(i,j)=k; %更新经过的点 end end end k; %显示迭代步数 d; %显示每步迭代后的路长 r ; %显示每步迭代后的路径 pd=0; for i=1:n if(d(i,j)20; for mm=2:20; if d(tt1,mm)20; mjz1=mjz1+mianji(mm); jl1(mm)=1; end end for nn