任 愛 紅

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

0 引 言

雙層規(guī)劃問題(bilevel programming problem，BLPP)是一類具有主從遞階結構的復雜決策問題，已被廣泛應用于經(jīng)濟管理、網(wǎng)絡規(guī)劃、供應鏈管理、工程問題等實際領域[1-4]．雙層規(guī)劃的NP-hard性以及非凸不可微性，使得求解此類問題異常復雜，目前對雙層規(guī)劃的研究仍以所有系數(shù)均為實數(shù)的確定型雙層規(guī)劃為主．然而，在許多實際兩層遞階決策問題中，經(jīng)常存在著各種不確定性，如模糊不確定性和隨機不確定性等，顯然確定型雙層規(guī)劃無法完全反映這些不確定性現(xiàn)象，在使用上存在一定程度的局限性，因此將各種不確定性現(xiàn)象考慮到雙層規(guī)劃問題中的研究將具有重要的實際意義．

基于模糊規(guī)劃和隨機規(guī)劃這兩類不確定性優(yōu)化方法，模糊雙層規(guī)劃和隨機雙層規(guī)劃模型被相繼提出．盡管這兩種不確定型雙層規(guī)劃模型能分別從模糊不確定性和隨機不確定性的角度描述不確定兩層遞階決策問題，但難以全面刻畫同時含模糊性和隨機性的雙重不確定性環(huán)境下的實際遞階決策過程，因此需進一步深入研究包含模糊隨機不確定性的雙層規(guī)劃．模糊隨機變量是描述模糊隨機雙重不確定性現(xiàn)象的一種數(shù)學工具．近年來，一些學者將模糊隨機變量這一數(shù)學概念引入到雙層規(guī)劃問題中，開展了對模糊隨機不確定性環(huán)境下雙層規(guī)劃問題的研究．相比模糊或隨機雙層規(guī)劃，由于雙重不確定性的復雜性和雙層規(guī)劃自身求解困難的特性，模糊隨機雙層規(guī)劃問題更加難以處理．

目前關于求解模糊隨機雙層規(guī)劃的研究大多集中在上下層目標函數(shù)中含模糊隨機變量系數(shù)和約束函數(shù)中是實系數(shù)的情形．例如，Sakawa等[5]在上下層決策者非合作的情況下，采用Fractile模型以及可能性和必然性測度將模糊隨機雙層規(guī)劃變形為一個確定雙層線性分數(shù)規(guī)劃，通過結合變量變形法和K次最好算法求得問題的一個Stackelberg解．針對同樣的問題，Ren等[6]基于區(qū)間規(guī)劃方法和期望優(yōu)化模型將原問題轉化為一個確定多目標雙層規(guī)劃模型，并設計了求解偏好最優(yōu)解的兩個算法．隨后，Sakawa等[7]利用可能性和必然性測度以及絕對偏差最小化方法來處理模糊隨機雙層規(guī)劃問題．然而，針對求解上下層目標函數(shù)和約束函數(shù)均含有模糊隨機變量系數(shù)的雙層情形，當前研究成果還非常少．Ren等[8]結合最優(yōu)值區(qū)間方法、期望模型以及概率機會約束條件討論了此類模糊隨機雙層規(guī)劃的最優(yōu)值問題．

本文針對所有系數(shù)均為模糊隨機變量的模糊隨機雙層規(guī)劃模型，引入模糊隨機變量的期望值、模糊數(shù)的確定可能性均值和模糊機會約束條件處理原問題的隨機性和模糊性，建立模糊隨機雙層確定可能性均值-機會約束規(guī)劃模型，給出其確定等價雙層線性模型，并利用K次最好算法進行求解．最后以數(shù)值例子證明所提方法的可行性．

1 理論基礎

其中函數(shù)L，R：[0，)→[0，1]是單調(diào)不增函數(shù)，且滿足L(0)=R(0)=1，ξ(ω)是模糊隨機變量的中心值，αξ，βξ>0分別為左寬度和右寬度．LR型模糊隨機變量可表示為?ω∈Ω．本文假設ξ是服從均值為E(ξ)和方差為的正態(tài)分布的隨機變量，記為

2 基于確定可能性均值和機會約束規(guī)劃的求解方法

2.1 問題形式

考慮上下層目標函數(shù)和約束函數(shù)中同時含模糊隨機變量系數(shù)的模糊隨機雙層線性規(guī)劃問題，其數(shù)學模型表示為

x2是下面問題的解：

k=1，2，…，m，

x1=(x11x12…x1n1)T≥0，

x2=(x21x22…x2n2)T≥0

(1)

