第八章-序贯决策

《第八章-序贯决策》由会员分享，可在线阅读，更多相关《第八章-序贯决策（97页珍藏版）》请在金锄头文库上搜索。

1、第八章 序贯决策分析,广西大学数学与信息科学学院 运筹管理系,8.1 多阶段决策,8.1.1 多阶段决策问题 决策过程比较复杂； 需要将过程分为若干个相互联系的阶段，分别对每阶段都做出决策； 各阶段的决策结果前后相互衔接，彼此相互关联，前阶段决策结果影响后阶段决策目标，后阶段决策状态又依赖于前阶段状态设置； 各个阶段决策形成一个完整的决策过程（序列）；,8.1 多阶段决策,8.1.1 多阶段决策问题 决策者关心的是整个决策过程的总体效应，而不单是各阶段的决策结果。 总之，若一个决策问题需要经过相互衔接、相互关联的若干阶段决策才能完成，则自然称之为多阶段决策。,8.1 多阶段决策,8.1.2 多

2、阶段决策方法及其应用实例 多阶段决策分析的步骤 适当地划分阶段； 确定各阶段的状态变量，寻找各阶段之间的联系； 从后到前用逆序归纳法进行决策分析，每一阶段决策可采用各种单阶段决策方法。 主要方法是决策树方法和动态规划方法。,8.1 多阶段决策,例8.1 某企业考虑是否花费1万元购买某新产品专利。若购买了专利，可进行大批生产(a1)、中批生产(a2) 或小批生产(a3)，可能出现的市场销售情况也分为畅销(1)、一般(2)和滞销(3 )三种。其收益（利润，万元）矩阵如下表：,例8.1,为了更正确地掌握市场情况，正式投产公司打算先生产少量产品试销，试销费需要5000元。试销结果分为产品受欢迎(H1)

3、，一般(H2)和不受欢迎(H3)三种。 由于试销面不宽，试销结果的准确性有限。 其准确度（似然分布矩阵）见下表：,例8.1,如不买此项专利，把这笔费用用在其他方面，在同样的时期可获利1.1万元。那么，该公司应该如何决策？ （1）是否买专利？ （2）如果买专利，是否采取试销办法？ （3）如果不试销，应大批生产，中批生产还是小批生产？如果试销，又应该如何根据试销结果决定其行动？,第一阶段,1,2,7,买专利,不买专利,试销,不试销,3,4,5,6,H1,H2,H3,8,9,10,a1,a2,a3,1,2,3,（略）,第二阶段,第三阶段,例8.1,例8.1,解：这是一个三阶段决策问题，采用逆序归纳法

4、进行决策分析，先要计算在一定的试销结果下的各后验概率。由全概率公式：,计算得：,例8.1,再由贝叶斯公式：,计算得：,例8.1,当试销结果为 H1时：,故当试销结果为 H1时，应选择大批生产a1，截去方案a2、a3，结点4的值为3.406万元。,-结点8,-结点9,-结点10,例8.1,当试销结果为 H2时：,故当试销结果为 H2时，应选择中批生产a2，截去方案a1、a3 ，结点5的值为2.62万元 。,例8.1,当试销结果为 H3时：,故当试销结果为 H3时，也应选择中批生产a2，截去方案a1、a3 ，结点6的值为1.53万元 。,例8.1,试销收益期望值：,故当不试销时，应选择大批生产a1

5、，截去方案a2、a3 ，结点7的值为2.7万元。,不试销的收益期望值：,-结点3,例8.1,决策：（1）购买专利； （2）不试销； （3）大批生产a2。,购买专利总期望收益2.711.7万元，大于不买技术的收益1.1万元，截去不买专利方案，结点1的值为1.7万元 。,试销收益期望值扣除试销费用5000元后小于不试销的收益值，截去试销方案，结点2的值为2.7万元。,第一阶段,1,2,7,买专利,不买专利,试销,不试销,3,4,5,6,H1 0.44,H2 0.39,H3 0.17,8,9,10,a1,a2,a3,0.818,0.136,0.046,（略）,第二阶段,第三阶段,例8.1,4万元,2

