混合策略线性规划解法.ppt

§3 矩阵对策的混合策略 若不存在va=v=vb，则局中人甲、乙两方没有最优纯策略，就要考虑如何随机地使用自己的策略，使对方捉摸不到自己使用何种策略。即使用混合策略。 设矩阵对策 G = { S1, S2, A }。当 max min aij ? min max aij i j j i 时，不存在最优纯策略。 例：设一个赢得矩阵如下: min 5 9 5 A = max 6 策略?2 8 6 6 i max 8 9 min 8 策略?1 j 当甲取策略?2 ，乙取策略?1时，甲实际赢得8比预期的多2，乙当然不满意。考虑到甲可能取策略?2这一点，乙采取策略?2。若甲也分析到乙可能采取策略?2这一点，取策略?1，则赢得更多为9 … 。此时，对两个局中人甲、乙来说，没有一个双方均可接受的平衡局势，其主要原因是甲和乙没有执行上述原则的共同基础，即 max min aij ? min max aij 。 i j j i 一个自然的想法：对甲（乙）给出一个选取不同策略的概率分布，以使甲（乙）在各种情况下的平均赢得（损失）最多（最少）-----即混合策略。 求解混合策略的问题有图解法、迭代法、线性方程法和线性规划法等，我们这里只介绍线性规划法，其他方法略。 例：设甲使用策略?1的概率为X1′，使用策略?2的概率为X2′ ，并设在最坏的情况下，甲赢得的平均值为V（未知）。 5 9 A= STEP 1 8 6 1) X1′+X2′=1 X1′, X2′?0 2)无论乙取何策略，甲的平均赢得应不少于V: 对乙取?1： 5X1’+ 8X2’ ?V 对乙取?2： 9X1’+ 6X2’ ?V 注意 V0,因为A各元素为正。 STEP 2 作变换： X1= X1’/V ; X2= X2’/V 得到上述关系式变为： X1+ X2=1/V (V愈大愈好）待定 5X1+ 8X2?1 9X1+ 6X2?1 X1, X2?0 建立线性模型： min X1+X2 s.t. 5X1+8X2?1 X1= 0.048 9X1+6X2?1 X2= 0.095 X1, X2?0 所以，V=6.993 返回原问题： X1’= X1V= 0.336 X2’= X2V= 0.664 于是甲的最优混合策略为： 以0.336的概率选?1策略， 以0.664的概率选?2策略，简记为Ｘ﹡＝（0.336,0.664）T ， 最优值V=6.993。 例1：求解“齐王赛马”问题。 已知齐王的赢得矩阵A 求得 故不存在纯策略问题下的解，可求其混合策略。 A中有负元素，可以取k=2,在A的每个元素上加2得到A’如下： 建立对G′={S1，S2，A′}中求甲方最佳策略的线性规划如下： Min x1+x2+x3+x4+x5+x6 约束条件： 5x1+3x2+3x3+x4+3x5+3x6 ≥1 3x1+5x2+x3+3x4+3x5+3x6 ≥1 3x1+3x2+5x3+3x4+3x5+x6 ≥1 3x1+3x2+3x3+5x4+x5+3x6 ≥1 x1+3x2+3x3+3x4+5x5+3x6 ≥1 3x1+x2+3x3+3x4+3x5+5x6 ≥1 xi ≥ 0,i=1,2,…,6 可解