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

王建忠，杜 綱

0 引言

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

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

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

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

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

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

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

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

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

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

(4)若某個(gè) xi或 yj是自由變量，一般不通過(guò)變換將其轉(zhuǎn)化為大于零的變量。因?yàn)樵诟鞣N處理區(qū)間線性雙層規(guī)劃的方法中，可能會(huì)導(dǎo)致和x'i的系數(shù)不同，使變換失去意義。

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

(6)模型中僅涉及不等式約束。因?yàn)榈仁绞且环N嚴(yán)格的數(shù)量關(guān)系要求，區(qū)間等式在實(shí)際應(yīng)用中比較少見(jiàn)，而且一般將其轉(zhuǎn)化為各種形式的不等式約束來(lái)解釋相等關(guān)系。

2 最小最大后悔解的定義及性質(zhì)

定義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}；

對(duì)于x∈S，下層規(guī)劃的合理反應(yīng)集：

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

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

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

假設(shè)1約束域Ω非空且為緊集。

假設(shè)2對(duì)任意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）即轉(zhuǎn)化為確定型雙層規(guī)劃。根據(jù)定義3可知，對(duì)于(x,y)∈CS，無(wú)論系數(shù)c1,d1如何取值，(x,y)都是c1,d1取定后的確定型線性雙層規(guī)劃的最優(yōu)解。

根據(jù)定義4可知，對(duì)于 (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)解并不存在。下面引入后悔度及最小最大后悔度解的定義。

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

然而，在現(xiàn)實(shí)決策前，不可能猜到區(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)的最小最大后悔解可通過(guò)問(wèn)題(3)求解：

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

證明：由假設(shè)條件1和2下，IR非空，故對(duì)于任意給定的 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)的一個(gè)完全最優(yōu)解。

證明：假設(shè)(x*,y*)不是區(qū)間線性雙層規(guī)劃(2)的一個(gè)完全最優(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)的一個(gè)完全最優(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)式的內(nèi)層規(guī)劃問(wèn)題(5):

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

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

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

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

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

（3）選擇策略：采用轉(zhuǎn)盤(pán)賭選擇法和精英保留法組合的方法。

（4）交叉策略：采用自適應(yīng)算術(shù)交叉,其中交叉概率隨個(gè)體的適應(yīng)度大小變化，交叉概率

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

（5）變異策略：采用自適應(yīng)隨機(jī)變異，其中變異概率隨變異個(gè)體的適應(yīng)度大小變化，變異概率

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

在[1,m]上生成一個(gè)隨機(jī)整數(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ī)劃得到的相應(yīng)的解。

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

4 算例

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

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

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

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

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

5 結(jié)語(yǔ)

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

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