具有梯形結構大系統目標規劃模型的求解算法

張 杰, 劉 妮, 徐玲敏

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

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

1 大系統與縱向分解子系統約束不等式組解之間的關系

1.1 模型描述

其中各部分的含義與文獻[8]相同.

大系統模型(P)所對應的約束不等式組為

(1)

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

(2)

1.2 大系統與縱向分解子系統約束不等式組解之間的關系

一般的多目標規劃模型為

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

定理1若不等式組

(3)

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

(4)

(5)

(6)

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

由定理1和定理2可得:

2 具有梯形結構大系統目標規劃模型的順次解耦算法及數值算例

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

2.2 算法步驟

轉4).

2.3 順次解耦算法的數值算例

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

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

綜上所述, 本文提出了求解具有梯形結構大系統目標規劃模型的“順次解耦算法”. 利用該算法, 每次迭代只需要對規模較小的子問題進行求解, 即可得到大系統問題的最優解.

[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. (張杰, 馮英浚. 一類大系統目標規劃問題分解算法中最優解之間的關系 [J]. 數學研究, 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. (張杰, 馮英浚. 一般原方塊角形結構的大系統多目標規劃有效解的存在性 [J]. 哈爾濱工業大學學報, 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. (張杰, 魏彩霞. 梯形結構大系統多目標規劃子問題解的關系 [J]. 吉林大學學報： 理學版, 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. (張杰, 徐玲敏, 胡鼎. 具有梯形結構大系統目標規劃模型的雙向分解及解的關系 [J]. 吉林大學學報： 理學版, 2011, 49(5)： 802-808.)