一類區(qū)間線性雙層規(guī)劃的最小最大后悔解及其解法

王建忠，杜 綱

0 引言

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

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

1 區(qū)間線性雙層規(guī)劃

本文考慮如下形式的區(qū)間雙層線性規(guī)劃：

y是下面規(guī)劃的解: （1）

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

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

(1)對Min F型可通過Max-F變?yōu)橐陨闲问剑?/p>

(2)對≥型的約束，可通過兩邊同乘－1變?yōu)椤苄偷募s束；

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

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

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

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

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

定義1區(qū)間線性雙層規(guī)劃(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，下層規(guī)劃的合理反應集：

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

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

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

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

假設2對任意x∈S，下層規(guī)劃有唯一最優(yōu)解。

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

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

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

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

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

然而，在現(xiàn)實決策前，不可能猜到區(qū)間系數(shù)的真正取值，故

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

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

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

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

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

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

定理3(4)的最優(yōu)解為區(qū)間線性雙層規(guī)劃(2)的最小最大后悔解。

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

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

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

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

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

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

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

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

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

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

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

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

在[1,m]上生成一個隨機整數(shù)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)求下層規(guī)劃得到的相應的解。

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

4 算例

考慮如下區(qū)間線性雙層規(guī)劃：

x2,x3是如下規(guī)劃的解

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

表1 不同系數(shù)取值下的最優(yōu)解

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

5 結語

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

[1]彭錦,劉寶碇.不確定規(guī)劃的研究現(xiàn)狀及其發(fā)展前景.運籌與管理,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).