《《運(yùn)籌學(xué)教程》第五版運(yùn)籌學(xué)6對(duì)策論矩陣對(duì)策課件》由會(huì)員分享,可在線閱讀,更多相關(guān)《《運(yùn)籌學(xué)教程》第五版運(yùn)籌學(xué)6對(duì)策論矩陣對(duì)策課件(34頁(yè)珍藏版)》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。
1、,單擊此處編輯母版標(biāo)題樣式,單擊此處編輯母版文本樣式,第二級(jí),第三級(jí),第四級(jí),第五級(jí),2015/3/30,#,單擊此處編輯母版標(biāo)題樣式,單擊此處編輯母版文本樣式,第二級(jí),第三級(jí),第四級(jí),第五級(jí),*,*,基本,概念,對(duì)策論又稱(chēng)博弈論,,研究,沖突對(duì)抗條件下最優(yōu)決策問(wèn)題的理論。,策略,形勢(shì):,不完全競(jìng)爭(zhēng)條件下的對(duì)抗行為,,各方收益由自身行為和其他方行為共同決定。,基本要素,局中人(,I,),:有權(quán)決定自己行動(dòng)方案的對(duì)策參加者,理性人,策略,集(,S,),:供局中人選擇的實(shí)際可行完整行動(dòng)方案的集合,,一局對(duì)策中,各局中人選定策略的集合,稱(chēng),局勢(shì),贏得函數(shù)(,H(s),),:,對(duì)于任一局勢(shì),局中人的贏
2、得值。,支付函數(shù),嚴(yán)格占優(yōu)策略,/,嚴(yán)格劣勢(shì),策略,上策均衡,/,納什,均衡,基本概念對(duì)策論又稱(chēng)博弈論,研究沖突對(duì)抗條件下最優(yōu)決策問(wèn)題的理,1,典型案例和重要結(jié)論,結(jié)論,1,:不要選擇嚴(yán)格劣勢(shì)策略,。,結(jié)論,2,:個(gè)人理性選擇導(dǎo)致非最優(yōu)。,結(jié)論,3,:學(xué)會(huì)換位思考,。,囚徒困境,智豬博弈,求解方法:刪除嚴(yán)格劣勢(shì)策略,典型案例和重要結(jié)論結(jié)論1:不要選擇嚴(yán)格劣勢(shì)策略。,2,矩陣對(duì)策的基本理論,矩陣對(duì)策的基本理論,3,局中人個(gè)數(shù):二個(gè),多個(gè),策略集中的個(gè)數(shù):有限,無(wú)限,支付,/,贏得代數(shù)和:零和,非零和,局中人是否合作:非合作,合作,局中人行動(dòng)時(shí)間:靜態(tài),動(dòng)態(tài),局中人對(duì)他者信息了解程度:完全信息,非
3、完全信息,對(duì)策次數(shù):?jiǎn)未?,重?fù),對(duì)策,/,博弈分類(lèi),局中人個(gè)數(shù):二個(gè),多個(gè)對(duì)策/博弈分類(lèi),4,課程目標(biāo),理解并掌握矩陣對(duì)策的純策略,理解,并掌握,矩陣對(duì)策的混合策略,掌握矩陣對(duì)策的求解方法,課程目標(biāo) 理解并掌握矩陣對(duì)策的純策略,5,矩陣對(duì)策的策略,純策略:確定,的選擇某,策略,混合策略:以,某一概率分布選擇各策略。,矩陣對(duì)策的策略 純策略:確定的選擇某策略,6,矩陣對(duì)策的純策略,的贏得,矩陣,或,的,支付矩陣,的贏得矩陣為,-A,。,1,、矩陣對(duì)策的一般表達(dá),矩陣對(duì)策的純策略的贏得矩陣1、矩陣對(duì)策的一般表達(dá),7,矩陣對(duì)策的純策略,例:,田忌賽馬,局中人:田忌(,I,)、齊王(,II,),S,1
4、,=,(上、中、下),(上、下、中),(中、上、下),,(中、下、上),(下、中、上),(下、上、中),=,S,2,1,、矩陣對(duì)策的一般表達(dá),矩陣對(duì)策的純策略例:田忌賽馬1、矩陣對(duì)策的一般表達(dá),8,矩陣對(duì)策的純策略,-8,2,-10,-3,9,2,6,理智,行為:,從各自最不利情形中選擇最有利,I,:最大最小,原則,II,:最小最大原則,平衡局勢(shì):,雙方均可接受,且對(duì)雙方都是最穩(wěn)妥的結(jié)果。,(,2,,,2,),,局中人,I,和,II,的最優(yōu)純策略。,2,、矩陣對(duì)策解的引例,矩陣對(duì)策的純策略-89 2 6理智行為:,9,矩陣對(duì)策的純策略,從上例看出,矩陣,A,中平衡局勢(shì)(,2,,,2,)對(duì)應(yīng)的元
5、素,a,22,既是其所在行的最小元素,也是其所在列的最大元素,即有,a,i2,a,22,a,2j,i=1,2,3,4 j=1,2,3,3,、矩陣對(duì)策的最優(yōu)純策略,矩陣對(duì)策的純策略 從上例看出,矩陣A中平衡局勢(shì),10,矩陣對(duì)策的純策略,1,2,3,1,3,7 4 6,3,、矩陣對(duì)策的最優(yōu)純策略,矩陣對(duì)策的純策略13 7 4,11,矩陣對(duì)策的純策略,對(duì)于一個(gè)對(duì)策,G,=,S,1,S,2,A,若,有,則稱(chēng)局勢(shì)(,i,*,j,*,)為對(duì)策,G,的,鞍點(diǎn),,,V=a,i*j*,為,對(duì)策,G,的值。,注:在,矩陣中,一個(gè)數(shù)在所在行中是最大值,在所在列中是最小值,則被稱(chēng)為,鞍點(diǎn),。,4,、矩陣對(duì)策的鞍點(diǎn)與解
6、,矩陣對(duì)策的純策略對(duì)于一個(gè)對(duì)策G=S1,S2,A,若,12,矩陣對(duì)策的純策略,多鞍點(diǎn)與無(wú)鞍點(diǎn)對(duì)策,例,:,設(shè)有一矩陣對(duì)策如下,求它的解。,局勢(shì),(,1,2,),(,1,4,),,(,3,2,),(,3,4,)均構(gòu)成鞍點(diǎn),此對(duì)策有多個(gè)解。,4,、矩陣對(duì)策的鞍點(diǎn)與解,矩陣對(duì)策的純策略多鞍點(diǎn)與無(wú)鞍點(diǎn)對(duì)策局勢(shì)(1,2),(,13,矩陣對(duì)策的純策略,性質(zhì),1,:無(wú)差別性,若,(,i,1,,,j,1,),和,(,i,2,,,j,2,),是對(duì)策,G,的兩個(gè)解,則,a,i,1,j,1,=a,i,2,j,2,性質(zhì),2,:可交換性,若(,i,1,,,j,1,)和(,i,2,,,j,2,),是對(duì)策,G,的兩個(gè)解,,
7、則,(,i,1,,,j,2,),和,(,i,2,,,j,1,),也是,對(duì)策,G,的兩個(gè),解。,矩陣對(duì)策,的值唯一。,即當(dāng)一個(gè)局中人選擇了最優(yōu)純策略后,他的贏得值不依賴于對(duì)方的純策略,。,5,、矩陣對(duì)策純策略的性質(zhì),矩陣對(duì)策的純策略性質(zhì)1:無(wú)差別性5、矩陣對(duì)策純策略的性質(zhì),14,作業(yè),P385,習(xí)題,12.2,12.3,12.4,作業(yè)P385 習(xí)題,15,矩陣對(duì)策的混合策略,3,4,5,6,無(wú)鞍點(diǎn),1,、混合策略,35 6無(wú)鞍點(diǎn)1、混合策略,16,矩陣對(duì)策的混合策略,1,、混合策略,1、混合策略,17,矩陣對(duì)策的混合策略,2,、混合局勢(shì),3,、贏得期望,4,、混合策略對(duì)策模型,2、混合局勢(shì)3、贏
8、得期望4、混合策略對(duì)策模型,18,矩陣對(duì)策的混合策略,5,、最優(yōu)混合策略,設(shè) ,是矩陣對(duì)策 的混合擴(kuò)充。,5、最優(yōu)混合策略設(shè),19,矩陣對(duì)策的混合策略,5,、最優(yōu)混合策略,5、最優(yōu)混合策略,20,矩陣對(duì)策的混合策略,定理,2,:,矩陣對(duì)策,G,在混合策略意義下有解的充要條件是:,存在 ,使得對(duì)于任意 ,有,2,、最優(yōu)混合策略,定理2:矩陣對(duì)策G在混合策略意義下有解的充要條件是:2、最優(yōu),21,矩陣對(duì)策的混合策略,3,、最優(yōu)混合策略解,的引例,3、最優(yōu)混合策略解的引例,22,矩陣對(duì)策的解法,矩陣對(duì)策的解法,23,例:求解矩陣對(duì)策,G=,其中,解:,(,1,)不存在鞍點(diǎn),為混合策略求解問(wèn)題。,(,
9、2,)圖解法求解,設(shè)局中人,I,的混合策略為(,x,1-x,),T,,。,0,1,I,I,II,II,數(shù)軸上坐標(biāo)為,0,和,1,的兩點(diǎn)分別做兩條垂線,I-I,和,II-II,。,畫(huà),出局中人,II,的不同策略下局中人,I,的贏得線段。,2,5,7,2,3,11,1,=2x+7(1-x),2,=3x+5(1-x),3,=11x+2(1-x),圖解法,僅適用于贏得矩陣為,2n,或,m2,階的矩陣對(duì)策問(wèn)題。,1,:v,1,1,=2x+7(1-x),2,:,v,1,2,=3x+5(1-x,),3,:,v,1,3,=11x+2(1-x,),例:求解矩陣對(duì)策G=,其中,24,由于局中人,II,理性,局中人
10、,I,從最少可能收入中選擇最大的一個(gè),為局中人,I,的最優(yōu)對(duì)策。,B,2,求解方程組可得最優(yōu)混合策略和矩陣對(duì)策的值。,圖解法,0,1,I,I,II,II,2,5,7,2,3,11,1,=2x+7(1-x),2,=3x+5(1-x),3,=11x+2(1-x),B,1,B,2,B,3,B,4,聯(lián)立過(guò),B,2,點(diǎn)兩,條直線的方程組為,可解得,則,局中人,I,的最優(yōu)策略為,由圖可見(jiàn)局中人,II,的混合策略只有,2,和,3,組成。,由于局中人II理性,局中人I從最少可能收入中選擇最大的一個(gè),25,設(shè)局中人,II,的最優(yōu)混合策略為 ,且,P365,例,10,圖解法,求局中人,II,的最優(yōu)混合策略。,同理
11、,可得局中人,II,的贏得,,1,:v,2,1,=3y,2,+11y,3,2,:,v,2,2,=5y,2,+2y,3,畫(huà)出贏得線段,見(jiàn)右圖,0,1,y,y,*,3,1,11,5,2,2,局中人,I,理性,局中人,II,取最大損失的最小值,聯(lián)立方程組可得,解得,設(shè)局中人II的最優(yōu)混合策略為,26,方程組法,定理:,設(shè) ,則 為,G,的解的充要條件是:,存在數(shù),v,,使得,x,*,y,*,分別,是下列不等式組的解,且,v=V,G,。,若,x,i,*,y,j,*,均不為,0,,則上述不等式的求解即可轉(zhuǎn)化為下列兩個(gè)方程組的求解問(wèn)題。,注:,若上述,兩個(gè)方程組存在非負(fù)解,x,*,y,*,,即矩陣對(duì)策的解
12、。若不存在非負(fù)解,則將上述方程組中的某些等式轉(zhuǎn)化為不等式,繼續(xù)求解。,由于事先假設(shè),x,i,*,y,j,*,均不為,0,,故,當(dāng)最優(yōu)策略的某些分量為,0,時(shí),方程組可能無(wú)解,因此該方法具有一定的局限性。,定理:設(shè) ,則,27,方程組法,例:求解矩陣對(duì)策,G=,其中,A,為,解:(,1,)刪除劣勢(shì)策略,得到,無(wú)鞍點(diǎn),和,(,2,)構(gòu)造方程組,例:求解矩陣對(duì)策G=,其中,28,線性規(guī)劃法,注:,適用于所有,a,ij,0,若存在,a,ij,0,,可取一充分大的,M,0,,使得,M,+,a,ij,0,注:適用于所有aij0,29,線性規(guī)劃法,例:兩人“石頭、剪刀、布”矩陣對(duì)策求解,解:,(,X,*,,,Y,*,),為,矩陣對(duì)策的解,例:兩人“石頭、剪刀、布”矩陣對(duì)策求解(X*,Y*)為矩陣對(duì),30,作業(yè),P386,習(xí)題,12.5,12.6,12.7,作業(yè)P386 習(xí)題,31,Q&A,Q&A,32,33,謝謝!,33謝謝!,34,34,