運籌學(xué)教程-胡云權(quán)第五版運籌學(xué)--6對策論--矩陣對策ppt課件

1、第六章 對策論:根本概念根本概念對策論又稱博弈論，研討沖突對抗條件下最優(yōu)決策問題的實際。戰(zhàn)略情勢：不完全競爭條件下的對抗行為，各方收益由本身行為和其他方行為共同決議。根本要素局中人I ：有權(quán)決議本人行動方案的對策參與者，理性人戰(zhàn)略集S ：供局中人選擇的實踐可行完好行動方案的集合， 一局對策中，各局中人選定戰(zhàn)略的集合，稱局勢博得函數(shù) H(s) :對于任一局勢，局中人的博得值。支付函數(shù)嚴(yán)厲占優(yōu)戰(zhàn)略/嚴(yán)厲優(yōu)勢戰(zhàn)略上策平衡/納什平衡:典型案例和重要結(jié)論典型案例和重要結(jié)論結(jié)論1：不要選擇嚴(yán)厲優(yōu)勢戰(zhàn)略。結(jié)論2：個人理性選擇導(dǎo)致非最優(yōu)。結(jié)論3：學(xué)會換位思索。 囚徒姿態(tài) 智豬博弈 求解方法：刪除嚴(yán)厲優(yōu)勢戰(zhàn)略:

2、矩陣對策的根本實際:局中人個數(shù)：二個，多個戰(zhàn)略集中的個數(shù)：有限，無限支付/博得代數(shù)和：零和，非零和局中人能否協(xié)作：非協(xié)作，協(xié)作局中人行動時間：靜態(tài)，動態(tài)局中人對他者信息了解程度：完全信息，非完全信息對策次數(shù)：單次，反復(fù)對策對策/ /博弈分類博弈分類:課程目的課程目的 了解并掌握矩陣對策的純戰(zhàn)略 了解并掌握矩陣對策的混合戰(zhàn)略 掌握矩陣對策的求解方法:矩陣對策的戰(zhàn)略矩陣對策的戰(zhàn)略 純戰(zhàn)略：確定的選擇某戰(zhàn)略 混合戰(zhàn)略：以某一概率分布選擇各戰(zhàn)略。:矩陣對策的純戰(zhàn)略矩陣對策的純戰(zhàn)略的博得矩陣的博得矩陣或或的支付矩陣的支付矩陣的博得矩陣為的博得矩陣為-A -A 。1 1、矩陣對策的普通表達(dá)、矩陣對策的普通

3、表達(dá):矩陣對策的純戰(zhàn)略矩陣對策的純戰(zhàn)略例：田忌賽馬例：田忌賽馬局中人：田忌局中人：田忌I I、齊王、齊王II IIS1 =S1 =上、中、下，上、下、中，中、上、上、中、下，上、下、中，中、上、下，下， 中、下、上，下、中、上，下、上、中、下、上，下、中、上，下、上、中中= S2 = S2 311111131111113111111311111131111113A1 1、矩陣對策的普通表達(dá)、矩陣對策的普通表達(dá):矩陣對策的純戰(zhàn)略矩陣對策的純戰(zhàn)略-82-10-39 2 6明智行為：從各自最不利情形中選擇最有利明智行為：從各自最不利情形中選擇最有利 I I：最大最小原那么：最大最小原那么 II II

4、：最小最大原那么：最小最大原那么平衡局勢：雙方均可接受，且對雙方都是最穩(wěn)妥的結(jié)果。平衡局勢：雙方均可接受，且對雙方都是最穩(wěn)妥的結(jié)果。 2 2 ，22，局中人，局中人I I和和IIII的最優(yōu)純戰(zhàn)略。的最優(yōu)純戰(zhàn)略。2 2、矩陣對策解的引例、矩陣對策解的引例:矩陣對策的純戰(zhàn)略矩陣對策的純戰(zhàn)略 從上例看出，矩陣A中平衡局勢2 ，2對應(yīng)的元素a22既是其所在行的最小元素，也是其所在列的最大元素，即有 ai2a22 a2j i=1,2,3,4 j=1,2,33 3、矩陣對策的最優(yōu)純戰(zhàn)略、矩陣對策的最優(yōu)純戰(zhàn)略:矩陣對策的純戰(zhàn)略矩陣對策的純戰(zhàn)略12313 7 4 63 7 4 63 3、矩陣對策的最優(yōu)純戰(zhàn)略、

5、矩陣對策的最優(yōu)純戰(zhàn)略:矩陣對策的純戰(zhàn)略矩陣對策的純戰(zhàn)略對于一個對策G=S1, S2, A, 假設(shè)有那么稱局勢i*, j*為對策G的鞍點，V = a i*j*為對策G的值。*maxminminmaxjiijijijjiaaa注：在矩陣中，一個數(shù)在所在行中是最大值，在所在列中是最小值，那么被稱為鞍點。4 4、矩陣對策的鞍點與解、矩陣對策的鞍點與解:矩陣對策的純戰(zhàn)略矩陣對策的純戰(zhàn)略多鞍點與無鞍點對策多鞍點與無鞍點對策例例: : 設(shè)有一矩陣對策如下，求它的解。設(shè)有一矩陣對策如下，求它的解。6565142185750262A局勢1, 2，1, 4，3, 23, 4均構(gòu)成鞍點，此對策有多個解。4 4、矩陣