由于模型(1)中系數(shù)均為模糊隨機變量，運用擴展原則，可知上下層目標函數(shù)以及每個約束函數(shù)的左側都是模糊隨機變量，因此該問題不是一個嚴格的數(shù)學規(guī)劃模型．為解決此類問題，本文融合模糊隨機變量的期望值、模糊數(shù)的確定可能性均值和基于可能性測度的模糊機會約束條件處理模型中的雙重不確定性，由此構建模糊隨機雙層確定可能性均值-機會約束規(guī)劃模型，再給出其確定等價模型進行求解．

2.2 模糊隨機雙層確定可能性均值-機會約束規(guī)劃模型

模糊隨機變量的期望值是模糊隨機變量最重要的數(shù)字特征之一，它刻畫了模糊隨機變量向其均值靠攏的趨向值，是一種最常用的去隨機化方法．當決策者希望在期望約束下優(yōu)化上下層目標函數(shù)的平均值，則模型(1)中所有約束函數(shù)的左右兩側以及上下層目標函數(shù)就可以用其相應的期望值來代替，可得如下形式的模型：

x2是下面問題的解：

k=1，2，…，m，

x1=(x11x12…x1n1)T≥0，

x2=(x21x22…x2n2)T≥0

(2)

模糊隨機變量的期望值本質上是一個模糊數(shù)，故模型(2)中每一個約束都是模糊約束，上下層目標函數(shù)也全是模糊數(shù)，因此該模型便是一個模糊雙層規(guī)劃模型．

由于模糊約束不可能給出一個確定的約束域，若希望模糊約束能以一定的置信水平成立，則可采用模糊機會約束條件．基于可能性測度，模型(2)中第k個模糊約束可轉化為如下模糊機會約束條件：

k=1，2，…，m

其中θk∈[0，1]表示決策者事先給定的置信水平．

對于模型(2)中上下層目標函數(shù)，需引入模糊數(shù)之間的排序方法對不同決策變量下模糊目標函數(shù)值進行比較．本文利用Carlsson等[10]提出的模糊數(shù)確定可能性均值概念清晰反映模型(2)中上下層目標函數(shù)的期望值，并對模糊目標函數(shù)值進行比較．基于這一概念，模型(2)中上下層目標函數(shù)的確定可能性均值為

基于上面的討論，建立如下形式的模糊隨機雙層確定可能性均值-機會約束規(guī)劃模型：

x2是下面問題的解：

x1=(x11x12…x1n1)T≥0，

x2=(x21x22…x2n2)T≥0

(3)

對給定的θk(k=1，2，…，m)，令模型(3)的約束域為

接下來，引入模糊隨機雙層規(guī)劃問題(1)的M-POS-最優(yōu)解概念．

則稱x2為模型(1)下層規(guī)劃的M-POS-最優(yōu)解．

對給定的x1≥0，記M(x1;θk)表示模型(1)下層規(guī)劃的M-POS-最優(yōu)解集．

在給定置信水平θk(k=1，2，…，m)下，定義模型(1)的M-POS-可行域為

IR(θk)={(x1，x2)|(x1，x2)∈S(θk)，

x2∈M(x1;θk)}

由定理1可知，為獲得模糊隨機雙層規(guī)劃問題(1)的M-POS-最優(yōu)解只需求得模糊隨機雙層確定可能性均值-機會約束規(guī)劃模型(3)的最優(yōu)解．本文假設模型中不確定系數(shù)均為LR型模糊隨機變量，下面給出模型(3)的確定等價形式．

2.3 確定等價形式

且λ-水平集為

相似地，模型(1)中每個約束函數(shù)的左側也都是LR型模糊隨機變量，相應的期望值也是LR型模糊數(shù)，表示為

根據(jù)引理1，模型(3)中約束條件

等價于

根據(jù)以上結果，模型(3)變形為如下確定雙層線性規(guī)劃問題：

x2是下面問題的解：

x1=(x11x12…x1n1)T≥0，

x2=(x21x22…x2n2)T≥0

(4)

特別地，當L(x)=R(x)=1-x(x∈[0，1])時，則LR型模糊隨機變量系數(shù)退化為三角模糊隨機變量．因此模型(4)可寫為

x2是下面問題的解：

x1=(x11x12…x1n1)T≥0，

x2=(x21x22…x2n2)T≥0

(5)

雙層線性規(guī)劃問題至少有一個全局最優(yōu)解在其約束域的極點處達到．基于這一重要性質，本文利用K次最好算法[12]來求解模型(4)和(5)．這類方法的基本思想是首先在約束域上求解上層規(guī)劃獲得最優(yōu)解，再檢驗該解是否也是下層規(guī)劃的最優(yōu)解．若是，則這個解便是雙層線性規(guī)劃問題的最優(yōu)解；否則，從這個解的相鄰頂點組成的待檢驗頂點集合中尋找使上層規(guī)劃達到最優(yōu)的點，同時檢驗這個頂點是否是下層規(guī)劃的最優(yōu)解．重復以上過程，直到在約束域中獲得最優(yōu)解．

