線性三層規(guī)劃問題的模糊求解算法

陶李曼 (長江大學(xué)信息與數(shù)學(xué)學(xué)院，湖北 荊州 434023)

洪云飛 (長江大學(xué)期刊社，長江大學(xué)信息與數(shù)學(xué)學(xué)院，湖北 荊州 434023)

呂一兵 (長江大學(xué)信息與數(shù)學(xué)學(xué)院，湖北 荊州 434023)

多層規(guī)劃是一種具有遞階結(jié)構(gòu)的系統(tǒng)優(yōu)化問題[1～4]。在多層規(guī)劃中，每一層都有自己的目標(biāo)函數(shù)、約束條件和決策變量；每一層之間具有相對的獨(dú)立性，但是又會(huì)影響到其他決策層。一直以來，對多層規(guī)劃的研究主要集中在二層規(guī)劃問題。在二層規(guī)劃中，上層決策者首先給出自己的決策；下層決策者以上層決策為參數(shù)，選擇對自己最為有利的決策，然后再反饋給上層。在這樣不斷交互的過程中，雙方最終得到“最優(yōu)解”。

相比于雙層情況，一些實(shí)際決策問題可能涉及3個(gè)不同的決策者，同時(shí)這些決策者分別處于不同的層面。例如，在供應(yīng)鏈管理問題中，上層的材料供應(yīng)商通過制訂合適的材料價(jià)格來尋求利潤的最大化；中層的制造商通過制訂產(chǎn)品價(jià)格來最大化其利潤；而下層的分銷商通過訂購合適數(shù)量的產(chǎn)品來最大化個(gè)人的利潤。類似于雙層規(guī)劃，在上述三層決策問題中，每位決策者通過各自的決策變量來優(yōu)化其目標(biāo)函數(shù)，同時(shí)又會(huì)受到其他2位決策者的行為影響。

三層規(guī)劃問題正逐步引起研究者的關(guān)注。Bard[5]以下層問題的最優(yōu)性條件代替下層問題，同時(shí)將互補(bǔ)約束條件作為中層目標(biāo)函數(shù)的罰項(xiàng)，得到了相應(yīng)的二層規(guī)劃問題；然后對得到的二層規(guī)劃問題再次使用K-K-T條件轉(zhuǎn)化方法，從而得到了單層近似問題；最后對于單層近似問題設(shè)計(jì)了基于相鄰極點(diǎn)搜索的算法。在此基礎(chǔ)上，White[6]提出了線性三層規(guī)劃的罰函數(shù)方法，首先運(yùn)用線性規(guī)劃的對偶理論將線性三層規(guī)劃問題轉(zhuǎn)化成相應(yīng)的二層規(guī)劃問題；然后將二層規(guī)劃問題采用文獻(xiàn)[2]中的轉(zhuǎn)化方法，從而得到單層近似問題；最后以對偶間隙為罰項(xiàng)設(shè)計(jì)相應(yīng)的罰函數(shù)算法。Sinha[7,8]提出了線性多層規(guī)劃問題的K-K-T條件轉(zhuǎn)換方法。Ruan等[9]研究了多層規(guī)劃相關(guān)問題，分別討論了線性多層規(guī)劃的最優(yōu)條件和幾何性質(zhì)，在約束集S是有界且為非空的假設(shè)下，證明了線性多層規(guī)劃的可行集不僅由約束集S的一些非空面的并集組成，而且是連通的。Faísca[10]將二層規(guī)劃的參數(shù)求解算法推廣到三層規(guī)劃問題，其核心思想是將下層問題的最優(yōu)解以上一層的決策變量進(jìn)行。針對線性三層規(guī)劃問題的最優(yōu)解在可行域的頂點(diǎn)取得的性質(zhì)，Zhang等[11]設(shè)計(jì)了一種K-次最好算法，并且給出了相應(yīng)的算例。

