張立群

（蘭州交通大學(xué) 數(shù)理與軟件工程學(xué)院，甘肅 蘭州 730070）

0 引言

組合優(yōu)化問題是在給定的有限集所具備的某些條件的子集中，按某種目標(biāo)找出一個(gè)最優(yōu)符合標(biāo)準(zhǔn)的一類數(shù)學(xué)規(guī)劃問題［1］.所研究的問題涉及電路設(shè)計(jì)問題、運(yùn)輸線路問題、裝箱問題［2］等很多領(lǐng)域.下模函數(shù)是一類定義在有限的冪集上或格上的相對(duì)比較特殊的實(shí)值函數(shù)，下模函數(shù)的最值研究在組合優(yōu)化中起著重要的作用.

下模函數(shù)定義如下：給定一個(gè)有限集E和定義在E上的冪集合2E上的一個(gè)函數(shù)f：2E→Z，這里2E是由E的所有2｜E｜個(gè)子集組成的集合，如果對(duì)于E中任意兩個(gè)集合A和B，都滿足不等式

f（A）＋f（B）≥f（A∩B）＋f（A∪B），則稱f（·）是一個(gè)下模函數(shù).

本文考慮求解m個(gè)擬陣交構(gòu)成的獨(dú)立系統(tǒng)約束下的下模函數(shù)的最大值問題，即

OPT＝ max｛f（S），S∈F｝，

其中（E，F(xiàn)）是由m個(gè)擬陣的交構(gòu)成的獨(dú)立系統(tǒng).

1 若干定義、引理及其證明

定義1 設(shè)E是一個(gè)有限集合，L是E的一個(gè)子集族，若滿足I∈L且I′?I，則I′∈L，稱L中子集為獨(dú)立子集，稱（E，L）是一個(gè)獨(dú)立系統(tǒng).

定義2 設(shè)E是一個(gè)有限集合，L是一族E的子集合.如果（E，L）滿足兩個(gè)條件：

（1）若I∈L且I′?I，則I′∈L；

（2）對(duì)于E中的任意一個(gè)子集F，有u（F）＝v（F）；

就稱其是一個(gè)擬陣.

給定E的一個(gè)子集F，若F的任意一個(gè)獨(dú)立子集都不嚴(yán)格包含子集I?F，則稱I是F的一個(gè)極大獨(dú)立子集.對(duì)任意集合I?E，令｜I｜表示I中所包含元素的個(gè)數(shù).定義：

u（F）≡min｛｜I｜，I是F的一個(gè)極大獨(dú)立子集｝，v（F）≡max｛｜I｜，I是F的一個(gè)獨(dú)立子集｝.

證明 考慮以下給出的線性規(guī)劃：

容易得到其對(duì)偶規(guī)劃為

由于ρi≥ρi＋1，Zi＝ρi－ρi＋1，i＝1，2，…，k－1，ρk＝0是對(duì)偶可行解，其最優(yōu)值為，由線性規(guī)劃的對(duì)偶定理，易說明引理成立.

2 給出近似算法及其性能保證

OPT＝max｛f（S），S∈F｝，其中（E，F(xiàn)）是由m個(gè)擬陣的交構(gòu)成的獨(dú)立系統(tǒng).

給出近似算法及其近似度分析，求解fS｜F的近似算法示意［5］如下：

第1步 令i＝1，S0＝?，E0＝E；

第2步 若Ei－1＝?，則停止計(jì)算；

第3步 求ei∈Ei－1，使其滿足α·ρeij（Si－1）≥maxe∈Ei－1ρe（Si－1），α＞0；

第4步 判斷Si－1∪ ｛ei｝是否屬于F；

第5步 若Si－1∪ ｛ei｝不屬于F，則令Ei－1＝Ei－1＼｛ei｝，返回第2步；

若Si－1∪ ｛ei｝∈F，則令Si＝Si－1∪ ｛ei｝，ρi－1＝ρei（Si－1），Ei＝Ei－1＼｛ei｝；

第6步 令i＝i＋1，返回第2步.

下面繼續(xù)給出用近似算法求出的近似解的近似度分析.

定理 設(shè)（E，F(xiàn)）是一個(gè)由m個(gè)擬陣的交集相對(duì)獨(dú)立地構(gòu)成的系統(tǒng)，f是定義在Ω上的非負(fù)非減下模函數(shù)［4］.如果將Zg與OPT分別記作是通過以上近似算法得到的目標(biāo)函數(shù)值和目標(biāo)函數(shù)最優(yōu)解，那么有

證明 設(shè)S和T分別是問題fS｜F近似算法的解和最優(yōu)解，｜S｜＜k，由于（E，F(xiàn)）是一個(gè)獨(dú)立的系統(tǒng)，并不一定是擬陣，因此｜T｜不一定是k.

對(duì)于t＝1，2，…，k，令St－1＝T∩ （Ut＼Ut－1） ，Ut是第t次迭代得到的解集.為不失一般性，設(shè)U0＝ ?，Uk＝E，ρ＊（Si）＝ maxe∈Eiρe（Si），i＝1，2，…，k－1.

由于f是非負(fù)非減的下模函數(shù)，由引理2可以得到如下關(guān)系：

設(shè)t∈ ｛1，2，3，…，k｝，ρq（t）＝min｛ρi｜i＝1，2，…，t－1｝.對(duì)任意e∈T∩ （Ut＼Ut－1），由于f具有下模性，所以有

由ρ＊的定義和算法可得：ρe（S）≤ρe（St）≤ρ＊（St）≤ρ＊（Sq）（t）＋1）≤αρq（t）.

令ρ′t－1＝αρq（t），則有

由于q（t）具有非增性，所以ρ′t－1也具有非增性，即ρ′t－1≥ρ′t.另一方面

由上述不等式（1）和（2）可得

注意到St－1∈T∩ （Ut＼Ut－1） ，則有＝T∩Ut.

由于T是擬陣的獨(dú)立集，rM（SPM（St））＝t，，于是有

因?yàn)閷?duì) ?t，ρ′t，St≥0，ρ′t具有非增性，在引理2中，令，由上述不等式（5）有

再由不等式（4）得

即

［1］ 陳寶林.最優(yōu)化理論與算法［M］.北京：清華大學(xué)出版社，2006.

［2］ 羅亮，賈欣鑫，何尚錄，等.求解組合拍賣問題最大值的貪婪算法［J］.黑龍江科技學(xué)院學(xué)報(bào)，2008，18（5）：382－384.

［3］ FISHER M L，NEMHAUSER G L，WOLSEY L A，et al.An analysis of approximations for maximizing submodular set functions－II［J］.Mathematical Programming Study，1978，8：73－87.

［4］ SVIRIDENKO M.A note on maximizing a submodular set function subject to knapsack constraint［J］.Operations Research Letters，2004，32：41－43.

［5］ 王武民，張防防，柘曉莉，等.求解下模集函數(shù)最大值問題的局部搜索算法［J］.溫州大學(xué)學(xué)報(bào)：自然科學(xué)版，2008，29（3）：12－17.