利用動態(tài)規(guī)劃模型優(yōu)化天然氣產(chǎn)銷調(diào)度問題

張寧麗 馬燕 張相芬 徐曉鐘

(上海師范大學(xué)信息與機電工程學(xué)院,上海 200234)

利用動態(tài)規(guī)劃模型優(yōu)化天然氣產(chǎn)銷調(diào)度問題

張寧麗 馬燕 張相芬 徐曉鐘

(上海師范大學(xué)信息與機電工程學(xué)院,上海 200234)

在不確定條件下,如何優(yōu)化天然氣產(chǎn)銷調(diào)度使得產(chǎn)銷平衡,是天然氣公司急待解決的問題。天然氣的購買和銷售是一個多階段動態(tài)過程,所以將動態(tài)規(guī)劃理論應(yīng)用其中,建立以天然氣公司最大收益為目標(biāo)的動態(tài)規(guī)劃模型,并進行時間復(fù)雜度分析。結(jié)果表明,動態(tài)規(guī)劃算法能從時間與空間角度實現(xiàn)天然氣的合理調(diào)度;與線性求解過程相比,動態(tài)規(guī)劃算法對具有最優(yōu)解的實際問題的求解更加靈活,且計算量小,結(jié)果更可靠,為天然氣產(chǎn)銷優(yōu)化調(diào)度提供了新的解決方法。

天然氣 產(chǎn)銷平衡 動態(tài)規(guī)劃 最大收益 線性規(guī)劃 時間復(fù)雜度

0 引言

在天然氣產(chǎn)業(yè)中,天然氣公司的主要任務(wù)是購買和銷售天然氣。但是由于其購進和銷售的價格各不相同,如何在綜合考慮天然氣的購氣成本、售氣收入以及其他的基礎(chǔ)設(shè)備損耗等一些不確定因素的條件下,實現(xiàn)天然氣的有效購買與分配,達(dá)到天然氣公司的最大收益,是目前天然氣產(chǎn)業(yè)急待解決的問題[1]。天然氣的生產(chǎn)與銷售是一個連續(xù)的過程,同時上游油氣企業(yè)為保證氣田的供氣穩(wěn)定性,一般依據(jù)“照付不議”合同對天然氣公司供氣,以保證天然氣的供銷平衡[2]。在這種情況下,可以建立線性規(guī)劃模型[3],利用單純形法求解。但由于其產(chǎn)地與銷售地點相距較遠(yuǎn),市場的需求具有波動性,所以存在時間與空間上的不均勻性。

為了實現(xiàn)天然氣的合理調(diào)度,本文將動態(tài)規(guī)劃理論應(yīng)用于天然氣產(chǎn)銷優(yōu)化配置的研究中,建立動態(tài)規(guī)劃模型,求出天然氣的最優(yōu)配置,為天然氣的進一步研究提供參考。

1 動態(tài)規(guī)劃模型的建立及求解思路

1.1 基本假設(shè)

①假設(shè)天然氣公司從各個氣源的購氣費用與購氣量呈正比例關(guān)系,其向各用戶銷售天然氣所獲得的售氣收入與售氣量也呈正比例關(guān)系,即:

式中:ci為天然氣公司從氣源i購進單位天然氣的價格;Q1i為一段時期內(nèi),天然氣公司從氣源i購進的天然氣量;Ci為一段時期內(nèi),天然氣公司從氣源i購進Q1i天然氣的總費用;sj為天然氣公司向用戶j銷售單位天然氣的價格;Q2j為一段時期內(nèi),天然氣公司向用戶j銷售的天然氣的總量;Sj為一段時期內(nèi),天然氣公司向用戶j銷售Q2j天然氣的總收入。

②假定向第j個用戶銷售一定量的天然氣時,天然氣管道的運行費用和壓氣站的運行費用考慮為一個常數(shù)Cj。

③在目標(biāo)函數(shù)中不考慮管道、壓氣站的人工和設(shè)備維修費用,因為這些費用通常與管網(wǎng)的運行方案無關(guān),對天然氣公司的銷售收益不會有影響[4]。模型中沒有考慮天然氣的儲氣部分,所以假設(shè)天然氣的產(chǎn)銷是平衡的。

