運籌學(xué)教程胡云權(quán)第五運籌學(xué)對策論矩陣對策PPT學(xué)習(xí)教案

1、會計學(xué)1對策論又稱博弈論，研究沖突對抗條件下最優(yōu)決策問題的理論。策略形勢：不完全競爭條件下的對抗行為，各方收益由自身行為和其他方行為共同決定?；疽鼐种腥耍↖ ）：有權(quán)決定自己行動方案的對策參加者，理性人策略集（S ）：供局中人選擇的實際可行完整行動方案的集合， 一局對策中，各局中人選定策略的集合，稱局勢局勢贏得函數(shù)（ H(s) ）:對于任一局勢，局中人的贏得值。支付函數(shù)嚴(yán)格占優(yōu)策略/嚴(yán)格劣勢策略上策均衡/納什均衡第1頁/共33頁結(jié)論1：不要選擇嚴(yán)格劣勢策略。結(jié)論2：個人理性選擇導(dǎo)致非最優(yōu)。結(jié)論3：學(xué)會換位思考。 囚徒困境 智豬博弈 求解方法：刪除嚴(yán)格劣勢策略第2頁/共33頁第3頁/共33頁

2、第4頁/共33頁第5頁/共33頁第6頁/共33頁的贏得的贏得矩陣矩陣或或的的支付矩陣支付矩陣的贏得矩陣為的贏得矩陣為-A -A 。1 1、矩陣對策的一般表達(dá)、矩陣對策的一般表達(dá)第7頁/共33頁例：例：田忌賽馬田忌賽馬局中人：田忌（局中人：田忌（I I）、齊王（）、齊王（IIII）S S1 1 = =（上、中、下），（上、下、中），（中、上、下），（上、中、下），（上、下、中），（中、上、下）， （中、下、上），（下、中、上），（下、上、中）（中、下、上），（下、中、上），（下、上、中）= = S S2 2 311111131111113111111311111131111113A1 1、矩陣對

3、策的一般表達(dá)、矩陣對策的一般表達(dá)第8頁/共33頁-82-10-39 2 6理智理智行為：行為：從各自最不利情形中選擇最有利從各自最不利情形中選擇最有利 I：最大最?。鹤畲笞钚≡瓌t原則 II：最小最大原則：最小最大原則平衡局勢：平衡局勢：雙方均可接受，且對雙方都是最穩(wěn)妥的結(jié)果。雙方均可接受，且對雙方都是最穩(wěn)妥的結(jié)果。 （2 ，2），），局中人局中人I和和II的最優(yōu)純策略。的最優(yōu)純策略。2 2、矩陣對策解的引例、矩陣對策解的引例第9頁/共33頁 從上例看出，矩陣A中平衡局勢（2 ，2）對應(yīng)的元素a22既是其所在行的最小元素，也是其所在列的最大元素，即有 ai2a22 a2j i=1,2,3,4 j

4、=1,2,33 3、矩陣對策的最優(yōu)純策略、矩陣對策的最優(yōu)純策略第10頁/共33頁12313 7 4 63 3、矩陣對策的最優(yōu)純策略、矩陣對策的最優(yōu)純策略第11頁/共33頁對于一個對策G=S1, S2, A, 若有則稱局勢（i*, j*）為對策G的鞍點，V = a i*j*為對策G的值。*maxminminmaxjiijijijjiaaa注：在矩陣中，一個數(shù)在所在行中是最大值，在所在列中是最小值，則被稱為鞍點鞍點。4 4、矩陣對策的鞍點與解、矩陣對策的鞍點與解第12頁/共33頁多鞍點與無鞍點對策多鞍點與無鞍點對策例: 設(shè)有一矩陣對策如下，求它的解。6565142185750262A局勢（1, 2

5、），（1, 4），（3, 2）（3, 4）均構(gòu)成鞍點，此對策有多個解。4 4、矩陣對策的鞍點與解、矩陣對策的鞍點與解第13頁/共33頁性質(zhì)性質(zhì)1 1：無差別性：無差別性若若（i i1 1 ，j j1 1）和和（i i2 2，j j2 2）是對策是對策G G的兩個的兩個解，則解，則ai1j1 = ai2j2性質(zhì)性質(zhì)2 2：可交換性：可交換性若（若（i i1 1 ，j j1 1）和（）和（i i2 2，j j2 2）是對策是對策G G的兩個解，的兩個解，則則（i i1 1 ，j j2 2）和和（i i2 2，j j1 1）也是也是對策對策G G的兩個的兩個解。解。 矩陣對策矩陣對策的值唯一。的值唯

