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

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

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

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

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

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