網(wǎng)絡(luò)流對(duì)策中若干對(duì)策解的算法研究.pdf

1、合作對(duì)策考慮的中心問題是如何將聯(lián)盟的整體費(fèi)用(收益)公平合理的分配給聯(lián)盟N中的每個(gè)成員。根據(jù)不同的合理性要求產(chǎn)生了不同的對(duì)策解的概念,如核心、N-核、穩(wěn)定集和Shapley值等。對(duì)策解的定義往往是非常復(fù)雜的,算法設(shè)計(jì)是組合合作對(duì)策中重要的課題。網(wǎng)絡(luò)流對(duì)策源于網(wǎng)絡(luò)中與最大流相關(guān)的收益分配問題,是一類重要的組合合作對(duì)策,其算法研究具有重要意義。本文主要探討網(wǎng)絡(luò)流對(duì)策的核心和相對(duì)N-核的算法,主要結(jié)果有:
　　 (1)討論了帶有公共弧

2、的簡(jiǎn)單網(wǎng)絡(luò)流對(duì)策模型的核心元素的刻畫；利用最大流問題的弧一流表達(dá)式和線性規(guī)劃的對(duì)偶理論給出核心非空的充要條件的一個(gè)新證明；在此基礎(chǔ)上證明了該對(duì)策中有關(guān)核心的幾個(gè)算法問題(判斷核心的非空性、判定給定分配是否歸屬核心、構(gòu)造核心元素)都是多項(xiàng)式時(shí)間可解的。
　　 (2)對(duì)于不具有公共弧的簡(jiǎn)單網(wǎng)絡(luò)流對(duì)策模型,建立了其相對(duì)N-核的有效的刻畫；首先證明了當(dāng)網(wǎng)絡(luò)中最大流值等于1時(shí),相對(duì)N-核與對(duì)策的核心相同,不一定是單點(diǎn)集；其次利用Kopel