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

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

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