魏寶成，袁一星，郭爽
（哈爾濱工業(yè)大學(xué)給水排水系統(tǒng)研究室）

　　摘要：本文介紹了給水管網(wǎng)水力模擬計(jì)算的算法，以及提高水力模擬計(jì)算軟件計(jì)算速度的方法。
　　關(guān)鍵詞：給水管網(wǎng)；水力模擬

Optimization of Simulation Algorithm in Water Supply Network
Wei baocheng, Yun yixing, Guo Shuang
(Workgroup of Water & Wastewater System, Harbin Institute of Technology)

　　Abstract: This paper describes the algorithm of water supply net1work simulation and the method to accelerate the calculation of water supply network simulation software.
　　Key words: water supply network; hydraulic simulation

　　在供水綜合管理信息系統(tǒng)中，供水管網(wǎng)的水力模擬計(jì)算軟件處在一個(gè)非常關(guān)鍵的位置，是整個(gè)系統(tǒng)的“核心”所在。
　　由于城市規(guī)模的擴(kuò)大，供水管網(wǎng)的規(guī)模也越來(lái)越大，管網(wǎng)計(jì)算的運(yùn)算量也越來(lái)越大，以往的計(jì)算程序在計(jì)算幾十個(gè)節(jié)點(diǎn)的管網(wǎng)時(shí)還能勝任，而當(dāng)進(jìn)行幾百、幾千、甚至上萬(wàn)個(gè)節(jié)點(diǎn)的大規(guī)模管網(wǎng)時(shí)，其速度就變得無(wú)法令人忍受。另外在現(xiàn)代數(shù)學(xué)中，有很多優(yōu)化理論，單從理論本身出發(fā)是可以應(yīng)用于供水管網(wǎng)的優(yōu)化計(jì)算、實(shí)時(shí)調(diào)度方面，但由于管網(wǎng)信息量大，管網(wǎng)模擬計(jì)算軟件的速度較慢，進(jìn)行一次計(jì)算，往往需要幾個(gè)小時(shí)、幾天，這樣的計(jì)算結(jié)果對(duì)指導(dǎo)實(shí)踐是沒(méi)有實(shí)際意義的，因此提高供水管網(wǎng)水力計(jì)算的速度是一個(gè)重要的課題。

1、理論基礎(chǔ)

　　對(duì)給水管網(wǎng)進(jìn)行水力模擬總是聯(lián)立求解連續(xù)性方程、能量方程和壓降方程。其中解節(jié)點(diǎn)方程是聯(lián)立壓降方程和連續(xù)性方程，是現(xiàn)在多數(shù)水力計(jì)算程序采用的算法。
　　所謂連續(xù)性方程，就是對(duì)任一節(jié)點(diǎn)來(lái)說(shuō)，流向該節(jié)點(diǎn)的流量必須等于從該節(jié)點(diǎn)流出的流量。

　　　　　Q_i+Σq_ij=0

將管段的壓降方程代入連續(xù)性方程，則任意一個(gè)節(jié)點(diǎn)的連續(xù)性方程可寫成：

　　

　　式中指數(shù)α=0.54，Ｍ為節(jié)點(diǎn)數(shù)(不包括已知節(jié)點(diǎn))，q_i為節(jié)點(diǎn)流量(m³/s)。式中l(wèi)表示管段號(hào)，i,j表示管段l的上下游節(jié)點(diǎn)標(biāo)號(hào)，所謂上下游是這樣規(guī)定的，管段l的計(jì)算流向（參考流向）是從節(jié)點(diǎn)i流向節(jié)點(diǎn)j的。
　　這是一個(gè)非線形方程組，不能直接得到其解析解。解非線形方程組比較困難，方法有多種，比較常用的是牛頓-拉斐森方法。
記E為以E_i為分量的向量，f為以f_i分量的向量，在E的領(lǐng)域內(nèi)可進(jìn)行泰勒級(jí)數(shù)展開：

　　

　　偏導(dǎo)數(shù)構(gòu)成的矩陣是雅可比(Jacobian)矩陣J

　　

　　可以得到：

　　

　　

　　忽略高階項(xiàng)，并置F(E+δE)=0,將可得到一個(gè)關(guān)于修正項(xiàng)δE的線性方程組。即

　　　　J·δE=-F

