基于有上下界風(fēng)量約束的礦井風(fēng)量極值流算法研究*

尚文天，鄧立軍，劉 劍

(1.遼寧工程技術(shù)大學(xué) 安全科學(xué)與工程學(xué)院，遼寧 葫蘆島125105;2.遼寧工程技術(shù)大學(xué) 礦山熱動力災(zāi)害與防治教育部重點實驗室，遼寧 葫蘆島125105)

0 引言

在礦井通風(fēng)系統(tǒng)中，井巷風(fēng)速過高不僅會引起粉塵飛揚，危害作業(yè)人員健康，增加粉塵爆炸的可能性，同時使通風(fēng)阻力和礦井漏風(fēng)率加大，導(dǎo)致風(fēng)機耗電量增加，極大地增加了通風(fēng)成本[1-2]。而當風(fēng)速過低時又會無法滿足工作地點通風(fēng)量需求，及時稀釋、排出有害氣體等，甚至還可能導(dǎo)致瓦斯積聚，引起瓦斯爆炸和火災(zāi)事故[3]。《煤礦安全規(guī)程》對于不同類型井巷的風(fēng)速上限與下限作出了明確規(guī)定[4]。因此，礦井的總風(fēng)量也存在上限與下限，該上限為最大通風(fēng)量，下限為最小配風(fēng)量。

全礦最小配風(fēng)量與最大通風(fēng)量是礦井設(shè)計與生產(chǎn)系統(tǒng)改造的重要參數(shù)[4]。當最小配風(fēng)量與最大通風(fēng)量比較接近時，說明該通風(fēng)系統(tǒng)的設(shè)計比較經(jīng)濟，但擴大生產(chǎn)的潛力??；當最小配風(fēng)量與最大通風(fēng)量相差較大時，說明該通風(fēng)系統(tǒng)有較大的改造潛力[5]。但是在實際礦井通風(fēng)設(shè)計中，礦井總需風(fēng)量只是簡單地將各用風(fēng)地點需風(fēng)量線性求和，按照“由里至外”原則分配各巷道風(fēng)量。這一方法仍存在著工作面供風(fēng)量不能滿足需風(fēng)量要求的問題[6]，并且部分巷道的風(fēng)速可能無法滿足《煤礦安全規(guī)程》對巷道最低風(fēng)速的要求。

國內(nèi)外學(xué)者針對最大流算法的研究已經(jīng)比較成熟，一類是增廣路徑算法，另一類是預(yù)流推進算法[7]。很多學(xué)者也提出了其他改進算法，江錦成等提出的SAPR算法是在預(yù)流推進算法的基礎(chǔ)上提出的自適應(yīng)算法，具有很強的適應(yīng)性和穩(wěn)定性，為高效求解網(wǎng)絡(luò)最大流的研究提供了一種新思路[8]；趙禮峰等提出了1種增廣鏈修復(fù)算法，該算法能夠計算更大規(guī)模的網(wǎng)絡(luò)，并高效地處理一類稀疏網(wǎng)絡(luò)[9]；劉劍等提出的利用找獨立通路的思想來找增廣路在程序思想的簡潔性與運算量上都遠優(yōu)于經(jīng)典算法[10]；羅甜甜等提出了在最短增廣鏈算法基礎(chǔ)上根據(jù)相應(yīng)規(guī)則來選取增廣鏈的算法，可以保證最短增廣鏈優(yōu)先選取，增加了算法的準確性與高效性[11]；杜政均針對大規(guī)模網(wǎng)絡(luò)提出了Sense-Push算法，是1種最大流并行化算法，極大地提高了數(shù)據(jù)處理效率[12]。但是，采用最大流算法求最大通風(fēng)量只考慮井巷的最高風(fēng)速作為分支容量上界，忽略了井巷的最低風(fēng)速限制，最終得到的最大總通風(fēng)量無法保證所有巷道都滿足《煤礦安全規(guī)程》規(guī)定的最低風(fēng)速。而關(guān)于礦井最小配風(fēng)量的計算，仍未存在正確有效的算法。

