第15章 对策论ppt课件.ppt
《第15章 对策论ppt课件.ppt》由会员分享,可在线阅读,更多相关《第15章 对策论ppt课件.ppt(43页珍藏版)》请在三一办公上搜索。
1、经济与管理学院 何宜军,第15章 对策论,管理运筹学,第一节 对策论的基本概念 第二节 矩阵对策的最优纯策略 第三节 矩阵对策的混合策略 第四节 其他类型的对策论简介,提纲,齐王赛马,齐王与大将田忌商议赛马,双方约定:各自出上、中、下三种等级的马各一匹。每轮举行三场对抗赛。输者每输一场要付给胜者黄金一千两。由于田忌的马比齐王同等级的马都要略逊一筹,而在头一轮的比赛中,双方都是用同等级的马进行对抗,所以齐王很快赢了全部三场,得到了三千两黄金。鉴于第一次赛马的惨败,所以当齐王满面春风地再次邀请田忌赛马时,田忌感到很为难。一方面君王旨意不好违背,另一方面自己对这种必败的比赛失去了信心。田忌的军师孙膑
2、是颇有才能的军事家,他得知后,便替田忌出了一个主意:用自己的下等马和国王的上等马比赛,而用自己的上等马和国王的中等马比赛,中等马和国王的下等马比赛。比赛开始,第一场国王的马以极大的优势取得了胜利。国王没有料到田忌的马竟然如此不堪一击,为此俯仰大笑,得意不已。但美景不长,在二、三场中田忌的马都取得了胜利。这一轮国王不但没赢,反而输了一千金。可笑的是,齐王输了钱还弄不清自己是怎样输的呢!,1 对策论的基本概念,对策模型的三个基本要素:1.局中人:参与对抗的各方;2.策略集:局中人选择对付其它局中人的行动方案称为策略;某局中人的所有可能策略全体称为策略集;3.一局势对策的益损值:局中人各自使用一个对
3、策就形成了一个局势,一个局势决定了各局中人的对策结果(量化)称为该局势对策的益损值。,“齐王赛马”齐王在各局势中的益损值表(单位:千金),1 对策论的基本概念,其中:齐王的策略集:S1=1,2,3,4,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 对策论的基本概念,二人有限零和对策(又称矩阵对策):局中人为2;每个局中人的策略集的策略数目都是有限的;每一局势的对策均有确定的损益值,并且对同一局
4、势的两个局中人的益损值之和为零。通常将矩阵对策记为:G=S1,S2,A S1:甲的策略集;S2:乙的策略集;A:甲的赢得矩阵。“齐王赛马”是一个二人有限零和矩阵对策。,1 对策论的基本概念,在甲方的赢得矩阵中:A=aijmni 行代表甲方策略 i=1,2,m;j 行代表乙方策略 j=1,2,n;aij 代表甲方取策略 i,乙方取策略 j,这一局势下甲方的益损值。此时乙方的益损值为-aij(零和性质)。在考虑各方采用的策略时,必须注意一个前提,就是双方都是理智的,即双方都是从各自可能出现的最不利的情形选择一种最为有利的情况作为决策的依据。,2 矩阵对策的最优纯策略,例:甲乙乒乓球队进行团体对抗赛
5、,每队由三名球员组成,双方都可排成三种不同的阵容,每一种阵容可以看作一种策略,双方各选一种策略参赛。比赛共赛三局,规定每局胜者得1分,输者得-1分,可知三赛三胜得3分,三赛二胜得1分,三赛一胜得-1分,三赛三负得-3分。甲队的策略集为S1=1,2,3,乙队的策略集为S2=1,2,3。根据以往比赛的资料,有甲队的赢得矩阵为A,如下所示,请问这次比赛各队采用哪种阵容上场最为稳妥?,2 矩阵对策的最优纯策略,矩阵A中每行的最小元素分别为1,-3,-1。在这些最少赢得中最好的结果是1,故甲队会采取策略1,无论对手采取何策略,甲队至少得1分。对于乙队,1,2,3可能带来的最少赢得,即A中每列的最大元素,
6、分别为3,1,3。乙队会采取2策略,确保甲队不会超过最坏的结果1分。1和2分别称为局中人甲队、乙队的最优策略。由于双方必然选择这一种策略,所以,这种策略又称为最优纯策略。这种最优纯策略只有当赢得矩阵A=(aij)中等式 成立时,双方才有最优纯策略,并把(1,2)称为对策G在纯策略下的解,又称(1,2)为对策G的鞍点。把其值V称之为对策G=S1,S2,A的值。,2 矩阵对策的最优纯策略,例2 某单位采购员在秋天决定冬季取暖用煤的储量问题,已知在正常的冬季气温条件下要消耗15吨煤,在较暖和较冷的天气下要消耗10吨和20吨。假定冬天的煤价随天气寒冷程度而有所变化,在较暖和、正常、较冷的气候条件下每吨
7、煤价分别为10元、15元、20元。又设冬季时煤炭价格为每吨10元。在没有关于当年冬季准确的气象预报的条件下,秋天储煤多少吨能使得单位的支出最少?解:局中人I为采购员,局中人II为大自然,采购员有三个策略,买10吨、15吨、20吨。分别记为1,2,3。大自然也有三个策略:暖、正常、冷,分别记为1,2,3。,2 矩阵对策的最优纯策略,赢得矩阵如下:在此表上计算,有 得故(3,3)为对策G的解,VG=-200。,2 矩阵对策的最优纯策略,设矩阵对策 G=S1,S2,A。当 时,不存在最优纯策略。例:设一个赢得矩阵如下:min 5 9 5 A=8 6 6 max 8 9,3 矩阵对策的混合策略,当甲取
8、策略2,乙取策略1时,甲实际赢得8比预期的多2,乙当然不满意。考虑到甲可能取策略2这一点,乙采取策略2。若甲也分析到乙可能采取策略2这一点,取策略1,则赢得更多为9。此时,对两个局中人甲、乙来说,没有一个双方均可接受的平衡局势,其主要原因是甲和乙没有执行上述原则的共同基础,即 max min aij min max aij。i j j i 一个自然的想法:对甲(乙)给出一个选取不同策略的概率分布,以使甲(乙)在各种情况下的平均赢得(损失)最多(最少)-即混合策略。,3 矩阵对策的混合策略,求解混合策略的问题有图解法、迭代法、线性方程法和线性规划法等,我们这里只介绍线性规划法,其他方法略。例:设
9、甲使用策略1的概率为X1,使用策略2的概率为X2,并设在最坏的情况下,甲赢得的平均值为V(未知)。5 9 A=STEP 1 8 6 1)X1+X2=1 X1,X20,3 矩阵对策的混合策略,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 矩阵对策的混合策略,建立甲的线性模型:min X1+X2 s.t.5X1+8X21 X1=1/21 9X1+6X21
10、 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 矩阵对策的混合策略,同样可求乙的最优混合策略:设乙使用策略1的概率为Y1 Y1+Y2=1设乙使用策略2的概率为Y2 Y1,Y20 设在最坏的情况下,甲赢得的平均值为V。这也是乙损失的平均值,越小越好。作变换:Y1=Y1/V,Y2=Y2/V 建立乙的线性模型:max Y1+Y2 s.t.5Y1+9Y21 Y1=1/14 8Y1+6Y21 Y2=1/14 Y1,Y20 1/V=Y1+Y2=
11、1/7 所以,V=7,3 矩阵对策的混合策略,返回原问题: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 矩阵对策的混合策略,例:求解“齐王赛马”问题。已知齐王的赢得矩阵A求得故不存在纯策略问题下的解,可求其混合策略。A中有负元素,可以取k=2,在A的每个元素上加2得到A如下:,3 矩阵对策的混合策略,建立对G=S1
12、,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+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,所以甲的
13、最优策略为作出策略2、3、6的概率都为0.333,而作出1、4、5 的概率为0,此时VG=V=3。,3 矩阵对策的混合策略,同样可以建立对策G=S1,S2,A中求乙方最佳策略的线性规划如下:Max y1+y2+y3+y4+y5+y6 约束条件:5y1+3y2+3y3+3y4+y5+3y6 1 3y1+5y2+3y3+3y4+3y5+y6 1 3y1+y2+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
14、.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 矩阵对策的混合策略,齐王赛马问题的对策最优解可简记为X*=(0,1/3,1/3,0,0,1/3)T,Y*=(1/3,0,0,1/3,1/3,0)T,对策值VG=1。例3 两个局中人进行对策,规则是两人互相独立的各自从1、2、3这三个数字中任意选写一个数字。如果两人所写的数字之和为偶数,则局中人乙支付给局中人甲以数量为此和数的报酬;如果两人所写
15、数字之和为奇数,则局中人甲付给局中人乙以数量为此和数的报酬。试求出其最优策略。解:首先计算局中人甲的赢得矩阵如下表:,4-56,-34-5,2-34,1(出1)2(出2)3(出3),3(出3),2(出2),1(出1),甲的赢 得甲的策略,乙的策略,3 矩阵对策的混合策略,即甲的赢得矩阵为A:可知无纯策略意义的解,下面求其在混合策略下的解。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 10
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第15章 对策论ppt课件 15 策论 ppt 课件
链接地址:https://www.31ppt.com/p-2132950.html