　　其中δE可使每個(gè)函數(shù)都同時(shí)接近于零。
　　整個(gè)這一過(guò)程就是非線形方程組的“線形化”過(guò)程，可變化成解一個(gè)線性方程組，并將求出的修正項(xiàng)加到解向量中：

　　　　E_new=E_old+δE

　　這個(gè)過(guò)程不斷迭代，直到收斂為止。

2算法的優(yōu)化

2.1系統(tǒng)選用了高效的算法
　　1.牛頓法雖然已經(jīng)不能算是一個(gè)新算法，但它在收斂速度上有著無(wú)可比擬的優(yōu)勢(shì)，并且后面我們提到，可以對(duì)它適當(dāng)改造，來(lái)克服它自身的缺點(diǎn)。
　　2.改進(jìn)平方根法是解線性方程組直接解法中速度最快的一種，由于其很好的利用了連續(xù)性方程雅可比矩陣的性質(zhì)，使它在求解這一方程時(shí)，具有很高的效率，其求解效率幾乎是高斯法的兩倍，并且可以很好的與數(shù)據(jù)壓縮算法共同工作。
　　3.共軛梯度法是是解線性方程組迭代解法中較好的一種，其算法穩(wěn)定收斂快，并且可以進(jìn)一步節(jié)省內(nèi)存，當(dāng)管網(wǎng)的規(guī)模超大，直接解法不能運(yùn)算時(shí)，它是一種很好的補(bǔ)充；在一般規(guī)模的管網(wǎng)下，也可結(jié)合直接解法，使迭代的速度加快。
2.2牛頓步長(zhǎng)因子的改進(jìn)
　　牛頓法是求解非線形方程組的一個(gè)經(jīng)典方法，由于其收斂快，因此直到現(xiàn)在它仍然是一個(gè)重要方法，很多新的算法都是對(duì)它的改進(jìn)。但它的問(wèn)題也是很明顯的，就是當(dāng)初值選擇不好時(shí)，它有可能不收斂。而初值的選擇往往具有隨意性，這樣計(jì)算往往是發(fā)散的。
　　為解決這一問(wèn)題，迭代公式中加入步長(zhǎng)因子λ，這樣迭代公式就變成了

　　E_new=E_old+λδE

