一類區間線性雙層規劃的最小最大后悔解及其解法

王建忠，杜 綱

0 引言

雙層規劃由于其廣泛的實際背景而成為近年來一個重要研究主題，在理論和算法方面都取得了一系列的成果。這些成果主要是針對確定性的問題，但現實中許多遞階決策問題具有一定的不確定性。在各種不確定性的類型中，具有區間系數的規劃問題是最基本和重要的一種。這不僅因為其在實際應用中最為簡單和常用，而且其他不確定性的類型如含有模糊系數和隨機系數的情形[1]往往要化為區間系數的情形來處理。因此，研究具有區間系數的雙層規劃問題具有十分重要的意義。

目前，對于區間雙層規劃的研究還很少。本文將最小最大后悔原則方法[2～6]推廣到區間線性雙層規劃，提出了基于遺傳算法的求解方法，最后通過算例說明了方法的可行性和有效性。

1 區間線性雙層規劃

本文考慮如下形式的區間雙層線性規劃：

y是下面規劃的解: （1）

模型(1)的矩陣向量形式分別為：

對區間線性雙層規劃(1)作如下說明：

(1)對Min F型可通過Max-F變為以上形式；

(2)對≥型的約束，可通過兩邊同乘－1變為≤型的約束；

(3)若某個 xi≤0，通過變換 x'i=-xi，有 x'i≥0；yj≤0可作同樣處理；

(4)若某個 xi或 yj是自由變量，一般不通過變換將其轉化為大于零的變量。因為在各種處理區間線性雙層規劃的方法中，可能會導致和x'i的系數不同，使變換失去意義。

(5)對于自由變量 xi，可分別討論 xi≤0和 xi≥0的情形，然后根據決策問題的需要以及區間處理方法的選擇來進一步分析。

(6)模型中僅涉及不等式約束。因為等式是一種嚴格的數量關系要求，區間等式在實際應用中比較少見，而且一般將其轉化為各種形式的不等式約束來解釋相等關系。

2 最小最大后悔解的定義及性質

定義1區間線性雙層規劃(2)的約束域：

Ω={(x,y)|A1x≤h1,A2x+B2y≤h2,x≥0,y≥0}

約束域Ω在上層決策空間的投影：

S={x|?y,A1x≤h1,A2x+B2y≤h2,x≥0,y≥0}；

對于x∈S，下層規劃的合理反應集：

M(x)={y|y∈argmax{c2x+d2y,B2y≤h2-A2x,y≥0}}；

區間線性雙層規劃(2)的誘導域：

IR={(x,y)|(x,y)∈Ω,y∈M(x)}。

假設1約束域Ω非空且為緊集。

假設2對任意x∈S，下層規劃有唯一最優解。

定義2給定c1∈[-c1,cˉ1]，d1∈[-d1,dˉ1]，稱OS(c1,d1)={(x',y')∈IR|c1x'+d1y'=為區間線性雙層規劃在c1,d1下的最優解集。

取定c1,d1后，區間線性雙層規劃（2）即轉化為確定型雙層規劃。根據定義3可知，對于(x,y)∈CS，無論系數c1,d1如何取值，(x,y)都是c1,d1取定后的確定型線性雙層規劃的最優解。

根據定義4可知，對于 (x,y)∈PS，必然存在c1∈[-c1,cˉ1]，d1∈[-d1,dˉ1]使得 (x,y)為 c1,d1取定后的線性雙層規劃的最優解。

顯然，完全最優解是區間線性雙層規劃(2)最為理想的解定義，但很多情況下，完全最優解并不存在。下面引入后悔度及最小最大后悔度解的定義。

假設以某個(x*,y*)∈IR為區間線性雙層規劃(2)的解，而在此決策后，上層決策者知道目標函數中的區間系數的真正取值為c*1,d1*。1,d*1下的后悔度。

然而，在現實決策前，不可能猜到區間系數的真正取值，故

定義6稱R(x*,y*)=y*)]為 (x*,y*)在 c*定義5稱(c1, d 1,x*,y*) 為(x*,y*)∈IR的最大后悔度。

根據定義5、6和7，區間線性雙層規劃(2)的最小最大后悔解可通過問題(3)求解：

定理1在假設條件1和2下，區間線性雙層規劃(2)必然存在最小最大后悔解。

證明：由假設條件1和2下，IR非空，故對于任意給定的 c1∈[-c1,cˉ1],d1∈[1,1]，(2)均有最優解。根據定義7可知，區間線性雙層規劃(2)必然存在最小最大后悔解。證畢。

定理2若(x*,y*)是區間線性雙層規劃(2)的最小最大后悔解，且最大后悔值R(x*,y*)=0，則(x*,y*)為(2)的一個完全最優解。

