《大学运筹学经典课件第十五章――对策论》由会员分享，可在线阅读，更多相关《大学运筹学经典课件第十五章――对策论（39页珍藏版）》请在金锄头文库上搜索。
1、1,第十五章 对策论 1 对策论的基本概念 2 矩阵对策的最优纯策略 3 矩阵对策的混合策略 4 其他类型的对策论简介,2,第十五章 对策论 由“齐王赛马”引入,3,1对策论的基本概念,对策模型的三个基本要素： 1.局中人：参与对抗的各方； 2.策略集：局中人选择对付其它局中人的行动方案称为策略；某局中人的所有可能策略全体称为策略集； 3.一局势对策的益损值：局中人各自使用一个对策就形成了一个局势，一个局势决定了各局中人的对策结果（量化）称为该局势对策的益损值。,4,“齐王赛马”齐王在各局势中的益损值表（单位：千金）,1对策论的基本概念,5,其中：齐王的策略集: S1= 1, 2, 3, 4,
2、 5, 6 ， 田忌的策略集：S2= 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对策论的基本概念,6,二人有限零和对策（又称矩阵对策）： 局中人为2；每个局中人的策略集的策略数目都是有限的；每一局势的对策均有确定的损益值，并且对同一局势的两个局中人的益损值之和为零。 通常将矩阵对策记为: G = S1, S2, A S1：甲的策略集； S2：乙的策略集； A：甲的赢得矩阵。 “齐王赛马”是一个矩阵策略。,1对
3、策论的基本概念,7,在甲方的赢得矩阵中： A=aijmn i 行代表甲方策略 i=1, 2, , m；j 行代表乙方策略 j=1, 2, , n；aij 代表甲方取策略 i，乙方取策略 j，这一局势下甲方的益损值。此时乙方的益损值为 -aij（零和性质）。 在考虑各方采用的策略时，必须注意一个前提，就是双方都是理智的，即双方都是从各自可能出现的最不利的情形选择一种最为有利的情况作为决策的依据。,2 矩阵对策的最优纯策略,2矩阵对策的最优纯策略,8,例：甲乙乒乓球队进行团体对抗赛，每队由三名球员组成，双方都可排成三种不同的阵容，每一种阵容可以看作一种策略，双方各选一种策略参赛。比赛共赛三局，规定
4、每局胜者得1分，输者得-1分，可知三赛三胜得3分，三赛二胜得1分，三赛一胜得-1分，三赛三负得-3分。甲队的策略集为S1=1，2，3，乙队的策略集为S2=1，2，3。根据以往比赛的资料，有甲队的赢得矩阵为A，如下所示， 请问这次比赛各队采用哪种阵容上场最为稳妥?,2矩阵对策的最优纯策略,9,矩阵A中每行的最小元素分别为1，-3，-1。 在这些最少赢得中最好的结果是1，故甲队会采取策略1，无论对手采取何策略，甲队至少得1分。对于乙队，1，2，3可能带来的最少赢得，即A中每列的最大元素，分别为3，1，3。乙队会采取2策略，确保甲队不会超过1分。 1和2分别称为局中人甲队、乙队的最优策略。由于双方必
5、然选择这一种策略，所以，这种策略又称为最优纯策略。 这种最优纯策略只有当赢得矩阵A=（aij）中等式 成立时，双方才有最优纯策略，并把（1,2）称为对策G在纯策略下的解，又称（1,2）为对策G的鞍点。把其值V称之为对策G=S1，S2，A的值。,2矩阵对策的最优纯策略,10,例 某单位采购员在秋天决定冬季取暖用煤的储量问题，已知在正常的冬季气温条件下要消耗15吨煤，在较暖和较冷的天气下要消耗10吨和20吨。假定冬天的煤价随天气寒冷程度而有所变化，在较暖和、正常、较冷的气候条件下每吨煤价分别为10元、15元、20元。又设冬季时煤炭价格为每吨10元。在没有关于当年冬季准确的气象预报的条件下，秋天储煤
6、多少吨能使得单位的支出最少？ 解：局中人I为采购员，局中人II为大自然，采购员有三个策略，买10吨、15吨、20吨。分别记为1，2，3。大自然也有三个策略：暖、正常、冷，分别记为1，2，3。,2矩阵对策的最优纯策略,11,赢得矩阵如下： 在此表上计算，有 得 故（3，3）为对策G的解，VG=-200。,2矩阵对策的最优纯策略,12,设矩阵对策 G = S1, S2, A 。当 max min aij min max aij i j j i 时，不存在最优纯策略。 例：设一个赢得矩阵如下: min 5 9 5 A = max 6 策略2 8 6 6 i max 8 9 min 8 策略1 j,3
7、矩阵对策的混合策略,13,当甲取策略2 ，乙取策略1时，甲实际赢得8比预期的多2，乙当然不满意。考虑到甲可能取策略2这一点，乙采取策略2。若甲也分析到乙可能采取策略2这一点，取策略1，则赢得更多为9 。此时，对两个局中人甲、乙来说，没有一个双方均可接受的平衡局势，其主要原因是甲和乙没有执行上述原则的共同基础，即 max min aij min max aij 。 i j j i 一个自然的想法：对甲（乙）给出一个选取不同策略的概率分布，以使甲（乙）在各种情况下的平均赢得（损失）最多（最少）-即混合策略。,3矩阵对策的混合策略,14,求解混合策略的问题有图解法、迭代法、线性方程法和线性规划法等，
8、我们这里只介绍线性规划法，其他方法略。 例：设甲使用策略1的概率为X1，使用策略2的概率为X2 ，并设在最坏的情况下，甲赢得的平均值为V（未知）。 5 9 A= STEP 1 8 6 1) X1+X2=1 X1, X20,3矩阵对策的混合策略,15,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+ 8X21 9X1+ 6X21 X1, X20,3矩阵对策的混合策略
9、,16,建立线性模型： min X1+X2 s.t. 5X1+8X21 X1= 1/21 9X1+6X21 X2= 2/21 X1, X20 1/V= X1+X2=1/7 所以，V=7 返回原问题： X1= X1V= 1/3 X2= X2V= 2/3 于是甲的最优混合策略为： 以1/3的概率选1， 以2/3的概率选2，最优值V=7。,3矩阵对策的混合策略,17,同样可求乙的最优混合策略： 设乙使用策略1的概率为Y1 Y1+Y2=1 设乙使用策略2的概率为Y2 Y1,Y20 设在最坏的情况下，甲赢得的平均值为V。这也是乙损失的平均值，越小越好。 作变换： Y1= Y1/V ， Y2= Y2/V
10、建立线性模型： max Y1+Y2 s.t. 5Y1+9Y21 Y1= 1/14 8Y1+6Y21 Y2= 1/14 Y1, Y20 1/V= Y1+Y2=1/7 所以，V=7,3矩阵对策的混合策略,18,返回原问题： Y1= Y1V = 1/2 Y2= Y2V = 1/2 于是乙的最优混合策略为： 以 的概率选1；以 的概率选2 ，最优值 V=7。 当赢得矩阵中有非正元素时，V0 的条件不一定成立，可以作下列变换： 选一正数 k，令矩阵中每一元素加上 k 得到新的正矩阵A，其对应的矩阵对策 G= S1, S2, A 与 G = S1, S2, A 解相同，但VG = VG k。,3矩阵对策的
11、混合策略,19,例：求解“齐王赛马”问题。 已知齐王的赢得矩阵A 求得 故不存在纯策略问题下的解，可求其混合策略。 A中有负元素，可以取k=2,在A的每个元素上加2得到A如下：,3矩阵对策的混合策略,20,建立对G=S1，S2，A中求甲方最佳策略的线性规划如下： Min x1+x2+x3+x4+x5+x6 约束条件： 5x1+3x2+3x3+x4+3x5+3x6 1 3x1+5x2+x3+3x4+3x5+3x6 1 3x1+3x2+5x3+3x4+3x5+x6 1 3x1+3x2+3x3+5x4+x5+3x6 1 x1+3x2+3x3+3x4+5x5+3x6 1 3x1+x2+3x3+3x4+
12、3x5+5x6 1 xi 0,i=1,2,6 可解得解为：x1=x4=x5=0, x2=x3=x6=0.111, v=3, x1=x4=x5= 0， x2=x3=x6=1/3, 即X* =(0,1/3,1/3,0,0,1/3)T，所以甲的最优策略为作出策略2、3、6的概率都为0.333,而作出1、4、5 的概率为0，此时VG=V=3。,3矩阵对策的混合策略,21,同样可以建立对策G=S1，S2，A中求乙方最佳策略的线性规划如下： Min y1+y2+y3+y4+y5+y6 约束条件： 5y1+3y2+3y3+3y4+y5+3y6 1 3y1+5y2+3y3+3y4+3y5+y6 1 3y1+y
13、2+5y3+3y4+3y5+3y6 1 y1+3y2+3y3+5y4+3y5+3y6 1 3y1+3y2+3y3+y4+5y5+3y6 1 3y1+3y2+y3+3y4+3y5+5y6 1 yi0,i=1,2,6 可解得解为： y1=y4=y5=0.111, y2=y3=y6=0, v=3, y1=y4=y5= 1/3， y2=y3=y6=0，即Y* =(1/3,0,0,1/3,1/3,0)T。 所以田忌的最优混合策略为作出策略1、4、5的概率都为1/3,而作出2，3，6的概率为0，此时VG=VG-k=1。,3矩阵对策的混合策略,22,齐王赛马问题的对策最优解可简记为X*=(0,1/3,1/3
14、,0,0,1/3)T， Y*=(1/3,0,0,1/3,1/3,0)T，对策值VG=1。 例 两个局中人进行对策，规则是两人互相独立的各自从1、2、3这三个数字中任意选写一个数字。如果两人所写的数字之和为偶数，则局中人乙支付给局中人甲以数量为此和数的报酬；如果两人所写数字之和为奇数，则局中人甲付给局中人乙以数量为此和数的报酬。试求出其最优策略。 解：首先计算局中人甲的赢得矩阵如下表：,4 -5 6,-3 4 -5,2 -3 4,1（出1） 2（出2） 3（出3）,3（出3）,2（出2）,1（出1）,甲的赢 得 甲的策略,3矩阵对策的混合策略,乙的策略,23,即甲的赢得矩阵为A： 可知无纯策略意
15、义的解，下面求其在混合策略下的解。 A的各元素都加上6，得到 建立线性规划模型如下： Min x1+x2+x3 Max y1+y2+y3 S.T.8x1+3x2+10 x3 1 8y1+3y2+10y31 3x1+10 x2+x3 1 3y1+10y2+y3 1 10 x1+x2+12x3 1 10y1+y2+12y31 x1,x2,x3 0 y1,y2,y3 0,3矩阵对策的混合策略,24,得到 x1=0.25, x2=0.50, x3=0.25； y1=0.25, y2=0.50, y3=0.25。 即此对策的解为 X* =(0.25,0.50,0.25)T， Y* =(0.25,0.50,0.25)T。 VG=VG-k=0。,3矩阵对策的混合策略,25,例4 甲乙两个企业生产同一种电子产品，甲企业可以采取的策略措施有:(1)降低产品价格；(2)提高产品质量；(3)推出新产品。乙企业考虑采取的策略措施有(1)增加广告费用；(2)增设维修网点，加强售后服务；(3)改进产品性能。由于甲乙两个企业财力有限，都只能采取一个措施。假定这两个企业所占有的市场总份额一定，由于各自采取的措施不同，通过预测今后两个企业的市场占有份额变动情况如下表，试