相比于傳統(tǒng)的數(shù)值優(yōu)化方法，模糊規(guī)劃方法可以將各層決策者的目標(biāo)結(jié)合起來考慮，從而使優(yōu)化后的各層決策者的目標(biāo)值達(dá)到某種意義上的平衡。Lai[12]提出了最優(yōu)性隸屬度和決策力度的概念來解決多層規(guī)劃和分散優(yōu)化問題。在涉及到層次決策過程中，上層決策者(DM)首先在不考慮下層問題的情況下確定其每個(gè)可能目標(biāo)值的最優(yōu)值，從而得到上層DM最優(yōu)性的隸屬度函數(shù)，類似地為決策變量建立隸屬函數(shù)；然后觀察下層問題在給定約束下獨(dú)立計(jì)算出的最優(yōu)值，并建立下層DM的最優(yōu)性和決策權(quán)的隸屬函數(shù)。若得出的解不滿足條件，則下層DM的決策與相應(yīng)的最優(yōu)性和決策權(quán)的隸屬函數(shù)將提交給上層DM進(jìn)行修改，同時(shí)還要考慮到各層決策者的總體利益，直至達(dá)到最佳的解決方案。Shih[13]使用公差隸屬函數(shù)的概念，并對多目標(biāo)優(yōu)化設(shè)計(jì)了一種模糊方法：首先各層次的DM根據(jù)所有約束的集合獨(dú)立求解問題；然后根據(jù)公差建立所有DM目標(biāo)函數(shù)的隸屬度函數(shù)，上層DM確定最小滿意值，通過引入輔助變量將原問題轉(zhuǎn)化為線性規(guī)劃模型，并采用單純形法求解模型。該方法依賴于隸屬函數(shù)的變化而不是頂點(diǎn)枚舉，并且不會(huì)生成更高階的約束，因此，不會(huì)增加原始問題的復(fù)雜性，并且通常會(huì)在單次迭代中解決多層規(guī)劃問題。Sinha[14,15]設(shè)計(jì)了模糊數(shù)學(xué)規(guī)劃(FMP)方法來獲得線性多層規(guī)劃問題的解決方案，該方法使用線性隸屬函數(shù)的FMP方法來最小化目標(biāo)：首先通過獨(dú)立計(jì)算得到每一層DM的最優(yōu)解；然后決策過程從第1層開始，第1層DM將其最優(yōu)值范圍和決策向量提供給第2層DM，該步驟使用隸屬函數(shù)通過模糊集理論建模；如果得到的解決方案滿足條件，則第3層也包括在內(nèi)；否則，將修改公差值和隸屬函數(shù)，直到得到前2層問題滿意的解決方案，再將前2層的決策變量的首選值和目標(biāo)函數(shù)的最優(yōu)值界限傳遞給第3層DM；之后重復(fù)該過程，直到最后一層DM包含在系統(tǒng)中。

下面，筆者主要通過結(jié)合K-K-T條件轉(zhuǎn)換方法與模糊方法來求解線性三層規(guī)劃問題。該方法的主要思路為：采用下層問題的最優(yōu)性條件，將三層規(guī)劃問題轉(zhuǎn)化為下層含互補(bǔ)約束的二層規(guī)劃問題；然后采用模糊優(yōu)化方法求解得到的二層規(guī)劃問題，從而得到三層規(guī)劃問題的最優(yōu)解。

1 線性三層規(guī)劃問題的數(shù)學(xué)模型

考慮的線性三層規(guī)劃問題表述為：

(1)

式中：ci1∈Rn；ci2∈Rm；ci3∈Rp；bi∈Rqi；Ai∈Rqi×n；Bi∈Rqi×m；Ci∈Rqi×p；i=1,2,3；x,y,z分別為上層、中層和下層問題的決策變量；x∈Rn,y∈Rm,z∈Rp；f1,f2,f3:Rn×Rm×Rp→R分別是上層、中層和下層問題的目標(biāo)函數(shù)。

定義1線性三層規(guī)劃問題的約束集：

S={(x,y,z)≥0:Aix+Biy+Ciz≤bi,i=1,2,3}

對固定的x≥0，中層問題決策集：

S(x)={(y,z)≥0:Aix+Biy+Ciz≤bi,i=2,3}

對固定的(x,y)≥0，下層問題決策集：

S(x,y)={z≥0:A3x+B3y+C3z≤b3}

下層問題最優(yōu)決策集：

P(x,y)={z≥0:z∈arg min[f3(x,y,z):z∈S(x,y)]}