本文針對礦井通風(fēng)系統(tǒng)的最大通風(fēng)量和最小配風(fēng)量問題，提出1種基于有上下界風(fēng)量約束的極值流算法。即采用圖論數(shù)學(xué)方法，先將礦井的巷道和交叉口抽象為有向圖網(wǎng)絡(luò)模型，依據(jù)《煤礦安全規(guī)程》與《煤礦通風(fēng)能力核定標準》[13]，確定分支風(fēng)量上界與風(fēng)量下界約束，將求礦井最大通風(fēng)量、最小配風(fēng)量問題轉(zhuǎn)換為有上下界風(fēng)量約束的最大流和最小流問題并進行求解。

1 井巷最大、最小風(fēng)量約束

井巷最大、最小風(fēng)量約束要綜合考慮《煤礦安全規(guī)程》第101條與第110條規(guī)定的井巷最高風(fēng)速、最低風(fēng)速以及各用風(fēng)地點實際需風(fēng)量等因素。最大風(fēng)量約束由井巷最高風(fēng)速來確定，最小風(fēng)量約束則取井巷最低風(fēng)速、各用風(fēng)地點實際需風(fēng)量的最大值[14]。

《煤礦通風(fēng)能力核定標準》AQ 1056—2008對各用風(fēng)地點需風(fēng)量的計算方法作出了相關(guān)規(guī)定，以采煤工作面為例，計算出采煤工作面的最大、最小風(fēng)量約束。取上述計算風(fēng)量中最大者作為采煤工作面的最小風(fēng)量約束，如式(1)所示：

qcfmin=max {qcf1,qcf2,qcf3,qcf4,qcf5,qcf6}

(1)

式中：qcfmin為采煤工作面的最小風(fēng)量，m3/min；qcf1為按采煤工作面氣象情況計算得出的最小風(fēng)量，m3/min；qcf2為按采煤工作面的瓦斯涌出量取采煤工作面不均衡通風(fēng)系數(shù)最小值計算得出的最小風(fēng)量，m3/min；qcf3為按采煤工作面二氧化碳涌出量計算得出的最小風(fēng)量，m3/min；qcf4為按炸藥量計算得出的最小風(fēng)量，m3/min；qcf5為按現(xiàn)場最多作業(yè)施工人數(shù)計算得出的最小風(fēng)量，m3/min；qcf6為按風(fēng)速進行驗算得出的最小風(fēng)量，m3/min。

最大風(fēng)量約束由井巷的最高風(fēng)速來確定?！睹旱V通風(fēng)能力核定標準》也作出了相關(guān)規(guī)定，仍以采煤工作平面為例列出相關(guān)計算公式，如式(2)所示：

qcfmax≤60×4.0×Scs

(2)

式中：qcfmax為按風(fēng)速進行驗算得出的采煤工作面的最大風(fēng)量，m3/min；Scs為采煤工作面最小控頂有效斷面積，m。

其他巷道及用風(fēng)地點的最小風(fēng)量、最大風(fēng)量計算方法均可以此類推。

2 基于有上下界風(fēng)量約束的極值流算法

基于文獻[15]與[16]提出1種基于有上下界風(fēng)量約束的極值流算法，彌補文獻[5]求解最大流過程中忽略了分支容量下界與最小流計算方法，只適用于部分網(wǎng)絡(luò)的缺陷，算法的具體流程如圖1所示。

圖1 基于有上下界風(fēng)量約束的極值流算法流程Fig.1 Flow chart of extreme flow algorithm based on upper and lower bound air volume constraints

2.1 有源匯的有上下界流網(wǎng)絡(luò)定義

與傳統(tǒng)最大流問題的流網(wǎng)絡(luò)定義不同，有上下界流網(wǎng)絡(luò)中分支的流量不只是簡單的大于等于0，而是大于等于某一個下界。單一源匯流網(wǎng)絡(luò)G=(V,E)，其源匯點分別為s和t，E中的每條分支(u,v)都有容量下界b(u,v)≥0和容量上界c(u,v)≥0限制，且每條分支(u,v)給定1個流量值f(u,v)，如果f滿足以下2個條件，則稱f是G的1個可行流[15]。

2)容量限制條件：E中的任意1條分支(u,v)都滿足b(u,v)≤f(u,v)≤c(u,v)。

2.2 有上下界流網(wǎng)絡(luò)的可行流