1.2 建立動態(tài)規(guī)劃模型

天然氣產(chǎn)銷運行包括天然氣的生產(chǎn)、購買和銷售,所以在建立的動態(tài)規(guī)劃模型中應(yīng)包括氣源、天然氣公司和用戶三個參與者[5]。在一定時間段內(nèi),可以從N個氣源購進天然氣,根據(jù)“照付不議”合同,在產(chǎn)銷平衡的基礎(chǔ)上,將所購進的天然氣全部銷售給M個用戶,其中包括M1個可中斷用戶和M2個不可中斷用戶(M1+M2=M)。氣源、天然氣公司和用戶之間的供求關(guān)系如圖1所示。

圖1 氣源、天然氣公司和用戶三者關(guān)系圖Fig.1 Relationships among gas sources,gas company and users

一般情況下,天然氣產(chǎn)銷運行的周期為一年,在供氣周期的每一個調(diào)度時段,天然氣公司需要在空間上對市場內(nèi)不同的用戶進行最優(yōu)分配,以達(dá)到銷售利益的最大化[6]。為使模型簡單可行,同時也為保證模型的獨立性,避免季節(jié)變化等因素的干擾,本文將天然氣產(chǎn)銷運行的周期進一步細(xì)化為一個月。在每個月內(nèi),以天然氣公司在該階段現(xiàn)有的天然氣總量Qj作為狀態(tài)變量,以用戶個數(shù)劃分階段,具體如下[7]。

①階段變量j。本文根據(jù)用戶個數(shù)劃分階段,在該時段中有多少天然氣用戶,就將產(chǎn)銷運行過程劃分為多少個階段,則有j=1,2,…,M。

②狀態(tài)變量Qj。以該階段內(nèi)天然氣公司現(xiàn)有的總的天然氣量作為狀態(tài)變量,假設(shè)在運行初期,天然氣公司從各個氣源購買的天然氣總量為Q,并假定Q1=Q。

③決策變量Q2j。以天然氣公司向各個用戶銷售的天然氣總量作為決策變量,則:

式中:Q2j為第j個階段,天然氣公司向用戶j銷售的總的天然氣量;Q2ij為第j個階段,天然氣公司向各個用戶j銷售的屬于氣源i的天然氣量。

④狀態(tài)轉(zhuǎn)移方程:Qj+1=Qj-Q2j,即第(j+1)階段天然氣公司擁有的天然氣總量Qj+1等于第j個階段初期天然氣公司擁有的天然氣總量Qj與第j個階段公司向第j個用戶銷售的天然氣總量Q2j之差,則有QM+1=0,具體轉(zhuǎn)移過程如圖2所示,其中ri(Q2j)為效益函數(shù)。

圖2 各階段天然氣分配量以及效益函數(shù)圖Fig.2 Distribution amount of natural gas and benefit function at each stage

⑤效益函數(shù)ri(Q2j)。效益函數(shù)ri(Q2j)表示在第j個階段,天然氣公司向用戶j銷售Q2j的天然氣時獲得的收益。

則最終目標(biāo)函數(shù)為:

1.3 約束條件

由于每個氣田和用戶具有一定的供氣和購氣限制,所以天然氣公司在天然氣的購買與銷售過程中應(yīng)該滿足以下約束條件[8]。

①在一段時期內(nèi),天然氣公司向M個用戶銷售的屬于氣源i的天然氣總量應(yīng)該滿足:

②在第j個階段,天然氣公司向用戶j銷售的天然氣量應(yīng)該滿足用戶的用氣要求,即:

③各個時間段內(nèi),在產(chǎn)銷平衡的條件下,M個用戶的總用氣量應(yīng)與從N個氣源購買的天然氣量相等,即:

④在一段時間內(nèi),用戶j總購氣總量應(yīng)與從N個購買的天然氣的總和相等,即:

⑤各個變量的非負(fù)性約束:

1.4 模型的求解

根據(jù)動態(tài)規(guī)劃最優(yōu)原理,可得基本方程[9]:

