運籌學在燃氣行業的應用

朱凱敏 霍小亮

(1.中國市政工程西南設計研究總院有限公司，四川成都 610081;2.晉能燃氣集團有限公司，山西太原 030002)

運籌學(Operations Research)是一門管理有組織系統的科學，它通過建立數學模型，運用規劃論、存儲論、排隊論、圖論與網絡分析等數學方法，對作業合理安排，以達到經濟有效地利用資源［1］。運籌學研究的系統難以采用試驗的方法，而必須依賴數學模型。燃氣行業中諸如生產物資調運，運營線路選擇，輸配系統優化［3］、最大輸氣能力分析及最短敷管路由等問題也難以搬進實驗室，常不得已而采用經驗或保守決策，造成管理的粗放和資源的浪費。本文將以氣源調度最低運行成本、巡線最短重復路徑、輸配系統最大流三個具體問題，介紹運籌學方法在燃氣行業的應用。

1 物資調配運輸

物資調運成本取決于供應方、運輸方式、運距和運輸成本等因素。如制管廠向不同分廠的任務分配和鋼板廠的鋼板供應，又如管道工程中鋼管與防腐管的調運等［4］，再如燃氣管網的氣源調度。這些物資調運問題均能通過建立線性規劃模型，尋求最優調運組合方式，并通過“敏感性報告”分析變量對最優組合的影響。

問題:某市的三個區Bj(j=1，2，3)年需天然氣320個單位、250個單位和350個單位，由已簽訂照付不議協議的Ai(i=1，2)兩門站供應，其最大年供應量分別為400個和450個單位，Ai門站供應Bj區的單位成本詳見表1。由于供不應求，決定B1發展0個～30個單位用氣量的可中斷用戶，保證B2，B3供應量不低于270個單位，求供應無過剩時輸送成本最低的氣源調度方案。

表1 天然氣供需量和單位天然氣的輸送成本

解:設Xij為Ai門站輸往Bj的氣量，則最低輸送成本的目標函數:MinZ=15×X11+18×X12+22×X13+21×X21+25×X22+16×X23;

需滿足的約束條件:1)輸往B1的約束條件:290≤X11+X21≤320;2)輸往B2的約束條件:X12+X22=250;3)輸往B3的約束條件:270≤X13+X23≤350;4)門站 A1供應量的約束條件:X11+X12+X13≤400;5)門站 A2供應量的約束條件:X21+X22+X23≤450;6)供應無過剩的約束條件:X11+X12+X13+X21+X22+X23≥850。借助Excel的“規劃求解”工具可求得最低輸送費用為14 650，Xij值詳見表2。燃氣的物資調運問題還可運用運籌學的“表上作業法”(如最小元素法、西北角法)求解，因其步驟晦澀難懂，這里不再贅述，讀者可參閱文獻［1］［2］學習。

2 中國郵路問題

“中國郵路問題”指郵差從郵局出發并走遍所負責的街道去送信后返回郵局，如何可使重復的路徑最短。燃氣巡線、用戶安檢與抄表、瓶裝氣供應站的氣罐配送等均可轉化為中國郵路問題，并借圖論與網絡分析的“奇偶點圖上作業法”選取最短重復路徑。

問題:巡線工從輸配所m出發，巡檢圖1(其上數字為道路長度)的13條道路上的燃氣管線后，返回m。自然地，若要完成巡線任務，則至少應走過每條街道一次，問何種走法總行程最短。

圖1 巡線路網圖

求解該問題前先認識圖論與網絡分析的幾個概念和尋優的思路。奇點:圖G中，以V為端點的邊數為奇數條時，則V點為奇點;初等圈:圖G中，某個圈既無重復點也無重復邊者為初等圈;歐拉圖:若存在一條回路，經過每邊一次且僅一次，則稱該回路為歐拉回路;具有歐拉回路的圖稱為歐拉圖，圖G是歐拉圖的充要條件是圖G中無奇點。

實際路網形成的圖G中存在T字路口、斷頭路等奇點，因此存在重復行走的路段。“奇偶點圖上作業法”尋最短重復路徑的原理是在兩兩奇點之間構造重復邊以消除奇點，從而將圖G轉化為歐拉圖，新增的重復邊就表示重復走過的路段。當構造的重復邊滿足以下條件時，重復的路徑最短:條件A，每條邊最多重復一次;條件B，圖G中每個初等圈，重復邊的長度不超過圈長的一半。

解:第1步:定初始可行方案。

圖1存在b，u，y，m四奇點，因此不是歐拉圖。將b與y配對作b-c-w-v-y重復邊，u與m配對作u-v-w-m重復邊，所構造的歐拉圖如圖2a)所示，其含重復邊在內的任一歐拉回路均為可行方案，但非最短重復路徑，此時重復邊的總長為:Lbc+Lcw+Luv+2Lvw+Lwm+Lvy=24。

第2步:調整可行方案，使重復邊最多為一次以滿足“條件A”。去除(v，w)重復兩次的邊，調整為圖2b)，重復邊的總長降為:Lbc+Lcw+Luv+Lwm+Lvy=20。

