《运筹学教程》第五版运筹学6对策论矩阵对策共34张课件.pptx

1、基本基本概念概念对策论又称博弈论，研究冲突对抗条件下最优决策问题的理论。策略形势：不完全竞争条件下的对抗行为，各方收益由自身行为和其他方行为共同决定。基本要素局中人（I）：有权决定自己行动方案的对策参加者，理性人策略集（S）：供局中人选择的实际可行完整行动方案的集合，一局对策中，各局中人选定策略的集合，称局势局势赢得函数（H(s)）:对于任一局势，局中人的赢得值。支付函数严格占优策略/严格劣势策略上策均衡/纳什均衡典型案例和重要结论典型案例和重要结论结论1：不要选择严格劣势策略。结论2：个人理性选择导致非最优。结论3：学会换位思考。囚徒困境 智猪博弈 求解方法：删除严格劣势策略矩阵对策的基本理

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

3、策略例：例：田忌赛马田忌赛马局中人：田忌（局中人：田忌（I I）、齐王（）、齐王（II II）S S1 1=（上、中、下），（上、下、中），（中、上、下），（上、中、下），（上、下、中），（中、上、下），（中、下、上），（下、中、上），（下、上、中）（中、下、上），（下、中、上），（下、上、中）=S S2 2 311111131111113111111311111131111113A1 1、矩阵对策的一般表达、矩阵对策的一般表达矩阵对策的纯策略矩阵对策的纯策略-82 2-10-39 2 2 6理智理智行为：行为：从各自最不利情形中选择最有利从各自最不利情形中选择最有利 I I：最大最小：最大最

4、小原则原则 IIII：最小最大原则：最小最大原则平衡局势：平衡局势：双方均可接受，且对双方都是最稳妥的结果。双方均可接受，且对双方都是最稳妥的结果。（2，2），），局中人局中人I I和和IIII的最优纯策略。的最优纯策略。2 2、矩阵对策解的引例、矩阵对策解的引例矩阵对策的纯策略矩阵对策的纯策略 从上例看出，矩阵A中平衡局势（2，2）对应的元素a22既是其所在行的最小元素，也是其所在列的最大元素，即有 ai2a22 a2j i=1,2,3,4 j=1,2,33 3、矩阵对策的最优纯策略、矩阵对策的最优纯策略矩阵对策的纯策略矩阵对策的纯策略123 313 3 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,2）（3,4）均构成鞍点，此对策有多个解。4 4、矩阵对策的鞍点与解、矩阵对策的鞍点与解矩阵对

6、策的纯策略矩阵对策的纯策略性质性质1 1：无差别性：无差别性若若（i i1 1 ，j j1 1）和和（i i2 2，j j2 2）是对策是对策G G的两个解，则的两个解，则ai1j1=ai2j2性质性质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的两个的两个解。解。矩阵对策矩阵对策的值唯一。的值唯一。即当一个局中人选择了最即当一个局中人选择了最优纯策略后，他的赢得值不依赖于对方的纯策略优纯策略后，他的赢得值不

7、依赖于对方的纯策略。5 5、矩阵对策纯策略的性质、矩阵对策纯策略的性质作业P385 习题12.212.312.4矩阵对策的混合策略矩阵对策的混合策略34 45 5 6无鞍点无鞍点1 1、混合策略、混合策略矩阵对策的混合策略矩阵对策的混合策略1 1、混合策略、混合策略矩阵对策的混合策略矩阵对策的混合策略2 2、混合局势、混合局势3 3、赢得期望、赢得期望4 4、混合策略对策模型、混合策略对策模型矩阵对策的混合策略矩阵对策的混合策略5 5、最优混合策略、最优混合策略设 ，是矩阵对策 的混合扩充。;,*2*1*ESSG;,21ASSG 矩阵对策的混合策略矩阵对策的混合策略5 5、最优混合策略、最优混

8、合策略矩阵对策的混合策略矩阵对策的混合策略定理定理2 2：矩阵对策G在混合策略意义下有解的充要条件是：存在 ，使得对于任意 ，有*(,)(,)(,)E x yE xyE xy*12,xSyS*12,xSyS2 2、最优混合策略、最优混合策略*(,)(,)()(,)()TTTE x yx AyE xyxAyE xyxAy矩阵对策的混合策略矩阵对策的混合策略3 3、最优混合策略解、最优混合策略解的引例的引例矩阵对策的解法矩阵对策的解法例：求解矩阵对策G=,其中12,;SSA2311752A解：（1）不存在鞍点，为混合策略求解问题。（2）图解法求解设局中人I的混合策略为（x,1-x）T，。0,1x0

9、1IIIIII 数轴上坐标为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 求解方程组可得最优混合策略和矩阵对策的值。图解法图解法01IIIIII25723111=2x+7(1-x)2=3x+5(1-x)3=11x+2(

10、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 同理，可得局中人II的赢得，1:v21=3y2+11y32:v22=5y2+2y3画出赢得线段，见右图0 1 y y*3 111 5 2 2 局中人I理

11、性，局中人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,11,ijjjjja yvimyim注：若上述两个方程组存在非负解x*,y*，即矩阵对策的解。若不存在非负解，则将上述方程组中的某些等式转化为不等式，继续求解。由于事先假设xi

12、*,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 2TTGxyV（2）构造方程组线性规划法线性规划法注：适用于所有aij0 若存在aij0，可取一充分大的M0，使得M+aij0线性规划法线性规划法例：两人“石头、剪刀、布”矩阵对策求解解：解：(X*，Y*)为矩阵对策的解*11111111111111111101(1)(1)111(1)033333333333333333319V 作业P386 习题12.512.612.7Q&A33谢谢！谢谢！34