数模(对策与决策模型).ppt

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,数学模型电子教案,重庆邮电大学,计算机科学与技术学院,沈世云,1,第八章 对策与决策模型,2,第八章,对策与决策模型,对策与决策是人们生活和工作中经常会遇到的择优活动。人们在处理一个问题时，往往会面临几种情况，同时又存在几种可行方案可供选择，要求根据自己的行动目的选定一种方案，以期获得最佳的结果。,有时，人们面临的问题具有竞争性质，如商业上的竞争、体育中的比赛和军事行动、政治派别的斗争等等。这时竞争双方或各方都要发挥自己的优势，使己方获得最好结果。因而双方或各方都要根据不同情况、不同对手做出自己的决择，此时的决策称为对策。在有些情况下，如果我们把可能出现的若干种情况也看作是竞争对手可采取的几种策略，那么也可以把决策问题当作对策问题来求解。,3,8.1,对策问题,对策问题的特征是参与者为利益相互冲突的各方，其结局不取决于其中任意一方的努力而是各方所采取的策略的综合结果。,先考察几个实际例子。,例,8.1,（田忌赛马）,田忌赛马是大多数人都熟知的故事，传说战国时期齐王欲与大将田忌赛马，双方约定每人挑选上、中、下三个等级的马各一匹进行比赛，每局赌金为一千金。齐王同等级的马均比田忌的马略胜一筹，似乎必胜无疑。田忌的朋友孙膑给他出了一个主意，让他用下等马比齐王的上等马，上等马对齐王的中等马，中等马对齐王的下等马，结果田忌二胜一败，反而赢了一千金。,4,例,8.2,（石头,剪子,布）,这是一个大多数人小时候都玩过的游戏。游戏双方只能选石头、剪子、布中的一种，石头赢剪子，剪子赢布，而布又赢石头，赢者得一分，输者失一分，双方相同时不得分，见下表。,表,8.1,石头,剪子,布,石头,0,1,1,剪子,1,0,1,布,1,1,0,5,一、对策的基本要素,（,1,）,局中人,。参加决策的各方被称为决策问题的局中人，一个决策总是可以包含两名局中人（如棋类比赛、人与大自然作斗争等），也可以包含多于两名局中人（如大多数商业中的竞争、政治派别间的斗争）。局中人必须要拥用可供其选择并影响最终结局的策略，在例,8.2,中，局中人是,田忌,、,齐王,从这些简单实例中可以看出,对策现象中包含的几个基本要素,6,（,2,）,策略集合,。局中人能采取的可行方案称为策略，每一局中人可采取的全部策略称为此局中人的策略集合。对策问题中，对应于每一局中人存在着一个策略集合，而每一策略集合中至少要有两个策略，否则该局中人可从此对策问题中删去，因为对他来讲，不存在选择策略的余地。应当注意的是，所谓策略是指在整个竞争过程中对付他方的完整方法，并非指竞争过程中某步所采取的具体局部办法。例如下棋中的某步只能看和一个完整策略的组成部分，而不能看成一个完整的策略。当然，有时可将它看成一个多阶段对策中的子对策。策略集合可以是有限集也可以是无限集。策略集为有限集时称为有限对策，否则称为无限对策。,记局中人,i,的策略集合为,Si,。当对策问题各方都从各自的策略集合中选定了一个策略后，各方采取的策略全体可用一矢量,S,表示，称之为一个纯局势（简称局势）。,7,例如,，若一对策中包含,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,的策略,8,（,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.2,的局势集合和赢得函数。,9,二、零和对策,存在一类特殊的对策问题。在这类对策中，当纯局势确定后，,A,之所得恰为,B,之所失，或者,A,之所失恰为,B,之所得，即双方所得之和总为零。在零和对策中，因,F,1,(,s,)=,F,2,(,s,),，只需指出其中一人的赢得值即可，故赢得函数可用赢得矩阵表示。例如若,A,有,m,种策略，,B,有,n,种策略，赢得矩阵,表示若,A,选取策略,i,而,B,选取策略,j,，则,A,之所得为,a,ij,（当,a,ij,0,时为支付）。,10,在有些两人对策的赢得表中，,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),11,给定一个两人对策只需给出局中人,A,、,B,的策略集合,S,A,、,S,B,及表示双方赢得值的赢得矩阵,R,。综上所述，当遇到零和对策或可转化为零和对策的问题时，,R,可用通常意义下的矩阵表示，否则,R,的元素为一两维矢量。,故两人对策,G,又可称为矩阵对策并可简记成,G,=,S,A,S,B,R,12,例,8.3,给定,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.,13,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,，如何判断它是否具有鞍点呢？为了回答这一问题，先引入下面的极大极小原理。,14,定理,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,的稳定解。,15,（必要性）,若,G,具有稳定解（,p,q,），则,a,pq,为赢得矩阵的鞍点。故有,从而可得,+0,，但根据定理,8.1,，,+0,必成立，故必有,+=0,。,上述定理给出了对策问题有稳定解（简称为解）的充要条件。当对策问题有解时，其解可以不唯一。例如，若,则易见，（,2,2,），（,2,4,），（,4,2,），（,4,4,）均为此对策问题的解。,一般又可以证明。,16,定理,8.3,对策问题的解具有下列性质：,（,1,）无差别性。若（,）与（,）同为对策,G,的解，则必有 。,（,2,）可交换性。若（,j1,）、（,j2,）均为对策,G,的解，,则（,j2,）和（,j1,）也必为,G,的解。,17,具有稳定解的零和对策问题是一类特别简单的对策问题，它所对应的赢得矩阵存在鞍点，任一局中人都不可能通过自己单方面的努力来改进结果。然而，在实际遇到的零和对策中更典型的是,+0,的情况。由于赢得矩阵中不存在鞍点，至少存在一名局中人，在他单方面改变策略的情况下，有可能改善自己的收益。例如，考察（,8.1,）中的赢得矩阵,R,。若双方都采取保守的,max min,原则，将会出现纯局势,（,4,1,）或,（,4,3,）。但如果局中人,A,适当改换策略，他可以增加收入。例如，如果,B,采用策略,1,，而,A,改换策略,1,，则,A,可收益,3,。但此时若,B,改换策略,2,，又会使,A,输掉,4,，,。此时，在只使用纯策略的范围内，对策问题无解。这类决策如果只进行一次，局中人除了碰运气以外别无办法。但如果这类决策要反复进行多次，则局中人固定采用一种策略显然是不明智的，因为一旦对手看出你会采用什么策略，他将会选用对自己最为有利的策略。这时，局中人均应根据某种概率来选用各种策略，即采用混合策略的办法，使自己的期望收益尽可能大。,18,设,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,方的混合策略。,对于需要使用混合策略的对策问题，也有具有稳定解的对策问题的类似结果。,19,定义,8.2,若存在,m,维概率向量和,n,维概率向量，使得对一切,m,维概率向量,X,和,n,维概率向量,y,有,则称（,）为混合策略对策问题的鞍点。,定理,8.4,（,Von Neumann,）任意混合策略对策问题必存在鞍点，即必存在概率向,量和，使得：（证明从略）。,使用纯策略的对策问题（具有稳定解的对策问题）可以看成使用混合策略的对策,问题的特殊情况，相当于以概率,1,选取其中某一策略，以概率,0,选取其余策略。,对于双方均只有两种策略的对策问题（即,2,2,对策），可按几何方法求解。,20,例,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,21,赢得矩阵,R,=,（,a,ij,）,22,，,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,不存在鞍点，应当求最佳混合策略。,22,现设,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,的最佳混合策略可类似用几何方法求得）。,25,A,方选择混合策略 的目的是使得,其中,e,j,为只有第,j,个分量为,1,而其余分量均为零的向量，,E,j,=,X,T,Re,j,。,记 ，由于 ，在,y,k,=1,，,y,j,=0,（,j,k,）时达到最大值,u,，,26,故 应为线性规划问题,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,的解。,27,由线性规划知识，（,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,。,28,三、非零和对策,除了零和对策外，还存在着另一类对策问题，局中人获利之和并非常数。,例,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,）。,29,容易看出，从整体上看，结果并不是最好的，因为双方的总获利有可能达到,10,。不难看出，依靠单方面的努力不一定能收到良好的效果。看来，对这一对策问题，双方最好还是握手言和，相互配合，先取得总体上的最大获利，然后再按某一双方均认为较为合理的方式来分享这一已经获得的最大获利。,例,8.4,说明，总获利数并非常数的对策问题（即不能转化为零和对策的问题），是一类存在着合作基础的对策问题。当然，这里还存在着一个留待解决而又十分关键的问题：如何分享总获利，如果不能达到一个双方（或各方）都能接受的,“,公平,”,的分配原则，则合作仍然不能实现。怎样建立一个,“,公平,”,的分配原则是一个较为困难的问题，将在第九章中介绍。,30,定义,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,中,列的最优关系也有类似的结果。,31,利用这一定理，有时对策问题可先进行化简，降低矩阵的阶数。,现在回过来讨论美、德军队对策问题。在,Bradleg,构造的矩阵中容易发现,a,1,j,a,3,j,j,=1,2,故,3,优于,1,。,根据上面的定理,8.5,，可划去该矩阵的第一行，得到,22,赢得矩阵,这仍然是一个无鞍点的对策矩阵。设,Bradley,以概率,p,1,取策略,2,而以概率,p,2,取略,3,，则应有,解得,32,8.2,决策问题,人们在处理问题时，常常会面临几种可能出现的自然情况，同时又存在着几种可供选择的行动方案。此时，需要决策者根据已知信息作决策，即选择出最佳的行动方案，这样的问题称为决策问题。面临的几种自然情况叫做自然状态或简称状态。状态是客观存在的，是不可控因素。可供选择的行动方案叫做策略，这是可控因素，选择哪一方案由决策者决定。,33,例,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,）,自然状态,概率,收益,方案,问：决策者应如何作出决策？,34,解：由题意可以看出，决策问题应包含三方面信息：状态集合,Q,=,1,n,、策略集合,A,=,1,m,及收益,R,=,a,ij,，其中,a,ij,表示如果决策者选取策略,i,而出现的状态为,j,，则决策者的收益值为,a,ij,（当,a,ij,为负值时表示损失值）。,决策问题按自然状态的不同情况，常被分为三种类型：确定型、风险型（或随机型）和不确定型。,确定型决策是只存在一种可能自然状态的决策问题。这种决策问题的结构较为简单，决策者只需比较各种方案，确定哪一方案最优即可。值得一提的是策略集也可以是无限集，例如，线性规划就可行看成一个策略集是限集的确定型决策，问题要求决策者从可行解集合（策略集）中挑选出最优解。确定型决策的求解并非全是简单的，但由于这些问题一般均有其自己的专门算法，本节不准备再作介绍。在本节中，我们主要讨论风险型与不确定型决策，并介绍它们的求解方法。,35,一、风险型决策问题,在风险型决策问题中存在着两种以上可能出现的自然状态。决策者不知道究竟会出现哪一种状态，但知道各种状态出现的概率有多大。例如，例,8.8,就是一个风险型决策问题。,对于风险型决策问题，最常用的决策方法是期望值法，即根据各方案的期望收益或期望损失来评估各方案的优劣并据此作出决策。如对例,1,，分别求出方案,1,（钻井）和,2,（不钻井）的期望收益值：,E,（,1,）,=0.2,（,30,）,+0.520+0.340=16,（万元）,E,（,2,）,=0,由于,E,（,1,）,E,（,2,），选取,1,作为最佳策略。,风险型决策也可采用期望后悔值法求解。首先，求出采取方案,i,而出现状态,j,时的后悔值 。,36,例如，如果不钻井，但事实上该处可开出一口高产井，则后悔值为,40,。因为钻井可收益,40,万元，但决策者作了不钻井的决策，未获得本来可以获得的,40,万元收益。然后，比较各方案的期望后悔值，选取期望后悔最小的方案作为最佳策略。在例,8.8,中，如采用期望后悔值法，则,E,（,1,）,=6,，,E,（,2,）,=22,，取,1,为最佳策略。,在选取策略,i,而出现状态,j,时后悔值为 的理由是在,出现状态,j,情况下的最大可能收益为 。,定理,8.6,最大期望收益法与最小期望后悔值法等价，即两者选出的最佳,策略相同。,证明：由 得,故,等式（,8.4,）的右端项为一常数，其左端项为采取策略,i,时期后悔值与期望收益值之和，从而，若某策略使期望收益最大，则该策略必使期望后悔值最小，定理得证。,37,对于较为复杂的决策问题，尤其是需要作多阶段决策的问题，常采用较直观的决策树方法，但从本质上讲，决策树方法仍然是一种期望值法。,例,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,元。,38,如遇大风暴，也有两个方案可供选择：（,i,）维持正常速度施工，支付工程延期损失费,50000,元。（,ii,）采取应急措施。实施此应急措施也有三种可能结果：有,70%,可能减少误工期,2,天，支付应急费及误工费共,54000,元；有,20%,可能减少误工期,3,天，支付应急费及误工费共,46000,元；有,10%,可能减少误工期,4,天，支付应急费和误工费共,38000,元。,根据上述情况，试作出最佳决策使支付的额外费用最少。,解：由于未来的天气状态未知，但各种天气状况出现的概率已知，本例是一个风险型决策问题，所谓的额外费用应理解为期望值。,本例要求作多次决策，工程初期应决定是按正常速度施工还是提前紧急加班。如按正常速度施工，则,15,天后还需根据天气状况再作一次决策，以决定是否采取应急措施，故本例为多阶段（两阶段）决策问题。为便于分析和决策，采用决策树方法。,根据题意，作决策树如图,8.6,39,图,8.6,中，表示决策点，从它分出的分枝称为方案分枝，分枝的数目就是方案的个数。表示机会节点，从它分出的分枝称为概率分枝，一条概率分枝对应一条自然状态并标有相应的发生概率。称为未梢节点，右边的数字表示相应的收益值或损失值。,40,在决策树上由右向左计算各机会节点处的期望值，并将结果标在节点旁。遇到决策点则比较各方案分枝的效益期望值以决定方案的优劣，并且用双线划去淘汰掉的方案分枝，在决策点旁标上最佳方案的效益期望值，计算步骤如下：,（,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,点旁。,41,（,4,）在第二级决策点,A,处进行方案比较，划去提前紧急加班，将,14900,标在,A,点旁。,结论 最佳决策为前,15,天按正常速度施工，,15,天后按实际出现的天气状况再作决定。如出现阴雨天气，仍维持正常速度施工；如出现小风暴，则采取应急措施；如出现大风暴，也按正常速度施工，整个方案总损失的期望值为,14900,元。,根据期望值大小决策是随机型决策问题最常用的办法之一。实际应用时应根据具体情况作出分析，选取期望收益最大或期望损失最小的方案。,42,二、不确定型决策问题,只知道有几种可能自然状态发生，但各种自然状态发生的概率未知的决策问题称为不确定型决策问题，由于概率未知，期望值方法不能用于这类决策问题。下面结合一个例子，介绍几种处理这类问题的方法。,例,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,自然状态,方案,43,（,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,则对应于悲观法。,44,（,4,）等可能法（,Laplace,准则）,由于不能估计各状态出现的概率，决策者认为它们相差不会过大。此时，决策者采用将各状态的概率取成相同值的办法把问题转化为风险型，并借用风险型问题的期望值法来决策。对于例,8.10,，如取各状态出现的概率均为,0.2,，用期望值法决策，将选取策略,2,。,不难看出，对于不确定型决策问题，不论采用什么方法决策，最终采用的策略都不能称为最佳策略。事实上，采取什么方法决策与决策者的心理状态有关。而且，即使对同一决策者，在处理不同决策问题时也可能采取不同的方法。例如，在决定购买几元钱一张的对奖券时，决策者也许会采用乐观法。因为几元钱的损失对他来讲是无所谓的事，小额奖金他也许看不上眼，要中就来个大奖。但是，在决策购买何种股票时，因为关系重大，也许他为了保险又会采取悲观法。同而，不确定型问题的决策充其量只能算是在决策者某种心理状态下的选优。要作出较符合实际情况的决策，还需决策者多作些调查研究，以便对未来自然状态的出现作出较符合客观实际的预测，才能收到较好的效果。,45,例,8.11,（离散报童模型）设某商品的需求量,为离散变量，其取值范围为,Q,=,1,n,，取值,i,的概率为,P,(,i,),，,=1,。记该商品的进货量为 （决策变量），若,，进货过量，每单位进货过剩将造成,k,0,元过量损失；反之，若,，进货不足，每单位进货不足将造成,k,u,元的不足损失。试确定该商品的最佳进货量。,解：当 时，将有过量损失,k,0,（）；当,0,，,（,ii,）（,i,j,=1,2,n,），,则称之为正互反矩阵（易见,a,ii,=1,i,=1,n,）。,关于如何确定,a,ij,的值，,Saaty,等建议引用数字,19,及其倒数作为标度。他们认为，人们在成对比较差别时，用,5,种判断级较为合适。即使用相等、较强、强、很强、绝对地强表示差别程度，,a,ij,相应地取,1,3,5,7,和,9,。在成对事物的差别介于两者之间难以定夺时，,a,ij,可分别取值,2,、,4,、,6,、,8,。,55,从心理学观点来看，分级太多会超越人们的判断能力，既增加了作判断的难度，又容易因此而提供虚假数据。,Saaty,等人还用实验方法比较了在各种不同标度下人们判断结果的正确性，实验结果也表明，采用,19,标度最为合适。,如果在构造成对比较判断矩阵时，确实感到仅用,19,及其倒数还不够理想时，可以根据情况再采用因子分解聚类的方法，先比较类，再比较每一类中的元素。,步,3,层次单排序及一致性检验,上述构造成对比较判断矩阵的办法虽能减少其他因素的干扰影响，较客观地反映出一对因子影响力的差别。但综合全部比较结果时，其中难免包含一定程度的非一致性。如果比较结果是前后完全一致的，则矩阵,A,的元素还应当满足：,i,、,j,、,k,=1,2,n,56,定义,8.5,满足（,8.5,）关系式的正互反矩阵称为一致矩阵。,如前所述，如果判断者前后完全一致，则构造出的成对比较判断矩阵应,当是一个一致矩阵。但构造成对比较判断矩阵,A,共计要作,次比较（设有,n,个因素要两两比较），保证,A,是正互反矩阵是较容易办到的，但要求所有比较结果严格满足一致性，在,n,较大时几乎可以说是无法办到的，其中多少带有一定程度的非一致性。更何况比较时采用了,19,标度，已经接受了一定程度的误差，就不应再要求最终判断矩阵的严格一致性。如何检验构造出来的（正互反）判断矩阵,A,是否严重地非一致，以便确定是否接受,A,，并用它作为进一步分析研究的工具？,Saaty,等人在研究正互反矩阵和一致矩阵性质的基础上，找到了解决这一困难的办法，给出了确定矩阵,A,中的非一致性是否可以允忍的检验方法。,57,定理,8.7,正互反矩阵,A,的最大特征根,max,必为正实数，其对应特征向量的所有分量均为正实数。,A,的其余特征根的模均严格小于,max,。（证明从略）,现在来考察一致矩阵,A,的性质，回复到将单位重量的大石块剖分成重量为,1,n,的,n,块小石块的例子，如果判断者的判断结果完全一致，则构造出来的一致矩阵为,容易看出，一致矩阵,A,具有以下性质：,58,定理,8.8,若,A,为一致矩阵，则,（,1,）,A,必为正互反矩阵。,（,2,）,A,的转置矩阵,A,T,也是一致矩阵。,（,3,）,A,的任意两行成比例，比例因子（即,w,i,/w,j,）大于零，从而,rank,（,A,）,=1,（同样，,A,的任意两列也成比例）。,（,4,）,A,的最大特征根,max,=,n,，其中,n,为矩阵,A,的阶。,A,的其余特征根均为零。,（,5,）若,A,的最大特征根,max,对应的特征向量为,W,=,（,w,1,w,n,）,I,，则,a,ij,=w,i,/w,j,，,i,j,=1,2,n,。,（注：（,1,）、（,2,）可由一致矩阵定义得出，（,3,）,（,5,）均容易由线性代数知识得到，证明从略）。,59,定理,8.9,n,阶正互反矩阵,A,为一致矩阵当且仅当其最大特征根,max,=,n,，且当正互反矩阵,A,非一致时，必有,max,n,。,证明：,设正互反矩阵,A,的最大特征根为,max,，,对应的特征向量为,W,=,（,w,1,w,n,）,T,。,由定理，,max,0,且,w,i,0,，,i,=1,，,，,n,。又由特征根和特征向量的性质知，,AW,=,max,W,故,i=1,n,(8.7),（,8.7,）式两边同除,w,i,且关于,i,从,1,到,n,相加，得到,即,（,8.8,）式的括号内共有,项。,（,8.8,）,60,现证明必要性，由一致矩阵性质（,5,），有 ，,故由（,8.8,）式，得,max,=,n,。,再证明充分性。由于,(8.9),当且仅当,=1,（即 ）时（,8.9,）式中的等号成立，,故由（,8.8,）式,max,=,n,。因而当,max,=,n,时必有,=1,，,于是,a,ij,a,jk,=,a,ik,i,j,k,=1,2,n,成立，,A,为一致矩阵。,当,A,非一致矩阵时，（,8.9,）式中的等号不能对一切,i,，,j,成立，从而必有,max,n,。,61,根据定理,8.9,，我们可以由,max,是否等于,n,来检验判断矩阵,A,是否为一致矩阵。由于特征根连续地依赖于,a,ij,，故,max,比,n,大得越多，,A,的非一致性程度也就越为严重，,max,对应的标准化特征向量也就越不能真实地反映出,X,=,x,1,x,n,在对因素,Z,的影响中所占的比重。因此，对决策者提供的判断矩阵有必要作一次一致性检验，以决定是否能接受它。,为确定多大程度的非一致性是可以允忍的，,Saaty,等人采用了如下办法：,（,1,）求出 ，称,CI,为,A,的一致性指标。,容易看出，当且仅当,A,为一致矩阵时，,CI,=0,。,CI,的值越大，,A,的非一致性越严重。利用线性代数知识可以证明，,A,的,n,个特征根之和等于其对角线元素之和（即,n,）故,CI,事实上是,A,的除,max,以外其余,n,1,个特征根的平均值的绝对值。若,A,是一致矩阵，其余,n,1,个特征根均为零，故,CI,=0,；否则，,CI,0,，其值随,A,非一致性程度的加重而连续地增大。当,CI,略大于零时（对应地，,max,稍大于,n,），,A,具有较为满意的一致性；否则，,A,的一致性就较差。,62,（,2,）上面定义