中層問題最優(yōu)決策集：

P(x)={(y,z)≥0:(y,z)∈arg min[f2(x,y,z):(y,z)∈S(x),z∈P(x,y)]}

三層規(guī)劃問題的誘導(dǎo)域：

IR={(x,y,z)≥0:(x,y,z)∈S,(y,z)∈P(x)}

三層規(guī)劃問題的最優(yōu)解集：

OS={(x,y,z)≥0:(x,y,z)∈arg min[f1(x,y,z):(x,y,z)∈IR]}

為了保證所考慮的問題(1)存在最優(yōu)解，假設(shè)線性三層規(guī)劃問題的誘導(dǎo)域IR為非空緊集。

在線性三層規(guī)劃問題(1)中，如果下層問題滿足一定的約束規(guī)格，那么對于給定的決策變量(x,y)，下層問題的K-K-T最優(yōu)性條件為：

(2)

u(b3-A3x-B3y-C3z3)=0

(3)

vz=0

(4)

A3x+B3y+C3z-b3≤0

(5)

u，v≥0

(6)

式中：L(x,y,z,u)=f3(x,y,z,u)+u(b3-A3x-B3y-C3z)+vz是下層問題的拉格朗日函數(shù)；zL(x,y,z,u)表示函數(shù)L(x,y,z,u)在z處的梯度；u,v是拉格朗日乘子。

定理1[16](y,z)∈P(x)的充分必要條件是存在向量u，使得(x,y,z,u)滿足上述條件(2)～(6)。

基于定理1，通過K-K-T條件，可以將線性三層規(guī)劃問題(1)轉(zhuǎn)化為如下含有互補(bǔ)約束的二層規(guī)劃問題(7)：

(7)

定理2[16](x,y,z)是三層規(guī)劃問題(1)的最優(yōu)解，當(dāng)且僅當(dāng)(x,y,z,u)為二層規(guī)劃問題(7)的最優(yōu)解。

基于定理1和定理2，結(jié)合模糊規(guī)劃方法來尋找三層規(guī)劃問題(1)的一個(gè)滿意解(x,y,z)。

2 二層規(guī)劃問題的交互式模糊規(guī)劃方法

基于文獻(xiàn)[17]中的模糊優(yōu)化方法，下面設(shè)計(jì)問題(7)的模糊求解算法。這里f1,f2分別表示上層DM和下層DM的目標(biāo)函數(shù)，先由上層DM給出一個(gè)模糊目標(biāo)和最小滿意水平，并且評價(jià)由下層DM提出的解，然后參照上層給出的模糊目標(biāo)及最小滿意水平，求出下層問題的最優(yōu)解。為了簡單起見，可以通過采用線性隸屬函數(shù)來表示每層DM的模糊目標(biāo)的特征，與其相應(yīng)的線性隸屬函數(shù)可定義為：

(8)

(9)

考慮到相應(yīng)二層之間的整體滿意平衡，則二層決策者的滿意度可定義為：

根據(jù)耦合協(xié)調(diào)度模型測算出的結(jié)果,選取2005，2010與2015年淮海經(jīng)濟(jì)區(qū)旅游經(jīng)濟(jì)和城鎮(zhèn)化的耦合度,并借助ArcGIS聚類工具對測度結(jié)果進(jìn)行可視化(圖1)．

λ=min{μ1(f1(x)),μ2(f2(x))}

(10)

則問題(9)可變?yōu)椋?/p>

(11)

2.1 二層規(guī)劃問題模糊算法交互過程的終止條件

一般而言，二層規(guī)劃問題模糊算法的終止性條件一般采用如下2條：

(2)滿意度比Δ在給定的區(qū)間內(nèi)，該上限由上層DM指定。

條件(1)表示上層DM為下層DM提出的解決方案所需的條件；條件(2)以便在2個(gè)級別之間保持整體令人滿意的平衡。除非同時(shí)滿足條件，否則上層DM需要更新其最小滿意水平。

2.2 二層規(guī)劃問題的模糊規(guī)劃算法

二層規(guī)劃問題的模糊規(guī)劃算法具體步驟如下：

步2下層DM給出其模糊目標(biāo)的隸屬函數(shù)μ2(f2(x))；

