朱凱敏 霍小亮

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

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

1 物資調(diào)配運輸

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

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

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

解:設(shè)Xij為Ai門站輸往Bj的氣量，則最低輸送成本的目標(biāo)函數(shù):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供應(yīng)量的約束條件:X11+X12+X13≤400;5)門站 A2供應(yīng)量的約束條件:X21+X22+X23≤450;6)供應(yīng)無過剩的約束條件:X11+X12+X13+X21+X22+X23≥850。借助Excel的“規(guī)劃求解”工具可求得最低輸送費用為14 650，Xij值詳見表2。燃氣的物資調(diào)運問題還可運用運籌學(xué)的“表上作業(yè)法”(如最小元素法、西北角法)求解，因其步驟晦澀難懂，這里不再贅述，讀者可參閱文獻［1］［2］學(xué)習(xí)。

2 中國郵路問題

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

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

圖1 巡線路網(wǎng)圖

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

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

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

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

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

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

初等圈“b-c-w-v-b”中，圈總長為15，而重復(fù)邊的總長為8，大于該圈總長度的一半，作重復(fù)邊(b，v)，(v，w)代替(b，c)，(c，w)，調(diào)整為圖2c)，重復(fù)邊總長降為:Lbv+Lvw+Luv+Lwm+Lvy=19。同理，對初等圈“u-v-b-a-u”調(diào)整為圖2d)，此時所有初等圈均滿足“條件B”，重復(fù)邊總長為 Lab+Lvw+Lau+Lwm+Lvy=18?！癿-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”等任一歐拉回路均為最短重復(fù)路徑。

圖2“奇偶點圖上作業(yè)法”尋優(yōu)過程

3 管網(wǎng)最大流問題

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

圖3 中壓輸氣管網(wǎng)簡圖

圖4 初始可行流

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

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

圖5“標(biāo)號算法”求解過程

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

第1步:標(biāo)號過程，用以尋找可增廣鏈。

1)給發(fā)點 vs標(biāo)號(Δ，+∞);

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

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

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

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

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

4 結(jié)語

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

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

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

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

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

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