基于可信度法求解區間雙層線性規劃問題

任 愛 紅

(寶雞文理學院 數學與信息科學學院, 陜西 寶雞 721013)

雙層規劃是一類含有兩層遞階結構的復雜系統優化問題. 其模型在網絡設計、 經濟管理和電力定價等實際問題中應用廣泛[1-4]. 但由于雙層規劃的嵌套結構和NP-難特性, 導致求解該類問題很困難. 目前, 針對雙層規劃的研究主要集中在上下層目標函數和約束函數中所有系數都是實數的情形.

在實際應用中常存在各種不確定性, 可分別利用概率理論和模糊集理論描述兩層遞階決策問題中存在的隨機不確定性和模糊不確定性, 通過引入隨機雙層規劃和模糊雙層規劃解決該類問題. 針對這兩類不確定雙層規劃, 需要確定精確概率分布函數和隸屬度函數. 區間數方法是一種簡單有效地描述不確定性的方法, 它只需已知參數的上界和下界. 目前對區間雙層規劃的研究報道較少. 王建忠[5]根據決策背景, 提出了幾類區間雙層線性規劃模型和最優解的概念, 并設計了相應的求解方法; Calvete等[6]針對僅上下層目標函數中含區間系數的雙層線性規劃, 提出了KBB和KBW兩種極點算法, 分別求解原問題的最好最優解和最差最優解, 基于此給出上層目標函數的最優值范圍; 任愛紅等[7]設計了兩種割平面法求解區間雙層線性規劃問題, 得出了最好最優解和最差最優解; 樊揚揚等[8]提出了一種基于雙適應度函數評估的遺傳算法, 對一類上層目標函數中帶區間系數的雙層規劃問題進行求解. 本文考慮一類上下層目標函數和約束函數中所有系數均為區間數的雙層線性規劃問題. 為給決策者提供一個最優解, 先引入上下層目標函數的期望目標區間, 再基于區間數的可信度概念給出上下層目標函數的可信水平. 基于此, 提出區間雙層線性規劃可行域和最優解的概念. 對上下層規劃分別采用極大極小算子, 將原區間雙層線性規劃轉化為一個單層確定等價模型.

1 預備知識

定義1[9]記cI=[cL,cR]={x:cL≤x≤cR,x∈}, 稱cI為一個區間數, 其中cL和cR分別是區間數cI的下界和上界. 特別地, 當cL=cR時, 區間數cI退化為一個實數. 稱len(cI)=cR-cL為區間數cI的長度. 令I()表示全體區間數.

2 區間雙層線性規劃問題及其解的概念

考慮上下層目標函數和約束函數中所有系數均為區間數的雙層線性規劃問題：

(1)

其中x∈n和y∈m分別為上下層規劃的決策變量;FI,fI:n×m→I()分別為上下層規劃的目標函數均為n維區間向量均為m維區間向量均為區間數.

基于定義2中區間數之間的算術運算, 問題(1)中上下層目標函數已不再是一個精確的實值而是一個區間值, 同時約束函數是區間不等式約束, 因此問題(1)不是一個嚴格意義上的數學規劃問題. 如何定義問題(1)的可行域以及上下層目標函數最優值的概念是處理這類不確定雙層規劃問題的關鍵, 而解決這兩個問題涉及到不同區間數之間的排序. 目前已有許多比較和排序區間數的方法[11-12]. 考慮到不僅希望比較區間數之間的大小, 而且還可以度量區間數之間大小的程度, 同時符合決策者較精確的預期, 因此本文采用文獻[10]提出區間數排序的可信度定義, 比較不同上下層決策變量下上下層目標函數的區間值以及區間不等式約束.

令問題(1)的約束域為

在實際應用中, 決策者常需要依賴于預先給定的某個期望目標獲得一個最優解. 在該意義下, 基于定義3中可信度的概念, 下面給出區間雙層線性規劃問題(1)的可行域和最優解的概念.

稱y*是問題(1)中下層規劃的一個可信弱有效解.

IR={(x,y)∈n×m|(x,y)∈S,y∈M(x)}.

3 基于可信度法確定等價模型

(2)

其中:

令β表示上層規劃目標函數的可信水平, 利用極大極小算子方法, 問題(1)可轉化為如下問題:

(3)

結合問題(2),(3), 令α=min{λ,β}, 則問題(1)可轉化為下列單層規劃問題：

(4)

下面利用定義3中可信度法, 將問題(4)中所有不等式轉化為下列確定不等式形式：

因此問題(4)可轉化為下列確定數學模型：

(5)

定理1若問題(5)的最優解為(x*,y*,α*), 則(x*,y*)是問題(1)可信水平為α*的一個可信最優解.

令α*≤λ. 記

