若干組合優(yōu)化對策模型中的算法問題.pdf

1、合作對策考慮的是如何將收益v(N)合理地分配給聯(lián)盟N中的成員。根據(jù)不同的合理性要求產(chǎn)生了不同的對策解的概念，如核心，核子等等。在這篇論文中，我們主要討論的對策模型是由Kalai和Zemel在1982年首先提出的網(wǎng)鉻流對策，討論的內(nèi)容包括：網(wǎng)絡(luò)流對策的核心穩(wěn)定性和網(wǎng)絡(luò)流對策中核子計(jì)算的算法問題，主要結(jié)果有：·我們先定義了一種特殊的弧，稱之為亞元，亞元滿足的性質(zhì)是：在網(wǎng)絡(luò)中去掉亞元后不會影響網(wǎng)絡(luò)的最大流值。基于這一概念，我們證明了簡單網(wǎng)絡(luò)流

2、對策有穩(wěn)定的核心當(dāng)且僅當(dāng)網(wǎng)絡(luò)中沒有亞元。 ·我們討論了三個(gè)與核心穩(wěn)定性密切相關(guān)的性質(zhì)：核心的包容性、對策的精確性和可擴(kuò)性的等價(jià)性，并證明了它們這三個(gè)性質(zhì)與如下條件等價(jià)：在簡單網(wǎng)絡(luò)中每個(gè)(s，t)一截包含一個(gè)最小(s，t)一截。(其中s，t分別表示網(wǎng)絡(luò)的發(fā)點(diǎn)和收點(diǎn))·證明了可以在多項(xiàng)式時(shí)間內(nèi)求解簡單網(wǎng)絡(luò)流對策的核子。 ·證明了對于一般的網(wǎng)絡(luò)流對策，有關(guān)核子的計(jì)算問題是NP-困難的。 非合作對策理論中，最重要、最核心