运筹学教程-胡云权第五版运筹学--6对策论--矩阵对策ppt课件

1、第六章 对策论:根本概念根本概念对策论又称博弈论，研讨冲突对抗条件下最优决策问题的实际。战略情势：不完全竞争条件下的对抗行为，各方收益由本身行为和其他方行为共同决议。根本要素局中人I ：有权决议本人行动方案的对策参与者，理性人战略集S ：供局中人选择的实践可行完好行动方案的集合， 一局对策中，各局中人选定战略的集合，称局势博得函数 H(s) :对于任一局势，局中人的博得值。支付函数严厉占优战略/严厉优势战略上策平衡/纳什平衡:典型案例和重要结论典型案例和重要结论结论1：不要选择严厉优势战略。结论2：个人理性选择导致非最优。结论3：学会换位思索。 囚徒姿态 智猪博弈 求解方法：删除严厉优势战略:

2、矩阵对策的根本实际:局中人个数：二个，多个战略集中的个数：有限，无限支付/博得代数和：零和，非零和局中人能否协作：非协作，协作局中人行动时间：静态，动态局中人对他者信息了解程度：完全信息，非完全信息对策次数：单次，反复对策对策/ /博弈分类博弈分类:课程目的课程目的 了解并掌握矩阵对策的纯战略 了解并掌握矩阵对策的混合战略 掌握矩阵对策的求解方法:矩阵对策的战略矩阵对策的战略 纯战略：确定的选择某战略 混合战略：以某一概率分布选择各战略。:矩阵对策的纯战略矩阵对策的纯战略的博得矩阵的博得矩阵或或的支付矩阵的支付矩阵的博得矩阵为的博得矩阵为-A -A 。1 1、矩阵对策的普通表达、矩阵对策的普通

3、表达:矩阵对策的纯战略矩阵对策的纯战略例：田忌赛马例：田忌赛马局中人：田忌局中人：田忌I I、齐王、齐王II IIS1 =S1 =上、中、下，上、下、中，中、上、上、中、下，上、下、中，中、上、下，下， 中、下、上，下、中、上，下、上、中、下、上，下、中、上，下、上、中中= S2 = S2 311111131111113111111311111131111113A1 1、矩阵对策的普通表达、矩阵对策的普通表达:矩阵对策的纯战略矩阵对策的纯战略-82-10-39 2 6明智行为：从各自最不利情形中选择最有利明智行为：从各自最不利情形中选择最有利 I I：最大最小原那么：最大最小原那么 II II

4、：最小最大原那么：最小最大原那么平衡局势：双方均可接受，且对双方都是最稳妥的结果。平衡局势：双方均可接受，且对双方都是最稳妥的结果。 2 2 ，22，局中人，局中人I I和和IIII的最优纯战略。的最优纯战略。2 2、矩阵对策解的引例、矩阵对策解的引例:矩阵对策的纯战略矩阵对策的纯战略 从上例看出，矩阵A中平衡局势2 ，2对应的元素a22既是其所在行的最小元素，也是其所在列的最大元素，即有 ai2a22 a2j i=1,2,3,4 j=1,2,33 3、矩阵对策的最优纯战略、矩阵对策的最优纯战略:矩阵对策的纯战略矩阵对策的纯战略12313 7 4 63 7 4 63 3、矩阵对策的最优纯战略、

5、矩阵对策的最优纯战略:矩阵对策的纯战略矩阵对策的纯战略对于一个对策G=S1, S2, A, 假设有那么称局势i*, j*为对策G的鞍点，V = a i*j*为对策G的值。*maxminminmaxjiijijijjiaaa注：在矩阵中，一个数在所在行中是最大值，在所在列中是最小值，那么被称为鞍点。4 4、矩阵对策的鞍点与解、矩阵对策的鞍点与解:矩阵对策的纯战略矩阵对策的纯战略多鞍点与无鞍点对策多鞍点与无鞍点对策例例: : 设有一矩阵对策如下，求它的解。设有一矩阵对策如下，求它的解。6565142185750262A局势1, 2，1, 4，3, 23, 4均构成鞍点，此对策有多个解。4 4、矩阵

6、对策的鞍点与解、矩阵对策的鞍点与解:矩阵对策的纯战略矩阵对策的纯战略性质性质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、战略后，他的博得值不依赖于对方的纯战略。5 5、矩阵对策纯战略的性质、矩阵对策纯战略的性质:作业P385 习题12.212.312.4:矩阵对策的混合战略矩阵对策的混合战略345 65 6无鞍点无鞍点1 1、混合战略、混合战略:矩阵对策的混合战略矩阵对策的混合战略1 1、混合战略、混合战略:矩阵对策的混合战略矩阵对策的混合战略2 2、混合局势、混合局势3 3、博得期望、博得期望4 4、混合战略对策模型、混合战略对策模型:矩阵对策的混合战略矩阵对策的混合战略5 5、最优混合战略、最优混合战略设 ，是矩阵对策 的混合扩展。;,*2*1*ESSG ;,21ASSG :矩阵对策的混合战略矩阵对策的混合

8、战略5 5、最优混合战略、最优混合战略:矩阵对策的混合战略矩阵对策的混合战略定理定理2 2：矩阵对策：矩阵对策G G在混合战略意义下有解的充要条在混合战略意义下有解的充要条件是：件是：存在存在 ，使得对于恣，使得对于恣意意 ，有，有*( ,)(,)(, )E x yE xyE xy*12,xSyS*12,xSyS2 2、最优混合战略、最优混合战略*( ,)(,)()(, )()TTTE x yx AyE xyxAyE xyxAy:矩阵对策的混合战略矩阵对策的混合战略3 3、最优混合战略解的引例、最优混合战略解的引例:矩阵对策的解法矩阵对策的解法:例：求解矩阵对策G= ,其中12,; SSA23

9、11752A解：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理性，局中人I从最少能够收入中选择最大的一个，为局中人I的最优对策。B2 求

10、解方程组可得最优混合战略和矩阵对策的值。图解法图解法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 的最优战略为*38(,)11 11Tx 由图可见局中人II的混合战略只需2和3组成。: 设局中人II的最优混合战略为 ，且*123(,)Tyyyy*92(0,)11 11Ty 232349311,11495211yyyyP365 例10图解法图解法2311752A 求局中人II的最优混合战略。12311,0yyyy 同理

11、，可得局中人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，那么上述不等式的求解即可转化为以下两个方程组的求解问题。1,11,ijiiiia xvjnxim1,

12、11,ijjjjja yvimyim注：假设上述两个方程组存在非负解x*,y* ，即矩阵对策的解。假设不存在非负解，那么将上述方程组中的某些等式转化为不等式，继续求解。 由于事先假设xi*,yj*均不为0，故，当最优战略的某些分量为0时，方程组能够无解，因此该方法具有一定的局限性。:方程组法方程组法例：求解矩阵对策G= ,其中A为123453403050259739594687660883A12,; SSA12345解：1删除优势战略，得到347346A 12无鞍点34343474361xxvxxvxx和12121273461yyvyyvyy*34*1212,3311,225xxyyv*1 21 10,0,0,0,0,0,53 32 2TTG