根據(jù)文獻[15]，為求得可行流或者指出這樣的可行流不存在，便要根據(jù)計算原流網(wǎng)絡(luò)的無上下界等效流網(wǎng)絡(luò)G′(V′,E′)的最大流進行判斷。為解決等效流網(wǎng)絡(luò)因不存在容量上下界而導(dǎo)致其不滿足流量平衡與容量限制條件，保證等效流網(wǎng)絡(luò)的最大流f′(u,v)與原流網(wǎng)絡(luò)的可行流f(u,v)滿足關(guān)系式(3)：

f(u,v)=f′(u,v)+b(u,v)

(3)

應(yīng)對等效流網(wǎng)絡(luò)G′作如下定義：

1)G′的節(jié)點集合V′除包含原流網(wǎng)絡(luò)節(jié)點集合V中的所有節(jié)點外，再添加附加源點s′與附加匯點t′作為與不平衡節(jié)點相連分支的源匯點，即V′=V∪{s′,t′}。

2)G′的分支集合E′包含下列分支：

①原流網(wǎng)絡(luò)分支集合E中的所有分支。這些分支的容量取c′(u,v)，即滿足公式(4)：

c′(u,v)=c(u,v)-b(u,v)

(4)

②1條匯點t至源點s的新分支(t,s)，該分支容量設(shè)為+∞。

③為處理容量下界條件b(u,v)，根據(jù)下列方法遍歷所有節(jié)點后建立的新分支。

用m(i)表示原流網(wǎng)絡(luò)中任意節(jié)點i流入的下界總和減去流出的下界總和，即公式(5)：

(5)

根據(jù)m(i)的不同，分支的建立方式也不同，具體方式如下：

A.當m(i)=0時，表示流入的下界總和等于流出的下界總和，節(jié)點處流量平衡，無需建立新分支。

B.當m(i)>0時，表示流入的下界總和大于流出的下界總和，故要將流入的多余流量m(i)用其他分支流入該節(jié)點。利用附加源點s′建立分支(s′,i)，其分支容量設(shè)為c′(s′,i)=m(i)。

C.當m(i)<0時，表示流入的下界總和小于流出的下界總和，故要將流出的多余流量m(i)用其他分支流出該節(jié)點。利用附加源點t′建立分支(i,t′)，其分支容量設(shè)為c′(i,t′)=-m(i)。

以上便是等效流網(wǎng)絡(luò)的定義，其示意如圖2所示。

圖2 等效網(wǎng)絡(luò)示意Fig.2 Equivalent network diagram

再通過已經(jīng)成熟和完善的最大流算法[7]計算G′最大流f′，根據(jù)等效流網(wǎng)絡(luò)的定義，其中與原流網(wǎng)絡(luò)相同分支的f′(u,v)要滿足無上下界的容量限制與流量平衡條件，故應(yīng)符合公式(6)，(7)：

0≤f′(u,v)≤c′(u,v)

(6)

(7)

通過公式(3)，(4)，(6)可推出b(u,v)≤f(u,v)≤c(u,v)，即f(u,v)滿足流量平衡條件。

故可根據(jù)附加源點s′流出或流入附加源點t′的分支是否都達到飽和進行判斷，有以下2種情況：

1)附加源點s′流出或流入附加源點t′的分支都達到飽和，滿足容量限制與流量平衡條件，原流網(wǎng)絡(luò)G中存在可行流，即在G′最大流為f′時，根據(jù)公式(4)求得每條分支上的可行流f(u,v)。

2)附加源點s′流出或流入附加源點t′的分支未都達到飽和，只滿足容量限制條件，原流網(wǎng)絡(luò)G中不存在可行流。

存在可行流的情況下，等效流網(wǎng)絡(luò)的分支(t,s)上的流量為原流網(wǎng)絡(luò)可行流總流量的值?？尚辛鳚M足并不是一定最小流、也不一定是最大流，只能保證每條分支的流量滿足其容量上下界要求。

2.3 有上下界流網(wǎng)絡(luò)的最大流

可行流流量一定在上下界中，但是可能存在可增加的流量，這些流量存在于每條分支容量上界大于可行流流量的部分中。故可通過建立殘留網(wǎng)絡(luò)，即將原流網(wǎng)絡(luò)的分支容量改為容量上界與可行流流量的差，即殘留容量。再求其最大流，得到的最大流為增廣最大流，再將其與原流網(wǎng)絡(luò)的可行流相加，即為原流網(wǎng)絡(luò)的最大流即礦井的最大通風(fēng)量。具體步驟如下：