3 數(shù)值例子及分析

例1[8]考慮如下模糊隨機雙層規(guī)劃問題：

(x2，x3)是下面問題的解：

x1≥0，x2≥0，x3≥0

(6)

其中上下層目標函數(shù)以及約束函數(shù)中右側系數(shù)都為三角模糊隨機變量，具體數(shù)據(jù)如表1所示．

表1 例1中上下層目標函數(shù)和約束函數(shù)右側系數(shù)Tab.1 Coefficients in the upper and lower level objective functions as well as the right hand side of each constraint function of example 1

根據(jù)模型(5)，建立模型(6)的確定雙層線性規(guī)劃模型：

(x2，x3)是下面問題的解：

s.t.2x1+5x2+x3≤120.0+(1-θ1)×10.0，

5x1+3x2+2x3≤115.0+(1-θ2)×8.0，

x1+2x2+4x3≤100.0+(1-θ3)×5.0，

x1≥0，x2≥0，x3≥0

(7)

文獻[8]融合α-水平集的最優(yōu)值區(qū)間、期望模型和概率機會約束規(guī)劃方法來求解例1．當α=0.6時，可得該例的最好Stackelberg解和最差Stackelberg解分別為(14.4，0，21.5)和(13.4，0，20.7)．根據(jù)模型(7)，這兩個解相應的上層目標函數(shù)值分別為-186.6和-177.8，下層目標函數(shù)值分別為-60.00和-59.16．顯然，本文所提出的方法給出了更好的上層目標函數(shù)值；所得到的下層目標函數(shù)值好于最差Stackelberg解相應的目標值和略差于最好Stackelberg解相應的結果．考慮到上層決策者處于主導地位，更側重于關心上層目標函數(shù)值，因此本文方法得到的下層目標函數(shù)值是可接受的．

注意到模型中含有參數(shù)θ1、θ2、θ3，由于不同決策者會有想要達到的不同置信水平，因此需分析不同的置信水平對最優(yōu)解以及上下層目標函數(shù)最優(yōu)值的影響．為了方便計算，以下令θ1=θ2=θ3=θ．表2給出了置信水平θ的靈敏度分析．

由表2可以看出，不同的置信水平產(chǎn)生了不同的最優(yōu)解和不同的上下層目標函數(shù)值．當參數(shù)θ增大，上下層目標函數(shù)值H1和H2增大；反之隨著參數(shù)θ減小，兩個目標函數(shù)值減?。@是由于當參數(shù)θ取值較大時，問題的可行域將收縮，就會產(chǎn)生較差的目標函數(shù)值；反之θ取值較小時，問題的可行域將擴大，就會產(chǎn)生較好的目標函數(shù)值．此外，當參數(shù)θ取值較大時，破壞約束的風險將降低；反之θ取值較小時，破壞約束的風險將增大．

表2 例1中參數(shù)θ的靈敏度分析Tab.2 Sensitivity analysis of parameter θ of example 1

例2某一家電公司和其分公司生產(chǎn)4種廚房小家電，包括電壓力鍋、電磁爐、電烤箱和面包機．總公司處于決策主導地位，分公司處于決策從屬地位，他們的目標都是最小化各自生產(chǎn)費用．令上層決策變量x1、x2是總公司生產(chǎn)電壓力鍋、電磁爐的數(shù)量，下層變量y1、y2是分公司生產(chǎn)電烤箱和面包機的數(shù)量．由于市場經(jīng)濟的隨機變化和市場需求的模糊不確定性，總公司和分公司生產(chǎn)每一種家電的單位費用也是不確定的，既具有隨機性又具有模糊性，可考慮這些值為模糊隨機變量．此外，總公司和分公司的費用最小化需受到其原材料成本、人力成本、設備使用以及營銷成本的限制，相關參數(shù)也應考慮為模糊隨機變量．假定這些參數(shù)均是三角模糊隨機變量．基于以上分析，這個生產(chǎn)決策問題可通過如下模糊隨機雙層規(guī)劃模型表示：

(x3，x4)是下面問題的解：

x1≥0，x2≥0，x3≥0，x4≥0

(8)

其中模糊隨機變量系數(shù)的具體值見表3．

令置信水平θ1=θ2=θ3=θ4=0.9．由模型(5)，則問題(8)轉化為如下確定雙層線性規(guī)劃問題：

(x3，x4)是下面問題的解：

s.t.(1.0-0.1×0.5)x1+(1.0-0.1×0.4)x2+(1.0-0.1×0.3)x3+(1.0-0.1×0.4)x4≤50.0+0.1×1.5，

