1、泄洪设施修建计划 摘要 针对本题提出的如何修建泄洪河道使总费用最省以及维护人员在各村留宿 的概率的问题，分别建立了非线性规划模型、马氏链模型，并运用 matlab 和 lingo 数学软件，对模型进行求解，得出修建河道的最省方案和维护人员在各 村留宿的概率。最后还对原来建立的模型进行了评价，并加以推广。 在考虑修建的泄洪道路径和泄洪量的情况下，得到修建泄洪道的最省花费 的 0-1 规划模型。并通过 lingo 求解得到最优泄洪道网络连接图（见图 1）和 修建新泄洪河道最省总花费资金：547.0804 万元。 维护人员是在问题一中解得的新泄洪河道上移动的，从一个村移动到与之 相连的一个村，符合马
2、氏链，所以建立了马氏链模型。通过分析得出，该马氏 链是正则链。根据正则链的性质可知，正则链存在唯一的极限状态概率，所以 维护人员在各村留宿的概率分布是稳定的。并运用 matlab 软件编程求解出维护 人员在各村留宿的稳态概率（见表 3） 。 由于前面的模型仅是从修建泄洪道花费最省来建立的。而没有考虑建设后 的维护成本。且由于上游地势高的村庄的水流要汇入下游地势低的村庄，从而 会使得下游泄洪道的泄洪压力增大。有可能洪涝来临时对下游村庄带来危险。 所以从安全和维护等因素来看，综合该乡地势由西向东逐渐降低的地势特点。 可以考虑在该乡中间人口相对较少地区修建一由西向东的逐渐加宽的主渠道。 再由各村庄各
3、自修建泄洪渠道与主渠道相连，最终将洪水排出。 关键词： 0-1 变量 线性规划模型 马氏链模型 matlab lingo 1 一、问题重述 位于我国南方的某个偏远贫困乡，地处山区，一旦遇到暴雨，经常发生洪 涝灾害，以往下雨时，完全是依靠天然河流进行泄洪。2010 年入夏以来，由于 史无前例的连日大雨侵袭，加上这些天然河流泄洪不畅，造成大面积水灾，不 仅夏粮无收，而且严重危重到当地群众的生命财产安全。 为此，乡政府打算立即着手解决防汛水利设施建设问题。从长远考虑，可 以通过修建新泄洪河道的办法把洪水引出到主干河流。经测算，修建新泄洪河 道的费用为 （万元）23pLQ 其中 Q 表示新泄洪河道的可
4、泄洪量（万立方米/小时） ，L 表示新泄洪河道 的长度（公里） 。 该乡共有 10 个村，分别标记为-，下图给出了它们大致的相对地理位置， 海拔高度总体上呈自西向东逐渐降低的态势。 其中村距离主干河流最近，且海拔高度最低。乡政府打算拟定一个修建 在各村之间互通的新泄洪河道网络计划，将洪水先通过新泄洪河道引入村后， 再经村引出到主干河流。要求完成之后，每个村通过新泄洪渠道能够达到可 泄洪量 100 万立方米/小时以上的泄洪能力。 表 1 各村之间修建新泄洪河道的距离（单位：公里） 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 7 4 8 11 13 12 16 17
5、22 9 14 16 8 11 18 14 23 7 9 11 7 12 12 17 4 17 10 7 15 18 8 10 6 15 15 9 16 8 15 8 6 11 13 11 12 请通过数学建模的方法，解决以下问题： 问题 1：根据表 1 数据，为该乡提供一个各村之间修建新泄洪河道网络的 合理方案，使得总费用尽量最省。 （提示：从村 A 村 B 的新泄洪河道，一般要 求能够承载村 A 及上游新泄洪河道的泄洪量） 。 问题 2：新泄洪河道网络铺设完成后，打算安排一位维护人员，每天可以 从一个村到与之直接有新泄洪河道连接的相邻村进行设施维护工作，并在到达 2 的村留宿，次日再随机地
6、选择一个与该村直接有新泄洪河道连接的相邻村进行 维护工作。试分析长此以往，他在各村留宿的概率分布是否稳定？ 问题 3：是否能够为该乡提出一个更加合理的修建新泄洪河道的办法？ 二、问题分析 针对问题一，要求使得总费用尽量最省，而修建新泄洪河道的费用 （万元） ，由此可知费用与新泄洪河道的可泄洪量 Q 和泄洪河道的长23pLQ 度 L 有关，要使费用 P 最小，即泄洪量 尽量的小，且泄洪河道的长度 尽量QL 的短。对于此，可以运用 0-1 变量建立规划模型，进而运用 lingo 软件编程求 出最优方案。 针对问题二，维护人员是在问题一中解得的新泄洪河道网络上移动的，从 一个村移动到与之相连的一个村
7、，符合马氏链，所以建立了马氏链模型。通过 分析得出，该马氏链是正则链。根据正则链的性质可知，正则链存在唯一的极 限状态概率，所以维护人员在各村留宿的概率分布是稳定的。再用 matlab 软件 编程求解出维护人员在各村留宿的稳态概率。 针对问题三，由于上游地势高的村庄的洪水要汇入下游地势低的村庄，从 而会使得下游泄洪道的泄洪压力增大。有可能洪涝来临时对下游村庄带来危险。 且由于渠道较多后期维护较难。所以从安全和维护等因素来看，综合该乡地势 由西向东逐渐降低的地势特点。可以考虑修建一由西向东的逐渐加宽的主渠道。 最终将洪水排出。 三、问题假设 1、村子 1-10 的海拔高度自西向东递减。 2、A-
8、B 的泄洪河道，其中 B 村的泄洪河道能够承载村 A 泄洪量及上游所有 流入 A 的泄洪量。 3、若泄洪河道相交，假设互不影响各自泄洪量。 4、假设维修人员选择第一个村庄是随机的，且概率是相同的。 四、符号说明 ：第 i 村庄到第 j 村庄泄洪河道的流量。ijQ ：i 村到 j 村的距离jL0,i1jijX表 示 不 修 河 道表 示 修 建 河 道 ：修建河道总费用p ：维护员从村子 到相邻村子 的概率（ ） ；ijPij ji,1098,3, 且ji 3 ：在 i 村留宿的概率（ ）iw10,2i ：表示维护人员所处的状态（ 可以取 10 个离散值 ）nXnX10,2nX ：状态概率，维护
9、人员处在村 的概率 （ ）)()iPaniii ：转移概率，维护人员从村 转移到村 的概率（|1iXjij j ）j,098,32, 且 ：转移概率矩阵P ：各段主泄洪道的泄洪量（100-900） 。iQ ：各段主泄洪道的长度。iL ：各村的泄洪量。 j ：各村到主泄洪道的泄洪道长度。j 五、模型的建立与求解 5.1：根据表 1 数据，为该乡提供一个各村之间修建新泄洪河道网络的合理方案， 使得总费用尽量最省。 根据表 1 数据，为该乡提供一个各村之间修建新泄洪河道网络的合理方案，使 得总费用尽量最省。其中为了表述的方便将村庄做如下编号即： 3 2 5 7 1 6 10 4 9 8 于是，表一数
10、据整理为： 4 表 2 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 8 13 8 11 9 17 15 8 16 7 14 9 11 14 23 16 18 17 4 12 8 22 11 16 12 6 15 12 15 13 7 7 17 9 12 10 11 10 8 18 4 7 15 11 6 为使费用最小，依据题意引入 0-1 变量，其中 0 表述不修河道，1 表示要修 建河道。故建立如下优化模型： 910ijiji=j+2mn3pXLQiji-110ki ij=j=i+10jj=ijs.t 29Q（ ）（ ） 由 lingo 软件可以得到（程序见附录
11、 1 ）：2356461979,106,108,10,XXXX 则： 21133797785810,845650,2,0,3,10QQQQQ2137978510,8456,4,6,6,LLLL 由此可绘出下图： 5 3 2 5 7 1 6 10 4 9 8 图 1. 各村之间互通的新泄洪河道网络 可得出最小费用为： min547.08p万 元 5.2.1：维护人员的转移路线就是问题一中建立的新泄洪河道网络。为求维护人 员在各村留宿的概率分布以及是否稳定，建立马氏链模型。 由问题一得出的新泄洪河道修建方案可知转移概率矩阵为： 01/2000/ 1/201/30/30/ 1/ /000P 由马氏链
12、的性质可知： 的取值只取决于 的取值及转移概率，而与1nXnX 的取值无关。由状态转移的无后效性和全概率公式可以写出马氏,21nX 链的基本方程为 10,2,)()1(0iPnaajji 并且 6 1010(),0,12.,iijijanstPij 则状态概率向量（行向量）和转移概率矩阵 1210,0/ 00/ 1/2001/3/0/30/ 1/0/ /0 0ananP 则基本方程（1）可以表示为 Pna)1( 由该递推关系式还可以得到 n0)( 5.23判断该马氏链是否是正则链 正则链的定义为：一个有 个状态的马氏链如果存在正整数 ，使从任意k N 状态 经 次转移，都以大于零的概率到达状态
13、 ，则这样的马iN ),21,(kji 氏链称为正则链。 因为修建的新泄洪河道网络连接着这十个村，当维护人员沿着新泄洪河道 网络转移时，每个村都有可能到达。即假设维护人员在村 ，一定可以经过正整i 数 次转移到任意村 即都以大于零的概率到达状态 。),(jij 由正则链的定义可以知道，本问题中建立的马氏链模型是正则链。 5.2.4求解极限状态概率 由定理可知，正则链存在唯一的极限状态频率 ，使得当kw,.21 时状态概率 ， 与初始状态概率 无关。 满足nwna0a 7 1kiw P 所以，长此以往，维护人员在各村留宿的概率就是极限状态频率 ，则由正则链的性质可知，维护人员在各村留宿的概率是1
14、0921,., 稳定的。 由式可得： 1,.,.,0 10921092iwwP 联立可解得极限状态概率为（matlab程序见附录 2 ）： 0.1111 0.0556 0.1111 0.0556 0.1667 0.0556 0.166 7 0.1667 0.0556 0.0556 表3 即可得维护人员随机在各村留宿的稳态概率 1w23w45w/918/91/818/36789018/3/3/ 5.3：由于该乡地势由西向东逐渐降低。且各村庄由西向东分布。故可以在其中 间人口分布密度较少区建一由西向东的主泄洪道。泄洪道泄洪量依次递增。从 100-900。最终经村庄 8 注入主干河流。各村再各自修建
15、泄洪道与主泄洪道相连。 各村最大泄洪量用 Q 表示。L 为主泄洪道的长度。由几段构成。泄洪量 100-900。 目标函数： min2/3*2/3*i jjpQL 六、模型的评价和优化 模型的优点： 1、用 0-1 变量刻画村庄之间的河道修理与否，结合线性规划模型简单易懂用 lingo 软件求解也较方便。 2、问题二建立的马氏链模型，即符合题意也具有理论依据用 matlab 求解其程 8 序也比较简便。 3、该模型可运用性强，不仅仅运用于河道的修理也可以用于电缆的铺设、道路 的修建等等类似的模型。 模型的缺点： 1、该模型模型考虑的因素还不多，如有些地方可能因为地貌不能挖泄洪河道、 有的地方河道
16、没法加宽、以及修建排洪沟这样会使建立的模型对实际产 生较大的误差。 七、参考文献 1 孙祥 徐流美 吴清， matlab7.0 基础教程 ，清华大学出版社，2005 年. 2 刘卫国，MATLAB 程序设计与应用（第二版） ，北京：高等教育出版社， 2006 年。 3 姜启源 谢金星 叶俊，数学模型（第三版） ，北京：高等教育出版社，2006 年。 4 戴明强 李卫军 杨鹏飞，数学模型及其应用，北京：科学出版社，2007 年. 5 谢金星、薛毅编著，优化建模与 lingo/lindo 软件，北京：清华大学出版 社，2005.7. 9 附件： 附录 1 model: sets: cun/110/
17、; link(cun,cun) | endsets data: d = 8 13 8 11 9 17 15 8 16 7 14 9 11 14 23 16 18 17 4 12 8 22 11 16 12 6 15 12 15 13 7 7 17 9 12 10 11 10 8 18 4 7 15 11 6; enddata min=sum(link(k,i)|k#lt#i:x(k,i)*(2/3)*sqrt(q(k,i)*d(k,i); for(link(i,j)|i#lt#j:bin(x(i,j); for(link(i,j)|i#lt#j:q(i,j)=100); for(cun(i)|
18、i#ne#10 #and# i #ne# 1:sum(cun(j)|i #lt# j:q(i,j)*x(i,j)- sum(cun(j)|j #lt# i:q(j,i)*x(j,i)=100;); for(cun(i)|i #ne# 10:sum(cun(j)|i #lt# j:x(i,j)=1); !for(cun(i)|i #eq# 10:sum(cun(j)|j #lt# i:x(j,i)=1); End 附录 2 function main() clc p=0 1/2 1/2 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1/2 0 0 0 0 0 1/2 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1/3 0 1/3 0 1/3 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1/3 0 0 0 0 1/3 1/3 0 0 0 0 0 1/3 0 1/3 0 0 1/3 0 0 0 0 0 0 1 0 0 0 10 0 0 0 0 0 0 0 1 0 0; A=ones(10,1),zeros(10,9); B=p-eye(10)+A; W=1 0 0 0 0 0 0 0 0 0*inv(B); W
