运筹学教程ppt课件-第7章-对策论

第7章 对策论7.1 基本概念基本概念7.2 矩阵对策的矩阵对策的最优纯策略最优纯策略7.3 矩阵对策的矩阵对策的混合策略混合策略第7章 对策论7.1 基本概念17.1 基本概念田忌赛马（教材188页）三个基本要素1.局中人：参与对抗的各方；2.策略集：局中人选择对付其它局中人的行动方案称为策略。局中人的所有策略全体称为策略集；3.益损值：每局中人各自使用一个对策就形成一个局势，一个局势决定了各局中人的对策结果，称为该局势下的益损值。益损值形成的矩阵称嬴得矩阵。7.1 基本概念田忌赛马（教材188页）2例例1 “田忌赛马”齐王的益损值表7.1 基本概念例1 “田忌赛马”齐王的益损值表7.1 基本概念3例例1（续）（续）齐王的策略集齐王的策略集:S1=1,2,3,4,5,6田忌的策略集：田忌的策略集：S2=1,2,3,4,5,6齐王的赢得矩阵齐王的赢得矩阵A：3 1 1 1 -1 1 1 3 1 1 1 -1 A=1 -1 3 1 1 1 -1 1 1 3 1 1 1 1 1 -1 3 1 1 1 -1 1 1 3 7.1 基本概念例1（续）7.1 基本概念47.1 基本概念二人有限零和对策（又称矩阵对策）局中人为2；每局中人的策略集为有限集；每一局势双方均有确定的损益值，且同一局势的双方益损值和为零。7.1 基本概念二人有限零和对策（又称矩阵对策）57.1 基本概念矩阵对策记号G=S1,S2,A 甲的策略集甲的赢得矩阵乙的策略集“田忌赛马田忌赛马”是一个矩阵对策！是一个矩阵对策！Return7.1 基本概念矩阵对策记号 67.2 矩阵对策的最优纯策略甲方赢得矩阵A=aijmni行：表示甲方策略i，i=1,2,m.j列：表示乙方策略j，j=1,2,n.aij：表示甲方取策略i、乙方取策略j时甲方在该局势下的益损值.（！此时乙方的益损值为！此时乙方的益损值为-aij）7.2 矩阵对策的最优纯策略甲方赢得矩阵77.2 矩阵对策的最优纯策略例2 两个局中人甲、乙，甲策略=1,2,3，乙策略集=1,2,3,4，甲方赢得矩阵A:-5 0 -2 0 A =2 3 0 1 -2 -4 -1 3问：甲、乙应采取何策略比较适合？7.2 矩阵对策的最优纯策略例2 两个局中人甲、乙，甲策略8例2（续）甲：采取1至少得益5 2 0 3 -4乙：采取1甲最多得益2 2 3 3 0 4 3maxi minj aij=0 取最大：取最大：2minj maxi aij=0 取最小：取最小：37.2 矩阵对策的最优纯策略例2（续）maxi minj aij=0 9例2（续）甲采取策略2 不管乙采取如何策略，都至少得益0。乙采取策略3 不管甲采取如何策略，都至多损失0。2，3分别称甲，乙的最优策略，又称最优纯策略。7.2 矩阵对策的最优纯策略例2（续）7.2 矩阵对策的最优纯策略10最优纯策略存在条件：max min aij=min max aij=v i j j i!（2，3）亦称）亦称为对策G=S1,S2,A的鞍点，值V称为G的值。Return7.2 矩阵对策的最优纯策略最优纯策略存在条件：7.2 矩阵对策的最优纯策略117.3 矩阵对策的混合策略矩阵对策 G=S1,S2,A当 max min aij min max aij i j j i 时，不存在最优纯策略。求解混合策略！7.3 矩阵对策的混合策略矩阵对策 G=S1,S2,A127.3 矩阵对策的混合策略例3 设某赢得矩阵:min 3 6 3 A =max 4 策略2 5 4 4 i max 5 6 min 5 策略1 j 7.3 矩阵对策的混合策略例3 设某赢得矩阵:13例3（续）分析：甲取2，乙取1，甲实际赢得5（比预期多1），这时乙不满意，考虑采取策略2；为应对乙，甲采取策略1，赢得6；甲，乙没能达到令双方均满意的平衡局甲，乙没能达到令双方均满意的平衡局势！势！7.3 矩阵对策的混合策略例3（续）7.3 矩阵对策的混合策略14新思路：为甲、乙给出选取不同策略的概率分布，使双方在各种情况下的平均赢得（损失）最多（最少）混合策略7.3 矩阵对策的混合策略新思路：7.3 矩阵对策的混合策略157.3 矩阵对策的混合策略求解方法：线性规划法例4 设甲赢得矩阵A，赢得的平均值为V 3 6 A=5 4 7.3 矩阵对策的混合策略求解方法：线性规划法167.3 矩阵对策的混合策略例4（续）解：解：第一步第一步1)设甲采用策略 i的概率为Xi,i=1,2.则则 X1+X2=1，X1,X2 02)甲的平均赢得应不少于V:乙取1：3X1+5X2 V乙取2：6X1+4X2 V7.3 矩阵对策的混合策略例4（续）17例例4（续）（续）第二步第二步 令 X1=X1/V，X2=X2/V，得 X1+X2=1/V 3X1+5X2 1 6X1+4X2 1 X1,X2 07.3 矩阵对策的混合策略例4（续）7.3 矩阵对策的混合策略18例例4（续）（续）第三步第三步min X1+X2 X1=1/18建立线性模型：s.t.3X1+5X2 1 X2=1/6 6X1+4X2 1 1/V=X1+X2=2/9 X1,X2 0最优解X1=X1V=1/4，X2=X2V=3/4甲最优混合策略：以1/4的概率选 1；以3/4的概率选 2，最优值V=9/2.7.3 矩阵对策的混合策略例4（续）7.3 矩阵对策的混合策略19例例4 4（续）（续）设乙使用策略j的概率为Yj,j=1,2.Y1+Y2=1,Y1,Y2 0设乙损失的平均值V，作变换：Y1=Y1/V ，Y2=Y2/V建立线性模型 max Y1+Y2 s.t.3Y1+6Y2 1 Y1=1/9 5Y1+4Y2 1 Y2=1/9 Y1,Y2 0 1/V=Y1+Y2=2/9 7.3 矩阵对策的混合策略例4（续）7.3 矩阵对策的混合策略20例例4 4（续）（续）最优解Y1=Y1V=，Y2=Y2V=乙最优混合策略以1/2的概率选1；以1/2的概率选2，最优值V=9/2.7.3 矩阵对策的混合策略例4（续）7.3 矩阵对策的混合策略21注意：注意：若赢得矩阵若赢得矩阵A有非正元素，选有非正元素，选k0，令，令A=aij+k则矩阵对策则矩阵对策G=S1,S2,A与与G=S1,S2,A 解相同，但解相同，但VG=VG-k7.3 矩阵对策的混合策略注意：7.3 矩阵对策的混合策略22【优超概念优超概念】假设矩阵对策 G=S1,S2,A，甲方赢得矩阵A=aijmn。若存在两行（列）s、t，s 行（列）的各元素优于 t 行（列）的元素，即asjatj，j=1,2，n(ais ait，i=1,2，m)称甲方策略s优超于t(乙方s优超于t)。7.3 矩阵对策的混合策略矩阵对策的混合策略【优超概念】7.3 矩阵对策的混合策略23【优超原则优超原则】当局中人甲方策略t被其它策略所优超时，可在赢得矩阵A中划去第t行（同理，当局中人乙方策略t被其它策略所优超时，可在矩阵A中划去第t列）。如此得到阶数较小的赢得矩阵A，其对应的矩阵对策G=S1,S2,A与与G=S1,S2,A 等价。7.3 矩阵对策的混合策略矩阵对策的混合策略【优超原则】7.3 矩阵对策的混合策略24例例5 设甲方的赢得矩阵：1 2 0 3 0 3 0 1 4 8 A=7 3 9 5 9 4 6 8 7 5.5 6 0 8 8 3得到7 3 9 5 9 A1=4 6 8 7 5.5 6 0 8 8 37.3 矩阵对策的混合策略矩阵对策的混合策略被第3、4行所优超被第3行所优超被第1列所优超被第2列所优超例5 设甲方的赢得矩阵：7.3 矩阵对策的混合策略被第3、25例例5（续）（续）得到7 3 9 A2=4 6 5.5 6 0 3得到 7 3 9 A3=4 6 5.5 7 3最终得到 A4=4 6 7.3 矩阵对策的混合策略矩阵对策的混合策略被第1行所优超被第1列所优超例5（续）得到7.3 矩阵对策的混合策略被第1行所优超被第26例例5（续）（续）对对A4，用线性规划方法得到：，用线性规划方法得到：甲：X*=(0，0，1/3，2/3，0)T，V=5 乙：Y*=(1/2，1/2，0，0，0)T，V=5 （！A4行、列对应策略为3，4、1，2）7.3 矩阵对策的混合策略矩阵对策的混合策略例5（续）7.3 矩阵对策的混合策略27注意利用优超原则化简赢得矩阵时，可能将原对策问题的解也划去一些！习题：P206-4 Return7.3 矩阵对策的混合策略矩阵对策的混合策略注意7.3 矩阵对策的混合策略28