步4如果下層DM對上層DM提出的解滿足最后的終止條件，那么上層DM就把這個(gè)解認(rèn)為是滿意解，從而算法停止；否則，進(jìn)行下一步；

步6下層DM解問題(12)并向上層DM提出得到的解，返回步4:

(12)

3 數(shù)值試驗(yàn)

例1考慮如下線性三層規(guī)劃問題，其中，x1∈R,x2∈R,x3∈R：

(13)

將上述三層規(guī)劃問題通過下層問題的K-K-T條件轉(zhuǎn)化為如下帶互補(bǔ)約束的二層規(guī)劃問題：

(14)

每層對應(yīng)的目標(biāo)函數(shù)最優(yōu)解和最優(yōu)值如表1所示。

表1 問題(14)每層對應(yīng)的目標(biāo)函數(shù)最優(yōu)解和最優(yōu)值

s.t. 2x2-x3≥2

眾所周知，授人以魚不如授人以漁，課堂教學(xué)更是如此。作為教師的我們不可能手把手地教學(xué)生讀每一本課外書，因而閱讀方法的指導(dǎo)就顯得尤為重要。在閱讀指導(dǎo)課上，我首先就對學(xué)生進(jìn)行了閱讀整本書的方法指導(dǎo)。

-3x1+x2-x3≥-12

-3x2-x3≥-24

x1≥2

-x3≥-6

-2+u1+u2+u3+u5-u6=0

u1(2x2-x3-2)=0

u2(-3x1+x2-x3+12)=0

u3(-3x2-x3+24)=0

u4(x1-2)=0

u5(-x3+6)=0

u6x3=0

λ∈[0,1],x≥0

f1=-9.6μ1(f1(x))=0.85

f2=2.15μ2(f2(x))=0.787

在文獻(xiàn)[1]中，該問題的最優(yōu)解為(4.667,1.0)，其各層的最優(yōu)值及滿意度為：

f1=-16.668μ1(f1(x))=0.431

f2=-1μ2(f2(x))=0.25

f3=0μ3(f3(x))=0

由上述的分析可看出，模糊規(guī)劃算法得出的解對應(yīng)的各層滿意度更高；文獻(xiàn)[1]中給出的方法所得到的解雖然是例1的全局最優(yōu)解，但對應(yīng)的各層DM的滿意度并不理想。

例2考慮如下線性三層規(guī)劃問題，其中，x∈R，y∈R，z∈R：

(15)

將上述線性三層規(guī)劃問題通過K-K-T條件轉(zhuǎn)化為如下問題：

(16)

每層對應(yīng)的目標(biāo)函數(shù)最優(yōu)解和最優(yōu)值如表2所示：

表2 問題(16)每層對應(yīng)的目標(biāo)函數(shù)最優(yōu)解和最優(yōu)值

f1=-14.28μ1(f1(x))=0.7

f2=4.062μ2(f2(x))=0.618

在文獻(xiàn)[14]中，該問題的最優(yōu)解為(4,6,0)，其各層的最優(yōu)值及滿意度為：

f1=-20μ1(f1(x))=0.916

f2=10μ2(f2(x))=0.025

f3=-8μ3(f3(x))=0.583

通過比較可以看出，模糊規(guī)劃算法得出的解對應(yīng)的各層滿意度相對更高；而K次最好算法中上層DM完全占主導(dǎo)地位，下層DM無條件地服從上層的領(lǐng)導(dǎo)，并且在解線性多層規(guī)劃問題相對應(yīng)的模糊規(guī)劃問題時(shí)，K次最好算法需要經(jīng)過多次迭代才能得到問題的解。

4 結(jié)語

結(jié)合K-K-T條件轉(zhuǎn)化方法與模糊方法求解了三層規(guī)劃問題：首先通過K-K-T條件將三層問題轉(zhuǎn)化為二層，再用模糊集理論中的隸屬函數(shù)來描述各層決策者的目標(biāo)函數(shù)，通過求解各層滿意度的交互過程，最后達(dá)到整體的滿意度平衡。由于最上層主觀指定的滿意度具有隨意性，因此提出的方法需要進(jìn)一步研究和完善。