箱覆蓋對(duì)策及其核心的算法和計(jì)算復(fù)雜性.pdf

1、具有特征函數(shù)的合作對(duì)策模型Γ=是由局中人集合N={1,2,…,n}=N n和支付特征函數(shù)γ:2n→R所構(gòu)成的。當(dāng)聯(lián)盟S(S包含于N)的特征函數(shù)值γ(S)表示其該聯(lián)盟的局中人合作所獲得的收益（費(fèi)用）時(shí)，稱(chēng)該對(duì)策為收益（費(fèi)用）對(duì)策。如果特征函數(shù)值可通過(guò)求解某個(gè)組合最優(yōu)化問(wèn)題所確定，則稱(chēng)該對(duì)策為組合合作對(duì)策，其特點(diǎn)是對(duì)策的表達(dá)是簡(jiǎn)潔的，即其輸入規(guī)模是局中人個(gè)數(shù)的多項(xiàng)式長(zhǎng)度。合作對(duì)策理論主要是研究如何將聯(lián)盟的整體收益合理分配給參與合作

2、的各個(gè)理性參與人。其不同的公平、合理性條件導(dǎo)出了對(duì)策的各種解的概念。其中，核心(Core)及相關(guān)若干近似核心等是最重要的對(duì)策解，它們通過(guò)分配的聯(lián)盟合理性要求達(dá)到聯(lián)盟的穩(wěn)定。當(dāng)前，有關(guān)核心和近似核心的算法和計(jì)算復(fù)雜性問(wèn)題是合作對(duì)策研究的熱點(diǎn)，典型的計(jì)算問(wèn)題有：
　　(1)非空性判定：能否在多項(xiàng)式時(shí)間內(nèi)判定核心或近似核心是非空的？
　　(2)構(gòu)造問(wèn)題：如何在多項(xiàng)式時(shí)間內(nèi)構(gòu)造出屬于（近似）核心的一個(gè)分配？
　　(3)歸屬性判

3、定：能否在多項(xiàng)式時(shí)間內(nèi)判定一個(gè)給定分配屬（近似）核心？
　　本文主要針對(duì)建立在經(jīng)典的箱覆蓋問(wèn)題基礎(chǔ)上的一類(lèi)合作對(duì)策模型進(jìn)行研究，稱(chēng)為箱覆蓋對(duì)策。一般地，箱覆蓋問(wèn)題是將具有不同權(quán)重的多個(gè)物品分配到盡可能多的固定大小箱子中，要求分配到每個(gè)箱子中的物品總權(quán)重不小于箱子的大?。匆笙渥颖桓采w）。箱覆蓋問(wèn)題在實(shí)際中得到了廣泛應(yīng)用，如投資問(wèn)題等。建立箱覆蓋合作對(duì)策模型的目的是為了深入探討與此相關(guān)的收益分配問(wèn)題。
　　本文研究箱覆蓋對(duì)策

4、的性質(zhì)，并從計(jì)算復(fù)雜性和算法角度對(duì)核心和近似核心的有關(guān)算法問(wèn)題進(jìn)行討論。主要研究?jī)?nèi)容有：
　　(1)首先定義了由箱覆蓋問(wèn)題導(dǎo)出的合作對(duì)策模型——箱覆蓋對(duì)策：每個(gè)局中人對(duì)應(yīng)具有一定權(quán)重的物品，對(duì)于任意聯(lián)盟，其特征函數(shù)值是該聯(lián)盟所能覆蓋的最多箱子數(shù)；討論了該對(duì)策及其（近似）核心分配的若干性質(zhì)；對(duì)應(yīng)箱覆蓋問(wèn)題的0-1規(guī)劃模型，利用列生成法和動(dòng)態(tài)規(guī)劃方法給出了其線性規(guī)劃松弛的一個(gè)精確算法，利用這個(gè)算法可以很好地近似箱覆蓋對(duì)策的特征函數(shù)值。

5、
　　(2)對(duì)于整體聯(lián)盟的箱覆蓋數(shù)的0-1規(guī)劃(ILPn)，利用線性規(guī)劃對(duì)偶定理，箱覆蓋對(duì)策核心非空當(dāng)且僅當(dāng)該0-1規(guī)劃的線性規(guī)劃松弛(LP)N有整數(shù)最優(yōu)解，且此時(shí)核心恰是線性規(guī)劃松弛(LPn)的對(duì)偶最優(yōu)解集；當(dāng)核心是空集時(shí)，證明了能夠保證ε-近似核心非空的最小ε值（記為ε*mine）可由(ILPn)與其線性規(guī)劃松弛(LPn)的最優(yōu)目標(biāo)函數(shù)值的差來(lái)刻畫(huà)。
　　(3)研究了箱覆蓋對(duì)策有關(guān)核心和近似核心的計(jì)算復(fù)雜性和算法問(wèn)題。首