6、万元,3万元,1.1万元,3.406万,2.77万,1万,3.406万,2.62万,1.53万,2.78054万,-0.5万,2.7万,2.7万,-1万,1.7万,8.1 多阶段决策,有一类多阶段决策问题，在进行决策后又产生一些新情况，需要进行新的决策，接着又有一些新的情况，又需要进行新的决策。这样决策、情况、决策，就构成一个序列，这就是序列决策。 特点：决策次数事前并不明确，决策阶段划分次数依赖于决策过程中出现的特殊状况。 仍可用决策树法解这类问题，关键是：确定一个决策序列终止的原则。,【例8.2】,某厂家的产品装箱出厂，每箱有产品1000件，产品的次品率有0.01，0.40，0.90三种可

7、能，相应概率分别为 0.2，0.6，0.2。有两种产品检验方案： 整箱检验(a1)，检验费100元； 不作整箱检验(a)，在销售中若顾客发现次品，允许调换并赔偿，每件损失0.25元。,【例8.2】,为了更好地选择检验方案，可先从任意一箱中随机地抽取一件产品作为样品。 第一次抽样后，可继续进行第二次、第三次等若干次抽样，每次抽样成本均为4.2元，样本容量均为1。 试进行序列决策： （1）是否需要抽样？（若需要，抽样几次？） （2）在抽样或不抽样的前提下，采用何种方案进行检验？,【例8.2】,解： 1，2，3分别表示产品次品率为 0.01 ，0.4，0.9三种状态。对于抽样检验一件产品，X=1和X

8、=0分别表示样品为次品和合格品两个结果。结果值均用期望损失值表示。 序列决策树图不能够一次绘制成功，而是随着决策过程序列的延伸和终止依次进行。为了简化图形，行动方案al和a2、可能出现的状态及其对应的损失值均在图中略去，仅在方案枝末端标注上期望损失值。,4,5,3,2,8,6,7,抽样,继续抽样,a1,a2,A1,A2,A3,A4,不抽样,X1=0,X1=1,停止抽样,9,X2=0,X2=1,a1,a2,继续抽样,停止抽样,（略）,【例8.4】,相应的损失矩阵为,先进行第一次抽样的后验概率计算,该问题的费用矩阵为：,【例8.2】,【例8.2】,第一次抽样的后验概率矩阵为,【例8.2】,后验行动

9、方案的期望损失值矩阵为,一次抽样后最满意方案分别为：,6.89,4.325,0.4582,19.5,2.69,33.40,4.325,0.4582,53.31,19.5,25,抽样,a1,a2,a1,a2,a1,a2,A1,A2,A3,A4,S1,S2,不抽样,X1=0,X1=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,

10、0,0,0,0,125,期望损失值(包含抽样费用),4.20,若为正品，则无须检验整箱产品； 若为次品，则整箱检验。,最满意方案是，应抽取一件产品作样品检验。,【例8.2】,在A2上X1=1的决策点处，由于行动方案a1的期望损失值0.4582已小于抽样费用4.20，所以第二次抽样分支S2在此处被截断，决策序列在该分支上终止。 而在Xl0的决策点处，由于行动方案al，a2。的期望损失值分别为33.40和4.324，均大于抽样费用4.20，因此，在此分支上，可进行第二次抽样，抽样结果用X2表示。 X20和X2=1分别表示第二次抽样抽取一个样品为正品和次品。,【例8.2】,第二次抽样的后验概率计算如

