决策树网络计划动态规划参考.ppt

1、第 四 章决策分析方法,4.1 管理决策概述,一、基本概念 定义 决策：它是决策者对系统方案所作决定的过程和结果，是决策者的行为和职责。,管理决策分析就是为帮助决策者在多变的环境条件下进行正确决策而提供的一套推理方法、逻辑步骤和具体技术，以及利用这些技术和方法选择满意的行动方案的过程。,决策分析的过程 问题分析、诊断及信息活动。 对目标、准则及方案的设计活动。 对非劣备选方案进行综合分析、比较、评价的抉择活动。 将决策结果付诸实施并进行有效评估、反馈、跟踪、学习的实施活动,三、决策分析类型 1 确定型决策分析 存在决策者希望达到的明确目标 （收益大或损失小等）； 存在确定的自然状态；, 存在着

2、可供选择的两个以上的行动方案； 不同行动方案在确定状态下的益损值可以计算出来。,确定型决策分析问题求解方法： 在方案数量较大时，常用运筹学中规划论等方法来分析解决，如线性规划、目标规划。 严格来讲，确定型问题只是优化计算问题，而不属于真正的管理决策分析问题。,2风险型决策分析 存在决策者希望达到的明确目标（收益大或损失小）； 存在两个以上不以决策者主观意志为转移的自然状态，但决策者或分析人员根据过去的经验和科学理论等可预先估算出自然状态的概率值P ；, 存在两个以上可供决策者选择的行动方案； 不同行动方案在确定状态下的益损值可以计算出来。,风险型决策分析问题求解方法： 期望值、矩阵法、决策树法

