管理运筹学-对策论

1、编辑ppt1对策论由“齐王赛马”引入编辑ppt21.对策论的基本概念 三个基本要素； 1.局中人：参与对抗的各方； 2.策略集：局中人选择对付其它局中人的行动方案称为策略。 某局中人的所有可能策略全体称为策略集；3.局势对策的益损值：各局中人各自使用一个对策就形成一个局势，一个局势决定了个局众人 的对策结果（量化）称为该局势对策的益损值）编辑ppt3“齐王赛马”齐王在各局势中的益损值表（单位：千金）编辑ppt4 齐王的策略集: S S1 1=1, 2, 3, 4, 5, 6 田忌的策略集： S S2 2=1, 2, 3, 4, 5, 6 下列矩阵称齐王的赢得矩阵： 3 1 1 1 -1 13

2、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 编辑ppt51.基本概念（续）二人有限零和对策：（又称矩阵策略）局中人为2；每局中人的策略集中策略权目有限；每一局势的对策均有确定的损益值，并且对同一局势的两个局中人的益损值之和为零。编辑ppt61.基本概念（续） 记矩阵对策为: G = SG = S1 1, S, S2 2, A, A 甲的策略集 甲的赢得

3、矩阵 乙的策略集 “齐王赛马”即是一个矩阵策略.编辑ppt72.矩阵对策的最优纯策略 在甲方赢得矩阵中： A=aijm*n i行代表甲方策略 i=1,2m j行代表乙方策略 j=1,2n aij代表甲方取策略i,乙方取策略j,这一局势下甲方的益损值，此时乙方的益损值为-aij（零和性质）。 在讨论各方采用的策略是必须注意一个前提就是对方是理智的。这就是要从最有把握取得的益损值情况考虑。编辑ppt82.矩阵对策的最优纯策略(续) 例：有交易双方公司甲和乙，甲有三个策略1，2，3；乙有四个策略1，2，3，4，根据获利情况建立甲方的益损值 赢得矩阵。 -3 0 -2 0-3 0 -2 0 A= 2

4、3 0 1 A= 2 3 0 1 -2 -4 -1 3 -2 -4 -1 3 问：甲公司应采取什么策略比较适合？编辑ppt9甲：采取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编辑ppt10 甲采取策略2 不管乙采取如何策略，都至少得益。 乙采取策略3 不管甲采取如何策略， 都至少可以得

5、益。（最多损失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的值。编辑ppt113.矩阵对策的混合策略 设矩阵对策 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 时，不存在最优纯策略 求解混合策略。

6、编辑ppt123.矩阵对策的混合策略例：设一个赢得矩阵如下: 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编辑ppt13 矛盾：甲取2 ，乙取时1，甲实际赢得8比预期多2（乙就少2）这对乙讲是不满意的，考虑这一点，乙采取策略2，若甲分析到这一点，取策略1，则赢得更多为9 此时，甲，乙芳没有一个双方均可接受的平衡局势。 一个思路：对甲（乙）给出一个选取不同策略的概率分布，以使甲（乙）在各种情况下的平均赢得（损失）最多（最少）。-即混合策略编辑ppt14 求解

7、方法：线性规划法 （其他方法：图解法，迭代法，线性方程法等略） 例： 5 95 9 设在最坏的情况下， A=A= 甲赢得的平均值为V V. 8 68 6 （未知） STEP 1STEP 1 1)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编辑ppt152)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

8、作变换： 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编辑ppt16 建立线性模型： 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

9、 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.编辑ppt17 同样可求乙的最优混合策略： 设乙使用策略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. 这也是

10、乙损失的平均值，越小越好 作变换： 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 编辑ppt18 返回原问题： Y Y1 1= = Y Y1 1V= 1/2V= 1/2 Y Y2 2= = Y

11、 Y2 2V= 1/2V= 1/2 于是乙的最优混合策略为： 以1/21/2的概率选1 1；以1/21/2的概率选2 2 最优值V=7V=7. 当赢得矩阵中有非正元素时，V0的条件不一定成立，可以作下列变换： 选一正数k，令矩阵中每一元素加上k得到新的正矩阵A，其对应的矩阵对策 G= SG= S1 1,S,S2 2,A,A与与 G = SG = S1 1,S,S2 2,A ,A 解相同，但解相同，但V VG G = V = VG G - k - k编辑ppt19再讨论“齐王赛马” “齐王赛马”的赢得矩阵A有 max min amax min aijij1 1 min max a min max

12、 aijij3 3 i j j ii j j i 故需求混合策略，由于A中有非正元素，可选k2，令矩阵中每一元素加上k得到新的正矩阵A： 5 3 3 3 1 35 3 3 3 1 3 3 5 3 3 3 1 3 5 3 3 3 1 A = 3 1 5 3 3 3 A = 3 1 5 3 3 3 1 3 3 5 3 3 1 3 3 5 3 3 3 3 3 1 5 3 3 3 3 1 5 3 3 3 1 3 3 5 3 3 1 3 3 5编辑ppt20再讨论“齐王赛马”(续) 求甲方(齐王)最优策略的线性规划模型： min Xmin X1 1+X+X2 2 +X+X3 3 +X+X4 4 +X+X

