王 煒，李忠偉，王丹丹

（遼寧師范大學(xué) 數(shù)學(xué)學(xué)院，遼寧 大連 116029）

隨機(jī)規(guī)劃是一類含有隨機(jī)因素的數(shù)學(xué)規(guī)劃問題。在數(shù)學(xué)規(guī)劃問題的模型中引入隨機(jī)變量，能夠使模型更加符合實(shí)際情況，從而使決策更加合理。極小極大隨機(jī)線性優(yōu)化問題是由?á?ková[1]率先提出的。求解極小極大隨機(jī)優(yōu)化問題的算法包括樣本均值近似法[2]、基于梯度法[3]、切平面算法[4]和橢球算法[5]等。本研究在概率分布集合由一階矩和二階矩刻畫時(shí)，將兩階段極小極大隨機(jī)線性優(yōu)化問題轉(zhuǎn)化為為半定優(yōu)化問題。

面對各項(xiàng)系數(shù)都含有隨機(jī)變量的規(guī)劃問題時(shí)，往往需要在觀察到隨機(jī)變量的實(shí)現(xiàn)之前作出決策，會(huì)導(dǎo)致某些決策不滿足約束條件。此時(shí)，通常需要建立和引入二階段有補(bǔ)償?shù)膯栴}模型，既可以使決策滿足約束條件，又可以使損失懲罰達(dá)到最小。本研究擬引入帶有固定補(bǔ)償?shù)臉O小極大兩階段隨機(jī)線性優(yōu)化問題模型[6]解決含有隨機(jī)變量的數(shù)學(xué)規(guī)劃問題，如式（1）所示。

其中，

x為一階段決策變量，二階段決策變量w取自集合X(x) ={x ∈Rn:Ww= h - Tx,w ≥0}，W為補(bǔ)償矩陣，T為影響隨機(jī)變量ξ的一個(gè)參數(shù)矩陣，h為常量。P為隨機(jī)參數(shù)ξ的概率分布，在實(shí)際應(yīng)用中一般不能精確地求得，所以通常用概率分布集合P上第二階段期望成本的最大值來處理概率分布的不確定性。

為了使模型更接近實(shí)際，從而得到更加可靠的數(shù)值解，通常將風(fēng)險(xiǎn)考慮到模型中。風(fēng)險(xiǎn)建模的方法是在二階段成本中采用一個(gè)效用函數(shù)U(·)，如式（2）所示。

其中，效用函數(shù)U(Q(x,ξ))為置信水平為ε的最壞情況下的條件風(fēng)險(xiǎn)值

因此，式（2）即為本文要研究的兩階段隨機(jī)線性優(yōu)化問題的目標(biāo)函數(shù)。

設(shè)μ ∈Rk是均值，Σ ∈Sk是協(xié)方差矩陣（Sk為k 維對稱矩陣的集合），為了保證二階期望成本EP[U(Q(x,ξ))]有定義，假設(shè)μ,Σ是有限的，且Σ ?0，則由一階矩和二階矩描述的所有概率分布構(gòu)成的集合可表示為

A ?0 表示A 是正定矩陣，A-?0 表示A 是半正定的。同理，A ?0 表示A 是負(fù)定矩陣，A-?0 表示A 是負(fù)半定的。

1 目標(biāo)函數(shù)的內(nèi)部極大化

考慮式（2）的內(nèi)部極大化問題

假設(shè)該優(yōu)化問題的概率分布P對應(yīng)的測度為F，則式（3）就等價(jià)為

引入Lagrange乘子ζ ∈R,η ∈Rk,G ∈Sk，則式（4）的Lagrange函數(shù)為

其中，矩陣A,B的內(nèi)積定義為A,B = tr(ATB)，tr(· )表示矩陣的跡。由強(qiáng)對偶定理[7]可知

因此，式（4）的對偶問題為

2 效用函數(shù)的等價(jià)形式

由條件風(fēng)險(xiǎn)值的定義

可得

引入Lagrange乘子y0∈R,y ∈Rk,Y ∈Sk，則式（7）中的極大值函數(shù)

可得式（8）的對偶問題為

式（10）中的約束可以寫成兩個(gè)等價(jià)的約束

3 結(jié)論

將式（14）代入式（6）的約束[ξT1]H[ξT1]T≥U(Q(x,ξ))中，可得

即

上式又等價(jià)為

即

因此

綜上所述，問題（2）最終可以轉(zhuǎn)化為

把Ω、H、M帶入問題（15）中得半定規(guī)劃問題