决策理论与方法教学第四章课件

,决策理论与方法,第,*,页,Click to edit Master text styles,Second Level,Third Level,Fourth Level,Fifth Level,Click to edit Master title style,第,*,页,决策理论与方法,（,Decision Making Theory and Methods,）,决策理论与方法,编写组,教育部高等学校管理科学与工程类学科专业教学指导委员会推荐教材,第四章 动态决策分析,学习目的,了解多阶段决策、序贯决策的概念及特点；,掌握动态规划与决策树方法及其在多阶段决策、序贯决策中的应用。,本讲内容,4.3,序贯决策,4.3.1,序贯决策的基本概念,4.3.2,序贯决策的决策方法,4.3,序贯决策,4.3.1,序贯决策的基本概念,上面的多阶段决策，阶段数是确定的。除这种决策外，还有一些决策的阶段数不是事先确定的，它依赖于执行决策过程中出现的情况。这种决策问题称为序贯决策（,sequential decision problem,）。,序列决策在进行决策后又产生一些新的情况，需要进行新的决策，接着又有一些新的情况，又需要进行新的决策。这样决策、情况、决策,，这就构成一个序列。,4.3,序贯决策,4.3.1,序贯决策的基本概念,序贯决策是用于随机性或不确态定性动态系统最优化的决策方法。它的特点是：,1,）所研究的系统是动态的，即系统所处的状态与时间有关，可周期（或连续）地对它观察；,2,）决策是序贯地进行的，即每个时刻根据所观察到的状态和以前状态的记录，从一组可行方案中选用一个最优方案（即作最优决策），使取决于状态的某个目标函数取最优值（极大或极小值）；,3,）系统下一步,(,或未来,),可能出现的状态是随机的或不确定的。,4.3,序贯决策,4.3.1,序贯决策的基本概念,系统在每次作出决策后下一步可能出现的状态是不能确切预知的，存在两种情况：,1,）系统下一步可能出现的状态的概率分布是已知的，可用客观概率的条件分布来描述。对于这类系统的序贯决策研究得较完满的是状态转移律具有无后效性的系统，相应的序贯决策称为马尔可夫决策过程，它是将马尔可夫过程理论与决定性动态规划相结合的产物。,2,）系统下一步可能出现的状态的概率分布不知道，只能用主观概率的条件分布来描述。用于这类系统的序贯决策属于决策分析的内容。,4.3,序贯决策,4.3.2,序贯决策的决策方法,序贯决策的过程是：从初始状态开始，每个时刻做出最优决策后，接着观察下一步实际出现的状态，即收集新的信息，然后再做出新的最优决策，反复进行直至最后。,解决序贯决策问题的有效办法仍然是决策树，解决序贯决策的关键是确定一个决策序列终止的原则。在下例中，这个原则就是：不管到决策的哪个阶段，只要有一个非经抽样的后悔期望值小于进行一次抽样的费用，决策序列便可终止。,4.3,序贯决策,4.3.2,序贯决策的决策方法,例,4-3-1,某工厂的产品每,1000,件装成一箱出售。每箱中产品的次品率有,0.01,，,0.40,，,0.90,三种可能，其概率分别为,0.2,，,0.6,，,0.2,。现在的问题是：出厂前是否要对产品进行严格检验，将次品挑出。可以选择的行动有两个：整箱检验,(,a,1,),，检验费 为每箱,100,元；整箱不检验,(,a,),，但如果顾客在使用中发现次品，每件次品除条换为合格品外还要赔偿,0.25,元损失费。,4.3,序贯决策,为了更好地做出决定可以先从一箱中随机抽取,1,件作为样本检验它，然后根据这件产品是都次品再决定该箱是否要检验，抽样成本为,4.2,元。进行第一次抽样后，除选择检验还是不检验外，还可以根据前面抽样的结果，考虑再进行一次抽样检验如此形成一个决策序列。,试,进行序列决策：,（,1,）是否需要抽样？（若需要，抽样几次？）,（,2,）在抽样或不抽样的前提下，采用何种方案进行检验？,【,例,8.2】,解：,1,，,2,，,3,分别表示产品次品率为,0.01,，,0.4,，,0.9,三种状态。对于抽样检验一件产品，,X,=1,和,X,=0,分别表示样品为次品和合格品两个结果。结果值均用期望损失值表示。,序列决策树图不能够一次绘制成功，而是随着决策过程序列的延伸和终止依次进行。为了简化图形，行动方案,a,l,和,a,2,可能出现的状态及其对应的损失值均在图中略去，仅在方案枝末端标注上期望损失值。,4,5,3,2,8,6,7,抽样,继续抽样,a,1,a,2,A,1,A,2,A,3,A,4,不抽样,X,1,=0,X,1,=1,停止抽样,9,X,2,=0,X,2,=1,a,1,a,2,继续抽样,停止抽样,（略）,相应的损失矩阵为,先进行第一次抽样的后验概率计算,该问题的费用矩阵为：,【,例,8.2】,第一次抽样的后验概率矩阵为,后验行动方案的期望损失值矩阵为,一次抽样后最满意方案分别为：,6.89,4.325,0.4582,19.5,2.69,33.40,4.325,0.4582,53.31,19.5,25,抽样,a,1,a,2,a,1,a,2,a,1,a,2,A,1,A,2,A,3,A,4,S,1,S,2,不抽样,X,1,=0,X,1,=1,0.578,0.422,0.3426,0.6228,0.0346,0.3426,0.5687,0.4265,0.0047,0.5687,0.4265,0.2,0.6,0.2,0.0047,0.5687,0.4265,0.2,0.2,0.6,97.5,0,0,0,0,125,97.5,0,0,0,0,125,97.5,0,0,0,0,125,期望损失值,(,包含抽样费用,),4.20,若为正品，则无须检验整箱产品；,若为次品，则整箱检验。,最满意方案是，应抽取一件产品作样品检验。,在,A,2,上,X,1,=1,的决策点处，由于行动方案,a,1,的期望损失值,0.4582,已小于抽样费用,4.20,，所以第二次抽样分支,S,2,在此处被截断，决策序列在该分支上终止。,而在,X,l,0,的决策点处，由于行动方案,a,l,，,a,2,。的期望损失值分别为,33.40,和,4.324,，均大于抽样费用,4.20,，因此，在此分支上，可进行第二次抽样，抽样结果用,X,2,表示。,X,2,0,和,X,2,=1,分别表示第二次抽样抽取一个样品为正品和次品。,第二次抽样的后验概率计算如下,：,第二次抽样的,后验概率矩阵为,后验行动方案的期望损失值矩阵为,二次抽样后最满意方案分别为：,由于,X,2,=0,在的决策点处，方案,a,2,的期望损失值,0.6038,已小于抽样费用,4.20,，则序列决策的这一分支应该终止。同样，对于,X,2,=1,决策点处，由于方案,a,1,的期望损失值,1.1778,也小于抽样费用，则这一分枝也应终止。于是，到此决策序列全部终止。,4.20,a,1,a,2,s,1,a,1,a,2,s,2,X,1,=0,25,33.4,4.325,4.20,19.5,0.578,a,1,a,2,s,3,X,2,=0,46.17,0.6038,4.20,0.7163,a,1,a,2,s,3,X,1,=1,13.73,4.20,0.2837,1.1778,a,1,a,2,s,2,X,1,=1,13.73,4.20,0.422,0.4582,A,1,A,2,A,3,S,1,S,2,6.89,2.69,4.325,0.4582,0.7666,4.325,1.1778,在,A,3,上,X,2,=0,的决策点处，最满意行动方案为,a,2,，截去,a,1,和,s,3,；,在,X,2,=1,的决策点处，最满意行动方案为,a,1,，截去,a,2,和,s,3,。,在,s,2,状态点处，期望损失值为：,在,A,2,上,X,1,=0,的决策点处，最满意行动方案为,a,2,，截去,a,1,和,s,2,；,在,X,1,=1,的决策点处，最满意行动方案为,a,1,，截去,a,2,和,s,2,。,在,s,1,状态点处，期望损失值为：,在,A,1,决策点处，最满意方案的期望损失值为：,所以截去,a,1,和,a,2,。,综上所述，决策是：应该进行一次抽样检验。,若为正品，则采取行动方案,a,2,，即整箱产品不予检验；,若为次品，则采取行动方案,a,1,，即整箱产品予以检验，序列决策过程也可以用简化决策树图表示。,6.89,2.69,4.20,4.325,0.4582,s,1,0.578,0.422,a,1,a2,4.325,0.4621,4.4,马尔可夫决策,研究这样的一类决策问题：,采取的行动已经确定，但将这个行动付诸实践的过程又分为几个时期。在不同的时期，系统可以处在不同的状态，而这些状态发生的概率又可受前面时期实际所处状态的影响。,其中一种最简单、最基本的情形，是每一时期状态参数的概率分布只与这一时期的前一时期实际所处的状态有关，而与更早的状态无关，这就是所谓的马尔可夫链。,4.4,马尔可夫决策,4.4.1,马尔可夫决策问题,马氏过程,马尔科夫（,M.A.Markov,）提出一种描述系统状态转移的数学模型，称为马尔科夫过程，简称马氏过程。,马氏决策,利用马氏过程分析系统当前状态并预测未来状态的决策方法，称为马尔科夫决策，简称马氏决策。,4.4,马尔可夫决策,4.4.2,马尔可夫链与转移概率矩阵,若随机过程,X,(,t,),t,T,，对于任意的,t,1,t,2,t,n,，,t,i,T,都有,P,x,(,t,n,),y,|,x,(,t,n,-1,)=,x,n,-1,x,(,t,1,)=,x,1,=,P,x,(,t,n,),y,|,x,(,t,n,-1,)=,x,n,-1,则称,X,(,t,),t,T,具有马尔可夫性。,含义：,x,(,t,n,),的将来只是通过现在与过去发生联系，一旦现在已知，则将来与过去无关。,4.4.2,马尔可夫链与转移概率矩阵,条件概率,P,x,n,=j|x,n,-1,=i,称为转移概率，表示系统在,n,-1,步状态为,i,时，第,n,步状态为,j,的概率,一,步转移概率,。,若一步转移概率不随时间变化,(,具有稳定性,),记,p,ij,P,x,n,=j|x,n,-1,=i,，称矩阵,P,(,p,ij,),为转移概率矩阵。,其中：,4.4.2,马尔可夫链与转移概率矩阵,马尔可夫链定义,如果随机过程,X,t,t,=1,2,，满足下述性质，则称,X,t,是一个有限状态的马尔可夫（,Markov,）链。,（,1,）具有有限种状态；,（,2,）具有马尔可夫性；,（,3,）转移概率具有平稳性。,4.4,马尔可夫决策,例：,某企业为使技术人员具有多方面经验，实行技术人员在技术部门、生产部门和销售部门的轮换工作制度。轮换办法采取随机形式，每半年轮换一次。初始状态，即技术人员开始是在某部门工作的概率用,P,j,(0),表示，,j,1,，,2,，,3,；,p,ij,表示处于第,i,个部门的技术人员在半年后转移到第,j,个部门的概率。,4.4,马尔可夫决策,已知：,问某人开始在第,1,部门工作，一年后在第,2,部门工作的概率是多少？一年后，技术人员在,3,个部门工作的概率各为多少？,4.4,马尔可夫决策,解：,由状态,1,经过两次转移到状态,2,的所有途径为,112,，,122,，,132,记由状态,i,经两步转移到状态,j,的概率为，则：,若某人开始在第一部门工作，则一年后在第二部门工作的概率是,50%,。,4.4,马尔可夫决策,解：,记一年后技术人员在第,j,个部门工作的概率为,P,j,(2),，则：,一年后，技术人员在,3,个部门工作的概率,4.4,马尔可夫决策,由上例可看出,从而有,一般地，有,4.4,马尔可夫决策,4.4.3,稳态概率,为稳态概率。,由于初始状态对,n,步转移后所处状态的影响随,n,增大而减少，故：,因此我们可以从,n,步转移矩阵的 极限取得稳态概率分布,称,4.4,马尔可夫决策,得,且,此方程组称为稳态方程。,记,则,4.4.4,马尔可夫应用