运筹学管理运筹学-对策论.pptxVIP

对策论;1.对策论的基本概念;“齐王赛马”齐王在各局势中的益损值表（单位：千金）;其中： 齐王的策略集: S1={?1,?2,?3,?4,?5,?6} 田忌的策略集：S1={?1,?2,?3,?4,?5,?6} 下列矩阵称齐王的赢得矩阵： 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 ;1.基本概念（续）;1.基本概念（续）;2.矩阵对策的最优纯策略;2.矩阵对策的最优纯策略(续);甲： 采取?1至少得益–3(损失 3） ?2 0 ?3 -4(损失 4） 乙： 采取?1甲最多得益2 （乙最少得益-2） ?2 3（乙得益-3） ?3 0（乙得益 0） ?4 3（乙得益-3）;甲采取策略?2 不管乙采取如何策略，都至少得益。 乙采取策略?3 不管甲采取如何策略， 都至少可以得益。（最多损失0） 分别称甲，乙公司的最优策略，由唯一性又称最优纯策略。 存在前提： max min aij = min max aij = v i j j i 又称（ ?2 ，?3 ）为对策G={s1,s2,A} 的鞍点。值V为G的值。 ;3.矩阵对策的混合策略;3.矩阵对策的混合策略;矛盾：甲取?2 ，乙取时?1，甲实际赢得8比预期多2（乙就少2）这对乙讲是不满意的，考虑这一点，乙采取策略?2，若甲分析到这一点，取策略?1，则赢得更多为9… 此时，甲，乙方没有一个双方均可接受的平衡局势。 一个思路：对甲（乙）给出一个选取不同策略的概率分布，以使甲（乙）在各种情况下的平均赢得（损失）最多（最少）。-----即混合策略;求解方法：线性规划法 （其他方法：图解法，迭代法，线性方程法等略） 例： 5 9 设在最坏的情况下， A= 甲赢得的平均值为V. 8 6 （未知） STEP 1 1)设甲使用策略?1的概率为X1′ X1′+X2′=1 设甲使用策略?2的概率为X2′ 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= 1/21 9X1+6X2?1 X2= 2/21 X1, X2?0 1/V= X1+X2=1/7 所以：V=7 返回原问题： X1’= X1V= 1/3 X2’= X2V= 2/3 于是甲的最优混合策略为： 以1/3的概率选?1；以2/3的概率选?2 最优值V=7.;同样可求乙的最优混合策略： 设乙使用策略?1的概率为Y1′ Y1′+Y2′=1 设乙使用策略?2的概率为Y2′ Y1′,Y2′?0 设在最坏的情况下，甲赢得的平均值为V. 这也是乙损失的平均值，越小越好 作变换： Y1= Y1’/V ; Y2= Y2’/V 建立线性模型： max Y1+Y2 s.t. 5Y1+9Y2?1 Y1= 1/14 8Y1+6Y2?1 Y2= 1/14 Y1, Y2?0 1/V= Y1+Y2=1/7 所以：V=7 ;返回原问题： Y1’= Y1V= 1/2 Y2’= Y2V= 1/2 于是乙的最优混合策略为： 以1/2的概率选?1；以1/2的概率