《運(yùn)籌學(xué)教程》第五版運(yùn)籌學(xué)6對(duì)策論矩陣對(duì)策課件

《《運(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ì)策論又稱博弈論，,研究,沖突對(duì)抗條件下最優(yōu)決策問(wèn)題的理論。,策略,形勢(shì)：,不完全競(jìng)爭(zhēng)條件下的對(duì)抗行為,，各方收益由自身行為和其他方行為共同決定。,基本要素,局中人（,I,）,：有權(quán)決定自己行動(dòng)方案的對(duì)策參加者，理性人,策略,集（,S,）,：供局中人選擇的實(shí)際可行完整行動(dòng)方案的集合，,一局對(duì)策中，各局中人選定策略的集合，稱,局勢(shì),贏得函數(shù)（,H(s),）,:,對(duì)于任一局勢(shì)，局中人的贏

2、得值。,支付函數(shù),嚴(yán)格占優(yōu)策略,/,嚴(yán)格劣勢(shì),策略,上策均衡,/,納什,均衡,基本概念對(duì)策論又稱博弈論，研究沖突對(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ì)策,/,博弈分類,局中人個(gè)數(shù)：二個(gè)，多個(gè)對(duì)策/博弈分類,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,若,有,則稱局勢(shì)（,i,*,j,*,）為對(duì)策,G,的,鞍點(diǎn),，,V=a,i*j*,為,對(duì)策,G,的值。,注：在,矩陣中，一個(gè)數(shù)在所在行中是最大值，在所在列中是最小值，則被稱為,鞍點(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,。,畫,出局中人,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)策略為,由圖可見局中人,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,畫出贏得線段，見右圖,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,