狀態(tài)轉(zhuǎn)移方程為:Qj+1=Qj-Q2j,逆向遞推可以求得最優(yōu)決策序列(Q21,Q22,…,Q2M)和公司最大收益f1(Q1)。

天然氣動態(tài)規(guī)劃模型的逆序算法步驟如下。

①設(shè)定初始值,取j=M+1,fM+1(QM+1)=0,Q1=Q;

②逆向遞推,綜合以上約束條件,依次取j=M, M-1,…,1。

③根據(jù)初始條件fM+1(QM+1)=0,先求出第M個階段的最優(yōu)決策和最大收益,然后代入式(12),求出第(M-1)個階段的最優(yōu)決策。依次類推,求出每個階段的最優(yōu)決策和最大收益,直至求得f1(Q1),便可得到整段時期的最大收益。

1.5 算法的復(fù)雜度分析

動態(tài)規(guī)劃時間復(fù)雜度=狀態(tài)總數(shù)×每個狀態(tài)轉(zhuǎn)移的狀態(tài)數(shù)×每次狀態(tài)轉(zhuǎn)移的時間

對應(yīng)于文中所建立的產(chǎn)銷平衡的天然氣動態(tài)規(guī)劃模型,根據(jù)用戶個數(shù),將模型劃分為M個階段,所以狀態(tài)總數(shù)為M。每進行一次狀態(tài)轉(zhuǎn)移,確定一個用戶的應(yīng)購入量,所以每個狀態(tài)轉(zhuǎn)移的狀態(tài)數(shù)為1。每次狀態(tài)轉(zhuǎn)移需要確定該用戶從天然氣公司購買的屬于各個氣源的天然氣量,模型中共有N個氣源,因此,每次狀態(tài)轉(zhuǎn)移需要的時間為N,因此該算法的時間復(fù)雜度為O(MN)。

根據(jù)所得到的目標(biāo)函數(shù)和約束條件可知,該模型也是一個線性規(guī)劃模型,可以利用單純形法來求解。因此,對比于線性規(guī)劃,本文采用的動態(tài)規(guī)劃法真正起到了去除"冗余"和降維的作用[10]。

2 實例計算及結(jié)果分析

以圖3所示的輸氣管網(wǎng)為例,這是一個包含兩個氣源(A,B)、兩個用戶(D,E)和天然氣公司C的輸氣管網(wǎng)。下面制定計劃期為一個月的管網(wǎng)最優(yōu)輸配氣方案。

圖3 天然氣輸送管網(wǎng)示意圖Fig.3 Schematic diagram of natural gas transportation pipeline network

已知條件:從氣源i購買天然氣價格ci,氣源i可以提供的天然氣最小量為Q1imin,最大量為Q1imax,氣源數(shù)據(jù)如表1所示。

表1 氣源數(shù)據(jù)Tab.1 Data of gas sources

天然氣公司向用戶j出售天然氣價格sj、用戶j可以購買的天然氣最小量Q2jmin、最大量Q1imax,每個用戶購買天然氣時壓氣站和管道所產(chǎn)生的固定損耗Cj,用戶數(shù)據(jù)如表2所示。

表2 用戶數(shù)據(jù)Tab.2 Data of users

根據(jù)用戶個數(shù),將求解過程劃分為兩個階段,由此可得動態(tài)規(guī)劃基本方程為:

約束條件為:

第一階段:

第二階段:

