管理运筹学-对策论

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,对策论,由“齐王赛马”引入,1.对策论的基本概念,三个,基本要素；,1.局中人：参与对抗的各方；,2.策略集：局中人选择对付其它局中人的行动方案称为策略。,某局中人的所有可能策略全体称为策略集；,3.局势对策的益损值：各局中人各自使用一个对策就形成一个局势，一个局势决定了个局众人 的对策结果（量化）称为该局势对策的益损值）,“,齐王赛马”齐王在各局势中的益损值表（单位：千金）,其中：,齐王的策略集:,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.基本概念（续）,二人有限零和对策：（又称矩阵策略）,局中人为2；,每局中人的策略集中策略权目有限；,每一局势的对策均有确定的损益值，并且对同一局势的两个局中人的益损值之和为零。,1.基本概念（续）,记,矩阵对策为:,G=S,1,S,2,A,甲的策略集 甲的赢得矩阵,乙的策略集,“齐王赛马”即是一个矩阵策略.,2.矩阵对策的最优纯策略,在,甲方赢得矩阵中：,A=a,ij,m*n,i,行代表甲方策略,i=1,2m,J,列代表乙方策略,j=1,2n,a,ij,代表甲方取策略,i,乙方取策略,j,这一局势下甲方的益损值，此时乙方的益损值为-,a,ij,（,零,和性质）。,在讨论各方采用的策略是必须注意一个前提就是对方是理智的。这就是要从最有把握取得的益损值情况考虑。,2.矩阵对策的最优纯策略(续),例：有交易双方公司甲和乙，甲有三个策略,1,，,2,，,3,；乙有四个策略,1,，,2,，,3,，,4,，根据获利情况建立甲方的益损值 赢得矩阵。,-3 0 -2 0,A=2 3 0 1,-2 -4 -1 3,问：甲公司应采取什么策略比较适合？,甲：,采取,1,至少得益3(损失 3）,2,0,3,-4(损失 4）,乙：,采取,1,甲最多得益2,（乙最少得益-2）,2,3（乙得益-3）,3,0（乙得益 0）,4,3（乙得益-3）,取大则取,2,max min,a,ij,=0,i j,取小则取,3,min max a,ij,=0,j,i,甲,采取策略,2,不管乙采取如何策略，都至少得益。,乙采取策略,3,不管甲采取如何策略，,都至少可以得益。（最多损失0）,分别称甲，乙公司的最优策略，由唯一性又称最优纯策略。,存在前提：,max min,a,ij,=min max,a,ij,=v,i,j,j,i,又称,（,2,，,3,）,为对策,G=,s,1,s,2,A,的鞍点。值,V,为,G,的值。,3.矩阵对策的混合策略,设,矩阵对策,G=S,1,S,2,A,当,max min a,ij,min max a,ij,i j,j,i,时，不存在最优纯策略 求解混合策略。,3.矩阵对策的混合策略,例：设一个赢得矩阵如下:,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，,若甲分析到这一点，取策略,1，,则赢得更多为9,此时，甲，乙方没有一个双方均可接受的平衡局势。,一个思路：对甲（乙）给出一个选取不同策略的概率分布，以使甲（乙）在各种情况下的平均赢得（损失）最多（最少）。-即混合策略,求解方法：,线性规划法,（其他方法：图解法，迭代法，线性方程法等略）,例：,5 9,设在最坏的情况下，,A=,甲赢得的平均值为,V,.,8 6,（,未知）,STEP 1,1),设甲使用策略,1,的概率为,X,1,X,1,+X,2,=1,设甲使用策略,2,的概率为,X,2,X,1,X,2,0,2),无论乙取何策略，甲的平均赢得应不少于,V,:,对乙取,1,：,5,X,1,+8X,2,V,对乙取,2,：,9,X,1,+6X,2,V,注意,V0,因为,A,各元素为正。,STEP 2,作变换：,X,1,=X,1,/V ;X,2,=X,2,/V,得到上述关系式变为：,X,1,+X,2,=1/V (V,愈大愈好）待定,5,X,1,+8X,2,1,9X,1,+6X,2,1,X,1,X,2,0,建立线性模型：,min X,1,+X,2,s.t.5X,1,+8X,2,1,X,1,=1/21,9,X,1,+6X,2,1,X,2,=2/21,X,1,X,2,0 1/V=,X,1,+X,2,=1/7,所以：,V=7,返回原问题：,X,1,=,X,1,V=1/3,X,2,=,X,2,V=2/3,于是甲的最优混合策略为：,以,1/3,的概率选,1,；,以,2/3,的概率选,2,最优值,V=7,.,同样可求乙的最优混合策略：,设乙使用策略,1,的概率为,Y,1,Y,1,+Y,2,=1,设乙使用策略,2,的概率为,Y,2,Y,1,Y,2,0,设在最坏的情况下，甲赢得的平均值为,V,.,这也是乙损失的平均值，越小越好,作变换：,Y,1,=Y,1,/V ;Y,2,=Y,2,/V,建立线性模型：,max Y,1,+Y,2,s.t.5Y,1,+9Y,2,1,Y,1,=1/14,8,Y,1,+6Y,2,1,Y,2,=1/14,Y,1,Y,2,0 1/V=,Y,1,+Y,2,=1/7,所以：,V=7,返回原问题：,Y,1,=,Y,1,V=1/2,Y,2,=,Y,2,V=1/2,于是乙的最优混合策略为：,以,1/2,的概率选,1,；,以,1/2,的概率选,2,最优值,V=7,.,当赢得矩阵中有非正元素时，,V0,的条件不一定成立，可以作下列变换：,选一正数,k，,令矩阵中每一元素加上,k,得到新的正矩阵,A,，,其对应的矩阵对策,G,=S,1,S,2,A,与,G=S,1,S,2,A,解相同，但,V,G,=V,G,-k,例：,求解“齐王赛马”,问题（见备课稿）,优超原则：,假设,矩阵对策,G=S,1,S,2,A,甲方赢得矩阵,A=,a,ij,m,n,-,若存在两行（列），,s,行（列）的各元素均优于,t,行（列）的元素，即,a,sj,a,tj,j=1,2n(,a,is,a,it,i=1,2m),称甲方策略,s,优超于,t,(,s,优超于,t,),3.矩阵对策的混合策略(续),-优超原则：当局中人甲方的策略,t,被其它策略所,优超时，可在其赢得矩阵,A,中划去第,t,行（同理，当局中人乙方的策略,t,被其它策略所,优超时，可在矩阵,A,中划去第,t,列）。,如此得到阶数较小的赢得矩阵,A,，,其对应的矩阵对策,G,=S,1,S,2,A,与,G=S,1,S,2,A,等价，即解相同。,3.矩阵对策的混合策略(续),例 设,甲方的益损值 赢得矩阵。,3 2 0 3 0,被第3、4行所优超,5 0 2 5 9,被第3行所优超,A=7 3 9 5 9,4 6 8 7 5.5,6 0 8 8 3,得到,7 3,9 5,9,被第1列所优超,A,1,=4 6,8 7,5.5,被第2列所优超,6 0,8 8,3,3.矩阵对策的混合策略(续),续例 得到,7 3 9,A,2,=4 6 5.5,6 0 3,被第1行所优超,得到,7 3,9,被第1列所优超,A,3,=,4 6,5.5,7 3,最终得到,A,4,=,4 6,3.矩阵对策的混合策略(续),对,A,4,计算，用线性规划方法得到：,（注意：余下的策略为,3,，,4,，,1,，,2,）,甲：,X,*,=(0，0，1/15，2/15，0),T,V=5,X,*,=(0，0，1/3，2/3，0),T,乙：,Y,*,=(1/10，1/10，0，0，0),T,V=5,Y,*,=(1/2，1/2，0，0，0),T,注：,利用有超原则化简赢得矩阵时，有可能将原对策问题的解也划去一些（多解情况）；,线性规划求解时有可能是多解问题。,习题：,P,343,-1，3，4,3.矩阵对策的混合策略(续),