(1.0-0.1×0.8)x1+(3.0-0.1×0.5)x2+(1.0-0.1×0.3)x3+(5.0-0.1×0.4)x4≤80.0+0.1×1.5，

(1.0-0.1×0.6)x1+(4.0-0.1×0.5)x2+(2.0-0.1×0.4)x3+(4.0-0.1×0.8)x4≤100.0+0.1×1.5，

(2.0-0.1×0.2)x1+(2.0-0.1×0.8)x2+(6.0-0.1×0.6)x3+(3.0-0.1×0.4)x4≤120.0+0.1×1.0，

x1≥0，x2≥0，x3≥0，x4≥0

表3 例2模糊隨機變量系數(shù)Tab.3 Coefficients of fuzzy random variables of example 2

接下來令θ1=θ2=θ3=θ4=θ．現(xiàn)將置信水平分別設置為0.5、0.6、0.7、0.8和0.9，計算結果如表4所示．由表4可以看出，當θ=0.5時，獲得最好的上下層目標函數(shù)值分別為-149.382 0和-108.854 7；當θ=0.9時，獲得最差的上下層目標函數(shù)值分別為-129.285 8和-85.458 4．事實上，隨著置信水平降低，相應的確定性約束范圍變寬，更易產(chǎn)生更好的上下層目標函數(shù)最優(yōu)值；反之當置信水平提高，確定性約束范圍變窄，這將導致

表4 例2中參數(shù)θ的靈敏度分析Tab.4 Sensitivity analysis of parameter θ of example 2

更差的優(yōu)化結果．事實上，當置信水平較低時，即決策者提高了不滿足約束條件的風險水平，這將有利于獲得更好的上下層目標函數(shù)值．因此在實際的決策中，決策者可以根據(jù)自己的風險態(tài)度來選擇置信水平．例如，保守的決策者可以取較大的置信水平．

4 結 語

本文討論了一類上下層目標函數(shù)和約束函數(shù)中系數(shù)都是模糊隨機變量的雙層規(guī)劃問題．通過結合模糊隨機變量期望值、模糊數(shù)的確定可能性均值和模糊機會約束規(guī)劃方法，提出模糊隨機雙層確定可能性均值-機會約束規(guī)劃模型，給出確定雙層線性規(guī)劃，并利用K次最好算法進行求解．如何推廣本文提出的方法來求解模糊隨機多層規(guī)劃問題是下一步待研究的問題．

[1] KOZANIDIS G, KOSTARELOU E, ANDRIANESIS P,etal. Mixed integer parametric bilevel programming for optimal strategic bidding of energy producers in day-ahead electricity markets with indivisibilities [J].Optimization, 2013,62(8):1045-1068.

[2]FONTAINE P, MINNER S. Benders decomposition for discrete-continuous linear bilevel problems with application to traffic network design [J].TransportationResearchPartB:Methodological, 2014,70:163-172.

[3]WANG Danping, DU Gang, JIAO R J,etal. A Stackelberg game theoretic model for optimizing product family architecting with supply chain consideration [J].InternationalJournalofProductionEconomics, 2016,172:1-18.

[4]KALASHNIKOV V, MATIS T I, CAMACHO-VALLEJO J F,etal. Bilevel programming, equilibrium, and combinatorial problems with applications to engineering [J].MathematicalProblemsinEngineering, 2015,2015:490758.

[5]SAKAWA M, MATSUI T. Fuzzy random non-cooperative two-level linear programming through fractile models with possibility and necessity [J].EngineeringOptimization, 2013,45(7):811-833.

[6]REN Aihong, WANG Yuping. An interval approach based on expectation optimization for fuzzy random bilevel linear programming problems [J].JournaloftheOperationalResearchSociety, 2015,66(12): 2075-2085.

[7]SAKAWA M, MATSUI T. Bilevel linear programming with fuzzy random variables through absolute deviation minimization [J].InternationalJournalofOperationalResearch, 2016,25(1):1-27.

[8]REN Aihong, WANG Yuping. An interval programming approach for bilevel linear programming problem with fuzzy random coefficients [C] //2013IEEECongressonEvolutionaryComputation,CEC2013. Washington D C: IEEE Computer Society, 2013:462-469.

[9]PURI M L, RALESCU D A. Fuzzy random variables [J].JournalofMathematicalAnalysisandApplications, 1986,114(2):409-422.

[10]CARLSSON C, FULLéR R. On possibilistic mean value and variance of fuzzy numbers [J].FuzzySetsandSystems, 2001,122(2):315-326.

[11]LI Jun, XU Jiuping, GEN M. A class of multiobjective linear programming model with fuzzy random coefficients [J].MathematicalandComputerModelling, 2006,44(11/12):1097-1113.

[12]BIALAS W F, KARWAN M H. Two-level linear programming [J].ManagementScience, 1984,30(8):1004-1020.