具有梯形結(jié)構(gòu)大系統(tǒng)目標(biāo)規(guī)劃模型的求解算法

張 杰, 劉 妮, 徐玲敏

(東北電力大學(xué) 理學(xué)院, 吉林 吉林 132012)

由于大系統(tǒng)目標(biāo)規(guī)劃模型規(guī)模龐大、 結(jié)構(gòu)復(fù)雜, 很難直接求解, 所以需要根據(jù)其特殊結(jié)構(gòu)研究相應(yīng)的求解算法, 目前已取得了一些成果. Shastri等[1]將所研究的問題先轉(zhuǎn)化為兩階段隨機(jī)規(guī)劃問題, 再將對大型隨機(jī)非線性規(guī)劃問題的求解轉(zhuǎn)化為對不確定變量重復(fù)加權(quán), 并對目標(biāo)函數(shù)和約束條件進(jìn)行線性近似, 從而簡化模型. Saadouli[2]利用聚合法解決大型隨機(jī)動態(tài)規(guī)劃問題, 先將系統(tǒng)分解為幾個(gè)階段, 然后利用仿真和人工智能思想相結(jié)合, 從而得出高精度的有效解. Regis[3]提出了求解大系統(tǒng)優(yōu)化問題的隨機(jī)徑向基函數(shù)算法, 利用多重徑向基函數(shù)近似模型中的目標(biāo)函數(shù)和不等式約束, 得到替代模型, 并在每次迭代時(shí)運(yùn)用這些模型為函數(shù)估計(jì)確定合適的點(diǎn), 這種算法只需要相對較小的計(jì)算量即可得到較好的解. Anderson等[4]以生物系統(tǒng)為原型, 提出了兩種求解生物大系統(tǒng)問題的算法----分解法和降階法, 基本思路是對于不含不確定性參數(shù)的模型, 采用降階法； 對于含有不確定性參數(shù)的情況, 采用分解法, 在保證原模型動態(tài)特性不變的前提下, 將模型分解成較小的子系統(tǒng), 并對子系統(tǒng)進(jìn)行仿真求解, 進(jìn)而得到大系統(tǒng)的解. 文獻(xiàn)[5]根據(jù)原方塊角形結(jié)構(gòu)大系統(tǒng)多目標(biāo)規(guī)劃問題的特征, 將其進(jìn)行分解, 通過研究大系統(tǒng)模型與各個(gè)子系統(tǒng)模型最優(yōu)解之間的關(guān)系, 給出了此類大系統(tǒng)問題最優(yōu)解的判別條件. 文獻(xiàn)[6]針對原方塊角形結(jié)構(gòu)大系統(tǒng)目標(biāo)規(guī)劃問題, 研究了分解子問題與大系統(tǒng)問題有效解之間的關(guān)系, 并討論了大系統(tǒng)問題有效解的存在性. 文獻(xiàn)[7-8]對具有梯形結(jié)構(gòu)大系統(tǒng)多目標(biāo)規(guī)劃問題進(jìn)行了初步研究, 通過對模型進(jìn)行適當(dāng)?shù)姆纸? 探討了大系統(tǒng)問題最優(yōu)解與分解后子問題最優(yōu)解的關(guān)系, 旨在將大系統(tǒng)問題的求解轉(zhuǎn)化為求解子問題, 為研究這類大系統(tǒng)目標(biāo)規(guī)劃模型的有效求解算法奠定了基礎(chǔ). 本文在文獻(xiàn)[7-8]的基礎(chǔ)上, 先在縱向分解子問題對應(yīng)的約束不等式組有解的條件下, 證明子問題(Pi)的最優(yōu)解構(gòu)成大系統(tǒng)問題(P)的最優(yōu)解； 再針對一般情況, 提出求解梯形結(jié)構(gòu)大系統(tǒng)目標(biāo)規(guī)劃模型的“順次解耦算法”, 并結(jié)合實(shí)例說明了算法的迭代過程及其有效性.

1 大系統(tǒng)與縱向分解子系統(tǒng)約束不等式組解之間的關(guān)系

1.1 模型描述

其中各部分的含義與文獻(xiàn)[8]相同.

大系統(tǒng)模型(P)所對應(yīng)的約束不等式組為

(1)

縱向分解子問題(Pi)對應(yīng)的約束不等式組為