　　步長(zhǎng)因子λ控制迭代收斂的速度也影響著模型是否收斂，本文作者通過(guò)對(duì)步長(zhǎng)因子λ的處理使整個(gè)迭代過(guò)程即保證收斂而且收斂較快。
2.3數(shù)據(jù)的壓縮存儲(chǔ)
　　供水管網(wǎng)方程的連續(xù)性方程的雅可比矩陣的階數(shù)是很高的。計(jì)算數(shù)據(jù)占用的計(jì)算機(jī)內(nèi)存非常驚人的，如果不對(duì)雅克比矩陣進(jìn)行壓縮，可能將導(dǎo)致計(jì)算不能進(jìn)行。同時(shí)該矩陣具有對(duì)稱性、正定性、帶狀性、稀疏性的特點(diǎn)，進(jìn)行矩陣壓縮是可行的。通過(guò)對(duì)矩陣的壓縮也可使參與計(jì)算的數(shù)據(jù)量減小，從而提高計(jì)算的速度。作者采用的是一維變代寬存儲(chǔ)壓縮技術(shù)。
2.4優(yōu)化帶寬
　　用一維變帶寬算法存儲(chǔ)雅可比矩陣，矩陣的帶寬和節(jié)點(diǎn)的編號(hào)有關(guān)，管段的起止節(jié)點(diǎn)編號(hào)差越大，雅可比矩陣的半帶寬也越大，解方程組的效率也越低，如果帶寬太大而導(dǎo)致三角塊無(wú)法存儲(chǔ)，求解也就無(wú)法進(jìn)行。為了提高解方程的效率，在進(jìn)行節(jié)點(diǎn)編號(hào)時(shí)，要使節(jié)點(diǎn)差盡量的小。但如果這部分工作用手工完成，將花費(fèi)大量的精力。所以要采用自動(dòng)編號(hào)來(lái)對(duì)帶寬進(jìn)行優(yōu)化。
本文作者采用有限單元理論中的優(yōu)化編號(hào)方法，自動(dòng)進(jìn)行節(jié)點(diǎn)編號(hào)，對(duì)帶寬進(jìn)行優(yōu)化。使數(shù)據(jù)的存儲(chǔ)量變到最小，對(duì)提高計(jì)算速度起到十分明顯的作用。
2.5管網(wǎng)簡(jiǎn)化
　　前面提到供水管網(wǎng)連續(xù)性方程的階數(shù)是很高的，求解這一方程的計(jì)算量和階數(shù)的立方成正比，也就是說(shuō)如果管網(wǎng)中節(jié)點(diǎn)的個(gè)數(shù)增加到原來(lái)的2倍，其計(jì)算量幾乎增加到原來(lái)的8倍，因此如何能等效簡(jiǎn)化管網(wǎng)是一個(gè)非常有意義的課題。
　　1．支狀管網(wǎng)簡(jiǎn)化。供水管網(wǎng)中有許多支狀管網(wǎng)，根據(jù)流體力學(xué)的計(jì)算理論，這些管段完全可以簡(jiǎn)化掉，而且并不影響管網(wǎng)模擬計(jì)算的精度。
　　2．環(huán)狀管網(wǎng)簡(jiǎn)化。環(huán)狀管網(wǎng)簡(jiǎn)化比較復(fù)雜，會(huì)導(dǎo)致一定誤差。在允許誤差范圍內(nèi)簡(jiǎn)化環(huán)狀管網(wǎng)是一個(gè)很新的課題。國(guó)外有些研究單位可以將一個(gè)復(fù)雜管網(wǎng)簡(jiǎn)化到只有幾十個(gè)節(jié)點(diǎn)的程度，誤差還不大，這種技術(shù)主要應(yīng)用在優(yōu)化調(diào)度領(lǐng)域。
本文作者通過(guò)編寫計(jì)算機(jī)程序?qū)崿F(xiàn)了對(duì)管網(wǎng)數(shù)據(jù)自動(dòng)進(jìn)行支狀的簡(jiǎn)化。這種簡(jiǎn)化不影響計(jì)算結(jié)果，當(dāng)管網(wǎng)中支狀管數(shù)量較多時(shí)，通過(guò)這種處理后，水力模擬計(jì)算速度的提高是十分明顯的。
2.6管網(wǎng)數(shù)據(jù)檢查
　　平差計(jì)算時(shí)，錄入數(shù)據(jù)常常發(fā)生錯(cuò)誤，如編號(hào)錯(cuò)誤、遺漏節(jié)點(diǎn)管段等，這將直接直接影響導(dǎo)致網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的變化，當(dāng)網(wǎng)絡(luò)很復(fù)雜，查找錯(cuò)誤將變得很困難，因此編寫了自動(dòng)檢查錯(cuò)誤程序。
　　供水管網(wǎng)的拓?fù)浣Y(jié)構(gòu)是一張圖，用圖論中圖的遍歷算法可發(fā)現(xiàn)圖紙中拓?fù)浣Y(jié)構(gòu)的錯(cuò)誤。通常有兩條遍歷圖的路徑，深度優(yōu)先搜索和廣度優(yōu)先搜索。本文作者采用的是深度優(yōu)先搜索算法。
2.7數(shù)據(jù)結(jié)構(gòu)的優(yōu)化
　　進(jìn)行上訴算法的優(yōu)化必須以較好得數(shù)據(jù)結(jié)構(gòu)為基礎(chǔ)，作者編寫的計(jì)算程序中用面向?qū)ο虻木幊谭椒▽?duì)數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)了動(dòng)態(tài)描述。通過(guò)這種數(shù)據(jù)結(jié)構(gòu)的建立，可實(shí)現(xiàn)對(duì)數(shù)據(jù)的快速排序和查找，并能保證上訴優(yōu)化算法快速實(shí)現(xiàn)。
除此以外，計(jì)算程序中添加了計(jì)算結(jié)果的匯總分析功能，可生成詳盡的結(jié)果報(bào)告。

3計(jì)算結(jié)果檢驗(yàn)

