决策问题2.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,玩扑克牌，比大小,两组扑克牌，分别是,3,、,5,、,7,和,4,、,6,、,8,你们先选，然后先出,为什么我是总能赢？,这就是决策，对策,田忌赛马,田忌赛马是大多数人都熟知的故事，传说战国时期齐王欲与大将田忌赛马，双方约定每人挑选上、中、下三个等级的马各一匹进行比赛，每局赌金为一千金。齐王同等级的马均比田忌的马略胜一筹，似乎必胜无疑。田忌的朋友孙膑给他出了一个主意，让他用下等马比齐王的上等马，上等马对齐王的中等马，中等马对齐王的下等马，结果田忌二胜一败，反而赢了一千金。,第一场,第二场,第三场,获胜方,齐,王,上,中,下,田忌,1,上,中,下,齐王,田忌,2,上,下,中,齐王,田忌,3,中,上,下,齐王,田忌,4,中,下,上,齐王,田忌,5,下,上,中,田忌,田忌,6,下,中,上,齐王,田忌能赢，主要是已知齐王的策略而做出决策,如果田忌和齐王事先都不知道各自采用何种组合来赛马，那结果又如何,两人轮流报数，每次只能报,1,或,2,，把两人报的所有数加起来，谁报数后和是,10,，谁就获胜。想一想，如果让你先报数，为了确报胜利，你第一次应报几,?,接下来应该怎样报？,（囚犯的困惑）,警察同时逮捕了两人并分开关押，逮捕的原因是他们持有大量伪币，警方怀疑他们伪造钱币，但没有找到充分证据，希望他们能自己供认，这两个人都知道：如果他们双方都不供认，将被以使用和持有大量伪币罪被各判刑,18,个月；如果双方都供认伪造了钱币，将各被判刑,3,年；如果一方供认另一方不供认，则供认方将被从宽处理而免刑，但另一方面将被判刑,7,年。将嫌疑犯,A,、,B,被判刑的几种可能情况列表如下,：,嫌疑犯,B,供认,不供认,嫌疑犯,A,供认,不供认,（,3,，,3,）,（,0,，,7,）,（,7,，,0,）,（,1.5,，,1.5,）,表中每对数字表示嫌疑犯,A,、,B,被判刑的年数。如果两名疑犯均担心对方供认并希望受到最轻的惩罚，最保险的办法自然是承认制造了伪币。,对策论（博弈论）,解决具有对抗性局势的模型。在这类模型中，参与对抗的各方都有一些可供选择的策略，该模型为对抗各方提供获得最优对策的方法,决策分析,在决策环境不确定和风险情况下对几种被选方案进行决策的准则和方法,预测,对未来的发展作出的推测。如，基于历史数据及相关分析的定量方法、利用专家判断的定性方法,主要分支,一、对策的基本要素,（,1,）,局中人,。参加决策的各方被称为决策问题的局中人，一个决策总是可以包含两名局中人（如棋类比赛、人与大自然作斗争等），也可以包含多于两名局中人（如大多数商业中的竞争、政治派别间的斗争）。局中人必须要拥用可供其选择并影响最终结局的策略，在例,8.3,中，局中人是,A,、,B,两名疑犯，警方不是局中人。两名疑犯最终如何判刑取决于他们各自采取的态度，警方不能为他们做出选择。,从这些简单实例中可以看出对策现象中包含的几个基本要素。,（,2,）,策略集合,。局中人能采取的可行方案称为策略，每一局中人可采取的全部策略称为此局中人的策略集合。对策问题中，对应于每一局中人存在着一个策略集合，而每一策略集合中至少要有两个策略，否则该局中人可从此对策问题中删去，因为对他来讲，不存在选择策略的余地。应当注意的是，所谓策略是指在整个竞争过程中对付他方的完整方法，并非指竞争过程中某步所采取的具体局部办法。例如下棋中的某步只能看和一个完整策略的组成部分，而不能看成一个完整的策略。当然，有时可将它看成一个多阶段对策中的子对策。策略集合可以是有限集也可以是无限集。策略集为有限集时称为有限对策，否则称为无限对策。,记局中人,i,的策略集合为,Si,。当对策问题各方都从各自的策略集合中选定了一个策略后，各方采取的策略全体可用一矢量,S,表示，称之为一个纯局势（简称局势）。,例如,，若一对策中包含,A,、,B,两名局中人，其策略集合分别为,S,A,=,1,m,，,S,B,=,1,n,。若,A,选择策略,i,而,B,选策略,j,，则（,i,j,）就构成此对策的一个纯局势。显然，,S,A,与,S,B,一共可构成,m,n,个纯局势，它们构成表,8.3,。对策问题的全体纯局势构成的集合,S,称为此对策问题的局势集合。,(,m,n,),(,m,j,),(,m,2,),(,m,1,),m,(,i,n,),(,i,j,),(,i,2,),(,i,1,),i,(,2,n,),(,2,j,),(,2,2,),(,2,1,),2,(,1,n,),(,1,j,),(,1,2,),(,1,1,),1,A,的策略,n,J,2,1,B,的策略,（,3,）,赢得函数（或称支付函数）。对策的结果用矢量表示，称之为赢得函数。赢得函数,F,为定义在局势集合,S,上的矢值函数，对于,S,中的每一纯局势,S,，,F,（,S,）指出了每一局中人在此对策结果下应赢得（或支付）的值。综上所述，一个对策模型由局中人、策略集合和赢得函数三部分组成。记局中人集合为,I,=1,k,，对每一,i,I,，有一策略集合,S,i,，当,I,中每一局中人,i,选定策略后得一个局势,s,；将,s,代入赢得函数,F,，即得一矢量,F,(,s,)=(,F,1,(,s,),F,k,(,s,),，其中,F,i,(,s,),为在局势,s,下局中人,i,的赢得（或支付）。,本节讨论只有两名局中人的对策问题，即两人对策，其结果可以推广到一般的对策模型中去。对于只有两名局中人的对策问题，其局势集合和赢得函数均可用表格表示。例如，表,8.2,就给出了例,8.3,的局势集合和赢得函数。,二、零和对策,存在一类特殊的对策问题。在这类对策中，当纯局势确定后，,A,之所得恰为,B,之所失，或者,A,之所失恰为,B,之所得，即双方所得之和总为零。在零和对策中，因,F,1,(,s,)=,F,2,(,s,),，只需指出其中一人的赢得值即可，故赢得函数可用赢得矩阵表示。例如若,A,有,m,种策略，,B,有,n,种策略，赢得矩阵,表示若,A,选取策略,i,而,B,选取策略,j,，则,A,之所得为,a,ij,（当,a,ij,0,时为支付）。,在有些两人对策的赢得表中，,A,之所得并非明显为,B,之所失，但双方赢得数之和为一常数。例如在表,8.4,中，无论,A,、,B,怎样选取策略，双方赢得总和均为,10,，此时，若将各人赢得数减去两人的平均赢得数，即可将赢得表化为零和赢得表。表,8.4,中的对策在转化为零和对策后，具有赢得矩阵,表,8.4,局中人,B,1,2,3,局中人,A,1,(8,2),(1,9),(7,3),2,(4,6),(9,1),(3,7),3,(2,8),(6,4),(8,2),4,(6,4),(4,6),(6,4),给定一个两人对策只需给出局中人,A,、,B,的策略集合,S,A,、,S,B,及表示双方赢得值的赢得矩阵,R,。综上所述，当遇到零和对策或可转化为零和对策的问题时，,R,可用通常意义下的矩阵表示，否则,R,的元素为一两维矢量。,故两人对策,G,又可称为矩阵对策并可简记成,G,=,S,A,S,B,R,例,8.4,给定,G,=,S,A,S,B,R,，,其中,S,A,=,1,2,3,，,S,B,=,1,2,3,4,从,R,中可以看出，若,A,希望获得最大赢利,30,，需采取策略,1,，但此时若,B,采取策略,4,，,A,非但得不到,30,，反而会失去,22,。为了稳妥，双方都应考虑到对方有使自己损失最大的动机，在最坏的可能中争取最好的结果。局中人,A,采取策略,1,、,2,、,3,时，最坏的赢得结果分别为,min 12,6,30,22 =,22,min 14,2,18,10=2,min,6,0,10,16=,10,其中最好的可能为,max,22,2,10=2,。,如果,A,采取策略,2,，无论,B,采取什么策略，,A,的赢得均不会少于,2.,B,采取各方案的最大损失为,max 12,14,6=14,，,max,6,2,0=2,，,max 30,18,10=30,和,max,22,10,16=16,。当,B,采取策略,2,时，其损失不会超过,2,。注意到在赢得矩阵中，,2,既是所在行中的最小元素又是所在列中的最大元素。此时，只要对方不改变策略，任一局中人都不可能通过变换策略来增大赢得或减小损失，称这样的局势为对策的一个稳定点或稳定解，（注：也被称为鞍点）,定义,8.1,对于两人对策,G,=,S,A,S,B,R,，若有,，则称,G,具有稳定解，并称,V,G,为对策,G,的值。若纯局势（）使得,，则称（）为对策,G,的鞍点或稳定解，赢得矩阵中与（）相对应的元素 称为赢得矩阵的鞍点，与 分别称为局中人,A,与,B,的最优策略。,对（,8.1,）式中的赢得矩阵，容易发现不存在具有上述性质的鞍点。给定一个对策,G,，如何判断它是否具有鞍点呢？为了回答这一问题，先引入下面的极大极小原理。,定理,8.1,设,G,=,S,A,S,B,R,，记 ，,则必有,+,0,证明,:,，,易见,为,A,的最小赢得，,为,B,的最小赢得，,由于,G,是零和对策，故,+,0,必成立。,定理,8.2,零和对策,G,具有稳定解的充要条件为,+,=0,。,证明：,（充分性）,由,和,的定义可知，存在一行（例如,p,行）,为,p,行中的最小元素且存在一列（例如,q,列），,为,q,列中的最大元素。故有,a,pq,且,a,pq,又因,+,=0,，所以,=,，从而得出,a,pq,=,，,a,pq,为赢得矩阵的鞍点，（,p,q,）为,G,的稳定解。,（必要性）,若,G,具有稳定解（,p,q,），则,a,pq,为赢得矩阵的鞍点。故有,从而可得,+0,，但根据定理,8.1,，,+0,必成立，故必有,+,=0,。,上述定理给出了对策问题有稳定解（简称为解）的充要条件。当对策问题有解时，其解可以不唯一。例如，若,则易见，（,2,2,），（,2,4,），（,4,2,），（,4,4,）均为此对策问题的解。,一般又可以证明。,具有稳定解的零和对策问题是一类特别简单的对策问题，它所对应的赢得矩阵存在鞍点，任一局中人都不可能通过自己单方面的努力来改进结果。然而，在实际遇到的零和对策中更典型的是,+,0,的情况。由于赢得矩阵中不存在鞍点，至少存在一名局中人，在他单方面改变策略的情况下，有可能改善自己的收益。例如，考察（,8.1,）中的赢得矩阵,R,。,若双方都采取保守的,max min,原则。将会出现纯局势（,4,1,）或,（,4,3,）。但如果局中人,A,适当改换策略，他可以增加收入。例如，如果,B,采用策略,1,，而,A,改换策略,1,，则,A,可收益,3,。但此时若,B,改换策略,2,，又会使,A,输掉,4,，,。此时，在只使用纯策略的范围内，对策问题无解。这类决策如果只进行一次，局中人除了碰运气以外别无办法。但如果这类决策要反复进行多次，则局中人固定采用一种策略显然是不明智的，因为一旦对手看出你会采用什么策略，他将会选用对自己最为有利的策略。这时，局中人均应根据某种概率来选用各种策略，即采用混合策略的办法，使自己的期望收益尽可能大。,设,A,方用概率,x,i,选用策略,i,，,B,方用概率,y,j,选用策略,j,，,且双方每次选用什么策略是随机的，不能让对方看出规律，,记,X,=(,x,1,x,m,),T,，,Y,=(,y,1,y,n,),T,，则,A,的期望赢得为,E,(,X,Y,)=,X,T,RY,其中，,R,为,A,方的赢得矩阵,。,记,S,A,:,策略,1,m,S,B,:,策略,1,n,概率,x,1,x,m,概率,y,1,y,n,分别称,S,A,与,S,B,为,A,方和,B,方的混合策略。,对于需要使用混合策略的对策问题，也有具有稳定解的对策问题的类似结果。,定义,8.2,若存在,m,维概率向量和,n,维概率向量，使得对一切,m,维概率向量,X,和,n,维概率向量,y,有,则称（,）为混合策略对策问题的鞍点。,定理,8.4,（,Von Neumann,）任意混合策略对策问题必存在鞍点，即必存在概率向,量和，使得：（证明从略）。,使用纯策略的对策问题（具有稳定解的对策问题）可以看成使用混合策略的对策,问题的特殊情况，相当于以概率,1,选取其中某一策略，以概率,0,选取其余策略。,对于双方均只有两种策略的对策问题（即,2,2,对策），可按几何方法求解。,例,8.5,A,、,B,为作战双方，,A,方拟派两架轰炸机,I,和,II,去轰炸,B,方的指挥部，轰炸机,I,在前面飞行，,II,随后。两架轰炸机中只有一架带有炸弹，而另一架仅为护航。轰炸机飞至,B,方上空，受到,B,方战斗机的阻击。若战斗机阻击后面的轰炸机,II,，它仅受,II,的射击，被击中的概率为,0.3,（,I,来不及返回击它）。若战斗机阻击,I,，它将同时受到两架轰炸机的射击，被击中的概率为,0.7,。一旦战斗机未被击落，它将以,0.6,的概率击毁其选中的轰炸机。请为,A,、,B,双方各选择一个最优策略，即：对于,A,方应选择哪一架轰炸机装载炸弹？对于,B,方战斗机应阻击哪一架轰炸机？,解：,双方可选择的策略集分别为,S,A,=,1,2,1,：轰炸机,I,装炸弹，,II,护航,2,：轰炸机,II,装炸弹，,I,护航,S,A,=,1,2,1,：阻击轰炸机,I,2,：阻击轰炸机,II,赢得矩阵,R,=,（,a,ij,）,2,2,，,a,ij,为,A,方采取策略,i,而,B,方采取策略,j,时，轰炸机轰炸,B,方指挥部的概率，由题意可计算出：,a,11,=0.7+0.3(1,0.6)=0.82,a,12,=1,a,21,=1,a,22,=0.3+0.7(1,0.6)=0.58,即,易求得 ，。,由于,+,0,，,矩阵,R,不存在鞍点，应当求最佳混合策略。,现设,A,以概率,x,1,取策略,1,、概率,x,2,取策略,2,；,B,以概率,y,1,取策略,1,、概率,y,2,取策略,2,。,先从,B,方来考虑问题。,B,采用,1,时，,A,方轰炸机攻击指挥部的概率的期望值为,E,（,1,）,=0,。,82,x,1,+,x,2,，而,B,采用,2,时，,A,方轰炸机攻击指挥部的概率的期望值为,E,（,2,）,=,x,1,+0.58,x,2,。若,E,（,1,）,E,（,2,），不妨设,E,（,1,）,2,且,n,2,时，采用几何方法求解就变得相当麻烦，,此时通常采用线性规划方法求解。,现设,A,以概率,x,2,采取策略,2,，若,B,采取策略,2,，则,A,的期望赢得为,a,11,(1,x,2,)+,a,21,x,2,。,对应,x,2,的不同取值（,0,x,2,1,），,a,11,(1,x,2,)+,a,12,x,2,恰好构成连接两个,B,1,的直线段。类似地，连接两个,B,2,的直线段恰好对应当,B,取,2,而,A,以概率,x,2,取,2,时的赢得,a,12,(1,x,2,)+,a,22,x,2,。,设两直线段相交于,N,，,并设,N,对应于 。若,A,以小于 的,x,2,取策略,2,，则,B,可以采取,1,使,A,的期望赢得减小；反之，若,x,2,，则,B,又可采取,2,而使,A,的赢得减小。故,A,的最佳混合策略为以,=1,概率取,1,，以概率取,2,（注：,B,的最佳混合策略可类似用几何方法求得）。,A,方选择混合策略 的目的是使得,其中,e,j,为只有第,j,个分量为,1,而其余分量均为零的向量，,E,j,=,X,T,Re,j,。,记 ，由于 ，在,y,k,=1,，,y,j,=0,（,j,k,）时达到最大值,u,，,故 应为线性规划问题,min,u,j,=1,2,n,(,即,E,j,E,k,),x,i,0,i,=1,2,m,S.t,的解。,同理，应为线性规划,max,i,=1,2,m,y,j,0,i,=1,2,n,S.t,的解。,由线性规划知识，（,8.2,）与（,8.3,）互为对偶线性规划，它们具有相同的最优目标函数值。关于线性规划对偶理论，有兴趣的读者可以参阅有关书籍，例如鲁恩伯杰的“线性与非线性规划引论”。,为了寻找例,8.5,中,A,方的最优混合策略，求解线性规划,min,u,S.t,0.82,x,1,+,x,2,u,x,1,+0.58,x,2,u,x,1,+,x,2,=1,x,1,x,2,0,可得最优混合策略,x,1,=0.7,x,2,=0.3,。类似求解线性规划,max,S.t,0.82,y,1,+,y,2,y,1,+0.58,y,2,y,1,+,y,2,=1,y,1,y,2,0,可得,B,方最优混合策略：,y,1,=0.7,y,2,=0.3,。,田忌赛马，田忌不知齐王出马次序，请问田忌应如何出马,三、非零和对策,除了零和对策外，还存在着另一类对策问题，局中人获利之和并非常数。,例,8.4,现有一对策问题，双方获利情况见表,8.5,。,表,8.5,B,方,A,方,1,2,3,1,2,3,4,（,8,2,）,（,3,4,）,（,1,6,）,（,4,2,）,（,0,9,）,（,9,0,）,（,6,2,）,（,4,6,）,（,7,3,）,（,2,7,）,（,8,1,）,（,5,1,）,假如,A,、,B,双方仍采取稳妥的办法，,A,发现如采取策略,4,，则至少可获利,4,，而,B,发现如采取策略,1,，则至少可获利,2,。因而，这种求稳妥的想法将导至出现局势（,4,，,2,）。,容易看出，从整体上看，结果并不是最好的，因为双方的总获利有可能达到,10,。不难看出，依靠单方面的努力不一定能收到良好的效果。看来，对这一对策问题，双方最好还是握手言和，相互配合，先取得总体上的最大获利，然后再按某一双方均认为较为合理的方式来分享这一已经获得的最大获利。,例,8.4,说明，总获利数并非常数的对策问题（即不能转化为零和对策的问题），是一类存在着合作基础的对策问题。当然，这里还存在着一个留待解决而又十分关键的问题：如何分享总获利，如果不能达到一个双方（或各方）都能接受的“公平”的分配原则，则合作仍然不能实现。怎样建立一个“公平”的分配原则是一个较为困难的问题，将在第九章中介绍。,最后，我们来考察几个对策问题的实例。,例,8.6,（战例分析）,1944,年,8,月，美军第一军和英军占领法国诺曼第不久，立即从海防前线穿过海峡，向,Avranches,进军。美军第一军和英军的行动直接威胁到德军第九军。美军第三军也开到了,Avranches,的南部，双方军队所处的地理位置如图,8.2,所示。,美军方面的指挥官是,Bradley,将军，德军指挥官是,Von Kluge,将军。,Von Kluge,将军面临的问题是或者向西进攻，加强他的西部防线，切断美军援助；或者撤退到东部，占据塞那河流域的有利地形，并能得到德军第十五军的援助。,Bradley,将军的问题是如何调动他的后备军，后备军驻扎在海峡南部。,Bradley,将军有三种可供选择的策略：他可以命令后备军原地待命，当海峡形势危急时支援第一军或出击东部敌人，以减轻第一军的压力。,双方应如何决策，使自己能有较大的机会赢得战争的胜利呢？,我们将用建立矩阵对策模型的方法，来试图求得双方的最优策略。模型假设：,1,、,Bradley,将军和,Von Kluge,将军分别为对策问题的局中人,A,和,B,。,2,、局中人,A,的策略集合为,S,A,=,1,2,3,，,其中：,1,为后备军增援保卫海峡；,2,为后备军东征，切断德军后路；,3,为后备军待命,3,、局中人,B,的策略集合为,S,B,=,1,2,，,其中：,1,为德国向西进攻海峡，切断美军援助；,2,为德军撤退到东部，占领塞纳河流域有利地形。,4,、,S,A,、,S,B,构成六种纯局势，综合双方实力，各种局势估计结果如下。若,B,采取策略,1,，即德军采取攻势，则有,（,1,）（,1,1,），估计美军击败德军并占领海峡的可能性（即概率）为,（,2,）（,2,1,），估计美军取胜的可能为 。德军很可能打破美军第一军的防线，并切断美军的退路。,（,3,）（,3,1,），估计美军可以根据需要增援。如不需增援，后备军可东进绕行到德军后方。这样，美军将占领海峡并彻底歼灭德军第九军。,情况（,1,）、（,2,）、（,3,）如图,8.3,（,1,）、（,2,）、（,3,）所示。,若,B,采取策略,2,，即德军第九军东撤，占据塞纳河流域有利地形，则有,（,4,）（,1,2,），美方扩大了战线，德军虽占据了有利地形，美军仍有击败,德军的可能性。,（,5,）（,2,2,），美后备军东进给德军东撤造成压力并挫伤德军，使美军击败,德军的可能性增大到 。,（,6,）（,3,2,），美后备军待命。在发现德军撤退后，奉命向东扰乱敌方撤退，,为以后歼灭德第九军创造条件，估计是美军击败德军的可能性 。,情况（,4,）、（,5,）、（,6,）见图,8.3,（,4,）、（,5,）（,6,）所示。,上述分析估计是由,Bradley,将军作出的，据此构造出,A,方赢得矩阵,这是一个,3,2,对策矩阵。可以求得 ，不存在稳定解，需要考虑其他解法。,定义,8.3,对于赢得矩阵,R,，,如果对所有,j,，,a,ij,a,kj,均成立，且至少存在一个 使,得 则称,i,行优于,k,行（策略,a,i,优于,a,k,）。,同样，如对一切,i,有,a,ij,a,kl,，,且至少有一个,i,0,使得 ，则称,j,列优于,l,例（局中人,B,的策略,j,优于,l,）。,易见，若一个对策矩阵的第,i,行优于第,k,行，则无论局中人,B,选择哪种策略，局中,人,A,采取策略,i,的获利总优于（至少不次于）采取策略,k,的获利。,定理,8.5,对于矩阵对策,G,=,S,A,S,B,R,，,若矩阵,R,的某行优于第,i,1,i,k,行，,则局中人,A,在选取最优策略时，必取 。,令 ，,R,为从,R,中划去第,i,1,行，,，,i,k,行后剩下的矩,阵，则 的最优策略即原对策,G,的最优策略，对于,R,中,列的最优关系也有类似的结果。,利用这一定理，有时对策问题可先进行化简，降低矩阵的阶数。,现在回过来讨论美、德军队对策问题。在,Bradleg,构造的矩阵中容易发现,a,1,j,a,3,j,j,=1,2,故,3,优于,1,。,根据上面的定理,8.5,，可划去该矩阵的第一行，得到,2,2,赢得矩阵,这仍然是一个无鞍点的对策矩阵。设,Bradley,以概率,p,1,取策略,2,而以概率,p,2,取略,3,，则应有,解得,类似地，设,Von Kluge,以概率,q,1,取策略,1,而以概率,q,2,取策略,2,，则应有,解得 。,由于两军作战并非可以反复进行的对策问题，看来最大的可能是美军采取策略,3,而德军采取策略,2,，即美方后备军待命而德军第九军东撤。事实上，当时双方指挥官正是这样决策的，如果真能实行，双方胜负还难以料定。但正当德军第九军刚开始东撤时，突然接到了希特勒的命令要他们向西进攻，从而失去了他们有可能取得的最佳结局，走上必然灭亡的道路。,Von Kluge,将军指挥的德军向西进攻，开始时德军占领了海峡，但随之即被美军包围遭到了全军复灭，,Von Kluge,本人在失败后自杀。,例,8.7,（防坦克地雷场的布设）,实战中，攻方为了增强攻击力，大量使用攻击力强、防御坚固的坦克；守方为了抵御对方攻击，需要大量杀伤敌方的有生力量，有效对策之一是布设防坦克地雷场。,1,、分析,评价防坦克地雷场的重要指标是战斗效力，而布雷密度是基本因素之一。只要有足够多的地雷，用较高密度的地雷场对付敌方进攻总是行之有效的。但在实际战斗中，地雷不太可能是足够多的。假设：,（,1,）防坦克地雷数量有限；,（,2,）通过侦察、分析，已知敌方可能采用,1,、,2,、,、,n,种进攻策略之一；,（,3,）通过敌情分析，确定了防御正面的宽度，并根据我方地雷数量，设计,了,1,2,m,这,m,种布雷方案。,问采取哪一方案或什么样的混合策略能有效击毁敌方的坦克？,本例在过去一般是凭指挥员的作战经验定性决策的，现用矩阵对策方法进行定量择优。,由于每两辆坦克之间一般要保持,50,米的间距，因而进攻正面拉得很宽，如一个梯队,20,辆坦克，进攻正面约为一公里宽。因为只有有限个防御正面，用有限个进攻策略来描述敌方的进攻状态是非常接近实际情况的。对守方来讲，布雷密度通常可分成,0.5,1,1.5,2,等有限个等级。按常规做法，在防御正面上一般采用同一种技术密度。为了提高杀伤率，现将一个防御正面划分成几段，各段允许采用不同密度。,2,、对策决策,要用矩阵对策决策，关键问题是如何列出守方的赢得矩阵。由效率评定试验可得出在各种布雷密度下的杀伤率表，如表,8.6,所示。,表,8.6,布雷密度,0.5,1,1.5,2,杀伤率,0.64,0.87,0.95,0.98,根据上表，在确定方案后即可根据各段不同密度针对攻方的进攻策略计算出坦克的杀伤率。为便于理解，作为实例分析下面两种情况：,情况,1,设守方只有,1500,个防坦克地雷，欲布设在攻方必经的,2,公里攻击正面上。攻方一个坦克梯队的,20,辆坦克展开成,1,公里宽的阵面，但既可能从左侧进攻（策略,1,）也可能从右侧进攻（策略,2,）。守方设计了三种布雷方案,1,2,3,（图,8.4,），试求守方的赢得矩阵和最优策略。,图,8.4,情况,1,求解：容易求得守方的赢得矩阵,这是一个有鞍点的矩阵，鞍点为,a,22,。守方只要按,2,方案布雷，则不管攻方从哪一侧进攻，总可毁伤对方,47.5%,的坦克。,情况,2,攻方一梯队,20,辆坦克可从左侧（,1,）、中路（,2,）或右翼（,3,）进攻，展开成,1,公里布阵。守方只有,2000,个防坦克地雷，初步提出三种布雷方案，如图,8.5,所示，试求守方采用何种布雷方案较好。,图,8.5,对情况,2,，可求得守方的赢得矩阵为,此时，矩阵,A,中不存在鞍点，对策无稳定解，应采用混合策略。可以求得，此时守方如按照,0.166:0.456:0.378,的比例采取策略,1,2,3,布雷，平均可毁伤对方,83.5%,的坦克。,由本例可以看出，在决策问题中，策略的设计至关重要，它直接影响到赢得矩阵。策略的设计并没有包含在决策问题的求解中，事实上，仅当策略设计完成后，即策略集合给定后，决策问题才被给定，从而才能被求解，因而，在用对策论方法研究实际课题时，应当特别注意策略的设计。这一部分工作既具有一定的创造性又在很大程度上影响到结果，对它研究也是十分有趣的。,8.2,决策问题,人们在处理问题时，常常会面临几种可能出现的自然情况，同时又存在着几种可供选择的行动方案。此时，需要决策者根据已知信息作决策，即选择出最佳的行动方案，这样的问题称为决策问题。面临的几种自然情况叫做自然状态或简称状态。状态是客观存在的，是不可控因素。可供选择的行动方案叫做策略，这是可控因素，选择哪一方案由决策者决定。,例,8.8,在开采石油时，会遇到是否在某处钻井的问题。尽管勘探队已作了大量调研分析，但由于地下结构极为复杂，仍无法准确预测开采的结果，决策者可以决定钻井，也可以决定不钻井。设根据经验和勘探资料，决策者已掌握一定的信息并列出表,8.7,。,表,8.7,0,0,0,不钻井（,2,）,40,20,30,钻井（,1,）,P,(,3,)=0.3,P,(,2,)=0.5,P,(,1,)=0.2,（亿元）,高产油井（,3,）,一般（,2,）,无油（,1,）,自然状态,概率,收益,方案,问：决策者应如何作出决策？,解：由题意可以看出，决策问题应包含三方面信息：状态集合,Q,=,1,n,、策略集合,A,=,1,m,及收益,R,=,a,ij,，其中,a,ij,表示如果决策者选取策略,i,而出现的状态为,j,，则决策者的收益值为,a,ij,（当,a,ij,为负值时表示损失值）。,决策问题按自然状态的不同情况，常被分为三种类型：确定型、风险型（或随机型）和不确定型。,确定型决策是只存在一种可能自然状态的决策问题。这种决策问题的结构较为简单，决策者只需比较各种方案，确定哪一方案最优即可。值得一提的是策略集也可以是无限集，例如，线性规划就可行看成一个策略集是限集的确定型决策，问题要求决策者从可行解集合（策略集）中挑选出最优解。确定型决策的求解并非全是简单的，但由于这些问题一般均有其自己的专门算法，本节不准备再作介绍。在本节中，我们主要讨论风险型与不确定型决策，并介绍它们的求解方法。,一、风险型决策问题,在风险型决策问题中存在着两种以上可能出现的自然状态。决策者不知道究竟会出现哪一种状态，但知道各种状态出现的概率有多大。例如，例,8.8,就是一个风险型决策问题。,对于风险型决策问题，最常用的决策方法是期望值法，即根据各方案的期望收益或期望损失来评估各方案的优劣并据此作出决策。如对例,1,，分别求出方案,1,（钻井）和,2,（不钻井）的期望收益值：,E,（,1,）,=0.2,（,30,）,+0.5,20+0.3,40=16,（,万元）,E,（,2,）,=0,由于,E,（,1,）,E,（,2,），,选取,1,作为最佳策略。,风险型决策也可采用期望后悔值法求解。首先，求出采取方案,i,而出现状态,j,时的后悔值 。,例如，如果不钻井，但事实上该处可开出一口高产井，则后悔值为,40,。因为钻井可收益,40,万元，但决策者作了不钻井的决策，未获得本来可以获得的,40,万元收益。然后，比较各方案的期望后悔值，选取期望后悔最小的方案作为最佳策略。在例,8.8,中，如采用期望后悔值法，则,E,（,1,）,=6,，,E,（,2,）,=22,，取,1,为最佳策略。,在选取策略,i,而出现状态,j,时后悔值为 的理由是在,出现状态,j,情况下的最大可能收益为 。,定理,8.6,最大期望收益法与最小期望后悔值法等价，即两者选出的最佳,策略相同。,证明：由 得,故,等式（,8.4,）的右端项为一常数，其左端项为采取策略,i,时期后悔值与期望收益值之和，从而，若某策略使期望收益最大，则该策略必使期望后悔值最小，定理得证。,对于较为复杂的决策问题，尤其是需要作多阶段决策的问题，常采用较直观的决策树方法，但从本质上讲，决策树方法仍然是一种期望值法。,例,8.9,某工程按正常速度施工时，若无坏天气影响可确保在,30,天内按期完工。但根据天气预报，,15,天后天气肯定变坏。有,40%,的可能会出现阴雨天气而不影响工期，在,50%,的可能会遇到小风暴而使工期推迟,15,天，另有,10%,的可能会遇到大风暴而使工期推迟,20,天。对于可能出现的情况，考虑两种方案：,（,1,）提前紧急加班，在,15,天内完成工程，实施此方案需增加开支,18000,元。,（,2,）先按正常速度施工，,15,天后根据实际出现的天气状况再作决策。,如遇到阴雨天气，则维持正常速度，不必支付额外费用。,如遇到小风暴，有两个备选方案：（,i,）维持正常速度施工，支付工程延期损失费,20000,元。（,ii,）采取应急措施。实施此应急措施有三种可能结果：有,50%,可能减少误工期,1,天，支付应急费用和延期损失费共,24000,元；有,30%,可能减少误工期,2,天，支付应急费用和延期损失费共,18000,元；有,20%,可能减少误工期,3,天，支付应急费用和延期损失费共,12000,元。,如遇大风暴，也有两个方案可供选择：（,i,）维持正常速度施工，支付工程延期损失费,50000,元。（,ii,）采取应急措施。实施此应急措施也有三种可能结果：有,70%,可能减少误工期,2,天，支付应急费及误工费共,54000,元；有,20%,可能减少误工期,3,天，支付应急费及误工费共,46000,元；有,10%,可能减少误工期,4,天，支付应急费和误工费共,38000,元。,根据上述情况，试作出最佳决策使支付的额外费用最少。,解：由于未来的天气状态未知，但各种天气状况出现的概率已知，本例是一个风险型决策问题，所谓的额外费用应理解为期望值。,本例要求作多次决策，工程初期应决定是按正常速度施工还是提前紧急加班。如按正常速度施工，则,15,天后还需根据天气状况再作一次决策，以决定是否采取应急措施，故本例为多阶段（两阶段）决策问题。为便于分析和决策，采用决策树方法。,根据题意，作决策树如图,8.6,图,8.6,中，,表示决策点，从它分出的分枝称为方案分枝，分枝的数目就是方案的个数。,表示机会节点，从它分出的分枝称为概率分枝，一条概率分枝对应一条自然状态并标有相应的发生概率。,称为未梢节点，右边的数字表示相应的收益值或损失值。,在决策树上由右向左计算各机会节点处的期望值，并将结果标在节点旁。遇到决策点则比较各方案分枝的效益期望值以决定方案的优劣，并且用双线划去淘汰掉的方案分枝，在决策点旁标上最佳方案的效益期望值，计算步骤如下：,（,1,）在机会节点,E,、,F,处计算它们的效益期望值,E,(,E,)=0.5,（,24000,）,0.3,（,18000,）,0.2,（,12000,）,=,19800,E,(,F,)=0.7,（,54000,）,0.2,（,46000,）,0.1,（,38000,）,=,50800,（,2,）在第一级决策点,C,、,D,处进行比较，在,C,点处划去正常速度分枝，在,D,处划去应急分枝。,（,3,）计算第二级机会节点,B,处的效益期望值,E,(,B,)=0.4,0,0.5,（,19800,）,0.1,（,50000,）,=,14900,并将,14900,标在,B,点旁。,（,4,）在第二级决策点,A,处进行方案比较，划去提前紧急加班，将,14900,标在,A,点旁。,结论,最佳决策为前,15,天按正常速度施工，,15,天后按实际出现的天气状况再作决定。如出现阴雨天气，仍维持正常速度施工；如出现小风暴，则采取应急措施；如出现大风暴，也按正常速度施工，整个方案总损失的期望值为,14900,元。,根据期望值大小决策是随机型决策问题最常用的办法之一。实际应用时应根据具体情况作出分析，选取期望收益最大或期望损失最小的方案。,二、不确定型决策问题,只知道有几种可能自然状态发生，但各种自然状态发生的概率未知的决策问题称为不确定型决策问题，由于概率未知，期望值方法不能用于这类决策问题。下面结合一个例子，介绍几种处理这类问题的方法。,例,8.10,设存在五种可能的自然状态，其发生的概率未知。有四种可供选择的行动方案，相应的收益值见表,8.7,表,8.8,6,6,6,5,3,4,1,5,9,6,4,3,8,7,5,4,3,2,6,6,5,4,4,1,5,4,3,2,1,自然状态,方案,（,1,）乐观法（,max max,原则）,采用乐观法时，决策者意在追求最大可能收益。他先计算每一方案的最大收益值，再比较找出其中的最大者，并采取这一使最大收益最大的方案，在例,8.10,中，,max,a,1,j,=6,，,max,a,2,j,=8,，,max,a,3,j,=9,，,max,a,4,j,=6,，而,max 6,，,8,，,9,，,6=9,，,采取方案,3,。,（,2,）悲观法（,max min,原则）,采用悲观法时，决策者意在安全保险。他先求每一方案的最小收益,再比较找出其中的最大者，并采取这一使最小收益值最大化的方案。对于例,8.10,，,min,a,1,j,=4,，,min,a,2,j,=3,，,min,a,3,j,=1,，,min,a,4,j,=3,。,因为,max 4,3,，,1,，,3=4,采取方案,1,。,（,3,）乐观系数法（,Hurwicz,决策准则）,乐观系数法采用折中的办法，引入一个参数,t,，,0,t,1,，称,t,为乐观系数。,作决策时，决策者先适当选取一个,t,的值；再对各方案,1,求出,；,最后再作比较，找出使,最大的方案。在例,8.10,中，若取,t,=0.5,，,采用乐观系数法决策，将选取,方案,2,。易见，,t,=1,对应乐观法，而,t,=0,则对应于悲观法。,（,4,）等可能法（,Laplace,准则）,由于不能估计各状态出现的概率，决策者认为它们相差不会过大。此