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

張寧麗 馬燕 張相芬 徐曉鐘

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

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

張寧麗 馬燕 張相芬 徐曉鐘

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

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

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

0 引言

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

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

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

1.1 基本假設(shè)

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

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

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

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

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

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

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

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

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

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

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

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

④狀態(tài)轉(zhuǎn)移方程:Qj+1=Qj-Q2j,即第(j+1)階段天然氣公司擁有的天然氣總量Qj+1等于第j個(gè)階段初期天然氣公司擁有的天然氣總量Qj與第j個(gè)階段公司向第j個(gè)用戶銷售的天然氣總量Q2j之差,則有QM+1=0,具體轉(zhuǎn)移過(guò)程如圖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個(gè)階段,天然氣公司向用戶j銷售Q2j的天然氣時(shí)獲得的收益。

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

1.3 約束條件

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

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

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

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

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

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

1.4 模型的求解

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

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

天然氣動(dòng)態(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個(gè)階段的最優(yōu)決策和最大收益,然后代入式(12),求出第(M-1)個(gè)階段的最優(yōu)決策。依次類推,求出每個(gè)階段的最優(yōu)決策和最大收益,直至求得f1(Q1),便可得到整段時(shí)期的最大收益。

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

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

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

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

2 實(shí)例計(jì)算及結(jié)果分析

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

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

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

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

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

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

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

約束條件為:

第一階段:

第二階段:

根據(jù)已知的約束條件,可得各個(gè)階段的最大收益和最優(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。

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

結(jié)果分析如下。

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

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

3 結(jié)束語(yǔ)

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

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

[2] 周章程,陳國(guó)群.天然氣長(zhǎng)輸管道管輸價(jià)格模型[J].油氣儲(chǔ)運(yùn), 2004,23(11):44-46.

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

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

[5] 李波.天然氣管網(wǎng)系統(tǒng)輸配氣運(yùn)行方案優(yōu)化[J].石油規(guī)劃設(shè)計(jì),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] 唐德善,周之豪,許連成.動(dòng)態(tài)規(guī)劃法在復(fù)雜水資源系統(tǒng)分析中的應(yīng)用[J].運(yùn)籌與管理,1993(3):48-53.

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

[10] 李書(shū)波,仙立東.運(yùn)籌學(xué)在燃?xì)廨斉湎到y(tǒng)中的應(yīng)用[J].系統(tǒng)工程理論與實(shí)踐,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è)基金資助項(xiàng)目(編號(hào):11510502400)。

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

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