基于確定可能性均值法求解模糊隨機(jī)雙層規(guī)劃問(wèn)題

任 愛(ài) 紅

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

0 引 言

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

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

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

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

1 理論基礎(chǔ)

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

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

2.1 問(wèn)題形式

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

x2是下面問(wèn)題的解：

k=1，2，…，m，

x1=(x11x12…x1n1)T≥0，

x2=(x21x22…x2n2)T≥0

(1)

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

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

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

x2是下面問(wèn)題的解：

k=1，2，…，m，

x1=(x11x12…x1n1)T≥0，

x2=(x21x22…x2n2)T≥0

(2)

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

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

k=1，2，…，m

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

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

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

x2是下面問(wèn)題的解：

x1=(x11x12…x1n1)T≥0，

x2=(x21x22…x2n2)T≥0

(3)

對(duì)給定的θk(k=1，2，…，m)，令模型(3)的約束域?yàn)?/p>

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

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

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

在給定置信水平θk(k=1，2，…，m)下，定義模型(1)的M-POS-可行域?yàn)?/p>

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

x2∈M(x1;θk)}

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

2.3 確定等價(jià)形式

且λ-水平集為

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

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

等價(jià)于

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

x2是下面問(wèn)題的解：

x1=(x11x12…x1n1)T≥0，

x2=(x21x22…x2n2)T≥0

(4)

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

x2是下面問(wèn)題的解：

x1=(x11x12…x1n1)T≥0，

x2=(x21x22…x2n2)T≥0

(5)

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

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

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

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

x1≥0，x2≥0，x3≥0

(6)

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

表1 例1中上下層目標(biāo)函數(shù)和約束函數(shù)右側(cè)系數(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)是下面問(wèn)題的解：

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)

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

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

由表2可以看出，不同的置信水平產(chǎn)生了不同的最優(yōu)解和不同的上下層目標(biāo)函數(shù)值．當(dāng)參數(shù)θ增大，上下層目標(biāo)函數(shù)值H1和H2增大；反之隨著參數(shù)θ減小，兩個(gè)目標(biāo)函數(shù)值減?。@是由于當(dāng)參數(shù)θ取值較大時(shí)，問(wèn)題的可行域?qū)⑹湛s，就會(huì)產(chǎn)生較差的目標(biāo)函數(shù)值；反之θ取值較小時(shí)，問(wèn)題的可行域?qū)U(kuò)大，就會(huì)產(chǎn)生較好的目標(biāo)函數(shù)值．此外，當(dāng)參數(shù)θ取值較大時(shí)，破壞約束的風(fēng)險(xiǎn)將降低；反之θ取值較小時(shí)，破壞約束的風(fēng)險(xiǎn)將增大．

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

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

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

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

(8)

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

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

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

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模糊隨機(jī)變量系數(shù)Tab.3 Coefficients of fuzzy random variables of example 2

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

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

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

4 結(jié) 語(yǔ)

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

[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.