管理运筹学对策论精选PPT.ppt
管理运筹学对策论第1页，此课件共23页哦1.对策论的基本概念三个基本要素；1.局中人：参与对抗的各方；2.策略集：局中人选择对付其它局中人的行动方案称为策略。某局中人的所有可能策略全体称为策略集；3.局势对策的益损值：各局中人各自使用一个对策就形成一个局势，一个局势决定了个局众人 的对策结果（量化）称为该局势对策的益损值）第2页，此课件共23页哦“齐王赛马”齐王在各局势中的益损值表（单位：千金）第3页，此课件共23页哦其中：齐王的策略集:S1=S1=1,2,3,4,5,6 田忌的策略集：S1=S1=1,2,3,4,5,6 下列矩阵称齐王的赢得矩阵：3 1 1 1 -1 13 1 1 1 -1 1 1 3 1 1 1 -1 1 3 1 1 1 -1A=1 -1 3 1 1 1A=1 -1 3 1 1 1 -1 1 1 3 1 1 -1 1 1 3 1 1 1 1 1 -1 3 1 1 1 1 -1 3 1 1 1 -1 1 1 3 1 1 -1 1 1 3 第4页，此课件共23页哦1.基本概念（续）二人有限零和对策：（又称矩阵策略）局中人为2；每局中人的策略集中策略权目有限；每一局势的对策均有确定的损益值，并且对同一局势的两个局中人的益损值之和为零。第5页，此课件共23页哦1.基本概念（续）记矩阵对策为:G=SG=S1 1,S,S2 2,A,A 甲的策略集 甲的赢得矩阵 乙的策略集“齐王赛马”即是一个矩阵策略.第6页，此课件共23页哦2.矩阵对策的最优纯策略在甲方赢得矩阵中：A=aijm*ni行代表甲方策略 i=1,2mJ列代表乙方策略 j=1,2naij代表甲方取策略i,乙方取策略j,这一局势下甲方的益损值，此时乙方的益损值为-aij（零和性质）。在讨论各方采用的策略是必须注意一个前提就是对方是理智的。这就是要从最有把握取得的益损值情况考虑。第7页，此课件共23页哦2.矩阵对策的最优纯策略(续)例：有交易双方公司甲和乙，甲有三个策略1，2，3；乙有四个策略1，2，3，4，根据获利情况建立甲方的益损值 赢得矩阵。-3 0 -2 0-3 0 -2 0 A=2 3 0 1 A=2 3 0 1 -2 -4 -1 3 -2 -4 -1 3问：甲公司应采取什么策略比较适合？第8页，此课件共23页哦甲：采取1至少得益3(损失 3）2 0 3 -4(损失 4）乙：采取1甲最多得益2 （乙最少得益-2）2 3（乙得益-3）3 0（乙得益 0）4 3（乙得益-3）取大则取取大则取 2 2 max min amax min aijij=0=0 i ji j取小则取取小则取 3 3 min max amin max aijij=0=0 j j i i第9页，此课件共23页哦甲采取策略2 不管乙采取如何策略，都至少得益。乙采取策略3 不管甲采取如何策略，都至少可以得益。（最多损失0）分别称甲，乙公司的最优策略，由唯一性又称最优纯策略。存在前提：max min amax min aij ij=min max a=min max aij ij=v=v i j j i i j j i又称（2 2，3 3）为对策G=G=s s1 1,s s2 2,A,A的鞍点。值V为G的值。第10页，此课件共23页哦3.矩阵对策的混合策略设矩阵对策 G=SG=S1 1,S,S2 2,A,A当 max min amax min aij ij min max a min max aij ij i j j ii j j i 时，不存在最优纯策略 求解混合策略。第11页，此课件共23页哦3.矩阵对策的混合策略例：设一个赢得矩阵如下:minmin 5 9 5 5 9 5 A =max 6 A =max 6 策略2 8 6 6 8 6 6 i i max 8 9 max 8 9 min 8 min 8 策略1 j第12页，此课件共23页哦矛盾：甲取2，乙取时1，甲实际赢得8比预期多2（乙就少2）这对乙讲是不满意的，考虑这一点，乙采取策略2，若甲分析到这一点，取策略1，则赢得更多为9此时，甲，乙方没有一个双方均可接受的平衡局势。一个思路：对甲（乙）给出一个选取不同策略的概率分布，以使甲（乙）在各种情况下的平均赢得（损失）最多（最少）。-即混合策略第13页，此课件共23页哦求解方法：线性规划法（其他方法：图解法，迭代法，线性方程法等略）例：5 95 9 设在最坏的情况下，A=A=甲赢得的平均值为V V.8 68 6 （未知）STEP 1STEP 11)1)设甲使用策略 1 1的概率为X X1 1 X X1 1+X+X2 2=1=1 设甲使用策略 2 2的概率为X X2 2 X X1 1,X,X2 2 0 0第14页，此课件共23页哦2)2)无论乙取何策略，甲的平均赢得应不少于V V:对乙取1：5X5X1 1+8X+8X2 2 V V对乙取2：9X9X1 1+6X+6X2 2 V V 注意 V0,V0,因为A A各元素为正。STEP 2 STEP 2 作变换：X X1 1=X=X1 1/V ;X/V ;X2 2=X=X2 2/V/V得到上述关系式变为：X X1 1+X+X2 2=1/V (V=1/V (V愈大愈好）待定愈大愈好）待定 5X5X1 1+8X+8X2 2 1 1 9X 9X1 1+6X+6X2 2 1 1 X X1 1,X,X2 2 0 0第15页，此课件共23页哦建立线性模型：min Xmin X1 1+X+X2 2 s.t.5Xs.t.5X1 1+8X+8X2 2 1 1 X X1 1=1/21=1/21 9 9X X1 1+6X+6X2 2 1 1 X X2 2=2/21=2/21 X X1 1,X,X2 2 0 1/V=0 1/V=X X1 1+X+X2 2=1/7=1/7 所以：V=7V=7 返回原问题：X X1 1=X X1 1V=1/3V=1/3 X X2 2=X X2 2V=2/3V=2/3 于是甲的最优混合策略为：以1/31/3的概率选 1 1；以2/32/3的概率选 2 2 最优值V=7V=7.第16页，此课件共23页哦同样可求乙的最优混合策略：设乙使用策略1 1的概率为Y1 1 Y Y1 1+Y+Y2 2=1=1 设乙使用策略2 2的概率为Y2 2 Y Y1 1,Y,Y2 2 0 0设在最坏的情况下，甲赢得的平均值为V V.这也是乙损失的平均值，越小越好 作变换：Y Y1 1=Y=Y1 1/V ;Y/V ;Y2 2=Y=Y2 2/V/V建立线性模型：max Ymax Y1 1+Y+Y2 2 s.t.5Ys.t.5Y1 1+9Y+9Y2 2 1 1 Y Y1 1=1/14=1/14 8 8Y Y1 1+6Y+6Y2 2 1 1 Y Y2 2=1/14=1/14 Y Y1 1,Y,Y2 2 0 1/V=0 1/V=Y Y1 1+Y+Y2 2=1/7=1/7 所以：V=7V=7 第17页，此课件共23页哦返回原问题：Y Y1 1=Y Y1 1V=1/2V=1/2 Y Y2 2=Y Y2 2V=1/2V=1/2 于是乙的最优混合策略为：以1/21/2的概率选1 1；以1/21/2的概率选2 2 最优值V=7V=7.当赢得矩阵中有非正元素时，V0的条件不一定成立，可以作下列变换：选一正数k，令矩阵中每一元素加上k得到新的正矩阵A，其对应的矩阵对策 G G=S=S1 1,S,S2 2,A,A 与与 G=SG=S1 1,S,S2 2,A,A 解相同，但解相同，但V VG G=V=VG G-k-k第18页，此课件共23页哦例：求解“齐王赛马”问题（见备课稿）优超原则：优超原则：假设矩阵对策 G=SG=S1 1,S,S2 2,A,A 甲方赢得矩阵 A=aijmn-若存在两行（列），s 行（列）的各元素均优于 t 行（列）的元素，即 asjatj j=1,2n(ais ait i=1,2m)称甲方策略s优超于t(s优超于t)3.3.矩阵对策的混合策略矩阵对策的混合策略(续续)第19页，此课件共23页哦-优超原则：当局中人甲方的策略t被其它策略所优超时，可在其赢得矩阵A中划去第t行（同理，当局中人乙方的策略t被其它策略所优超时，可在矩阵A中划去第t列）。如此得到阶数较小的赢得矩阵A，其对应的矩阵对策 G G=S=S1 1,S,S2 2,A,A 与与 G=SG=S1 1,S,S2 2,A,A 等价，即解相同。3.3.矩阵对策的混合策略矩阵对策的混合策略(续续)第20页，此课件共23页哦例 设甲方的益损值 赢得矩阵。3 2 0 3 03 2 0 3 0 被第3、4行所优超 5 0 2 5 95 0 2 5 9 被第3行所优超 A=7 3 9 5 9A=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 3 9 59 5 9 9 被第1列所优超 A A1 1=4 6 =4 6 8 78 7 5.5 5.5 被第2列所优超 6 0 6 0 8 88 8 3 33.3.矩阵对策的混合策略矩阵对策的混合策略(续续)第21页，此课件共23页哦续例 得到 7 3 97 3 9 A A2 2=4 6 5.5=4 6 5.5 6 0 36 0 3 被第1行所优超得到得到 7 3 7 3 9 9 被第1列所优超 A A3 3=4 6 4 6 5.55.5 7 3 7 3最终得到最终得到 A A4 4=4 6 4 6 3.3.矩阵对策的混合策略矩阵对策的混合策略(续续)第22页，此课件共23页哦对对A A4 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 注：利用有超原则化简赢得矩阵时，有可能将原对策问题的解也划去一些（多解情况）；线性规划求解时有可能是多解问题。习题：P343-1，3，43.3.矩阵对策的混合策略矩阵对策的混合策略(续续)第23页，此课件共23页哦
