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

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

2、勢策略;矩陣對策的基本理論;局中人個數：二個，多個策略集中的個數：有限，無限支付/贏得代數和：零和，非零和局中人是否合作：非合作，合作局中人行動時間：靜態(tài)，動態(tài)局中人對他者信息了解程度：完全信息，非完全信息對策次數：單次，反復對策對策/ /博弈分類博弈分類;課程目標課程目標 理解并掌握矩陣對策的純策略 理解并掌握矩陣對策的混合策略 掌握矩陣對策的求解方法;矩陣對策的策略矩陣對策的策略 純策略：確定的選擇某策略 混合策略：以某一概率分布選擇各策略。;矩陣對策的純策略矩陣對策的純策略的贏得矩陣的贏得矩陣或或的支付矩陣的支付矩陣的贏得矩陣為的贏得矩陣為-A -A 。1 1、矩陣對策的一般表達、矩陣對

3、策的一般表達;矩陣對策的純策略矩陣對策的純策略例：田忌賽馬例：田忌賽馬局中人：田忌局中人：田忌I I）、齊王）、齊王II II）S1 =S1 =（上、中、下），（上、下、中），（中、上、（上、中、下），（上、下、中），（中、上、下），下）， （中、下、上），（下、中、上），（下、上、（中、下、上），（下、中、上），（下、上、中）中）= S2 = S2 311111131111113111111311111131111113A1 1、矩陣對策的一般表達、矩陣對策的一般表達;矩陣對策的純策略矩陣對策的純策略-82-10-39 2 6理智行為：從各自最不利情形中選擇最有利理智行為：從各自最不利情形中

4、選擇最有利 I I：最大最小原則：最大最小原則 II II：最小最大原則：最小最大原則平衡局勢：雙方均可接受，且對雙方都是最穩(wěn)妥的結果。平衡局勢：雙方均可接受，且對雙方都是最穩(wěn)妥的結果。 （2 2 ，22），局中人），局中人I I和和IIII的最優(yōu)純策略。的最優(yōu)純策略。2 2、矩陣對策解的引例、矩陣對策解的引例;矩陣對策的純策略矩陣對策的純策略 從上例看出，矩陣A中平衡局勢2 ，2對應的元素a22既是其所在行的最小元素，也是其所在列的最大元素，即有 ai2a22 a2j i=1,2,3,4 j=1,2,33 3、矩陣對策的最優(yōu)純策略、矩陣對策的最優(yōu)純策略;矩陣對策的純策略矩陣對策的純策略123

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

6、 4），（3, 2）（3, 4均構成鞍點，此對策有多個解。4 4、矩陣對策的鞍點與解、矩陣對策的鞍點與解;矩陣對策的純策略矩陣對策的純策略性質性質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的兩個的兩個解。解。 矩陣對策的值唯一。即當一個局中人選擇了最矩陣對策的值唯一。

7、即當一個局中人選擇了最優(yōu)純策略后，他的贏得值不依賴于對方的純策略。優(yōu)純策略后，他的贏得值不依賴于對方的純策略。5 5、矩陣對策純策略的性質、矩陣對策純策略的性質;作業(yè)P385 習題12.212.312.4;矩陣對策的混合策略矩陣對策的混合策略345 65 6無鞍點無鞍點1 1、混合策略、混合策略;矩陣對策的混合策略矩陣對策的混合策略1 1、混合策略、混合策略;矩陣對策的混合策略矩陣對策的混合策略2 2、混合局勢、混合局勢3 3、贏得期望、贏得期望4 4、混合策略對策模型、混合策略對策模型;矩陣對策的混合策略矩陣對策的混合策略5 5、最優(yōu)混合策略、最優(yōu)混合策略設 ，是矩陣對策 的混合擴充。;,*

8、2*1*ESSG ;,21ASSG ;矩陣對策的混合策略矩陣對策的混合策略5 5、最優(yōu)混合策略、最優(yōu)混合策略;矩陣對策的混合策略矩陣對策的混合策略定理定理2 2：矩陣對策：矩陣對策G G在混合策略意義下有解的充要條在混合策略意義下有解的充要條件是：件是：存在存在 ，使得對于任，使得對于任意意 ，有，有*( ,)(,)(, )E x yE xyE xy*12,xSyS*12,xSyS2 2、最優(yōu)混合策略、最優(yōu)混合策略*( ,)(,)()(, )()TTTE x yx AyE xyxAyE xyxAy;矩陣對策的混合策略矩陣對策的混合策略3 3、最優(yōu)混合策略解的引例、最優(yōu)混合策略解的引例;矩陣對策

9、的解法矩陣對策的解法;例：求解矩陣對策G= ,其中12,; SSA2311752A解：（1不存在鞍點，為混合策略求解問題。 （2圖解法求解設局中人I的混合策略為x, 1-xT， 。0,1x01IIIIII 數軸上坐標為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(1-x)3 : v13 = 11x+2(1-x);2311752A由于局中人II理

10、性，局中人I從最少可能收入中選擇最大的一個，為局中人I的最優(yōu)對策。B2 求解方程組可得最優(yōu)混合策略和矩陣對策的值。圖解法圖解法01IIIIII25723111=2x+7(1-x)2=3x+5(1-x)3=11x+2(1-x)B1B2B3B4聯立過B2點兩條直線的方程組為35(1)112(1)GGxxVxxV可解得349,1111GxV那么，局中人I 的最優(yōu)策略為*38(,)11 11Tx 由圖可見局中人II的混合策略只有2和3組成。; 設局中人II的最優(yōu)混合策略為 ，且*123(,)Tyyyy*92(0,)11 11Ty 232349311,11495211yyyyP365 例10圖解法圖解法

11、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取最大損失的最小值聯立方程組可得解得;方程組法方程組法定理：設 ，那么 為G的解的充要條件是： 存在數v，使得x*,y*分別是下列不等式組的解，且v = VG。*12,xSyS*(,)xy1,11,01,ijiiiiia xvjnximxim1,11,01,ijjjjjja yvimyimyjn若xi*,yj*均不為0，則上述不等式的求解即可轉化為

12、下列兩個方程組的求解問題。1,11,ijiiiia xvjnxim1,11,ijjjjja yvimyim注：若上述兩個方程組存在非負解x*,y* ，即矩陣對策的解。若不存在非負解，則將上述方程組中的某些等式轉化為不等式，繼續(xù)求解。 由于事先假設xi*,yj*均不為0，故，當最優(yōu)策略的某些分量為0時，方程組可能無解，因此該方法具有一定的局限性。;方程組法方程組法例：求解矩陣對策G= ,其中A為123453403050259739594687660883A12,; SSA12345解：（1刪除劣勢策略，得到347346A 12無鞍點34343474361xxvxxvxx和12121273461yyvyyvyy*34*1212,3311,225xxyyv*1 21 10,0,0,0,0,0,53 32 2T