根據(jù)已知的約束條件,可得各個階段的最大收益和最優(yōu)決策:f1(Q1)=13 212.93、Q21=14.781、Q211=14.781 [Q221=0、f2(Q2)=12 853.93、Q21=71.217、Q211=14.717、Q221=56.5。

對比兩種求解過程,本文所用動態(tài)規(guī)劃求解算法更具靈活性,其充分考慮了變量在計算過程中不確定的因素,且計算量更小、結(jié)果與實際狀況更吻合。

結(jié)果分析如下。

①由于氣源B的氣價低于A的氣價,在滿足約束條件的前提下,應(yīng)盡量購買氣源B的天然氣,這與實際情況相符。

②對比于單純形法,利用動態(tài)規(guī)劃求解時,不但能夠得到全局的最優(yōu)配置,而且可以得到每個階段的最優(yōu)配置。由最終結(jié)果可知:用戶D是一個可中斷用戶,若實際需求有變化,可以適當(dāng)?shù)卣{(diào)整用戶D和用戶E的天然氣分配量,使模型更具靈活性。

3 結(jié)束語

本文針對天然氣管網(wǎng)不穩(wěn)定運行的特點,將動態(tài)規(guī)劃運用于天然氣產(chǎn)銷運行優(yōu)化調(diào)度的研究中。試驗證明,動態(tài)規(guī)劃法為我們?nèi)ソ鉀Q“在哪些條件下才能達(dá)到整體最優(yōu)”的問題提供了有效的途徑,尤其對于求解有上下限約束條件問題特別有效。為了簡化模型,文中未考慮壓氣站和儲氣庫部分。模型中所選的運行周期為一個月,這樣可以使模型具有一定的獨立性,不必考慮季節(jié)變化對其造成的影響?，F(xiàn)實中的天然氣管網(wǎng)模型是非常復(fù)雜的,要受到各種因素的制約,在此本文僅考慮相對簡化情形,為相關(guān)的計算提供一個參考的平臺。

[1] 彭赟,成金華,王小林,等.基于多目標(biāo)動態(tài)規(guī)劃的天然氣產(chǎn)銷運行優(yōu)化調(diào)度[J].經(jīng)濟縱橫論,2012(8):128-131,184.

[2] 周章程,陳國群.天然氣長輸管道管輸價格模型[J].油氣儲運, 2004,23(11):44-46.

[3] 裘哲勇.燃?xì)廨斉涞臄?shù)學(xué)模型[J].數(shù)學(xué)的實踐與認(rèn)識,2004, 34(12):1-7.

[4] 蔣維,陳開,鐘曉,等.基于動態(tài)規(guī)劃的資源受限隨機工序調(diào)度[J].計算機工程,2008,34(16):19-21.

[5] 李波.天然氣管網(wǎng)系統(tǒng)輸配氣運行方案優(yōu)化[J].石油規(guī)劃設(shè)計,2001,12(6):22-25.

[6] Bopp A E.An optimization model for planning natural gas purchases, transportation,storage and deliverability[C]∥Omega,International Journal of Management Science,1996,24(5):511-522.

[7] Hamedi M,Farahani R Z,Husseini M M.A distribution planning model for natural gas supply chain:a case study[J].Energy Policy,2009(37): 799-812.

[8] 唐德善,周之豪,許連成.動態(tài)規(guī)劃法在復(fù)雜水資源系統(tǒng)分析中的應(yīng)用[J].運籌與管理,1993(3):48-53.

[9] 孫素云.基于動態(tài)規(guī)劃的多鏈路出口路徑選擇算法[J].計算機工程,2010,36(9):117-119.

[10] 李書波,仙立東.運籌學(xué)在燃?xì)廨斉湎到y(tǒng)中的應(yīng)用[J].系統(tǒng)工程理論與實踐,1997(6):135-138.

Optimizing the Production and Marketing Dispatching of Nature Gas by using Dynamic Programming Model

How to optimize the production and marketing dispatching of natural gas and make the balance of production and sales under uncertainty is a pressing problem for the natural gas company.As the purchase and sales of natural gas is a dynamic process with multiple stages,so the dynamic programming theory is applied to solve this problem.The dynamic programming model with target of maximum benefit of the natural gas company is established,and the analysis of time complexity is conducted.The result shows that the reasonable dispatching of natural gas can be implemented from both time and space angles by this dynamic programming algorithm.Comparing with linear programming algorithm,the algorithm proposed is more flexible,more reliable,and with less calculation amount for solving practical problems and getting optimal solution,it provides new approach for the optimal production and marketing dispatching of natural gas.

Natural gas Balance of production and sales Dynamic programming Maximum benefit Linear programming Time complexity

TE832

A

上海市部分地方院校能力建設(shè)基金資助項目(編號:11510502400)。

修改稿收到日期:2014-02-07。

張寧麗(1990-),女,現(xiàn)為上海師范大學(xué)計算機軟件與理論專業(yè)在讀碩士研究生;主要從事天然氣的最優(yōu)調(diào)度研究。