6、一。即當(dāng)一個局中人選擇了最即當(dāng)一個局中人選擇了最優(yōu)純策略后，他的贏得值不依賴于對方的純策略優(yōu)純策略后，他的贏得值不依賴于對方的純策略。5 5、矩陣對策純策略的性質(zhì)、矩陣對策純策略的性質(zhì)第14頁/共33頁P385 習(xí)題12.212.312.4第15頁/共33頁矩陣對策的混合策略矩陣對策的混合策略345 6無鞍點無鞍點1 1、混合策略、混合策略第16頁/共33頁矩陣對策的混合策略矩陣對策的混合策略1 1、混合策略、混合策略第17頁/共33頁矩陣對策的混合策略矩陣對策的混合策略2 2、混合局勢、混合局勢3 3、贏得期望、贏得期望4 4、混合策略對策模型、混合策略對策模型第18頁/共33頁矩陣對策的混

7、合策略矩陣對策的混合策略5 5、最優(yōu)混合策略、最優(yōu)混合策略設(shè) ，是矩陣對策 的混合擴(kuò)充。;,*2*1*ESSG ;,21ASSG 第19頁/共33頁矩陣對策的混合策略矩陣對策的混合策略5 5、最優(yōu)混合策略、最優(yōu)混合策略第20頁/共33頁矩陣對策的混合策略矩陣對策的混合策略定理定理2 2：矩陣對策G在混合策略意義下有解的充要條件是：存在 ，使得對于任意 ，有*( ,)(,)(, )E x yE xyE xy*12,xSyS*12,xSyS2 2、最優(yōu)混合策略、最優(yōu)混合策略*( ,)(,)()(, )()TTTE x yx AyE xyxAyE xyxAy第21頁/共33頁矩陣對策的混合策略矩陣對

8、策的混合策略3 3、最優(yōu)混合策略解、最優(yōu)混合策略解的引例的引例第22頁/共33頁第23頁/共33頁例：求解矩陣對策G= ,其中12,; SSA2311752A解：（1）不存在鞍點，為混合策略求解問題。 （2）圖解法求解設(shè)局中人I的混合策略為（x, 1-x）T， 。0,1x01IIIIII 數(shù)軸上坐標(biāo)為0和1的兩點分別做兩條垂線I-I和II-II。 畫出局中人II的不同策略下局中人I的贏得線段。25723111=2x+7(1-x)2=3x+5(1-x)3=11x+2(1-x)圖解法圖解法僅適用于贏得矩陣為2n或m2階的矩陣對策問題。1: v11 = 2x+7(1-x)2 : v12 = 3x+5

9、(1-x)3 : v13 = 11x+2(1-x)第24頁/共33頁2311752A由于局中人II理性，局中人I從最少可能收入中選擇最大的一個，為局中人I的最優(yōu)對策。B2 求解方程組可得最優(yōu)混合策略和矩陣對策的值。圖解法圖解法01IIIIII25723111=2x+7(1-x)2=3x+5(1-x)3=11x+2(1-x)B1B2B3B4聯(lián)立過B2點兩條直線的方程組為35(1)112(1)GGxxVxxV可解得349,1111GxV則，局中人I 的最優(yōu)策略為*38(,)11 11Tx 由圖可見局中人II的混合策略只有2和3組成。第25頁/共33頁設(shè)局中人II的最優(yōu)混合策略為 ，且*123(,)

10、Tyyyy*92(0,)11 11Ty 232349311,11495211yyyyP365 例10圖解法圖解法2311752A 求局中人II的最優(yōu)混合策略。12311,0yyyy同理，可得局中人II的贏得，1: v21 = 3y2+11y32 : v22 = 5y2+2y3畫出贏得線段，見右圖0 1 y y*3 111 5 2 2局中人I理性，局中人II取最大損失的最小值聯(lián)立方程組可得解得第26頁/共33頁方程組法方程組法定理：設(shè) ，則 為G的解的充要條件是： 存在數(shù)v，使得x*,y*分別是下列不等式組的解，且v = VG。*12,xSyS*(,)xy1,11,01,ijiiiiia xvj

11、nximxim1,11,01,ijjjjjja yvimyimyjn若xi*,yj*均不為0，則上述不等式的求解即可轉(zhuǎn)化為下列兩個方程組的求解問題。1,11,ijiiiia xvjnxim1,11,ijjjjja yvimyim注：若上述兩個方程組存在非負(fù)解x*,y* ，即矩陣對策的解。若不存在非負(fù)解，則將上述方程組中的某些等式轉(zhuǎn)化為不等式，繼續(xù)求解。 由于事先假設(shè)xi*,yj*均不為0，故，當(dāng)最優(yōu)策略的某些分量為0時，方程組可能無解，因此該方法具有一定的局限性。第27頁/共33頁方程組法方程組法例：求解矩陣對策G= ,其中A為123453403050259739594687660883A12,; SSA12345解：（1）刪除劣勢策略，得到347346A 12無鞍點34343474361xxvxxvxx和12121273461yyvyyvyy*34*1212,3311,225xxyyv*1 21 10,0,0,0,0,0,53 32 2TTGxyV（2）構(gòu)造方程組第28頁/共33頁線性規(guī)劃法線性規(guī)劃法注：適用于所有aij0 若存在ai