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

  更多相關文章： 博弈排序 納什均衡 恒速機 激活費用 POA

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

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

【參考文獻】

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

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

，

本文編號：623054