運籌學教程-胡云權第五版運籌學--6對策論--矩陣對策ppt課件

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

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

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

4、：最小最大原那么：最小最大原那么平衡局勢：雙方均可接受，且對雙方都是最穩(wěn)妥的結果。平衡局勢：雙方均可接受，且對雙方都是最穩(wěn)妥的結果。 2 2 ，22，局中人，局中人I I和和IIII的最優(yōu)純戰(zhàn)略。的最優(yōu)純戰(zhàn)略。2 2、矩陣對策解的引例、矩陣對策解的引例:矩陣對策的純戰(zhàn)略矩陣對策的純戰(zhàn)略 從上例看出，矩陣A中平衡局勢2 ，2對應的元素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, 假設有那么稱局勢i*, j*為對策G的鞍點，V = a i*j*為對策G的值。*maxminminmaxjiijijijjiaaa注：在矩陣中，一個數(shù)在所在行中是最大值，在所在列中是最小值，那么被稱為鞍點。4 4、矩陣對策的鞍點與解、矩陣對策的鞍點與解:矩陣對策的純戰(zhàn)略矩陣對策的純戰(zhàn)略多鞍點與無鞍點對策多鞍點與無鞍點對策例例: : 設有一矩陣對策如下，求它的解。設有一矩陣對策如下，求它的解。6565142185750262A局勢1, 2，1, 4，3, 23, 4均構成鞍點，此對策有多個解。4 4、矩陣

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

7、戰(zhàn)略后，他的博得值不依賴于對方的純戰(zhàn)略。5 5、矩陣對策純戰(zhàn)略的性質、矩陣對策純戰(zhàn)略的性質:作業(yè)P385 習題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)略設 ，是矩陣對策 的混合擴展。;,*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圖解法求解設局中人I的混合戰(zhàn)略為x, 1-xT， 。0,1x01IIIIII 數(shù)軸上坐標為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組成。: 設局中人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)立方程組可得解得:方程組法方程組法定理：設 ，那么 為G的解的充要條件是： 存在數(shù)v，使得x*,y*分別是以下不等式組的解，且v = VG。*12,xSyS*(,)xy1,11,01,ijiiiiia xvjnximxim1,11,01,ijjjjjja yvimyimyjn假設xi*,yj*均不為0，那么上述不等式的求解即可轉化為以下兩個方程組的求解問題。1,11,ijiiiia xvjnxim1,

12、11,ijjjjja yvimyim注：假設上述兩個方程組存在非負解x*,y* ，即矩陣對策的解。假設不存在非負解，那么將上述方程組中的某些等式轉化為不等式，繼續(xù)求解。 由于事先假設xi*,yj*均不為0，故，當最優(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