第3步:逐個檢查初等圈，使其滿足“條件B”。

初等圈“b-c-w-v-b”中，圈總長為15，而重復邊的總長為8，大于該圈總長度的一半，作重復邊(b，v)，(v，w)代替(b，c)，(c，w)，調整為圖2c)，重復邊總長降為:Lbv+Lvw+Luv+Lwm+Lvy=19。同理，對初等圈“u-v-b-a-u”調整為圖2d)，此時所有初等圈均滿足“條件B”，重復邊總長為 Lab+Lvw+Lau+Lwm+Lvy=18。“m-w-vw-c-b-a-b-v-u-a-u-x-y-v-y-z-w-m”或“m-w-z-y-v-w-c-b-v-u-a-b-a-u-xy-v-w-m”等任一歐拉回路均為最短重復路徑。

圖2“奇偶點圖上作業法”尋優過程

3 管網最大流問題

問題:圖3為以vs為起點的某中壓輸氣管網，已知管道扣除途泄流量后的轉輸流量和流向如圖3數字和箭頭所示，現探討該管網經終點vt向相鄰中壓管網的應急供氣能力，即最大轉輸量。

圖3 中壓輸氣管網簡圖

圖4 初始可行流

上述管網的流量滿足以下三個條件，則是可行流:1)每條邊(vi，vj)的流量fij不超過各自的容量cij;2)源點輸出的量等于匯點輸入的量;3)中間點流入流出平衡。

定義μ為圖G中方向從vs到vt的一條鏈，μ上的邊與μ同向則稱為前向邊，反向則為后向邊，其集合分別用μ+和μ-表示，可行流f如滿足，則稱μ為從vs到vt的(關于f)的可增廣鏈。可增廣鏈意味著沿該鏈從vs輸送到vt的流f未飽和。故求最大流的方法為:尋找并調整可行流的可增廣鏈，每次調整之后的流量f'均比原來的可行流f要大，重復幾次直到不存在關于該流的可增廣鏈時就得到了最大流。

圖5“標號算法”求解過程

下面介紹用“標號算法”求取管網最大流的方法，標號過程中每條邊上的有序數表示(cij，fij)。

第1步:標號過程，用以尋找可增廣鏈。

1)給發點 vs標號(Δ，+∞);

2)選擇一個已標號的點vi，對于vi所有未標號的鄰接點vj用以下方式標號:a.若邊(vi，vj)為后向邊，且 fij＞0，則令 δj=min(fij，δi)，并給 vj以標號(-vi，δj);b.若邊(vi，vj)為前向邊，且 fij＜cij，則令 δj=min(cij-fij，δi)，并給 vj以標號(+vi，δj)。

3)重復步驟2)直到收點vt被標號或不再有頂點可標號時為止。若vt得到標號，說明找到一條可增廣鏈，轉第2步調整過程;若vt未得到標號，標號過程已無法進行時，說明f已是最大流。

第2步:調整過程，用以沿可增廣鏈調整f以增加流量。

2)去掉所有標號，回到第1步，對可行流f'重新標號。

解:1)因總存在可行流(如0流)，定義一個如圖4所示的初始可行流，其轉輸能力為6;2)按標號算法的第1步進行第一次標號，結果如圖5a)所示，由于vt被標號，說明存在可增廣鏈，由標號從后往前找到可增廣鏈為“vs-v1-v4-vt”;3)按標號算法的第2步對可增廣鏈“vs-v1-v4-vt”進行第一次調整后，其轉輸能力增至7，結果如圖5b)所示;4)按標號算法的第1步進行第2次標號，找到可增廣鏈為“vs-v3-v4-vt”，結果如圖5c)所示;5)按標號算法的第2步對可增廣鏈“vs-v3-v4-vt”進行第二次調整后，其轉輸能力增至9，結果如圖5d)所示。此時f4t，f5t均已達到各自容量 c4t，c5t，進行第3次標號時vt不可能獲得標號，說明已不存在可增廣鏈，因此管網的最大轉輸能力為9。

4 結語

隨著精益管理要求的提出以及越來越多的燃氣管理和運營人員參與運籌學等管理學科的學習，相信運籌學的方法和理念將會逐步融入到燃氣工程建設和運營管理中來，為企業提供更科學的決策依據。

［1］胡運權，郭耀煌.運籌學教程［M］.第3版.北京：清華大學出版社，2007.

［2］藍伯雄.管理數學(下)——運籌學［M］.北京：清華大學出版社，2003.

［3］李書波，仙立東.運籌學在燃氣輸配系統中的應用［J］.系統工程理論與實踐，1997(6)：135-138.

［4］田進波，李雪松，邢俊強.運籌學在管道物流管理中的應用［J］.石油工程建設，2010(36)：153-154.

［5］陳御釵，王建洲.運籌學在化工企業中的應用［J］.廣東化工，2007，34(10)：128-131.