13、5 5 +X+X6 6 s.t. 5Xs.t. 5X1 1+3X+3X2 2 +3X+3X3 3 + X+ X4 4 +3X+3X5 5 +3X+3X6 6 1 1 3X 3X1 1+5X+5X2 2 + X+ X3 3 +3X+3X4 4 +3X+3X5 5 +3X+3X6 6 1 1 3X 3X1 1+3X+3X2 2 +5X+5X3 3 +3X+3X4 4 +3X+3X5 5 + X+ X6 6 1 1 3X 3X1 1+3X+3X2 2 +3X+3X3 3 +5X+5X4 4 + X+ X5 5 +3X+3X6 6 1 1 X X1 1+3X+3X2 2 +3X+3X3 3 +3X+3

14、X4 4 +5X+5X5 5 +3X+3X6 6 1 1 3X 3X1 1+ X+ X2 2 +3X+3X3 3 +3X+3X4 4 +3X+3X5 5 +5X+5X6 6 1 1 X X1 1，X X2 2，X X3 3，X X4 4，X X5 5，X X6 6 0 0 可得两组解：可得两组解：(0,1/9,1/9,0,0,1/9)(0,1/9,1/9,0,0,1/9)T T, , (1/18,1/18,1/18,1/18,1/18,1/18) (1/18,1/18,1/18,1/18,1/18,1/18)T T ,V=3,V=3于是，于是，XX(0,1/3,1/3,0,0,1/3)(0,1

15、/3,1/3,0,0,1/3)T T, , XX(1/6,1/6,1/6,1/6,1/6,1/6)(1/6,1/6,1/6,1/6,1/6,1/6)T T V = V-2 V = V-2 = = 1 1即齐王的最优混合策略值是赢即齐王的最优混合策略值是赢1 1千金千金编辑ppt21再讨论“齐王赛马”(续) 求乙方(田忌)最优策略的线性规划模型： min Ymin Y1 1+Y+Y2 2 +Y+Y3 3 +Y+Y4 4 +Y+Y5 5 +Y+Y6 6 s.t. 5Ys.t. 5Y1 1+3Y+3Y2 2 +3Y+3Y3 3 +3Y+3Y4 4 + Y+ Y5 5 +3Y+3Y6 6 1 1 3Y

16、 3Y1 1+5Y+5Y2 2 +3Y+3Y3 3 +3Y+3Y4 4 +3Y+3Y5 5 + Y+ Y6 6 1 1 3Y 3Y1 1+ Y+ Y2 2 +5Y+5Y3 3 +3Y+3Y4 4 +3Y+3Y5 5 +3Y+3Y6 6 1 1 Y Y1 1+3Y+3Y2 2 +3Y+3Y3 3 +5Y+5Y4 4 +3Y+3Y5 5 +3Y+3Y6 6 1 1 3Y 3Y1 1+3Y+3Y2 2 +3Y+3Y3 3 + Y+ Y4 4 +5Y+5Y5 5 +3Y+3Y6 6 1 1 3Y 3Y1 1+3Y+3Y2 2 + Y+ Y3 3 +3Y+3Y4 4 +3Y+3Y5 5 +5Y+5Y6

17、6 1 1 Y Y1 1，Y Y2 2，Y Y3 3，Y Y4 4，Y Y5 5，Y Y6 6 0 0 可得两组解：可得两组解：(1/9,0,0,1/9,1/9,0)(1/9,0,0,1/9,1/9,0)T T, , (1/18,1/18,1/18,1/18,1/18,1/18) (1/18,1/18,1/18,1/18,1/18,1/18)T T ,V=3,V=3于是，于是，YY(1/3,0,0,1/3,1/3,0)(1/3,0,0,1/3,1/3,0)T T, , YY(1/6,1/6,1/6,1/6,1/6,1/6)(1/6,1/6,1/6,1/6,1/6,1/6)T T V = V-2

18、 V = V-2 = = 1 1即田忌的最优混合策略值是输即田忌的最优混合策略值是输1 1千金千金编辑ppt22 优超原则：优超原则： 假设矩阵对策 G = SG = S1 1,S,S2 2,A ,A 甲方赢得矩阵 A=aijmn- 若存在两行，s 行的各元素均优于 t 行的元素，即 asjatj j=1,2n 称甲方策略s优超于t - 若存在两列，s 列的各元素均优于 t 列的元素，即 ais ait i=1,2,m 称乙方策略 s优超于t3.3.矩阵对策的混合策略矩阵对策的混合策略( (续续) )编辑ppt23- 优超原则：当局中人甲方的策略t被其它策略所优超时，可在其赢得矩阵A中划去第t

19、行（同理，当局中人乙方的策略t被其它策略所优超时，可在矩阵A中划去第t列）。 如此得到阶数较小的赢得矩阵A，其对应的矩阵对策 G= SG= S1 1,S,S2 2,A,A与与 G = SG = S1 1,S,S2 2,A ,A 等价，即解相同。3.3.矩阵对策的混合策略矩阵对策的混合策略( (续续) )编辑ppt24 例 设甲方的益损值 赢得矩阵。 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