11、下：,【例8.2】,【例8.2】,第二次抽样的 后验概率矩阵为,后验行动方案的期望损失值矩阵为,二次抽样后最满意方案分别为：,【例8.2】,由于X2=0在的决策点处，方案a2的期望损失值0.6038已小于抽样费用4.20，则序列决策的这一分支应该终止。同样，对于X2=1决策点处，由于方案a1的期望损失值1.1778也小于抽样费用，则这一分枝也应终止。于是，到此决策序列全部终止。,【例8.2】,4.20,a1,a2,s1,a1,a2,s2,X1=0,25,33.4,4.325,4.20,19.5,0.578,a1,a2,s3,X2=0,46.17,0.6038,4.20,0.7163,a1,a2

12、,s3,X1=1,13.73,4.20,0.2837,1.1778,a1,a2,s2,X1=1,13.73,4.20,0.422,0.4582,A1,A2,A3,S1,S2,6.89,2.69,4.325,0.4582,0.7666,4.325,1.1778,【例8.2】,在A3上 X2=0的决策点处，最满意行动方案为a2 ，截去a1和 s3； 在 X2=1的决策点处，最满意行动方案为 a1，截去 a2和 s3。 在 s2状态点处，期望损失值为：,【例8.2】,在A2上 X1=0的决策点处，最满意行动方案为a2 ，截去a1和 s2； 在 X1=1的决策点处，最满意行动方案为 a1，截去 a2和

13、 s2。 在 s1状态点处，期望损失值为：,在A1决策点处，最满意方案的期望损失值为：,所以截去a1和a2。,【例8.2】,综上所述，决策是：应该进行一次抽样检验。 若为正品，则采取行动方案a2，即整箱产品不予检验； 若为次品，则采取行动方案a1，即整箱产品予以检验，序列决策过程也可以用简化决策树图表示。,6.89,2.69,4.20,4.325,0.4582,s1,0.578,0.422,a1,a2,4.325,0.4621,8.2 马尔可夫决策,研究这样的一类决策问题： 采取的行动已经确定，但将这个行动付诸实践的过程又分为几个时期。在不同的时期，系统可以处在不同的状态，而这些状态发生的概率

14、又可受前面时期实际所处状态的影响。 其中一种最简单、最基本的情形，是每一时期状态参数的概率分布只与这一时期的前一时期实际所处的状态有关，而与更早的状态无关，这就是所谓的马尔可夫链。,8.2 马尔可夫决策,8.2.1 马尔可夫决策问题 马氏过程 马尔科夫（ M . A . Markov ）提出一种描述系统状态转移的数学模型，称为马尔科夫过程，简称马氏过程。 马氏决策 利用马氏过程分析系统当前状态并预测未来状态的决策方法，称为马尔科夫决策，简称马氏决策。,8.2 马尔可夫决策,8.2.2 马尔可夫链与转移概率矩阵 若随机过程X(t), tT，对于任意的 t1t2tn，tiT 都有 Px(tn)y

15、| x(tn-1)=xn-1, , x(t1)=x1 =Px(tn)y | x(tn-1)=xn-1 则称X(t), tT具有马尔可夫性。 含义：x(tn)的将来只是通过现在与过去发生联系，一旦现在已知，则将来与过去无关。,8.2.2 马尔可夫链与转移概率矩阵,条件概率Pxn=j | xn-1=i 称为转移概率，表示系统在n-1步状态为i时，第n步状态为j的概率一步转移概率。 若一步转移概率不随时间变化(具有稳定性),记 pijPxn=j | xn-1=i ，称矩阵P(pij )为转移概率矩阵。 其中：,8.2.2 马尔可夫链与转移概率矩阵,马尔可夫链定义 如果随机过程Xt, t=1,2, ，满足下述性质，则称Xt是一个有限状态的马尔可夫（Markov）链。 （1）具有有限种状态； （2）具有马尔可夫性； （3）转移概率具有平稳性。,8.2 马尔可夫决策,例： 某企业为使技术人员具有多方面经验，实行技术人员在技术部门、生产部门和销售部门的轮换工作制度。轮换办法采取随机形式，每半年轮换一次。初始状态，即技术人员开始是在某部门工作的概率用Pj(0)表示，j1，2，3；pij表示处于第i个部门的技术人员在半年后转移到第j个部