新河道修建问题.doc

新河道修建问题 （郑海量，刘佳明，黄学刚）摘要位于我国南方的某个县经常是春旱夏涝，针对今年该县遭遇的春旱灾害某乡政府打算立即着手解决水利实施建设问题，解决春旱和夏涝问题。对此，我们对旧河道历年的水流量的数据拟合和预测做出开挖和修建河道的计划。针对问题一，我们对历年流水量进行分析，先用补充数据再用Matlab R2010a中的cftool工具分别拟合出四条天然河道的流水量关于时间的函数，并求得各个回归系数的值和其相对应的置信区间，用于预测未来五年天然河道的流水量。在此基础上我们采用0-1规划模型，在通过LINGO 9.0软件求解得到此计划的最小总费用167万。流水河道修建计划的实施方案如下：2013年开挖第2,4,5,6,号河道，2014年开挖1号河道。开挖这些河道，并且能够在三年内完成一段20公里长的新流水河道，可流水量为100万立方米/小时，这样能够解决该县的干旱问题，而且保证在未来几年都能够满足并超出政府的设定的指标。模型二是根据问题二（修建在各村之间互通的河道网络计划）而建立的。通过表3得出各个村庄的距离，我们赋予其不同的权值，使用Matlab R2010a软件来处理各个村庄的权值和利用最小生成树法来求解模拟河道网络。求得河道网络：村1到村2，村2到村6，村6到村9，村1到村3，村3到村7，村3到村4，村4到村8，村4到村5.村5到村10。模型三在问题二的基础上进行分析，该乡给出的各村的相对地理位置，且海拔成西高东低的态势。因为从A村到B村的河道要承载B村及下游的流水量，考虑两村之间河道修建距离与河道流水量不断累积扩大的问题，题设要求求出最优费用。我们考虑使用最小费用最大流的方法来求解问题，并在满足约条件的情况下，建立0-1规划模型，并运用Matlab编程，得到最优修建方案，并得到最低费用为554.5356万元。最后，评价模型的优缺点，并提出模型的推广，对模型的改进方向以及优缺点进行了讨论。关键词：Matlab软件 0-1规划模型 LINGO软件 最小生成树 最小费用最大流- 16 -一、问题重述据气象部门对该县中长期天气预测，全县春旱将持续，部分乡镇有加剧的可能。为此，某乡政府打算立即着手解决水利实施建设问题。解决春旱和夏涝问题，干旱时要引水库中的水进村，夏天要泄洪。从长远考虑，可以通过修建新河道的办法把水库里的水引入各村。经测算，修建新河道的费用为(万元)。其中Q表示新河道的水流量（万立方米/小时），L表示新河道的长度（公里）。请你们通过数学建模方法，解决以下问题：问题一：开始修建一段20公里长的河道，修建工程从开工到完工需要3年时间，乡镇府从2013年开始，连续三年，每年最多可提供60万元用于该村开挖和修建河道，保证该乡从2013至2017年这五年间每年分别能至少达到可流水量150、160、170、180、190万立方米/小时的水流能力，请做出一个从2013年起三年的开挖河道和修建新河道计划，使整个方案的总开支尽量节省（不考虑利息的因素在内）。问题二：该乡有10个村，乡镇府打算拟定一个修建在各村之间互通的河道网络计划，将水库中的水先通过河道引入村后，再经村引入其它村。要求完成之后，每个村通过新河道能够达到水流量为100万立方米/小时的能力。 问题三：请你们根据表3的数据，为该乡提供一个各村之间修建新河道网络的合理方案，使得总费用尽量节省。（说明：从A村到B村的河道要承载B村及下游的流水量。）二、问题分析问题一的分析由于修建河道过程历时三年，乡政府从2013年开始，只提供三年的资金且每年最多60万用于该村开挖流水和修建河道，所以新河道从2013年开始动工。2013及2015年政府的拨款用于支付开挖河道和修建新河道工程。新河道长度L已知为20公里，可流水量Q为100万立方米/小时，故修建费用P一定，故只需考虑开挖流水河道的计划。为设计一个从2013年起三年的开挖河道和修建新河道的，保证该乡从2013至2017年这五年间每年分别能至少达到可流水量150、160、170、180、190万立方米/小时的水流能力，且整个方案的总开支尽量节省，考虑利用0-1规划模型。问题二的分析题目要求我们修建各村之间相连的河道网络，由于海拔总体上呈现自西向东逐渐降低的趋势，所以水流只能从高海拔村庄流量低海拔村庄，形成一个有方向的网络图，根据表3得出各村庄的距离我们赋予其不同的权值，因此我们将问题通过使用最小生成树法来解决使各个村庄之间互通的河道网络使河道最短且充分利用了海拔地势。再通过Matlab对各个村庄权值的处理和最小生成树法来求解河道网络。 问题三的分析该乡镇地势西高东低，故按地势从高到底依次对各村进行分析，对流水量进行累加，利用目标函数与约束条件，建立一般非线性规划模型。村1毗邻水库且海拔最高，则河道必须先通过村1再与其他村庄相连。修建河道的费用为，修建费用受河道流水量(万立方米/小时)及修建河道的长度（公里）两个因素约束。因为从A村到B村的河道要承载B村及下游的流水量，考虑两村之间河道修建距离与河道流水量不断累积扩大的问题。本模型对任一村庄分析修建河道的可行性，且修建河道的总费用最小。考虑到将河道是否修建设为0-1变量表示函数关系，故本文仍采用0-1规划模型。再根据最小费用最大流的方法建立模型。再通过表三各村之间修建河道的距离，利用距离得出相对应权值，使用Matlab软件求解最优方案和最低费用。三、模型的假设与符号说明3.1模型的假设1.每条流水河道的可流水量的减小速率恒为每年10%； 2.修建新流水河道的费用需在三年内完工； 3.同一海拔的村庄间不修河道； 4.流水河道水流量由河道本身决定，不受人为因素与气候变动的影响；5.任意一新建流水河道为过水断面、平均流速、水深沿流动方向不变的明渠等。 6.流水河道汇流产生的干扰因素与水力特性的改变忽略不计；3.2符号说明 ：表示第年内第条是否开挖；（=1,2,8; =1,2,3） ：表示第条河道开挖费用；（=1,2,8） ：表示总费用； ：表示2013-2017的计划流水量； ：表示第年4条天然河道的总流量； ：为第条河道未完工的流量； ：表示第年修建总费用； ：表示第村庄到第村庄是否修建河道；（）四、模型的建立和求解4.1问题一：三年开挖河道和修建新流水河道计划4.1.1现有四条天然河道在2013-2015年的可流水量的预测4.1.1.1观察1号河道的流水量关于时间的散点图，经观测猜想为线性函数，经过Matlab中的cftool工具拟合得：一号天然河道往年流水量数据拟合图象通过拟合得到线性方程：f(x) = p1*x + p2表1：一号天然河道第一次拟合函数的检验结果系数值估计值系数置信区间p1=-1.188(-1.201, -1.176)p2=2414(2388, 2439)方差: 0.011834.1.1.2二号河道的可流水量关于时间的散点图，经观测猜想为指数函数，经过Matlab中的cftool工具拟合得：二号天然河道往年流水量数据拟合图象通过拟合的指数函数表2：二号天然河道第二次拟合函数的检验结果系数值估计值系数置信区间a1 =183.4(-3.364e+005, 3.368e+005)b1 =1997(-1139, 5134)c1 =8.067(-1288, 1304)a2 =-105(-3.453e+005, 3.451e+005)b2 =1999(-496.2, 4495)c2 =7.118(-1163, 1178)方差：0.02089 决定系数0.9999 校正后的决定系数0.9998 标准差0.083454.1.1.3三号河道的可流水量关于时间的散点图，经观测猜想为线性函数，经过Matlab中的cftool工具拟合得：三号天然河道往年流水量数据拟合图象通过拟合的指数函数表3：三号天然河道第三次拟合函数的检验结果系数值估计值系数置信区间a1=0b1=1993c1=0.883a2=46.69(-228.6, 322)b2=1994(1904, 2083)c2=15.3(-28.66, 59.26)方差：1.62 决定系数0.9951 校正后的决定系数0.9869 标准差0.73484.1.1.4四号河道的可流水量关于时间的散点图，经观测猜想为线性函数，经过Matlab中的cftool工具拟合得：四号天然河道往年流水量数据拟合图象通过拟合的指数函数表4：四号天然河道第四次拟合函数的检验结果系数值估计值系数置信区间a1=670.2(-1.004e+007, 1.004e+007)b1=1969(-9.423e+004, 9.816e+004)c1=18.85(-4.01e+004, 4.013e+004)a2=295.4(-2.434e+007, 2.434e+007)b2=1952(-1.159e+006, 1.163e+006)c2=32.91(-2.518e+005, 2.519e+005)方差：0.008263 决定系数1 校正后的决定系数0.9999 标准差0.06428表5：现有四条天然河道在近几年的流水量（万立方米/小时）年份编号201320142015201620171号河道21.558320.3719.181717.993316.8052号河道1.443961.069410.792020.3199080.1863053号河道7.641615.195263.247181.867810.9943284号河道12.545510.87319.428658.180377.100684.1.2开挖和修建河道方案的设计该乡政府从2013至2015年，每年最多可提供60万元用于该村开挖河道和修建新河道，所以规划的总费用不应多于180万元，且应该保证该村从2013年开始在未来五年间每年分别能至少达到可流水量150、160、170、180、190万立方米/每小时，在充分满足约束条件的情况下求使开挖和修建费用最小的修建计划。我们针对这个模型建立0-1规划：目标函数使用LINGO 9.0软件求解，得： 从附录一中可清楚得出此计划最小总费用为167.0000万元。 2013年度开挖第2,4,5,6条河道，总流水量为152.18937万立方米/小时，开挖河道花费为7+4+6+5=22万元，修建新河道花费=60-22=38万元；2014年度开挖第1条河道，总流水量为160.6077万立方米/小时，开挖河道费用为5万元，修建新河道花费=60-5=55万元；2015年度开挖第3条河道，总流水量为175.43955万立方米/小时，开挖河道费用为6万元，修建新河道花费=167-120-6=41万元；2016年度为255.8724万立方米/小时。2017年度为240.7462万立方米/小时。该模型计划能够达到该乡政府的要求，而且能够较好的解决各村的“春旱夏涝”问题。4.2问题二：各村之间修建流水河道网络的合理方案 乡政府为拟建一个在各村之间互通的河道网络计划，其中村距离水库最近，且海拔地势最高，将水库中的水先通过河道引入村后，再经村引入其他村。通过分析讨论，我们利用最小生成树法来解决各个村庄之间互通的河道网络使河道最短且充分利用了海拔地势，从而使修建计划更加合理。表6：各村之间修建河道的距离相对应的权值村庄权值村01059121412161820村0091517818181422村000790712017村00003006018村000000012010村00111980814816村0001010008010村00000000012村001215140611018村0000000000根据表中权值，通过Matlab对其处理，再用最小生成树来求解河道网络从附录二中可得：result = 1 3 4 4 3 1 2 6 5 3 4 5 8 7 2 6 9 10 5 7 3 6 7 10 8 8 10用更为直观的网路图表示如下：各个村庄修建河道计划图及各村之间权值在问题二中乡镇府如图修建各村间的河道能是工程更加合理，减少对相应修建资源的浪费，并且能满足修建要求。4.3问题三：各村之间修建流水河道网络的合理方案及其最小费用 该乡镇地势西高东低，这水流只能从西流向东，从村庄排布图中可以看出村1毗邻水库且地势最高，有且只有修建河道先通过村1再通过村1引向各个村庄。考虑到将河道是否修建设为0-1变量易表示函数关系，故本文仍采用0-1规划模型。4.3.1模型的建立 所建立的变量关系式满足各村庄地势要求。因为从村A村B的新流水河道，一般要求能够满足村A及上游新流水河道的流水量，所以流出河道的可流水量之和应不小于流入河道的流水量及村A要求达到的100万立方米/小时的流水量之和，因此我们将在满足各村的最低要求的情况下进行建模，即各村的要求流水量都为100万立方米/小时。根据约束条件列出如下模型：目标函数：其中，由从A村到B村的河道要承载B村及下游的流水量，则=流入村河道的流量和+100，即为100万立方米/小时的整数倍。约束条件：4.3.2模型的求解使用Matlab R2010a求解，得到修建流水河道的最小费用合理方案，修建河道情况如下表： 流入流出123456789100000001020000100003000010000400010000050000100006000000001700000001080000000019000000001河道网络图如下：根据计算的最终费用为554.5356万元。五、模型的评价及推广5.1优点：1.对数据进行合理的处理，采用拟合的方法对数据间的关系进行图像化，使得其问题分析更加明显，简化。2将每个小问题的分析串联起来，使其思路更加清晰3由三年开挖流水河道和修建新河道方案设计的0-1规划模型，得到每年开挖排洪沟、修建新河道的具体计划及所需的最小费用。4可移植性强，对于类似的优化问题，只需在程序中输入数据，并用相同的规则判断，便可以容易得到结果，具有一定的推广性。5.2缺点：1由于新修建河道的长度默认为题设的20公里及100万立方米/小时，在建设完成的后两年，总的流水量远超过要求的180、190万立方米/小时，在一定程度上浪费了水资源。程设施量过大，在一定程度上加大了政府的开支，未能达到最优。2在问题二中，只考虑了路程的最短，而没有考虑到地理环境等因素，这样在一定程度上降低了模型的可行性。5.3、模型的推广1.模型的建立及求解过程中，考虑的约束条件相对不是很全面，如海拔高度差、各村庄干旱程度、农业灌溉面积、因地形地貌不同产生的流水速度的差异等。推广时，可以先对这些因素加以考虑，然后建立更加完善的模型；2.本模型是针对修建流水河道问题建立而成的。在保证解决“春旱夏涝”的预期前提下，使得费用最低，可以利用这类方法来解决运输、旅游等问题。参考文献1 姜启源，谢金鑫，叶俊数学建模（第四版），北京：高等教育出版社，2010。3谢金星，薛毅，优化建模与LINDOLINGO软件，清华大学出版社，2005。附录模型代码及结果：模型一：模型一代码：model:sets:he/1.8/:m,Q;time/1.3/:newhe;link(time,he):x;endsetsdata:Q=25,36,32,15,30,28,22,12;m=5,7,6,4,6,5,5,4;enddatamin=sum(link(i,j):x(i,j)*m(j)+134;!目标函数;newhe(1)+newhe(2)+newhe(3)=134;!三年新修河道用于修建费用的总和;for(time(i):sum(link(i