由定理1, 只需通過求解模型(5), 即可獲得問題(1)的一個可信最優解. 注意到問題(5)是一個非線性規劃問題, 通?？刹捎眯刨囉蚍椒ā?內點法、 可行方向法等求解這類問題. 本文利用MATLAB優化工具箱求解非線性規劃問題(5).

4 數值實例

為表明本文所提方法的可行性, 考慮下列區間雙層線性規劃問題：

(6)

首先確定上下層目標函數的期望目標區間. 對于下層規劃, 根據Tong[14]的最優值區間方法, 對給定的x, 可求得下層最好和最差最優值分別為7x-28和5x-6, 因此下層目標函數的期望目標區間可給定為[7x-28,5x-6]. 此外, 依據文獻[15]中定理3.3, 可求得上層最好和最差最優值分別為-5.6和-1.5, 因此上層目標函數的期望目標區間確定為[-5.6,-1.5]. 由模型(5)知, 問題(6)可轉化為相應的單層確定數學模型. 利用MATLAB優化工具箱, 可求得最優解為x*=3.471 3,y*=0,α*=0.057 5. 因此, 相應的上層目標函數最優值區間為[-3.471 3,-1.735 7], 且[-3.471 3,-1.735 7]?[-5.6,-1.5]. 顯然所求的最優值滿足邊界條件.

綜上可見, 本文提出的方法能靈活地為決策者提供在一定可信度下上層區間目標函數的最優值范圍, 使所得結果具有較高的可行性.

[1] Gzara F. A Cutting Plane Approach for Bilevel Hazardous Material Transport Network Design [J]. Operations Research Letters, 2013, 41(1): 40-46.

[2] Calvete H I, Galé C, Oliveros M J. Bilevel Model for Production: Distribution Planning Solved by Using Ant Colony Optimization [J]. Computers & Operations Research, 2011, 38(1): 320-327.

[3] Labbé M, Violin A. Bilevel Programming and Price Setting Problems [J]. 4OR, 2013, 11(1): 1-30.

[4] Kalashnikov V V, Dempe S, Pérez-Valdés G A, et al. Bilevel Programming and Applications [J/OL]. Mathematical Problems in Engineering, 2015-03. http://dx.doi.org/10.1155/2015/310301.

[5] 王建忠. 區間線性雙層規劃方法研究 [D]. 天津: 天津大學, 2010. (WANG Jianzhong. Research on the Methods of Interval Linear Bi-level Programming [D]. Tianjin: Tianjin University, 2010.)

[6] Calvete H I, Galé C. Linear Bilevel Programming with Interval Coefficient [J]. Journal of Computational and Applied Mathematics, 2012, 236(15): 3751-3762.

[7] REN Aihong, WANG Yuping. A Cutting Plane Method for Bilevel Linear Programming with Interval Coefficients [J]. Annals of Operations Research, 2014, 223(1): 355-378.

[8] 樊揚揚, 李和成. 一類區間系數線性雙層規劃問題的遺傳算法 [J]. 計算機應用, 2014, 34(1): 185-188. (FAN Yangyang, LI Hecheng. Genetic Algorithm for Solving Linear Bilevel Programming with Interval Coefficients [J]. Journal of Computer Applications, 2014, 34(1): 185-188.)

[9] Moore R E, Kearfott R B, Cloud M J. Introduction to Interval Analysis [M]. Philadelphia, PA: SIAM, 2009.

[10] 秦成燕, 李煒. 區間線性規劃問題的可信度及其改進解 [J]. 杭州電子科技大學學報, 2011, 31(3): 74-77. (QIN Chengyan, LI Wei. Possibility Degree and Improvement Solution of the Interval Linear Programming [J]. Journal of Hangzhou Dianzi University, 2011, 31(3): 74-77.)

[11] Nakahara Y, Sasaki M, Gen M. On the Linear Programming Problems with Interval Coefficients [J]. Computer & Industrial Engineering, 1992, 23(1/2/3/4): 301-304.

[12] Sengupta A, Pal T K. On Comparing Interval Numbers [J]. European Journal of Operational Research, 2000, 127(1): 28-43.

[13] 史加榮, 劉三陽, 熊文濤. 區間數線性規劃的一種新解法 [J]. 系統工程理論與實踐, 2005, 25(2): 101-106. (SHI Jiarong, LIU Sanyang, XIONG Wentao. A New Solution for Interval Number Linear Programming [J]. Systems Engineering: Theory & Practice, 2005, 25(2): 101-106.)

[14] TONG Shaocheng. Interval Number and Fuzzy Number Linear Programmings [J]. Fuzzy Sets and Systems, 1994, 66(3): 301-306.

[15] Hamidi F, Mishmast N H. Bilevel Linear Programming with Fuzzy Parameters [J]. Iranian Journal of Fuzzy Systems, 2013, 10(4): 83-99.