(2)

1.2 大系統(tǒng)與縱向分解子系統(tǒng)約束不等式組解之間的關(guān)系

一般的多目標(biāo)規(guī)劃模型為

記模型(P′)的最優(yōu)集為A(P′).

定理1若不等式組

(3)

有解, 設(shè)其解集為U(G), 則U(G)=A(P′).

(4)

(5)

(6)

綜上所述, 有U(G)=A(P′).

由定理1和定理2可得:

2 具有梯形結(jié)構(gòu)大系統(tǒng)目標(biāo)規(guī)劃模型的順次解耦算法及數(shù)值算例

2.1 順次解耦算法的基本思想

2.2 算法步驟

轉(zhuǎn)4).

2.3 順次解耦算法的數(shù)值算例

利用順次解耦算法求解大系統(tǒng)目標(biāo)規(guī)劃模型(P)： 求x=(xij:i=1,2,3;j=1,2,3,4), 使得

該解與直接對模型(P)求解得到的結(jié)果一致.

綜上所述, 本文提出了求解具有梯形結(jié)構(gòu)大系統(tǒng)目標(biāo)規(guī)劃模型的“順次解耦算法”. 利用該算法, 每次迭代只需要對規(guī)模較小的子問題進(jìn)行求解, 即可得到大系統(tǒng)問題的最優(yōu)解.

[1] Shastri Y, Diwekar U. An Efficient Algorithm for Large Scale Stochastic Nonlinear Programming Problems [J]. Computers & Chemical Engineering, 2006, 30(5)： 864-877.

[2] Saadouli N. Computationally Efficient Solution Algorithm for a Large Scale Stochastic Dynamic Program [J]. Procedia Computer Science, 2010, 1(1)： 1397-1405.

[3] Regis R G. Stochastic Radial Basis Function Algorithms for Large-Scale Optimization Involving Expensive Black-Box Objective and Constraint Functions [J]. Computers & Operations Research, 2011, 38(5)： 837-853.

[4] Anderson J, CHANG Yo-cheng, Papachristodoulou A. Model Decomposition and Reduction Tools for Large-Scale Networks in Systems Biology [J]. Automatica, 2011, 47(6)： 1165-1174.

[5] ZHANG Jie, FENG Ying-jun. The Criteria of Optimal Solution on a Kind of Large Scale Goal Programming [J]. Journal of Mathematical Study, 2000, 33(2)： 163-168. (張杰, 馮英浚. 一類大系統(tǒng)目標(biāo)規(guī)劃問題分解算法中最優(yōu)解之間的關(guān)系 [J]. 數(shù)學(xué)研究, 2000, 33(2)： 163-168.)

[6] ZHANG Jie, FENG Ying-jun. Existence of Effective Solution on Large Scale Multiobjective Programming with General Diagonal Structure [J]. Journal of Harbin Institute of Technology, 2001, 33(5)： 617-619. (張杰, 馮英浚. 一般原方塊角形結(jié)構(gòu)的大系統(tǒng)多目標(biāo)規(guī)劃有效解的存在性 [J]. 哈爾濱工業(yè)大學(xué)學(xué)報(bào), 2001, 33(5)： 617-619.)

[7] ZHANG Jie, WEI Cai-xia. Relations of Solutions among Subproblems on Large Scale Multiobjective Programming with Trapezoidal Structure [J]. Journal of Jilin University： Science Edition, 2010, 48(2)： 237-240. (張杰, 魏彩霞. 梯形結(jié)構(gòu)大系統(tǒng)多目標(biāo)規(guī)劃子問題解的關(guān)系 [J]. 吉林大學(xué)學(xué)報(bào)： 理學(xué)版, 2010, 48(2)： 237-240.)

[8] ZHANG Jie, XU Ling-min, HU Ding. Bidirectional Decomposition of Large Scale Multiobjective Programming Model with Trapezoidal Structure and Relations of Its Solutions [J]. Journal of Jilin University： Science Edition, 2011, 49(5)： 802-808. (張杰, 徐玲敏, 胡鼎. 具有梯形結(jié)構(gòu)大系統(tǒng)目標(biāo)規(guī)劃模型的雙向分解及解的關(guān)系 [J]. 吉林大學(xué)學(xué)報(bào)： 理學(xué)版, 2011, 49(5)： 802-808.)