《大学运筹学经典课件第十五章——对策论》由会员分享，可在线阅读，更多相关《大学运筹学经典课件第十五章——对策论（39页珍藏版）》请在金锄头文库上搜索。
1、管管 理理 运运 筹筹 学学1第十五章 对策论 11 对策论的基本概念对策论的基本概念 2 2 矩阵对策的最优纯策略矩阵对策的最优纯策略 3 3 矩阵对策的混合策略矩阵对策的混合策略 4 4 其他类型的对策论简介其他类型的对策论简介管管 理理 运运 筹筹 学学2第十五章 对策论 由“齐王赛马”引入管管 理理 运运 筹筹 学学31 1对策论的基本概念对策模型的三个基本要素：对策模型的三个基本要素：1.1.局中人局中人：参与对抗的各方；：参与对抗的各方；2.2.策略集：局中人选择对付其它局中人的行动方案称策略集：局中人选择对付其它局中人的行动方案称为为策略策略；某局中人的所有可能策略全体称为；某局
2、中人的所有可能策略全体称为策略集策略集；3.3.一局势对策的益损值：局中人各自使用一个对策就一局势对策的益损值：局中人各自使用一个对策就形成了形成了一个局势一个局势，一个局势决定了各局中人的对策，一个局势决定了各局中人的对策结果（量化）称为该局势对策的结果（量化）称为该局势对策的益损值益损值。管管 理理 运运 筹筹 学学4“齐王赛马齐王赛马”齐王在各局势中的益损值表（单位：千金）齐王在各局势中的益损值表（单位：千金）1 1对策论的基本概念管管 理理 运运 筹筹 学学5其中：齐王的策略集其中：齐王的策略集: : S1= 1, 2, 3, 4, 5, 6 ， 田忌的策略集：田忌的策略集：S2= 1
3、, 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对策论的基本概念管管 理理 运运 筹筹 学学6二人有限零和对策二人有限零和对策（又称（又称矩阵对策矩阵对策）：）： 局中人为局中人为2 2；每个局中人的策略集的策略数目都；每个局中人的策略集的策略数目都是有限的；每一局势的对策均有确定的损益值，并且是有限的；每一局势的对策均有确定的损益值，并且对同一局势的两个局中人的益损值之和为零。对同一局势的
4、两个局中人的益损值之和为零。 通常将矩阵对策记为通常将矩阵对策记为: : G = S1, S2, A S1：甲的策略集；：甲的策略集； S2：乙的策略集；：乙的策略集；A：甲的赢得矩阵。甲的赢得矩阵。 “齐王赛马齐王赛马”是一个矩阵策略。是一个矩阵策略。1 1对策论的基本概念管管 理理 运运 筹筹 学学7在甲方的赢得矩阵中：在甲方的赢得矩阵中：A=aijmni 行代表甲方策略行代表甲方策略 i=1, 2, , m；j 行代表乙方策略行代表乙方策略 j=1, 2, , n；aij 代表甲方取策略代表甲方取策略 i，乙方取策略乙方取策略 j，这一局势下甲方这一局势下甲方的益损值。此时乙方的益损值为
5、的益损值。此时乙方的益损值为 - -aij（零和性质）。（零和性质）。 在考虑各方采用的策略时，必须注意一个前提，就是双在考虑各方采用的策略时，必须注意一个前提，就是双方都是理智的，即双方都是从各自可能出现的最不利的情形方都是理智的，即双方都是从各自可能出现的最不利的情形选择一种最为有利的情况作为决策的依据。选择一种最为有利的情况作为决策的依据。2 2 矩阵对策的最优纯策略矩阵对策的最优纯策略2 2矩阵对策的最优纯策略矩阵对策的最优纯策略管管 理理 运运 筹筹 学学8 例：甲乙乒乓球队进行团体对抗赛，每队由三名球员组成，双例：甲乙乒乓球队进行团体对抗赛，每队由三名球员组成，双方都可排成三种不同
6、的阵容，每一种阵容可以看作一种策略，双方方都可排成三种不同的阵容，每一种阵容可以看作一种策略，双方各选一种策略参赛。比赛共赛三局，规定每局胜者得各选一种策略参赛。比赛共赛三局，规定每局胜者得1 1分，输者得分，输者得- -1 1分，可知三赛三胜得分，可知三赛三胜得3 3分，三赛二胜得分，三赛二胜得1 1分，三赛一胜得分，三赛一胜得-1-1分，三分，三赛三负得赛三负得-3-3分。甲队的策略集为分。甲队的策略集为S S1 1= 1 1， 2 2， 3 3 ，乙队的策略集，乙队的策略集为为S S2 2= 1 1， 2 2， 3 3 。根据以往比赛的资料，有甲队的赢得矩阵为。根据以往比赛的资料，有甲队
7、的赢得矩阵为A A，如下所示，如下所示， 请问这次比赛各队采用哪种阵容上场最为稳妥请问这次比赛各队采用哪种阵容上场最为稳妥? ?2 2矩阵对策的最优纯策略矩阵对策的最优纯策略管管 理理 运运 筹筹 学学9矩阵矩阵A A中每行的最小元素分别为中每行的最小元素分别为1 1，-3-3，-1-1。 在这些最少赢得中最好的结果是在这些最少赢得中最好的结果是1 1，故甲队会采取策略，故甲队会采取策略 1 1，无论对手，无论对手采取何策略，甲队至少得采取何策略，甲队至少得1 1分。对于乙队，分。对于乙队， 1 1， 2 2， 3 3 可能带来的最少可能带来的最少赢得，即赢得，即A A中每列的最大元素，分别为
8、中每列的最大元素，分别为3 3，1 1，3 3。乙队会采取。乙队会采取 2 2策略，确保策略，确保甲队不会超过甲队不会超过1 1分。分。 1 1和和 2 2分别称为局中人甲队、乙队的最优策略。由于双方必然选择这分别称为局中人甲队、乙队的最优策略。由于双方必然选择这一种策略，所以，这种策略又称为最优纯策略。一种策略，所以，这种策略又称为最优纯策略。 这种最优纯策略只有当赢得矩阵这种最优纯策略只有当赢得矩阵A=A=（a aijij）中等式）中等式 成立时，双方才有最优纯策略，并把（成立时，双方才有最优纯策略，并把（ 1 1, , 2 2）称为对策）称为对策G G在纯策略下的在纯策略下的解，又称（解
9、，又称（ 1 1, , 2 2）为对策）为对策G G的鞍点。把其值的鞍点。把其值V V称之为对策称之为对策G=SG=S1 1，S S2 2，AA的值。的值。2 2矩阵对策的最优纯策略矩阵对策的最优纯策略管管 理理 运运 筹筹 学学10 例例 某单位采购员在秋天决定冬季取暖用煤的储量问题，已知某单位采购员在秋天决定冬季取暖用煤的储量问题，已知在正常的冬季气温条件下要消耗在正常的冬季气温条件下要消耗1515吨煤，在较暖和较冷的天气下要吨煤，在较暖和较冷的天气下要消耗消耗1010吨和吨和2020吨。假定冬天的煤价随天气寒冷程度而有所变化，在吨。假定冬天的煤价随天气寒冷程度而有所变化，在较暖和、正常、
10、较冷的气候条件下每吨煤价分别为较暖和、正常、较冷的气候条件下每吨煤价分别为1010元、元、1515元、元、2020元。又设冬季时煤炭价格为每吨元。又设冬季时煤炭价格为每吨1010元。在没有关于当年冬季准确的元。在没有关于当年冬季准确的气象预报的条件下，秋天储煤多少吨能使得单位的支出最少？气象预报的条件下，秋天储煤多少吨能使得单位的支出最少？ 解：局中人解：局中人I I为采购员，局中人为采购员，局中人IIII为大自然，采购员有三个策为大自然，采购员有三个策略，买略，买1010吨、吨、1515吨、吨、2020吨。分别记为吨。分别记为 1 1， 2 2， 3 3。大自然也有三个。大自然也有三个策略：
11、暖、正常、冷，分别记为策略：暖、正常、冷，分别记为 1 1， 2 2， 3 3。2 2矩阵对策的最优纯策略矩阵对策的最优纯策略管管 理理 运运 筹筹 学学11赢得矩阵如下：赢得矩阵如下：在此表上计算，有在此表上计算，有 得得故（故（ 3 3， 3 3）为对策）为对策G G的解，的解，V VG G=-200=-200。 1 1 2 2 3 3 1 1(10(10吨）吨）-100-175-300 2 2(15(15吨）吨）-150-150-250 3 3(20(20吨）吨）-200-200-200 1 1 2 2 3 3minmin 1 1(10(10吨）吨）-100-175-300-300 2
12、2(15(15吨）吨）-150-150-250-250 3 3(20(20吨）吨）-200-200-200-200*maxmax-100-150-200*2 2矩阵对策的最优纯策略矩阵对策的最优纯策略管管 理理 运运 筹筹 学学12 设矩阵对策设矩阵对策 G = S1, S2, A 。当当 max min aij min max aij i j j i时，不存在最优纯策略。时，不存在最优纯策略。 例：设一个赢得矩阵如下例：设一个赢得矩阵如下: : min min 5 9 5 5 9 5 A = max 6 = max 6 策略策略 2 8 6 6 8 6 6 i i max 8 9 max 8
13、 9 min 8 min 8 策略策略 1 j j3 3矩阵对策的混合策略矩阵对策的混合策略管管 理理 运运 筹筹 学学13 当甲取当甲取策略策略 2 2 ，乙取，乙取策略策略 1 1时，甲实际赢得时，甲实际赢得8比预期的多比预期的多2 2，乙，乙当然不满意。考虑到甲可能取当然不满意。考虑到甲可能取策略策略 2 2这一点，乙采取策略这一点，乙采取策略 2 2。若甲。若甲也分析到也分析到乙可能采取策略乙可能采取策略 2 2这一点，取策略这一点，取策略 1 1，则赢得更多为则赢得更多为9 9 。此时，对两个局中人甲、乙来说，没有一个双方均可接受的平衡。此时，对两个局中人甲、乙来说，没有一个双方均可
14、接受的平衡局势，其主要原因是甲和乙没有执行上述原则的共同基础，即局势，其主要原因是甲和乙没有执行上述原则的共同基础，即 max min aij min max aij 。 i j j i 一个自然的想法：对甲（乙）给出一个选取不同策略的概率分一个自然的想法：对甲（乙）给出一个选取不同策略的概率分布，以使甲（乙）在各种情况下的平均赢得（损失）最多（最少）布，以使甲（乙）在各种情况下的平均赢得（损失）最多（最少）-即混合策略。即混合策略。3 3矩阵对策的混合策略矩阵对策的混合策略管管 理理 运运 筹筹 学学14 求解求解混合策略的混合策略的问题有问题有图解法、迭代法、线性方程法和线性规图解法、迭代
15、法、线性方程法和线性规划法等，我们这里只介绍划法等，我们这里只介绍线性规划法线性规划法，其他方法略。，其他方法略。 例：设甲使用策略例：设甲使用策略 1 1的概率为的概率为X1 1，使用策略，使用策略 2 2的概率为的概率为X2 ，并设在最坏的情况下，甲赢得的平均值为，并设在最坏的情况下，甲赢得的平均值为V（未知）。（未知）。 5 9 A= STEP 1 8 6 1) 1) X1+X2=1 X1, X2 0 3 3矩阵对策的混合策略矩阵对策的混合策略管管 理理 运运 筹筹 学学152)2)无论乙取何策略，甲的平均赢得应不少于无论乙取何策略，甲的平均赢得应不少于V:V:对乙取对乙取 1 1： 5
16、X5X1 1+ 8X+ 8X2 2 V V对乙取对乙取 2 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 03 3矩阵对策的混合策略矩阵对策的混
17、合策略管管 理理 运运 筹筹 学学16建立线性模型：建立线性模型： 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=7 V=7 返回原问题：返回原问题： X X1 1= = X X1 1V= 1/3V= 1/3 X X2 2= = X X2 2V= 2/3V= 2/3于是甲的最优混合策略为：于是甲的最
18、优混合策略为：以以1/31/3的概率选的概率选 1 1， 以以2/32/3的概率选的概率选 2 2，最优值，最优值V=7V=7。3 3矩阵对策的混合策略矩阵对策的混合策略管管 理理 运运 筹筹 学学17 同样可求乙的最优混合策略：同样可求乙的最优混合策略：设乙使用策略设乙使用策略 1 1的概率为的概率为Y Y1 1 Y Y1 1+Y+Y2 2=1=1设乙使用策略设乙使用策略 2 2的概率为的概率为Y Y2 2 Y Y1 1,Y,Y2 2 0 0 设在最坏的情况下，甲赢得的平均值为设在最坏的情况下，甲赢得的平均值为V V。这也是乙损失的平均。这也是乙损失的平均值，越小越好。值，越小越好。 作变换
19、：作变换： Y Y1 1= Y= Y1 1/V /V ， Y 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=7 V=7 3 3矩阵对策的混合策略矩阵对策的混合策略管管 理理 运运 筹筹 学学18返回原问题：返回原问题： Y1= Y1V
20、 = 1/2 Y2= Y2V = 1/2于是乙的最优混合策略为：于是乙的最优混合策略为：以以 的概率选的概率选 1 1；以以 的概率选的概率选 2 2 ，最优值，最优值 V=7。 当赢得矩阵中有非正元素时，当赢得矩阵中有非正元素时，V 0 的条件不一定成立，可以的条件不一定成立，可以作下列变换：作下列变换： 选一正数选一正数 k，令矩阵中每一元素加上，令矩阵中每一元素加上 k 得到新的正得到新的正矩阵矩阵AA，其对应的矩阵对策，其对应的矩阵对策G= SG= S1 1, S, S2 2, A , A 与与 G = SG = S1 1, S, S2 2, A , A 解相同，但解相同，但VG =
21、VG k。3 3矩阵对策的混合策略矩阵对策的混合策略管管 理理 运运 筹筹 学学19例例：求解：求解“齐王赛马齐王赛马”问题。问题。已知齐王的赢得矩阵已知齐王的赢得矩阵A A求得求得故不存在纯策略问题下的解，可求其混合策略。故不存在纯策略问题下的解，可求其混合策略。A A中有负元素，可以取中有负元素，可以取k=2,k=2,在在A A的每个元素上加的每个元素上加2 2得到得到A A如下：如下：3 3矩阵对策的混合策略矩阵对策的混合策略管管 理理 运运 筹筹 学学20 建立对建立对G G=S=S1 1，S S2 2，A A 中求甲方最佳策略的线性规划如下：中求甲方最佳策略的线性规划如下： Min
22、xMin x1 1+x+x2 2+x+x3 3+x+x4 4+x+x5 5+x+x6 6 约束条件：约束条件： 5x5x1 1+3x+3x2 2+3x+3x3 3+x+x4 4+3x+3x5 5+3x+3x6 6 11 3x 3x1 1+5x+5x2 2+x+x3 3+3x+3x4 4+3x+3x5 5+3x+3x6 6 11 3x 3x1 1+3x+3x2 2+5x+5x3 3+3x+3x4 4+3x+3x5 5+x+x6 6 11 3x 3x1 1+3x+3x2 2+3x+3x3 3+5x+5x4 4+x+x5 5+3x+3x6 6 11 x x1 1+3x+3x2 2+3x+3x3 3+
23、3x+3x4 4+5x+5x5 5+3x+3x6 6 11 3x 3x1 1+x+x2 2+3x+3x3 3+3x+3x4 4+3x+3x5 5+5x+5x6 6 11 x xi i 0,i=1,2, 0,i=1,2,6,6 可解得解为：可解得解为：x x1 1=x=x4 4=x=x5 5=0, x=0, x2 2=x=x3 3=x=x6 6=0.111, v=0.111, v=3, x=3, x1 1=x=x4 4=x=x5 5= 0= 0，x x2 2=x=x3 3=x=x6 6=1/3, =1/3, 即即X X* * =(0,1/3,1/3,0,0,1/3)=(0,1/3,1/3,0,0
24、,1/3)T T，所以甲的最优策略为作出策，所以甲的最优策略为作出策略略 2 2、 3 3、 6 6的概率都为的概率都为0.333,0.333,而作出而作出 1 1、 4 4、 5 5 的概率为的概率为0 0，此时，此时V VG G=V=V=3=3。3 3矩阵对策的混合策略矩阵对策的混合策略管管 理理 运运 筹筹 学学21 同样可以建立对策同样可以建立对策G G=S=S1 1，S S2 2，A A 中求乙方最佳策略的线性规划如下：中求乙方最佳策略的线性规划如下： Min yMin y1 1+y+y2 2+y+y3 3+y+y4 4+y+y5 5+y+y6 6 约束条件：约束条件： 5y5y1
25、1+3y+3y2 2+3y+3y3 3+3y+3y4 4+y+y5 5+3y+3y6 6 11 3y 3y1 1+5y+5y2 2+3y+3y3 3+3y+3y4 4+3y+3y5 5+y+y6 6 11 3y 3y1 1+y+y2 2+5y+5y3 3+3y+3y4 4+3y+3y5 5+3y+3y6 6 11 y y1 1+3y+3y2 2+3y+3y3 3+5y+5y4 4+3y+3y5 5+3y+3y6 6 11 3y 3y1 1+3y+3y2 2+3y+3y3 3+y+y4 4+5y+5y5 5+3y+3y6 6 11 3y 3y1 1+3y+3y2 2+y+y3 3+3y+3y4
26、4+3y+3y5 5+5y+5y6 6 11 y yi i0,i=1,2,0,i=1,2,6,6 可解得解为：可解得解为： y y1 1=y=y4 4=y=y5 5=0.111, y=0.111, y2 2=y=y3 3=y=y6 6=0, v=0, v=3, y=3, y1 1=y=y4 4=y=y5 5= 1/3= 1/3， y y2 2=y=y3 3=y=y6 6=0=0，即，即Y Y* * =(1/3,0,0,1/3,1/3,0)=(1/3,0,0,1/3,1/3,0)T T。 所以田忌的最优混合策略为作出策略所以田忌的最优混合策略为作出策略 1 1、 4 4、 5 5的概率都为的概率
27、都为1/3,1/3,而作出而作出 2 2， 3 3， 6 6的概率为的概率为0 0，此时，此时V VG G=V=VG G-k=1-k=1。3 3矩阵对策的混合策略矩阵对策的混合策略管管 理理 运运 筹筹 学学22 齐王赛马问题的对策最优解可简记为齐王赛马问题的对策最优解可简记为X X* *= =(0,1/3,1/3,0,0,1/3)(0,1/3,1/3,0,0,1/3)T T，Y Y* *= =(1/3,0,0,1/3,1/3,0)(1/3,0,0,1/3,1/3,0)T T，对策值，对策值V VG G=1=1。例例 两个局中人进行对策，规则是两人互相独立的各自从两个局中人进行对策，规则是两人
28、互相独立的各自从1 1、2 2、3 3这三个这三个数字中任意选写一个数字。如果两人所写的数字之和为偶数，则局中人乙数字中任意选写一个数字。如果两人所写的数字之和为偶数，则局中人乙支付给局中人甲以数量为此和数的报酬；如果两人所写数字之和为奇数，支付给局中人甲以数量为此和数的报酬；如果两人所写数字之和为奇数，则局中人甲付给局中人乙以数量为此和数的报酬。试求出其最优策略。则局中人甲付给局中人乙以数量为此和数的报酬。试求出其最优策略。 解：首先计算局中人甲的赢得矩阵如下表：解：首先计算局中人甲的赢得矩阵如下表：4-56-34-52-34 1 1（出（出1 1） 2 2（出（出2 2） 3 3（出（出3
29、 3） 3 3（出（出3 3） 2 2（出（出2 2） 1 1（出（出1 1）甲的赢甲的赢 得得甲的策略甲的策略3 3矩阵对策的混合策略矩阵对策的混合策略乙的策略乙的策略管管 理理 运运 筹筹 学学23即甲的赢得矩阵为即甲的赢得矩阵为A A： 可知无纯策略意义的解，下面求其在混合策略下的解。可知无纯策略意义的解，下面求其在混合策略下的解。A A的各元素都加上的各元素都加上6 6，得到，得到建立线性规划模型如下：建立线性规划模型如下： Min xMin x1 1+x+x2 2+x+x3 3 Max yMax y1 1+y+y2 2+y+y3 3 S.T.8xS.T.8x1 1+3x+3x2 2+
30、10x+10x3 3 1 8y1 8y1 1+3y+3y2 2+10y+10y3 311 3x 3x1 1+10x+10x2 2+x+x3 3 1 3y1 3y1 1+10y+10y2 2+y+y3 3 11 10x 10x1 1+x+x2 2+12x+12x3 3 1 10y1 10y1 1+y+y2 2+12y+12y3 311 x x1 1,x,x2 2,x,x3 3 0 y0 y1 1,y,y2 2,y,y3 3 00 3 3矩阵对策的混合策略矩阵对策的混合策略管管 理理 运运 筹筹 学学24得到得到x x1 1=0.25, x=0.25, x2 2=0.50, x=0.50, x3
31、3=0.25=0.25；y y1 1=0.25, y=0.25, y2 2=0.50, y=0.50, y3 3=0.25=0.25。即此对策的解为即此对策的解为X X* * =(0.25,0.50,0.25)=(0.25,0.50,0.25)T T，Y Y* * =(0.25,0.50,0.25)=(0.25,0.50,0.25)T T。V VG G=V=VG G-k=0-k=0。3 3矩阵对策的混合策略矩阵对策的混合策略管管 理理 运运 筹筹 学学25例例4 4 甲乙两个企业生产同一种电子产品，甲企业可以采取的策略措施有甲乙两个企业生产同一种电子产品，甲企业可以采取的策略措施有: :(1)
32、(1)降低产品价格；降低产品价格；(2)(2)提高产品质量；提高产品质量；(3)(3)推出新产品。乙企业考虑采取推出新产品。乙企业考虑采取的策略措施有的策略措施有(1)(1)增加广告费用；增加广告费用；(2)(2)增设维修网点，加强售后服务；增设维修网点，加强售后服务；(3)(3)改进产品性能。由于甲乙两个企业财力有限，都只能采取一个措施。假定改进产品性能。由于甲乙两个企业财力有限，都只能采取一个措施。假定这两个企业所占有的市场总份额一定，由于各自采取的措施不同，通过预这两个企业所占有的市场总份额一定，由于各自采取的措施不同，通过预测今后两个企业的市场占有份额变动情况如下表，试求出这两个企业各
33、自测今后两个企业的市场占有份额变动情况如下表，试求出这两个企业各自的最优策略。的最优策略。3-58-6510108-12 1 1（措施（措施1 1） 2 2（措施（措施2 2） 3 3（措施（措施3 3） 3 3（措施（措施3 3） 2 2（措施（措施2 2） 1 1（措施（措施1 1）3 3矩阵对策的混合策略矩阵对策的混合策略甲的赢甲的赢 得得甲的策略甲的策略乙的策略乙的策略管管 理理 运运 筹筹 学学26解：解：易知此对策无纯策略意义下的解。把易知此对策无纯策略意义下的解。把A A的每一个元素加上的每一个元素加上1212，得到，得到A A建立线性规划模型如下：建立线性规划模型如下： Min
34、 xMin x1 1+x+x2 2+x+x3 3 Max yMax y1 1+y+y2 2+y+y3 3 S.T.22xS.T.22x1 1+20x+20x2 21 22y1 22y1 1+6y+6y2 2+15y+15y3 3 11 6x 6x1 1+17x+17x2 2+22x+22x3 3 1 20y1 20y1 1+17y+17y2 2+7y+7y3 3 11 15x 15x1 1+7x+7x2 2+20x+20x3 3 1 22y1 22y2 2+20y+20y3 3 11 x x1 1,x,x2 2,x,x3 30 y0 y1 1,y,y2 2,y,y3 300得到：得到：x x1
35、 1=0.027,x=0.027,x2 2=0.020,x=0.020,x3 3=0.023=0.023；y y1 1=0.0225,y=0.0225,y2 2=0.0225,y=0.0225,y3 3=0.025=0.025。V=14.29V=14.29。x x1 1=0.3858, x=0.3858, x2 2=0.2858, x=0.2858, x3 3=0.3286=0.3286；y y1 1=0.3215,y=0.3215,y2 2=0.3215,y=0.3215,y3 3=0.3572=0.3572。即此对策的解为即此对策的解为 X X* * =(0.3858,0.2858,0.3
36、286)=(0.3858,0.2858,0.3286)T T ,Y,Y* * =(0.3215,0.3215,0.3572)=(0.3215,0.3215,0.3572)T T。V VG G=V=VG G-k=2.29-k=2.29。3 3矩阵对策的混合策略矩阵对策的混合策略管管 理理 运运 筹筹 学学27优超原则：优超原则： 假设假设矩阵对策矩阵对策 G = SG = S1 1, S, S2 2, A , A 甲方赢得矩阵甲方赢得矩阵 A=aA=aijij m m n n若存在两行（列），若存在两行（列），s s 行（列）的各元素均优于行（列）的各元素均优于 t t 行（列）的元行（列）的元
37、素，即素，即a asjsj a atj tj j=1,2 j=1,2 n ( a n ( ais is a ait it i=1,2 i=1,2 m ) m )称甲方策略称甲方策略 s s优超于优超于 t t ( ( s s优超于优超于 t t) )。 优超原则优超原则：当局中人甲方的策略：当局中人甲方的策略 t t被其它策略所被其它策略所优超时，可在优超时，可在其赢得矩阵其赢得矩阵A A中划去第中划去第t t行（同理，当局中人乙方的策略行（同理，当局中人乙方的策略 t t被其它策被其它策略所略所优超时，可在矩阵优超时，可在矩阵A A中划去第中划去第t t列）。列）。 如此得到阶数较小的赢得矩
38、阵如此得到阶数较小的赢得矩阵A A，其对应的矩阵对策其对应的矩阵对策G= S1, S2, A 与与 G = S1, S2, A 等价，即解相同。等价，即解相同。3 3矩阵对策的混合策略矩阵对策的混合策略管管 理理 运运 筹筹 学学28例例. . 设设甲方的益损值，赢得矩阵为甲方的益损值，赢得矩阵为 3 2 0 3 0 被第被第3 3、4 4行所优超行所优超 5 0 2 5 9 被第被第3 3行所优超行所优超A= 7 3 9 5 9 4 6 8 7 5.5 6 0 8 8 3得到得到 7 3 9 5 9 被第被第1 1列所优超列所优超A1= 4 6 8 7 5.5 被第被第2 2列所优超列所优超
39、 6 0 8 8 33 3矩阵对策的混合策略矩阵对策的混合策略管管 理理 运运 筹筹 学学29得到得到 7 3 9 A2= 4 6 5.5 6 0 3 被第被第1 1行所优超行所优超得到得到 7 3 9 被第被第1 1列所优超列所优超 A3= 4 6 5.5 7 3最终得到最终得到 A4= 4 6 3 3矩阵对策的混合策略矩阵对策的混合策略管管 理理 运运 筹筹 学学30对对A A4 4计算，用线性规划方法得到：计算，用线性规划方法得到：（注意：余下的策略为（注意：余下的策略为 3 3， 4 4， 1 1， 2 2）甲：甲： X* = (0，0，1/15，2/15，0)T V=5 X*= (0
40、，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 。 注：注：利用优超原则化简赢得矩阵时，有可能将原对策问题的解也利用优超原则化简赢得矩阵时，有可能将原对策问题的解也划去一些（多解情况）；划去一些（多解情况）；线性规划求解时有可能是多解问题。线性规划求解时有可能是多解问题。3 3矩阵对策的混合策略矩阵对策的混合策略管管 理理 运运 筹筹 学学31 4 4其他类型的对策论简介其他类型的对策论简介 在对策论中可以根据不同方式对对策问题进行分类，通在对策论中可以根据不同方式对对策问题进行分类，通常分类的方
41、式有（常分类的方式有（1）根据局中人的个数，分为二人对策和多）根据局中人的个数，分为二人对策和多人对策；（人对策；（2）根据各局中人的赢得函数的代数和是否为零，）根据各局中人的赢得函数的代数和是否为零，可分为零和对策和非零和对策；（可分为零和对策和非零和对策；（3）根据局中人是否合作，）根据局中人是否合作，又可分为合作对策和非合作对策；（又可分为合作对策和非合作对策；（4）根据局中人的策略集）根据局中人的策略集中个数，又分为有限对策和无限对策（或连续对策）；（中个数，又分为有限对策和无限对策（或连续对策）；（5）也可根据局中人掌握信息的情况及决策选择是否和时间有关也可根据局中人掌握信息的情况及
42、决策选择是否和时间有关可分为完全信息静态对策、完全信息动态对策、非完全信息可分为完全信息静态对策、完全信息动态对策、非完全信息静态对策及非完全信息动态对策；也可以根据对策模型的数静态对策及非完全信息动态对策；也可以根据对策模型的数字特征又分为矩阵对策、连续对策、微分对策、阵地对策、字特征又分为矩阵对策、连续对策、微分对策、阵地对策、凸对策、随机对策。凸对策、随机对策。 本节只对对策论中非合作对策的完全信息对策、多人非本节只对对策论中非合作对策的完全信息对策、多人非合作对策、非零和对策作一个简单的叙述性介绍。合作对策、非零和对策作一个简单的叙述性介绍。管管 理理 运运 筹筹 学学32 4 4其他
43、类型的对策论简介其他类型的对策论简介一、完全信息静态对策一、完全信息静态对策 该对策是指掌握了参与人的特征、战略空间、支付函数等知识和信息该对策是指掌握了参与人的特征、战略空间、支付函数等知识和信息并且参与人同时选择行动方案或虽非同时但后行动者并不知道前行动者采并且参与人同时选择行动方案或虽非同时但后行动者并不知道前行动者采取了什么行动方案。取了什么行动方案。 纳什均衡是一个重要概念。在一个战略组合中，给定其他参与者战略纳什均衡是一个重要概念。在一个战略组合中，给定其他参与者战略的情况下，任何参与者都不愿意脱离这个组合，或者说打破这个僵局，这的情况下，任何参与者都不愿意脱离这个组合，或者说打破
44、这个僵局，这种均衡就称为种均衡就称为纳什均衡纳什均衡。下面以著名的。下面以著名的“囚徒困境囚徒困境”来进一步阐述。来进一步阐述。 例例1 “1 “囚徒困境囚徒困境”说的是两个囚犯的故事。这两个囚徒一起做坏事，结果被说的是两个囚犯的故事。这两个囚徒一起做坏事，结果被警察发现抓了起来，分别关在两个独立的不能互通信息的牢房里进行审讯。在这警察发现抓了起来，分别关在两个独立的不能互通信息的牢房里进行审讯。在这种情形下，两个囚犯都可以做出自己的选择：或者坦白（即与警察合作，从而背种情形下，两个囚犯都可以做出自己的选择：或者坦白（即与警察合作，从而背叛他的同伙），或者抵赖（也就是与他的同伙合作，而不是与警
45、察合作）。这两叛他的同伙），或者抵赖（也就是与他的同伙合作，而不是与警察合作）。这两个囚犯都知道，如果他俩都能抵赖的话，就都会被释放，因为只要他们拒不承认，个囚犯都知道，如果他俩都能抵赖的话，就都会被释放，因为只要他们拒不承认，警方无法给他们定罪。但警方也明白这一点，所以他们就给了这两个囚犯一点儿警方无法给他们定罪。但警方也明白这一点，所以他们就给了这两个囚犯一点儿刺激：如果他们中的一个人坦白，即告发他的同伙，那么他就可以被无罪释放。刺激：如果他们中的一个人坦白，即告发他的同伙，那么他就可以被无罪释放。而他的同伙就会被按照最重的罪来判决。当然，如果这两个囚犯都坦白，两个人而他的同伙就会被按照最
46、重的罪来判决。当然，如果这两个囚犯都坦白，两个人都会被按照轻罪来判决。如图都会被按照轻罪来判决。如图1-11-1所示。所示。管管 理理 运运 筹筹 学学33 4 4其他类型的对策论简介其他类型的对策论简介坦白坦白抵赖抵赖轻罪，轻罪轻罪，轻罪重罪，无罪重罪，无罪重罪，无罪重罪，无罪释放，释放释放，释放坦白坦白抵赖抵赖图图1-1 1-1 囚徒困境囚徒困境 由分析可知，上例中每个囚犯都会选择坦白，因此这个战略组合由分析可知，上例中每个囚犯都会选择坦白，因此这个战略组合是固定的，是固定的，( (坦白，坦白坦白，坦白) )就是纳什均衡解。而这个均衡是不会被打破的，就是纳什均衡解。而这个均衡是不会被打破的
47、，即使他们在坐牢之前达成协议。即使他们在坐牢之前达成协议。 囚徒困境反映了个人理性和集体理性的矛盾。对于双方，（抵赖，囚徒困境反映了个人理性和集体理性的矛盾。对于双方，（抵赖，抵赖）的结果是最好的，但因为每个囚徒都是理性人，他们追求自身效抵赖）的结果是最好的，但因为每个囚徒都是理性人，他们追求自身效应的最大化，结果就变成了（坦白，坦白）。个人理性导致了集体不理应的最大化，结果就变成了（坦白，坦白）。个人理性导致了集体不理性。性。管管 理理 运运 筹筹 学学34 4 4其他类型的对策论简介其他类型的对策论简介二、完全信息动态对策二、完全信息动态对策 在完全信息静态对策中，假设各方都同时选择行动。
48、现在情况稍复杂在完全信息静态对策中，假设各方都同时选择行动。现在情况稍复杂一些。如果各方行动存在先后顺序，后行的一方会参考先行者的策略而采一些。如果各方行动存在先后顺序，后行的一方会参考先行者的策略而采取行动，而先行者也会知道后行者会根据他的行动采取何种行动，因此先取行动，而先行者也会知道后行者会根据他的行动采取何种行动，因此先行者会考虑自己行动会对后行者的影响后选择行动。这类问题称为完全信行者会考虑自己行动会对后行者的影响后选择行动。这类问题称为完全信息动态对策问题。息动态对策问题。 例例2 2 某行业中只有一个垄断企业某行业中只有一个垄断企业A A，有一个潜在进入者，有一个潜在进入者企业企
49、业B B。B B可以选可以选择进入或不进入该行业这两种行动，而择进入或不进入该行业这两种行动，而A A当当B B进入时，可以选择默认或者报复两种进入时，可以选择默认或者报复两种行动。如果行动。如果B B进入后进入后A A企业报复，将造成两败俱伤的结果，但如果企业报复，将造成两败俱伤的结果，但如果A A默认默认B B进入，必进入，必然对然对A A的收益造成损失。同样的，如果的收益造成损失。同样的，如果B B进入而进入而A A报复，则报复，则B B受损，反之，将受益。受损，反之，将受益。把此关系用图把此关系用图1-21-2表示。表示。默许默许报复报复50,10050,100-20,0-20,00,
50、2000,2000,2000,200进入进入不进入不进入图图1-2 A1-2 A、B B的行动及结果的行动及结果A AB B管管 理理 运运 筹筹 学学35 4 4其他类型的对策论简介其他类型的对策论简介 由分析可知，上例中（由分析可知，上例中（B B选择不进入，选择不进入，A A选择报复）和（选择报复）和（B B选择进入，选择进入，A A选择默许）都是纳什均衡解。但在实际中，（选择默许）都是纳什均衡解。但在实际中，（B B选择不进入，选择不进入，A A选择报复）这种情况是不可能出现的。因为选择报复）这种情况是不可能出现的。因为B B知道他如果进入，知道他如果进入，A A只能默许，所以只有（只
51、能默许，所以只有（B B选择进入，选择进入，A A选择选择默许）会发生。或者说，默许）会发生。或者说，A A选择报复行动是不可置信的威胁。选择报复行动是不可置信的威胁。对策论的术语中，称（对策论的术语中，称（A A选择默许，选择默许，B B选择进入）为精炼纳什选择进入）为精炼纳什均衡。当只当参与人的战略在每一个子对策中都构成纳什均均衡。当只当参与人的战略在每一个子对策中都构成纳什均衡，这个纳什均衡才称为衡，这个纳什均衡才称为精炼纳什均衡精炼纳什均衡。 当然，如果当然，如果A A下定决心一定要报复下定决心一定要报复B B，即使自己暂时损失。，即使自己暂时损失。这时威胁就变成了可置信的，这时威胁就
52、变成了可置信的，B B就会选择不进入，（就会选择不进入，（B B选择不选择不进入，进入，A A选择报复）就成为精炼纳什均衡。选择报复）就成为精炼纳什均衡。 军事交战时，军事交战时，“破釜沉舟破釜沉舟”讲的就是一种可置信威胁。讲的就是一种可置信威胁。实际企业经营中也有很多类似的例子。实际企业经营中也有很多类似的例子。 管管 理理 运运 筹筹 学学36 4 4其他类型的对策论简介其他类型的对策论简介三、多人非合作对策三、多人非合作对策 有三个或三个以上对策方参加的对策就是有三个或三个以上对策方参加的对策就是“多人对策多人对策” ” 。多人对策。多人对策同样也是对策方在意识到其他对策方的存在，意识到
53、其他对策方对自己决同样也是对策方在意识到其他对策方的存在，意识到其他对策方对自己决策的反应和反作用存在的情况下寻求自身最大利益的决策活动。因而，它策的反应和反作用存在的情况下寻求自身最大利益的决策活动。因而，它们的基本性质和特征与两人对策是相似的，我们常常可以用研究两人对策们的基本性质和特征与两人对策是相似的，我们常常可以用研究两人对策同样的思路和方法来研究它们，或将两人对策的结论推广到多人对策。不同样的思路和方法来研究它们，或将两人对策的结论推广到多人对策。不过，毕竟多人对策中出现了更多的追求各自利益的独立决策者，因此，策过，毕竟多人对策中出现了更多的追求各自利益的独立决策者，因此，策略的相
54、互依存关系也就更为复杂，对任一对策方的决策引起的反应也就要略的相互依存关系也就更为复杂，对任一对策方的决策引起的反应也就要比两人对策复杂得多。并且，在多人对策中还有一个与两人对策有本质区比两人对策复杂得多。并且，在多人对策中还有一个与两人对策有本质区别的特点，即可能存在别的特点，即可能存在“破坏者破坏者”。所谓破坏者即一个对策中具有下列特。所谓破坏者即一个对策中具有下列特征的对策方：其策略选择对自身的得益没有任何影响，但却会影响其它对征的对策方：其策略选择对自身的得益没有任何影响，但却会影响其它对策方的得益，有时这种影响甚至有决定性的作用。例如有三个城市争夺某策方的得益，有时这种影响甚至有决定
55、性的作用。例如有三个城市争夺某届奥运会的主办权。届奥运会的主办权。管管 理理 运运 筹筹 学学37 4 4其他类型的对策论简介其他类型的对策论简介 多人对策可以分为合作的和非合作的。非合作对策顾名多人对策可以分为合作的和非合作的。非合作对策顾名思义，就是局中人之间不存在合作，即各局中人在采取行动思义，就是局中人之间不存在合作，即各局中人在采取行动之前，没有事前的交流和约定，在其行为发生相互作用时，之前，没有事前的交流和约定，在其行为发生相互作用时，也不会达成任何有约束力的协议。每个局中人都选择于已最也不会达成任何有约束力的协议。每个局中人都选择于已最有利的策略以使效用水平最大化。然而，在非合作
56、对策中，有利的策略以使效用水平最大化。然而，在非合作对策中，双方的利益也并非是完全冲突的，即对一个局中人有利的局双方的利益也并非是完全冲突的，即对一个局中人有利的局势并不一定对其他局中人一定不利，故多人非合作对策不一势并不一定对其他局中人一定不利，故多人非合作对策不一定是零和对策。定是零和对策。 如同矩阵对策中纯策略意义下的解有时不存在一样，有如同矩阵对策中纯策略意义下的解有时不存在一样，有些非合作对策也不存在纯策略纳什均衡。在这种情况下，局些非合作对策也不存在纯策略纳什均衡。在这种情况下，局中人就必须考虑混合策略。中人就必须考虑混合策略。管管 理理 运运 筹筹 学学38 4 4其他类型的对策
57、论简介其他类型的对策论简介四、非零和对策四、非零和对策 所谓零和对策，就是一方的收益必定是另一方的损失。这种对策的特所谓零和对策，就是一方的收益必定是另一方的损失。这种对策的特点是不管各对策方如何决策，最后各对策方得益之和总是为零。有某些对点是不管各对策方如何决策，最后各对策方得益之和总是为零。有某些对策中，每种结果之下各对策方的得益之和不等于策中，每种结果之下各对策方的得益之和不等于0 0，但总是等于一个非零，但总是等于一个非零常数，就称之为常数，就称之为“常和对策常和对策”。当然，可以将零和对策本身看作是常和对。当然，可以将零和对策本身看作是常和对策的特例。策的特例。 “ “零和对策零和对
58、策”和和“常和对策常和对策”之外的所有对策都可被称为之外的所有对策都可被称为“非零和对非零和对策策”。非零和对策即意味着在不同策略组合（结果）下各对策方的得益之。非零和对策即意味着在不同策略组合（结果）下各对策方的得益之和一般是不相同的。如前述囚徒困境就是典型的非零和对策。应该说，非和一般是不相同的。如前述囚徒困境就是典型的非零和对策。应该说，非零和对策是最一般的对策类型，而常和对策和零和对策都是它的特例。在零和对策是最一般的对策类型，而常和对策和零和对策都是它的特例。在非零和对策中，存在着总得益较大的策略组合和总得益较小的策略组合之非零和对策中，存在着总得益较大的策略组合和总得益较小的策略组
59、合之间的区别，这也就意味着在对策方之间存在着互相配合，争取较大的总得间的区别，这也就意味着在对策方之间存在着互相配合，争取较大的总得益和个人得益的可能性。益和个人得益的可能性。 两人零和对策是完全对抗性的，总得益为两人零和对策是完全对抗性的，总得益为0 0，其解法可能性根据矩阵，其解法可能性根据矩阵对策予以求解，但在非零和对策下，矩阵对策求解法已经不适用了，下面对策予以求解，但在非零和对策下，矩阵对策求解法已经不适用了，下面用例子予以说明。用例子予以说明。 管管 理理 运运 筹筹 学学39 4 4其他类型的对策论简介其他类型的对策论简介 例例3 3 甲乙两公司生产同一产品，均想以登广告扩大产品
60、销售，每家甲乙两公司生产同一产品，均想以登广告扩大产品销售，每家公司都有公司都有“登登”与与“不登不登”两种策略，双方的得益矩阵如下。两种策略，双方的得益矩阵如下。 登登不登不登3,23,29,-39,-3-2,8-2,86,56,5登登不登不登图图1-3 1-3 甲乙两家公司行动及结果甲乙两家公司行动及结果乙乙甲甲 我们根据得益矩阵来分析。从甲公司立场上看，登有利，不管乙公我们根据得益矩阵来分析。从甲公司立场上看，登有利，不管乙公司如何，保证赢利至少是司如何，保证赢利至少是3 3，最多是，最多是9 9。如果不登，可能要蒙受损失。如果不登，可能要蒙受损失2 2。从。从乙公司的立场上看，同样理由
61、，还是登广告好。但是，这是从理智行为乙公司的立场上看，同样理由，还是登广告好。但是，这是从理智行为出发的策略，是以彼此不能合作为前提的。上述两公司均采取登广告的出发的策略，是以彼此不能合作为前提的。上述两公司均采取登广告的策略是稳定的结局。可是，如果彼此能够合作，而都不登广告，免去了策略是稳定的结局。可是，如果彼此能够合作，而都不登广告，免去了广告费，反而各自的赢利要多。在彼此不能合作的情况下，如果甲不登，广告费，反而各自的赢利要多。在彼此不能合作的情况下，如果甲不登，恰好乙登，甲只好出现败局，这是非理智的策略，带有危险性。因此，恰好乙登，甲只好出现败局，这是非理智的策略，带有危险性。因此，非零和对策常常不易获得最理想的答案。对于三个以上的多人零和对策，非零和对策常常不易获得最理想的答案。对于三个以上的多人零和对策，互相利害关系更加复杂。互相利害关系更加复杂。