3、 风险型决策问题是一般决策分析的主要内容。在基本方法的基础上，应注意把握信息的价值及其分析和决策者的效用观等重要问题。,3不确定型决策 存在决策者希望达到的明确目的 （收益大或损失小）； 自然状态不确定，且其出现的概率不可知；, 存在两个以上可供决策者选择的行动方案； 不同行动方案在确定状态下的益损值可以计算出来。,不确定型决策分析问题的求解方法： 乐观法（最大最大原则）、 悲观法（最小最大原则）、 等概率法( Laplace 准则，也是一种特殊的风险型决策）、 后悔值法（SaVage准则或后悔值最大最小原则）。,案例：某企业准备生产一种新产品。估计该产品的销售量有较高、一般、较低、很低四种情

4、况，而对每种状态出现的概率则无法预测。为生产该产品，企业有三种实施方案：新建一个车间进行生产；改造一个现有车间进行生产；部分零件在现有车间生产，部分零件外购。该新产品企业准备生产10年，10年内在不同状态下的损益值（扣除投资费用）如下表所示。请分别用乐观法、悲观法和后悔值法来决策实施方案。,解： （1）乐观法 每个方案在不同状态下的最大收益分别为： max 850，420，-150，-400=850 A1 max 600,400,-100,-350=600 A2 max 400,250,90,-50=400 A3 取各方案最大收益值中的最大值，可得： max850，600，400=850 对应

5、实施方案为A1 ，即建新车间。,（2）悲观法 每个方案在不同状态下的最小收益分别为： min 850，420，-150，-400= -400 A1 min 600,400,-100,-350= -350 A2 min 400,250,90,-50= -50 A3 取各方案最小收益值中的最大值，可得： max-400，-350，-50 = -50 对应实施方案为A3 ，即部分自己生产，部分外购。,（3）后悔值法,最后，找出最小后悔值300，对应方案A2，即改造现有车间生产。,对于不确定型决策分析问题，若采用不同求解方法，则所得的结果也会有所不同，因为这些决策方法是各自从不同的决策准则出发来选择最

6、优方案的。而具体采用何种方法，又视决策者的态度或效用观而定，在理论上还不能证明哪种方法是最为合适的。,4对抗型决策 Wij = f(Ai,Bj) i=1,2,3m, j=1,2,n 式中A决策者的策略集； B竞争对手的策略集。 可采用对策论及其冲突分析等方法来分析解决。这类决策分析问题是当前管理、经济界比较关注的问题。,5多目标决策 由于系统工程所研究的大规模复杂系统一般具有属性及目标多样化的特点，在管理决策时通常要考虑多个目标，但它们在很多情况下又是相互消长或矛盾的，这就使得多目标决策分析在管理决策分析中具有了日益重要的作用。,多目标决策的理沦、方法与应用，在国际上是最近二三十年才得到蓬勃发

7、展的，目前分析该类决策问题的方法已有不少，常用方法有：化多目标为单目标的方法（含系统评价中的加权和及各种确定目标权重的方法）、重排次序法、目标规划法及层次分析（AHP ）方法等。,4.2 风险型决策分析,一、基本方法 期望值法 E(X)=pixi Xi 随机离散变量x的第i个取值， i=1,2,3m； pi x=xi时的概率,期望值法就是利用上述公式算出每个行动方案的益损期望值并加以比较。若采用决策目标准则是期望收益最大，则选择收益期望值最大的行动方案；反之，采用费用期望值最小的方案为最优。,案例一：某轻工企业要决定一轻工产品明年的产量，以便及早做好生产前的各项准备工作。假设产量的大小主要根据

8、该产品的销售价格好坏而定。根据以往市场销售价格统计资料及市场预测信息得知：未来产品销售价格出现上涨、价格不变和价格下跌三种状态的概率分别为0.3 , 0.6 和0.1 。,若该产品按大、中、小三种不同批量（即三种不同方案）投产，则下一年度在不同价格状态下的益损值可以估算出来，如表所示。现要求通过决策分析来确定下一年度的产量，使该产品能获得的收益期望为最大。益损值表如下图所示：,41,如何决策可以获得最大的投资收益？,这是一个面临三种自然状态和三种行动方案的风险型决策分析问题，可以利用前述的多种方法求解。 现运用期望值法求解如下：,( l）根据表41 所列各种自然状态的概率和不同行动方案的益损值

9、，可用公式 E(X)=pixi， 计算出每种行动方案的益损期望值 如下：,(2）通过计算并比较后可知，方案A2的数学期望E(A2) = 33.6万元，为最大，所以选择行动方案A2为最优方案。 也就是下一年度的产品产量按中批生产规模进行生产所获得的收益期望值最大。,决策树法 所谓决策树法，就是利用树形图模型来描述决策分析问题，并直接在决策树图上进行决策分析其决策目标（准则）。可以是益损期望值或经过变换的其他指标值。 现仍以前例为例介绍决策树法。,（1）绘制决策树。 按表41 所示各种行动方案和自然状态及其相应的益损值和主观概率等信息，按由左至右的顺序画出决策树图，如下图所示：,图42 决策树模型

10、,图中各节点的名称及含义如下： “ ”表示决策节点，从它引出的分枝叫做方案分枝。分枝数量与行动方案数量相同。如前例有三个行动方案，则图42 所示就有三个方案分枝。 决策节点表明，从它引出的行动方案需要进行分析和决策。,“ ”表示状态节点，从它引出的分枝叫做状态分枝或概率分枝，在每一分枝处注明自然状态名称及概率状态分枝数量与自然状态数量相同。,“ ”表示结果节点，即将不同行动方案在不同自然状态下的结果（如益损值）注明在结果节点的右端。,( 2 ）计算各行动方案的益损期望值，并将计算结果标注在相应的状态节点上 。 图43 所示为方案A2的益损期望值。,图43,(3）将计算所得的各行动方案的益损期望

11、值加以比较，选择其中最大的期望值并标注在决策节点上方，如图44 所示。,与最大期望值相对应的是方案A2, 则A2即为最优方案。然后，在其余的方案分枝上画上“| ”符号，表明这些方案已被舍弃，图44 所示即是一个经过决策分析选择行动方案A2为最优方案的决策树图。,图44 例41,多级决策树 从例41中可知，如果只需作一次决策，其分析求解即告完成，则这种决策分析问题就叫做单级决策。反之，有些决策问题需要经过多次决策才告完成，则这种决策问题就叫做多级决策问题。应用决策树法进行多级决策分析叫做多级决策树。,案例讨论：某化妆品公司生产BF 型号护肤化妆品。由于现有生产工艺比较落后，产品质量不易保证，且成

12、本较高，销路受到影响。若产品价格保持现有水平无利可图，若产品价格下降还要亏本，只是在产品价格上涨时才稍有盈利。,为此公司决定要对该产品生产工艺进行改进，提出两种方案以供选择：一是从国外引进一条自动化程度较高的生产线；二是自行设计一条有一定水平的生产线。,根据公司以往引进和自行设计的工作经验显示，引进生产线投资较大，但产品质量好，且成本较低，年产量大，引进技术的成功率为80。而自行设计生产线，投资相对较小，产品质量也有保证，成本也较低，年产量也大，但自行设计的成功率只有60。,进一步考虑到无论是引进或自行设计生产线，产量都可能增加。因此，公司生产部门又制定了两个生产方案：一是产量与过去相同（保持

13、不变）, 二是产量增加，为此又需要进行决策。最后，若引进或自行设计均不成功，公司只得仍采用原有生产工艺继续生产，产量自然保持不变。,公司打算该护肤化妆品生产5年。根据以往价格统计资料和市场预测信息，该类产品在今后5年内价格下跌的概率为0.1，保持原价的概率为0.5，而涨价的概率为0.4。通过估算，可得各种方案在不同价格状态下的益损值如下表所示。,表42 例42,讨论 如何决策才能获得最大的收益？,本例是个二级决策分析问题，今用多级决策树进行分析，其过程和结果如下图所示：,a,b,c,d,e,h,i,f,j,k,g,-250,80,200,-400,100,300,-100,0,125,-250

14、,0,250,-350,-250,650,-100,0,125,引进,设计,Success,Failed,Normal,Increase,Bad,Normal,Good,Bad,Normal,Good,Bad,Normal,Good,Bad,Normal,Good,Bad,Normal,Good,Bad,Normal,Good,Success,Failed,Normal,increase,0.8,0.2,0.6,0.4,0.1,0.5,0.4,0.1,0.5,0.4,0.1,0.1,0.1,0.1,0.5,0.4,0.5,0.4,0.5,0.4,0.5,0.4,112,95,130,40,13

15、0,112,75,100,40,100,76,图45例42,二、信息的价值 信息和决策的关系十分密切。要获得正确的决策，必须依赖足够和可靠的信息。 决策所需信息的分类：一类是完全信息，即据此可以得到完全肯定的自然状态，有助于正确的决策；一类是抽样信息，这是一类不完全可靠的信息。,完全信息价值 案例分析 某化工厂生产一种化工产品。据对统计资料的分析表明，该产品的次品率可以分成五个等级（即五种状态），每个等级（状态）的概率如下表所示：,由进一步的分析可知，产品次品率的高低与该产品所用主要原料的纯度有关。今已知，化工原料纯度高，次品率低（如S1为0.02），反之则次品率高。而化工原料的纯度高低，又与

16、运输、保存日期等因素有关。为此，工厂主管生产的部门建议在生产该产品前，先对该化工原料增加一道“提纯”工序，通过提纯工序，能使全部原料处于S1状态，从而降低了次品率。但增加提纯工序就增加了工序费用。,经过核算可知，每批原料的提纯费用为3400元。经估算，在不同纯度状态下其益损值如下表所示。如果在生产前，先将化工原料检验一下，通过检验可以掌握每批化工原料处于何种纯度状态，这样可以对不同纯度的原料采用不同策略，即提纯或不提纯，从而使益损期望值为最大。,益损值表 (单位：元),要求：如何进行决策才能获得最好的投资收益？,【分析】：今用决策树法对该问题进行分析，具体过程和结果如图所示。由下图可知，通过检

17、验，当某批原料纯度处于S1、 S2或S3，状态时，采用A2(不提纯)方案，其益损值大于A1方案。反之若处于S4或S5状态时，采用A1(提纯)方案，这时其益损值大于A2方案。据此可计算益损期望值为2220元。与没有经过检验工序相比，由于通过检验完全知道原料纯度的状态信息，因此可得完全信息的价值为2220元 - 1760元 = 460元。,通过该例可知，为获得完全信息所要付出的代价，不应大于完全信息所能得到的收益期望，本例中不应大于460元。本例如图中提纯方案分枝菱形内的数字为50，即增加检验工序只花费250元，而能多获得460元的收益。因此，增加检验工序是可取的。,抽样信息价值 通过抽样所获得的

18、信息，用统计方法来推断自然状态出现的概率，据此来选择行动方案。抽样信息虽不十分可靠，但为获得此类信息的代价也较少，且在多数情况下，也只可能获得这类信息，以供决策之需,案例讨论：某公司有50000元多余资金，如用于某项开发事业估计成功率为96%，成功时一年可获利12%，但一旦失败，有丧失全部资金的危险。如把资金存放到银行中，则可稳得年利6%。为获取更多情报，该公司求助于咨询服务，咨询费用为500元，但咨询意见只是提供参考。根据过去咨询公司类似200例咨询意见实施结果，情况见表所示：,试用决策树法分析： (a)该公司是否值得求助于咨询服务； (b)该公司多余资金应如何合理使用?,解答要点： 多余资

19、金用于开发事业成功时可获利6000元，若存人银行可获利3000元。 设 T1咨询公司意见可以投资 T2咨询公司意见不宜投资 E1投资成功 E2投资失败,P(E1/T1)0.987，P(E2/T1)0.013 P(El/T2)0.865，P(E2/T2)0.135 由题意知P(T1)0.78，P(T2)0.22， P(E1)0.96，P(E2)=0.04 因为P(E/T)P(T,E)P(T)， 又P(Tl，E1)0.77，P(T1,E2)0.01， P(T2，E1)0.19 ，P(T2，E2)0.03,故求得： P(E1/T1)0.987 P(E2/T1)0.013 P(El/T2)0.865

20、P(E2/T2)0.135,决策结论： (a)该公司应求助于咨询服务； (b)如咨询意见可投资开发，可投资于开发事业，如咨询意见不宜投资开发，应将多余资金存入银行。,三、效用曲线的应用 风险型决策分析的求解中，均是以益损期望值的大小作为在风险情况下选择最优方案的准则，仅代表大量实验的平均值，却不能表达决策者的主观意图和倾向及其满意程度等。因此，效用曲线应运而生。效用实质上反映了决策者对风险所抱的态度。,定义： 在直角坐标系内，用横坐标表示益损值，纵坐标表示效用值，将决策者对风险所持的态度的变化关系用曲线来反映。,用效用曲线进行决策和计算的步骤 绘制决策者的效用曲线 据效用曲线找出各方案与益损值

21、相对应的效用值。 根据效用曲线的效用期望值进行计算和决策。,例.某制药厂欲投产A、B两种新药，但受到资金及销路限制，只能投产其中之一。若已知投产新药A需要资金30万元，投产新药B只需资金16万元，两种新药生产期均定为5年。估计在此期间，两种新药销路好的概率为0.7，销路差的概率为0.3。它们的益损值如下表所示。问究竟投产哪种新药为宜?,益损值表：,采用益损值法，显然以生产新药A为最优，决策树如下图,若用效用值作为决策准则，其步骤如下： 绘制决策人的效用曲线。 据效用曲线找出方案与益损值相对应的效用值。 利用效用值为决策准则进行计算和决策。,效用曲线,由此可见，若以效用值作为决策准则，方案B优于

22、方案A。这是因为决策人是个保守型人物。,第 五 章 网络规划模型,5.1 基本概念及其术语,一、概念 网络图：由具有始点和终点的有向曲线或线段组成的图形。 网络技术：一种新方法，是借助网络图表示一项工程中多项工作及计算相关参数，从而对工作进行统筹安排的一种方法。,二、基本术语,工程：一个科研项目，一个工作任务。 作业：即工序。 紧前工序，紧后工序。 作业长度：表示工序所花时间。 结点：表示工序的开工和完工。 结点最早开工时间（ES）：即紧后工序最早开工时间。,结点最迟完工时间（LF）：即紧前工序允许的最迟完工时间。 关键路线：作业时差为零的路线。 关键工序：关键路线上的工序。 结点最早完工时间

23、（EF）。 结点最迟开工时间（LS）。,ES = 该事件所有紧前工序的EF的最大值； LF = 该事件所有紧后工序的LS的最小值； 作业时差 = 结点最迟结束时间 前一结点最早开工时间 工序时间；,三、两种网络图模型 AOA AON,5.2 方法分析,1 某工厂要进行生产线改造，其时间和进度安排如下表所示： 要求：（1）画出该工程作业的网络图； （2）计算最短工程时间。 （3）计算作业时差； （4）找出该工程的关键路线；,要求： （1）画出该工程作业的网络图模型； （2）计算最短工程时间； （3）计算作业时差； （4）找出该工程的关键路线。,A,E,C,D,B,F,G,J,H,K,I,M,L,

24、N,P,0,208,8,8,0,288,280,248,280,248,208,213,16,310,296,288,312,248,233,213,20,320,320,316,316,312,A B. C. E. F B D C D D H I E H I F G G H H J,I J J K. L K M. N L M M P N P P,8 8 8 24 4 6 4,8 8 12 35 225 200 40 32,ES=largest EF of the immediate predecessors,LF=smallest LS of the immediate successors

25、,Thus, the critical path is AFGHJLMP,网络图如下图所示。,结果关键路线为A-F-G-H-J-L-M-P； 最短工程时间为320小时。,案例分析二：某项工程（如新产品开发），安排如下：,要求： (1) 画出网络图 (2) 计算工程时间 (3) 计算作业时差 (4) 找出关键路线,A,F,D,G,H,J,L,N,M,K,I,E,B,C,6,3,4,12,13,6,2,5,12,10,9,4,8,11,6,9,13,18,0,12,18,23,32,33,41,52,52,41,33,23,23,37,18,16,12,9,12,0,网络图如下：,关键路线工序：B

26、EHJLN 工程时间：52天,5.3 计算作业时间,一、根据实际情况中的定额、统计资料和类比资料来确定。 二、三种时间估计法 最乐观时间，即在最顺利情况下完成工序的最短时间，用a表示。 最保守时间，即在最不顺利情况下完成工序的最长时间，用b表示。 最可能时间，即在一般情况下完成工序的时间，用c表示。,平均工序时间: t(a+b+4c)/6(经验公式) t 是一个平均值，其方差为： 2=(b-a)/6) 2 均方差：=(b-a)/6 ti=(ai+bi+4ci)/6，其中ti是随机变量。 E(ti)= (ai+bi+4ci)/6,T=ti，总工程周期T是各个相互独立的随机 变量之和，所以当工序很

27、多时，必然服从正态分布 TN（，）,所以 E(t)= TE= E(ti)= E(ti) = (ai+bi+4ci)/6) =(bi-ai)/6) 2) ,三、上述公式的意义 可用计算工程完工时间的概率。 可以计算具有一定概率值的工程实际完工时间。,案例研讨1：已知建设一个汽车库及引道的作业明细如下表所示（单位：天）,要 求： (1) 画出网络图 (2) 计算工程时间 (3) 计算作业时差 (4) 找出关键路线,网络图如下图所示：,关键路线为A-C-E-F-G-J-K-N； 最短工程时间为80天。,案例研讨2：某一汽车制造企业为加快产品开发进程，缩短产品的开发时间，现将其产品开发的工作任务分解安

28、排如下：,要求： (1) 建立网络图模型 (2) 计算工程时间 (3) 计算作业时差 (4) 找出关键路线,（1）建立网络图模型如下：,（2）计算每个节点的最早开工时间、最迟完工时间，得到工程总时间，工程时间61天 （3）计算作业时差，得到作业时差为零的工序集，即关键路线工序：BEHJLN 注：本题采用AOA方法，若使用AON方法也可以。,比较AON和AOA,案例研讨三： 某工厂要进行生产线改造，其时间和进度安排如下表所示： 要求：（1）画出该工程作业的网络图； （2）计算最短工程时间。 （3）计算作业时差； （4）找出该工程的关键路线；,要求： （1）画出该工程作业的网络图模型； （2）计算

29、最短工程时间； （3）计算作业时差； （4）找出该工程的关键路线。,Solution: Construction of AON Network,Solution: Analysis of AON Network,第七章 动态规划及其应用,基本思想： 把某项决策过程在时间上（有时推广到空间上）分成几个相互联系的阶段，依次（顺序或逆行）在每个阶段上进行决策，即采用多阶段序贯决策的方法，从而找出一个整体的最有方案。,例6-1 某人从A城到K城，选择最优开车路线,解题的思路和模型,1. 阶段的划分,解题的思路和模型,2. 描述阶段状态和决策方案 Sn：第n阶段状态变量 Xn：第n阶段决策方案 3.列出

30、效益函数 Rn（Sn，Xn）:阶段n状态Sn决策方案Xn的效益函数 4. 建模，采用倒序的方法 Fn（Sn）min（Max）Rn（Sn，Xn）+Fn+1(Sn+1) 某阶段最优值 本阶段效益值 后阶段最优值,解：阶段IV F3（S4）minR4（S4，X4）+F5(S5) 某阶段最优值 本阶段效益值 后阶段最优值 H点： Fh4（S4）minRh4（S4，X4）+F5(S5) =min(7+0)=7 I点： FI4（S4）minRI4（S4，X4）+F5(S5) =min(5+0)=5 J点： FJ4（S4）minRJ4（S4，X4）+F5(S5) =min(6+0)=6,解：阶段III F3

31、（ S3 ）minR3（ S3 ，X3）+F4(S4) 某阶段最优值 本阶段效益值 后阶段最优值 E点： FE3（S3）min(RE3（ S3 ，EH）+FH4(S4), (RE3（ S3 ，EI）+FI4(S4) =min(7+7,6+5)=11 F点： FF3（S3）min(RF3（ S3 ，FH）+FH4(S4), (RF3（ S3 ，FI）+FI4(S4), (RF3（ S3 ，FJ）+FJ4(S4) =min（67，35，36）8 G点： FG3（S3）min(RG3（ S3 ，GI）+FI4(S4), (RG3（ S3 ，GJ）+FJ4(S4) min（25，46）7,解：阶段II F2（ S2 ）minR2（ S2 ，X2）+F3(S3