6、對策的鞍點與解、矩陣對策的鞍點與解:矩陣對策的純戰(zhàn)略矩陣對策的純戰(zhàn)略性質(zhì)性質(zhì)1 1：無差別性：無差別性假設(shè)假設(shè)i1 i1 ，j1j1和和i2i2，j2j2是對策是對策G G的兩個解，的兩個解，那么那么ai1j1 = ai2j2ai1j1 = ai2j2性質(zhì)性質(zhì)2 2：可交換性：可交換性假設(shè)假設(shè)i1 i1 ，j1j1和和i2i2，j2j2是對策是對策G G的兩個解，的兩個解，那么那么i1 i1 ，j2j2和和i2i2，j1j1也是對策也是對策G G的兩個的兩個解。解。 矩陣對策的值獨一。即當(dāng)一個局中人選擇了最矩陣對策的值獨一。即當(dāng)一個局中人選擇了最優(yōu)純戰(zhàn)略后，他的博得值不依賴于對方的純戰(zhàn)略。優(yōu)純

7、戰(zhàn)略后，他的博得值不依賴于對方的純戰(zhàn)略。5 5、矩陣對策純戰(zhàn)略的性質(zhì)、矩陣對策純戰(zhàn)略的性質(zhì):作業(yè)P385 習(xí)題12.212.312.4:矩陣對策的混合戰(zhàn)略矩陣對策的混合戰(zhàn)略345 65 6無鞍點無鞍點1 1、混合戰(zhàn)略、混合戰(zhàn)略:矩陣對策的混合戰(zhàn)略矩陣對策的混合戰(zhàn)略1 1、混合戰(zhàn)略、混合戰(zhàn)略:矩陣對策的混合戰(zhàn)略矩陣對策的混合戰(zhàn)略2 2、混合局勢、混合局勢3 3、博得期望、博得期望4 4、混合戰(zhàn)略對策模型、混合戰(zhàn)略對策模型:矩陣對策的混合戰(zhàn)略矩陣對策的混合戰(zhàn)略5 5、最優(yōu)混合戰(zhàn)略、最優(yōu)混合戰(zhàn)略設(shè) ，是矩陣對策 的混合擴(kuò)展。;,*2*1*ESSG ;,21ASSG :矩陣對策的混合戰(zhàn)略矩陣對策的混合

8、戰(zhàn)略5 5、最優(yōu)混合戰(zhàn)略、最優(yōu)混合戰(zhàn)略:矩陣對策的混合戰(zhàn)略矩陣對策的混合戰(zhàn)略定理定理2 2：矩陣對策：矩陣對策G G在混合戰(zhàn)略意義下有解的充要條在混合戰(zhàn)略意義下有解的充要條件是：件是：存在存在 ，使得對于恣，使得對于恣意意 ，有，有*( ,)(,)(, )E x yE xyE xy*12,xSyS*12,xSyS2 2、最優(yōu)混合戰(zhàn)略、最優(yōu)混合戰(zhàn)略*( ,)(,)()(, )()TTTE x yx AyE xyxAyE xyxAy:矩陣對策的混合戰(zhàn)略矩陣對策的混合戰(zhàn)略3 3、最優(yōu)混合戰(zhàn)略解的引例、最優(yōu)混合戰(zhàn)略解的引例:矩陣對策的解法矩陣對策的解法:例：求解矩陣對策G= ,其中12,; SSA23

9、11752A解：1不存在鞍點，為混合戰(zhàn)略求解問題。 2圖解法求解設(shè)局中人I的混合戰(zhàn)略為x, 1-xT， 。0,1x01IIIIII 數(shù)軸上坐標(biāo)為0和1的兩點分別做兩條垂線I-I和II-II。 畫出局中人II的不同戰(zhàn)略下局中人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(1-x)3 : v13 = 11x+2(1-x):2311752A由于局中人II理性，局中人I從最少能夠收入中選擇最大的一個，為局中人I的最優(yōu)對策。B2 求

10、解方程組可得最優(yōu)混合戰(zhàn)略和矩陣對策的值。圖解法圖解法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)戰(zhàn)略為*38(,)11 11Tx 由圖可見局中人II的混合戰(zhàn)略只需2和3組成。: 設(shè)局中人II的最優(yōu)混合戰(zhàn)略為 ，且*123(,)Tyyyy*92(0,)11 11Ty 232349311,11495211yyyyP365 例10圖解法圖解法2311752A 求局中人II的最優(yōu)混合戰(zhàn)略。12311,0yyyy 同理

11、，可得局中人II的博得，1: v21 = 3y2+11y32 : v22 = 5y2+2y3畫出博得線段，見右圖0 1 y y*3 111 5 2 2 局中人I理性，局中人II取最大損失的最小值聯(lián)立方程組可得解得:方程組法方程組法定理：設(shè) ，那么 為G的解的充要條件是： 存在數(shù)v，使得x*,y*分別是以下不等式組的解，且v = VG。*12,xSyS*(,)xy1,11,01,ijiiiiia xvjnximxim1,11,01,ijjjjjja yvimyimyjn假設(shè)xi*,yj*均不為0，那么上述不等式的求解即可轉(zhuǎn)化為以下兩個方程組的求解問題。1,11,ijiiiia xvjnxim1,

12、11,ijjjjja yvimyim注：假設(shè)上述兩個方程組存在非負(fù)解x*,y* ，即矩陣對策的解。假設(shè)不存在非負(fù)解，那么將上述方程組中的某些等式轉(zhuǎn)化為不等式，繼續(xù)求解。 由于事先假設(shè)xi*,yj*均不為0，故，當(dāng)最優(yōu)戰(zhàn)略的某些分量為0時，方程組能夠無解，因此該方法具有一定的局限性。:方程組法方程組法例：求解矩陣對策G= ,其中A為123453403050259739594687660883A12,; SSA12345解：1刪除優(yōu)勢戰(zhàn)略，得到347346A 12無鞍點34343474361xxvxxvxx和12121273461yyvyyvyy*34*1212,3311,225xxyyv*1 21 10,0,0,0,0,0,53 32 2TTG