線性三層規劃問題的模糊求解算法

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

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

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

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

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

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

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

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

1 線性三層規劃問題的數學模型

考慮的線性三層規劃問題表述為：

(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分別是上層、中層和下層問題的目標函數。

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

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}

下層問題最優決策集：

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

中層問題最優決策集：

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

三層規劃問題的誘導域：

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

三層規劃問題的最優解集：

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

為了保證所考慮的問題(1)存在最優解，假設線性三層規劃問題的誘導域IR為非空緊集。

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

(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是下層問題的拉格朗日函數；zL(x,y,z,u)表示函數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條件，可以將線性三層規劃問題(1)轉化為如下含有互補約束的二層規劃問題(7)：

(7)

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

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

2 二層規劃問題的交互式模糊規劃方法

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

(8)

(9)

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

根據耦合協調度模型測算出的結果,選取2005，2010與2015年淮海經濟區旅游經濟和城鎮化的耦合度,并借助ArcGIS聚類工具對測度結果進行可視化(圖1)．

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

(10)

則問題(9)可變為：

(11)

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

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

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

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

2.2 二層規劃問題的模糊規劃算法

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

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

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

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

(12)

3 數值試驗

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

(13)

將上述三層規劃問題通過下層問題的K-K-T條件轉化為如下帶互補約束的二層規劃問題：

(14)

每層對應的目標函數最優解和最優值如表1所示。

表1 問題(14)每層對應的目標函數最優解和最優值

s.t. 2x2-x3≥2

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

-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

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

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

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

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

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

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

(15)

將上述線性三層規劃問題通過K-K-T條件轉化為如下問題：

(16)

每層對應的目標函數最優解和最優值如表2所示：

表2 問題(16)每層對應的目標函數最優解和最優值

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

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

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

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

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

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

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

4 結語

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