證明：假設(x*,y*)不是區間線性雙層規劃(2)的一個完全最優解，即存在 c1'∈[c-1,cˉ1],d1'∈[-d1,dˉ1]和 (x',y')≠(x*,y*)使得(x',y')是取c1=c1'，d1=d1'后線性雙層規劃(2)的最優解，則有 c1'x'+d1'y'＞c1'x*-d1'y*。根據最大后悔度的定義，d'1y*＞0，與R(x*,y*)=0矛盾。故(x*,y*)(2)的一個完全最優解。證畢。

定理3(4)的最優解為區間線性雙層規劃(2)的最小最大后悔解。

其中，φ ={(c11,…,c1m,d11,…,d1n)|c1i=cˉ1i或-c1i,d1j=dˉ1j或-d1j,i=1,…,m,j=1,…,n}。

證明：任意給定(x*,y*)∈IR，考慮(3)式的內層規劃問題(5):

設(5)的最優解為 c*1∈[-c1,cˉ1],d*1∈[-d1,dˉ1],(xˉ,yˉ)。

3 基于遺傳算法的最小最大后悔解求解

具有區間系數的規劃問題的最小最大后悔解的求解比較復雜，即便是最簡單的區間線性規劃。Averbakh和Lebedev證明了基于最小最大后悔度的區間系數目標函數的線性規劃的計算復雜性是NP-Hard的。遺傳算法是一種通過模擬自然進化過程搜索最優解的方法，具有較好的全局收斂性。本文采用實數編碼的遺傳算法求解區間線性雙層規劃的最小最大后悔解，具體設計如下：

（1）個體表達：個體(x,y)采用實數編碼，每個個體中y的取值通過單純形法計算(2)的下層規劃求得。

（2）適應度函數： Fit(x[r],y[r])=M-+d1y-c1x[r]-d1y[r])，其中，M為較大的數；ψ中的每個元素由(c1,d1)∈φ及其對應的線性雙層規劃的最優解(x,y)組成。

（3）選擇策略：采用轉盤賭選擇法和精英保留法組合的方法。

（4）交叉策略：采用自適應算術交叉,其中交叉概率隨個體的適應度大小變化，交叉概率

式中，fmax為最大適應度值，favg為當代群體中的平均適應度值，Fit'為要交叉的兩個個體中較大的適應度值。設交叉的個體為 x[r1]和 x[r2]，則后代中的分別為將代入(2)求下層規劃得到的相應的解，其中β為[-0.2,1.2]上的隨機數。若交叉后代不可行，則重新生成隨機數β，重新進行交叉。

（5）變異策略：采用自適應隨機變異，其中變異概率隨變異個體的適應度大小變化，變異概率

設x*為變異個體，在[0,1]上生成隨機數β2和β3，

在[1,m]上生成一個隨機整數k，β2≥0.5，令x'

i=x*i,i=1…,k-1,k+1,…,m,x'k=x*k+ β3(xˉk-x*k)；否 則 ，令x'i=x*i,i=1…,k-1,k+1,…,m,x'k=x*k-β3(x*k-)，其中 xˉk和為(6)和(7)的解，y'為將 x'代入(2)求下層規劃得到的相應的解。

若變異后代(x',y')不可行，則重新進行變異。

4 算例

考慮如下區間線性雙層規劃：

x2,x3是如下規劃的解

首先，計算(c1,d1)∈φ時，各種系數組合下(8)的最優解，如表1所示：

表1 不同系數取值下的最優解

采用遺傳算法對其求解,設置種群規模為20，交叉概率參數 Pc1=0.4，Pc2=0.1，變異概率參數 Pm1=0.1，Pm2=0.05，最大迭代次數為500。通過Matlab R2008a計算得最小最大后悔解為（1,1.5,0.5）,即當上層決策者選擇x=1為決策時，最大后悔度最小，最大后悔度的值為1。

5 結語

具有區間系數的雙層規劃是一類重要的不確定遞階決策問題。針對上層目標函數具有區間系數的區間線性雙層規劃，提出了最小最大后悔解的概念，并討論了其與可能最優解和完全最優解的關系，根據最小最大后悔解的特點設計了基于遺傳算法的求解方法。數值算例驗證了算法的有效性和可行性。

[1]彭錦,劉寶碇.不確定規劃的研究現狀及其發展前景.運籌與管理,2002,11(2).

[2]Shimizu K,Aiyoshi E.Necessary Conditions for Min-max Problems and Algorithms by a Relaxation Procedure[J].IEEE Transactions on Automatic Control,1980,（25）.

[3]Inuiguchi M,Sakawa M.Maximum Regret Analysis in Linear Programs with an Interval Objective Function[C].In Proceedings of IWSCI’96,1996.

[4]Mausser H E,Laguna M.A.New Mixed Integer Formulation for the Maximum Regret Problem[C].Working Paper,Graduate School of Business,University of Colorado,Boulder,CO,1997.

[5]Kouvelis P,Yu G.Robust Discrete Optimization and Its Applications[M].Boston:Kluwer Academic Publishers,1997.

[6]Mausser H E,Laguna M.A Heuristic to Minimax Absolute Regret for Linear Programs with Interval Objectives Function Coefficients[J].European Journal of Operational Research,1999,117(1).