1)建立殘留網(wǎng)絡(luò)G殘(V,E)，用c殘(u,v)表示殘留網(wǎng)絡(luò)分支容量，如式(8)所示：

c殘(u,v)=c(u,v)-f′(u,v)

(8)

2)對殘留網(wǎng)絡(luò)G殘進行1次最大流計算，計算得出其每條分支的增廣最大流量為f殘(u,v)。

3)計算原流網(wǎng)絡(luò)G最大流的分支流量，用fmax(u,v)表示原流網(wǎng)絡(luò)G處于最大流情況下分支(u,v)的流量值，如式(9)所示：

fmax(u,v)=f′(u,v)-f殘(u,v)

(9)

4)計算原流網(wǎng)絡(luò)G的最大流，用Fmax(G)表示原流網(wǎng)絡(luò)G處于最大流情況下的總流量值，如式(10)所示：

(10)

2.4 有上下界容量限制下網(wǎng)絡(luò)的最小流

可行流流量除可能存在可增加的流量外，也可能存在可減少的流量，這些流量存在于每條分支可行流流量大于容量下界的部分中。故可通過建立反轉(zhuǎn)殘留網(wǎng)絡(luò)，即使原流網(wǎng)絡(luò)分支反轉(zhuǎn)，其分支容量改為可行流流量與容量下界的差，即反轉(zhuǎn)殘留容量。再對其求最大流，得到的最大流為消減最大流，再用原流網(wǎng)絡(luò)的可行流減去消減最大流，即為原流網(wǎng)絡(luò)的最小流即礦井的最小配風(fēng)量。具體步驟為：

1)建立反轉(zhuǎn)殘留網(wǎng)絡(luò)G反(V,E)，反轉(zhuǎn)流網(wǎng)絡(luò)G的流向，用c反(v,u)表示殘留網(wǎng)絡(luò)分支容量，如式(11)所示：

c反(v,u)=f′(u,v)-b(u,v)

(11)

2)對反殘留網(wǎng)絡(luò)G反進行1次最大流計算，計算得出其每條分支的消減最大流為f反(v,u)。

3)計算原流網(wǎng)絡(luò)G最小流的分支流量，用fmin(u,v)表示原流網(wǎng)絡(luò)G處于最小流情況下分支(u,v)的流量值，如式(12)所示：

fmin(u,v)=f′(u,v)-f反(v,u)

(12)

4)計算原流網(wǎng)絡(luò)G的最小流，用Fmin(G)表示原流網(wǎng)絡(luò)G處于最小流情況下的總流量值，如式(13)所示：

(13)

3 實例分析

3.1 可行流計算

以文獻[5]中的通風(fēng)網(wǎng)絡(luò)為例，如圖3所示，源點和匯點分別為V1和V10，分支的容量上、下界見表1。

圖3 13分支通風(fēng)網(wǎng)絡(luò)Fig.3 Thirteen edges ventilation network

表1 通風(fēng)網(wǎng)絡(luò)分支的容量上、下界Table 1 The upper and lower bounds of edges capacity inventilation network

先計算該通風(fēng)網(wǎng)絡(luò)的可行流，按照前文的方法添加1條由匯點t至源點s的新分支(t,s)，該分支容量設(shè)為無窮大+∞。等效流網(wǎng)絡(luò)包含的原流網(wǎng)絡(luò)分支的容量為原容量上界減去下界。構(gòu)造等效流網(wǎng)絡(luò)添加附加源s′和附加匯t′。根據(jù)任意節(jié)點i流入下界總和減去流出下界總和的值m(i)添加新分支(s′,i)或(i,t′)，所有節(jié)點的m(i)通過計算添加的分支及其容量、飽和狀態(tài)見表2，可知所有從附加源點s′流出或流入附加匯點t′的分支均達到飽和，因此，原流網(wǎng)絡(luò)存在可行流，可行流分配結(jié)果見表3。

表2 原流網(wǎng)絡(luò)分支的容量下界Table 2 The lower bound of the capacity of the edges of the original stream network m3/s

表3 通風(fēng)網(wǎng)絡(luò)可行流分配結(jié)果Table 3 The feasible flow distribution results of the ventilation network

