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

1、第7章 对策论7.1 基本概念基本概念7.2 矩阵对策的矩阵对策的最优纯策略最优纯策略7.3 矩阵对策的矩阵对策的混合策略混合策略7.1 基本概念 田忌赛马（教材188页）三个基本要素1.局中人：参与对抗的各方；2.策略集：局中人选择对付其它局中人的行动方案称为策略。局中人的所有策略全体称为策略集；3.益损值：每局中人各自使用一个对策就形成一个局势，一个局势决定了各局中人的对策结果，称为该局势下的益损值。益损值形成的矩阵称嬴得矩阵。例例1 “田忌赛马”齐王的益损值表7.1 基本概念例例1 1（续）（续）齐王的策略集齐王的策略集:S1=1,2,3,4,5,6 田忌的策略集：田忌的策略集：S2=1

2、,2,3,4,5,6 齐王的赢得矩阵齐王的赢得矩阵A 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 基本概念7.1 基本概念二人有限零和对策（又称矩阵对策）局中人为2；每局中人的策略集为有限集；每一局势双方均有确定的损益值，且同一局势的双方益损值和为零。7.1 基本概念 矩阵对策记号 G=S1,S2,A 甲的策略集 甲的赢得矩阵 乙的策略集“田忌赛马田忌赛马”是一个矩阵对策！是一个矩阵对策！ReturnReturn7.2 矩阵对策的最优纯策略甲方赢得矩阵A=aijmn

3、i行：表示甲方策略i，i=1,2,m.j列：表示乙方策略j，j=1,2,n.aij：表示甲方取策略i、乙方取策略j时甲方在该局势下的益损值.（！此时乙方的益损值为！此时乙方的益损值为-aij）7.2 矩阵对策的最优纯策略例2 两个局中人甲、乙，甲策略=1,2,3，乙策略集=1,2,3,4，甲方赢得矩阵A:-5 0 -2 0 A =2 3 0 1 -2 -4 -1 3问：甲、乙应采取何策略比较适合？例2（续）甲：采取1至少得益5 2 0 3 -4乙：采取1甲最多得益2 2 3 3 0 4 3maxi minj aij=0 取最大：取最大：2minj maxi aij=0 取最小：取最小：37.2

4、 矩阵对策的最优纯策略例2（续）甲采取策略2 不管乙采取如何策略，都至少得益0。乙采取策略3 不管甲采取如何策略，都至多损失0。2，3分别称甲，乙的最优策略，又称最优纯策略。7.2 矩阵对策的最优纯策略最优纯策略存在条件：max min amax min aij ij=min max a=min max aij ij=v=v i j j i i j j i!（2，3）亦称）亦称为对策G=S1,S2,A的鞍点，值V称为G的值。Return7.2 矩阵对策的最优纯策略7.3 矩阵对策的混合策略矩阵对策 G=S1,S2,A 当 max min aij min max aij i j j i 时，不存

5、在最优纯策略。求解混合策略！7.3 矩阵对策的混合策略例3 设某赢得矩阵:minmin 3 6 3 3 6 3 A =max 4 A =max 4 策略2 5 4 4 5 4 4 i i max 5 6 max 5 6 min 5 min 5 策略1 j 例3（续）分析：甲取2，乙取1，甲实际赢得5（比预期多1），这时乙不满意，考虑采取策略2；为应对乙，甲采取策略1，赢得6；甲，乙没能达到令双方均满意的平衡局甲，乙没能达到令双方均满意的平衡局势！势！7.3 矩阵对策的混合策略新思路：为甲、乙给出选取不同策略的概率分布，使双方在各种情况下的平均赢得（损失）最多（最少）混合策略7.3 矩阵对策的混

6、合策略7.3 矩阵对策的混合策略求解方法：线性规划法例4 设甲赢得矩阵A，赢得的平均值为V 3 6 A=5 4 7.3 矩阵对策的混合策略例4（续）解：解：第一步第一步1)设甲采用策略 i的概率为Xi,i=1,2.则则 X1+X2=1，X1,X2 02)甲的平均赢得应不少于V:乙取1：3X1+5X2 V 乙取2：6X1+4X2 V例例4 4（续）（续）第二步第二步 令 X1=X1/V，X2=X2/V，得 X1+X2=1/V 3X1+5X2 1 6X1+4X2 1 X1,X2 07.3 矩阵对策的混合策略例例4 4（续）（续）第三步第三步 min X1+X2 X1=1/18建立线性模型：s.t.

7、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 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 4（续）

8、（续）最优解Y1=Y1V=，Y2=Y2V=乙最优混合策略以1/2的概率选1；以1/2的概率选2，最优值V=9/2.7.3 矩阵对策的混合策略注意：注意：若赢得矩阵若赢得矩阵A有非正元素，选有非正元素，选k0，令，令A=aij+k则矩阵对策则矩阵对策G=S1,S2,A与与G=S1,S2,A 解相同，但解相同，但VG=VG-k7.3 矩阵对策的混合策略【优超概念优超概念】假设矩阵对策 G=S1,S2,A，甲方赢得矩阵A=aijmn。若存在两行（列）s、t，s 行（列）的各元素优于 t 行（列）的元素，即asjatj，j=1,2，n(ais ait，i=1,2，m)称甲方策略s优超于t(乙方s优超于

9、t)。7.3 矩阵对策的混合策略矩阵对策的混合策略【优超原则优超原则】当局中人甲方策略t被其它策略所优超时，可在赢得矩阵A中划去第t行（同理，当局中人乙方策略t被其它策略所优超时，可在矩阵A中划去第t列）。如此得到阶数较小的赢得矩阵A，其对应的矩阵对策G=S1,S2,A与与G=S1,S2,A 等价。7.3 矩阵对策的混合策略矩阵对策的混合策略例例5 5 设甲方的赢得矩阵：1 2 0 3 01 2 0 3 0 3 0 1 4 8 3 0 1 4 8 A=7 3 9 5 9=7 3 9 5 9 4 6 8 7 5.5 4 6 8 7 5.5 6 0 8 8 3 6 0 8 8 3 得到 7 3 7

10、 3 9 59 5 9 9 A1=4 6 =4 6 8 78 7 5.5 5.5 6 0 6 0 8 88 8 3 37.3 矩阵对策的混合策略矩阵对策的混合策略被第3、4行所优超被第3行所优超被第1列所优超被第2列所优超 例例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（续）（续）对对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 矩阵对策的混合策略矩阵对策的混合策略注意利用优超原则化简赢得矩阵时，可能将原对策问题的解也划去一些！习题：P206-4 Return7.3 矩阵对策的混合策略矩阵对策的混合策略