本文關(guān)鍵詞：恒速機(jī)下的有限資源博弈排序最優(yōu)性研究

  更多相關(guān)文章： 博弈排序 納什均衡 恒速機(jī) 激活費(fèi)用 POA

【摘要】：排序問(wèn)題是一類(lèi)組合最優(yōu)化問(wèn)題,由于排序問(wèn)題中的處理機(jī)、任務(wù)或作業(yè)是有限的,絕大部分排序問(wèn)題是從有限個(gè)可行解中找出一個(gè)最優(yōu)解,使目標(biāo)函數(shù)達(dá)到極小.本文主要研究有限資源的博弈排序問(wèn)題,我們考慮的資源是相同的,博弈的社會(huì)成本是實(shí)用的.在恒速機(jī)博弈排序模型中,每一個(gè)工件都可以自主選擇一個(gè)合適的機(jī)器來(lái)加工它自己,這樣每個(gè)工件的目標(biāo)就是使它自己的成本最小.工件的成本是指它所選擇的那臺(tái)機(jī)器的總完工時(shí)間.本文的結(jié)構(gòu)安排如下:第一章為緒論部分,主要介紹了排序問(wèn)題、博弈論和納什均衡問(wèn)題、博弈排序的產(chǎn)生背景和主要內(nèi)容以及后兩章內(nèi)容需要用到的一些預(yù)備知識(shí).第二章考慮了恒速機(jī)下的博弈排序模型.在納什均衡中,在每個(gè)工件的策略都不改變的情況下,任何一個(gè)工件都不能通過(guò)單方面的改變自己的策略來(lái)降低它的成本,但是納什均衡不一定是最優(yōu)的,實(shí)際上還常常與最優(yōu)值存在很大差距.在這里我們使用POA(the price of anarchy)和POS(the price of stability)來(lái)分析納什均衡的質(zhì)量.當(dāng)目標(biāo)函數(shù)是總完工時(shí)間時(shí),求得POA界和POS界.當(dāng)目標(biāo)函數(shù)是時(shí)間表長(zhǎng)度時(shí),求得POA界.第三章考慮了兩臺(tái)和m臺(tái)帶激活費(fèi)用的恒速機(jī)模型,研究的整體目標(biāo)函數(shù)是機(jī)器的總完工時(shí)間和激活費(fèi)用之和,最后我們用POA來(lái)衡量納什均衡時(shí)的最差的整體目標(biāo)函數(shù)值與最優(yōu)值之間的差異.兩臺(tái)機(jī)器時(shí),我們假設(shè)機(jī)器的速度分別是1和a,每臺(tái)機(jī)器的激活費(fèi)用和它的速度相等,.m臺(tái)機(jī)器時(shí),我們假設(shè)機(jī)器的激活費(fèi)用都是1,不隨每臺(tái)機(jī)器的速度變化,分別求得兩種情況下的POA界.
【關(guān)鍵詞】：博弈排序 納什均衡 恒速機(jī) 激活費(fèi)用 POA
【學(xué)位授予單位】：曲阜師范大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2015
【分類(lèi)號(hào)】：O223
【目錄】：

• 摘要3-4
• Abstract4-6
• 第1章 緒論6-11
• 1.1 排序問(wèn)題的介紹6-7
• 1.2 博弈論和納什均衡問(wèn)題的介紹7-8
• 1.3 博弈排序問(wèn)題的介紹8-9
• 1.4 本文研究的主要內(nèi)容9-11
• 第2章 無(wú)激活費(fèi)用的恒速機(jī)博弈排序模型11-19
• 2.1 引言11
• 2.2 問(wèn)題描述11-13
• 2.3 m臺(tái)恒速機(jī)上社會(huì)成本為總完工時(shí)間的博弈排序問(wèn)題13-16
• 2.4 m臺(tái)恒速機(jī)上社會(huì)成本為時(shí)間表長(zhǎng)度的博弈排序問(wèn)題16-18
• 2.5 總結(jié)18-19
• 第3章 帶激活費(fèi)用的恒速機(jī)博弈排序19-24
• 3.1 引言19
• 3.2 問(wèn)題描述19-20
• 3.3 兩臺(tái)帶激活費(fèi)用的恒速機(jī)POA分析20-21
• 3.4 m臺(tái)帶激活費(fèi)用的恒速機(jī)POA分析21-22
• 3.5 總結(jié)22-24
• 參考文獻(xiàn)24-27
• 在讀期間發(fā)表的學(xué)術(shù)論文及研究成果27-28
• 致謝28

【參考文獻(xiàn)】

中國(guó)期刊全文數(shù)據(jù)庫(kù) 前1條

1 CHEN Bo;LI SongSong;ZHANG YuZhong;;Strong stability of Nash equilibria in load balancing games[J];Science China(Mathematics);2014年07期

，

本文編號(hào)：623054