以上過程所建立的等效流網(wǎng)絡(luò)與求解出的原流網(wǎng)絡(luò)可行流風(fēng)量分配結(jié)果如圖4所示，可看出等效流網(wǎng)絡(luò)與原流網(wǎng)絡(luò)中任意節(jié)點的流入量與流出量保持等效。

圖4 求解原流網(wǎng)絡(luò)可行流風(fēng)量分配Fig.4 Seeking the feasible flow air volume distribution of the original flow network

3.2 最大流計算

建立殘留網(wǎng)絡(luò)，即原流網(wǎng)絡(luò)的分支容量改為容量上界與可行流的差c殘(u,v)。殘流網(wǎng)絡(luò)所有分支的容量、最大流算法求解后的流量以及飽和狀態(tài)見表4。將殘留網(wǎng)絡(luò)的最大流與原流網(wǎng)絡(luò)可行流相加，即為原流網(wǎng)絡(luò)的最大流。根據(jù)其源匯點的流出與流入值，可得通風(fēng)網(wǎng)絡(luò)最大流的流量值為55，即該礦井的最大通風(fēng)量為55 m3/s。

表4 殘留網(wǎng)絡(luò)的分支容量Table 4 Edges capacities of residual network

以上過程所建立的殘留網(wǎng)絡(luò)與求解出的原網(wǎng)絡(luò)最大流如圖5所示，可以看出殘留網(wǎng)絡(luò)中源匯點之間存在通路，故可使用最大流方法對其求解，求解結(jié)果即為增廣最大流。

圖5 求解原流網(wǎng)絡(luò)最大流風(fēng)量分配Fig.5 Seeking the distribution of maximum air flow in the original flow network

3.3 最小流計算

建立反轉(zhuǎn)殘留網(wǎng)絡(luò)，即原流網(wǎng)絡(luò)的分支容量改為可行流與容量下界的差c反(v,u)，并使原流網(wǎng)絡(luò)分支反轉(zhuǎn)。反轉(zhuǎn)殘流網(wǎng)絡(luò)所有分支的容量、最大流算法求解后的流量以及飽和狀態(tài)見表5。根據(jù)其源匯點的流出與流入值，可得通風(fēng)網(wǎng)絡(luò)最小流的流量值為50，即該礦井的最小配風(fēng)量為50 m3/s。

表5 反轉(zhuǎn)殘留網(wǎng)絡(luò)的分支容量Table 5 Edges capacities of reversal residual network

以上過程所建立的反轉(zhuǎn)殘留網(wǎng)絡(luò)與求解出的原網(wǎng)絡(luò)最小流見圖6，可看出反轉(zhuǎn)殘留網(wǎng)絡(luò)中源匯點之間無通路，故其最大流量一定為0，故不存在消減最大流。

圖6 求解原流網(wǎng)絡(luò)最小流風(fēng)量分配Fig.6 Seeking the distribution of minimum air flow in the original flow network

4 結(jié)論

1)提出的基于有上、下界風(fēng)量約束的礦井風(fēng)量極值流算法，改進了文獻[5]分支分配到的流量不一定在上、下界約束內(nèi)、最小流的計算方法應(yīng)用范圍小的弊病。不僅可以計算出流網(wǎng)絡(luò)的極值流，還可以求出其中每個分支的流量分配情況。并且通過增加分支容量上、下界約束，使求得的極值流滿足所有分支分配到的流量都在容量的上、下界約束內(nèi)。

2)通過實例驗證，本文提出的計算方法在滿足上、下界限制的可行流基礎(chǔ)上通過分別向容量上、下界逼近得出最大流與最小流，故可保證求得的最大流與最小流都同時滿足上、下界限制。

3)基于有上、下界風(fēng)量約束的極值流算法可應(yīng)用于礦井通風(fēng)系統(tǒng)，準確地求解出礦井通風(fēng)系統(tǒng)的最大、最小通風(fēng)量，并給出分配方案，在保證安全的前提下，減少開支，增大收益。還可以使用本算法評定礦井通風(fēng)系統(tǒng)的經(jīng)濟性與礦井改造潛力，為礦井改造方案提供依據(jù)。本算法除應(yīng)用于礦井通風(fēng)系統(tǒng)外，還可以應(yīng)用其他需要上、下界容量限制的流體網(wǎng)絡(luò)，如電路分支上有用電元件的電路網(wǎng)絡(luò)等。