3.1計(jì)算結(jié)果的正確性檢查
　　為驗(yàn)證計(jì)算結(jié)果的正確性，用3個(gè)相同的算例，不同的程序?qū)λM(jìn)行了計(jì)算，對(duì)計(jì)算結(jié)果進(jìn)行了比較，其計(jì)算結(jié)果符合的非常好。這3個(gè)算例，一個(gè)是自己設(shè)計(jì)的(53個(gè)節(jié)點(diǎn)，78條管段)；一個(gè)是公主嶺的管網(wǎng)(312個(gè)節(jié)點(diǎn)，386條管段)；一個(gè)是天津市供水管網(wǎng)(3435個(gè)節(jié)點(diǎn)，4498條管段)。選用的對(duì)比程序有3個(gè)，一個(gè)是LOOP(世界銀行貸款資助的軟件);一個(gè)是WM5(國(guó)外知名水力模擬軟件，全名WaterMan ver5.0);另外一個(gè)是國(guó)內(nèi)的一個(gè)優(yōu)秀計(jì)算軟件WQR。計(jì)算結(jié)果之間的差別是很小的，主要是選取有效數(shù)字位數(shù)不同或采用的計(jì)算公式不同造成的。

數(shù)據(jù) WQR WM5程序 Loop程序 小例子 0.1% 0.1% 0.4% 公主嶺管網(wǎng) 0.2% 0.2% 0.5% 天津管網(wǎng) 0.4% - -

3.2優(yōu)化編號(hào)的作用
　　對(duì)于前兩個(gè)算例，計(jì)算速度很難進(jìn)行比較，因?yàn)橛?jì)算的時(shí)間太短了，但采用共軛梯度法的計(jì)算程序，在管網(wǎng)規(guī)模不是很大時(shí)，其計(jì)算計(jì)算速度十分快，原因是方程階數(shù)低造成的管網(wǎng)初值與正確解比較接近，使共軛梯度法的收斂速度得到充分的發(fā)揮。管網(wǎng)規(guī)模擴(kuò)大時(shí)，由于LOOP和WM5都不能求解，所以只能與WQR程序進(jìn)行對(duì)比。計(jì)算天津管網(wǎng)，WQR程序需要150秒，而這個(gè)程序只需要22秒。速度的提升是明顯的，而且在理論上，管網(wǎng)的規(guī)模越大，其速度比將越大。

項(xiàng)目 優(yōu)化編號(hào)前 優(yōu)化編號(hào)后 計(jì)算時(shí)間 122 22

3.3支狀管網(wǎng)簡(jiǎn)化
　　支狀管網(wǎng)簡(jiǎn)化的效果根據(jù)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)的不同而不同。由于數(shù)據(jù)結(jié)構(gòu)的優(yōu)化，進(jìn)行簡(jiǎn)化的過(guò)程很短，對(duì)于天津這樣大型的管網(wǎng)花費(fèi)的時(shí)間在0.5秒左右。

數(shù)據(jù) 原計(jì)算節(jié)點(diǎn)數(shù) 簡(jiǎn)化后計(jì)算節(jié)點(diǎn)數(shù) 計(jì)算速度提高率 小例子 49 49 0 公主嶺管網(wǎng) 290 216 30% 天津管網(wǎng) 3435 2645 18.5%

　　支狀管網(wǎng)的簡(jiǎn)化可以進(jìn)一步縮小總帶寬，以天津管網(wǎng)為例，簡(jiǎn)化后其總帶寬由20萬(wàn)左右縮小為15萬(wàn)左右，使計(jì)算速度進(jìn)一步提高，由22秒減少到不到18秒。
3.4計(jì)算時(shí)間對(duì)比
　　通過(guò)對(duì)算法的多方面優(yōu)化，系統(tǒng)計(jì)算速度得到明顯的提高，與測(cè)試程序相比較其計(jì)算速度都有較大的優(yōu)勢(shì)。

數(shù)據(jù) 本程序 WQR程序 Loop程序 WM5程序 小例子 0.05 0.77 1.5 0.51 公主嶺管網(wǎng) 0.11 2.12 10 1.44 天津管網(wǎng) 17.93 150.22 - -

　　(以上測(cè)試均是在聯(lián)想Pentium 300內(nèi)存64M的筆記本計(jì)算機(jī)上完成的。)

---

作者簡(jiǎn)介：
魏寶成 講師 哈爾濱工業(yè)大學(xué)市政環(huán)境工程學(xué)院
通 訊 處： 150090 哈爾濱工業(yè)大學(xué)（二區(qū)）624#信箱
電話：0451-6282281
Email:wbc@mail.hrbucea.edu.cn