1第二讲动态规划讲授:白丹宇2本章内容•多阶段决策过程的最优化•动态规划的基本概念和基本原理•动态规划模型的建立与求解3美国数学家贝尔曼(Richard.Bellman)创始时间上个世纪50年代创始人4•是运筹学的一个主要分支•是解决多阶段决策过程的最优化的一种方法多阶段决策过程:资源分配问题生产计划与库存问题投资问题装载问题排序问题生产过程的最优控制等多阶段决策过程的最优化的目标:达到整个活动过程的总体效果最优•主要用于解决:最优路径问题5动态规划模型分类离散确定型离散随机型连续确定型连续随机型6多阶段决策问题(Multi-Stagedecisionprocess)状态x1阶段1T1决策u1状态x2决策u2阶段2T2状态x3...状态xk决策uk阶段kTk状态xk+1...状态xn决策un阶段nTn状态xn+1§1多阶段决策过程的最优化71.多阶段决策过程的最优化动态规划方法与“时间”关系很密切,随着时间过程的发展而决定各时段的决策,产生一个决策序列,这就是“动态”的意思。然而它也可以处理与时间无关的静态问题,只要在问题中人为地引入“时段”因素,就可以将其转化为一个多阶段决策问题。在本章中将介绍这种处理方法。§1多阶段决策过程的最优化82.多阶段决策问题举例属于多阶段决策类的问题很多,例如1)工厂生产过程:由于市场需求是一随着时间而变化的因素,因此,为了取得全年最佳经济效益,就要在全年的生产过程中,逐月或者逐季度地根据库存和需求情况决定生产计划安排。§1多阶段决策过程的最优化9•例1:某厂与用户签订了如表所示的交货合同,表中数字为月底的交货量。该厂的生产能力为每月400件,该厂仓库的存货能力为300件。已知每百件货物的生产费用为10000元。在进行生产的月份,工厂还要支付经常费4000元。仓库保管费为每百件货物每月1000元。假设开始时及6月底交货后无存货。月份123456交货量(百件)125321§1多阶段决策过程的最优化102)设备更新问题:一般企业用于生产活动的设备,刚买来时故障少,经济效益高,即使进行转让,处理价值也高,随着使用年限的增加,就会逐渐变为故障多,维修费用增加,可正常使用的工时减少,加工质量下降,经济效益差,并且,使用的年限越长、处理价值也越低,自然,如果卖去旧的买新的,还需要付出更新费.因此就需要综合权衡决定设备的使用年限,使总的经济效益最好。例2:下表给出了某单位的预测数据,现决定考虑到1998年(n=5),试作5年内的设备更新计划§1多阶段决策过程的最优化产品年代机龄收入额维护费新设备购置费旧设备折价199312345181616141488991050201510521994012342221201816668810503025201510199501232725242256895231262115199601229262455652332820199701302845553530199803246040123)连续生产过程的控制问题:一般化工生产过程中,常包含一系列完成生产过程的设备,前一工序设备的输出则是后一工序设备的输入,因此,应该如何根据各工序的运行工况,控制生产过程中各设备的输入和输出,以使总产量最大。§1多阶段决策过程的最优化13以上所举问题的发展过程都与时间因素有关,因此在这类多阶段决策问题中,阶段的划分常取时间区段来表示,并且各个阶段上的决策往往也与时间因素有关,这就使它具有了“动态”的含义,所以把处理这类动态问题的方法称为动态规划方法。不过,实际中尚有许多不包含时间因素的一类“静态”决策问题,就其本质而言是一次决策问题,是非动态决策问题,但是也可以人为地引入阶段的概念当作多阶段决策问题,应用动态规划方法加以解决。§1多阶段决策过程的最优化144)资源分配问题:便属于这类静态问题。如:某工业部门或公司,拟对其所属企业进行稀缺资源分配,为此需要制定出收益最大的资源分配方案。这种问题原本要求一次确定出对各企业的资源分配量,它与时间因素无关,不属动态决策,但是,我们可以人为地规定一个资源分配的阶段和顺序,从而使其变成一个多阶段决策问题(后面我们将详细讨论这个问题)。§1多阶段决策过程的最优化15•例3:某工厂生产A、B、C三种产品,都使用某种原材料,现有原材料4吨。将不同数量的这种原料分配给各种产品时产生的收益如表所示,试确定使总收益最大的分配法。ABC01230101720061718081111165)运输网络问题:如图7-1所示的运输网络,点间连线上的数字表示两地距离(也可是运费、时间等),要求从A至F的最短路线。这种运输网络问题也是静态决策问题。但是,按照网络中点的分布,可以把它分为5个阶段,而作为多阶段决策问题来研究。§1多阶段决策过程的最优化17§1多阶段决策过程的最优化18本章内容•多阶段决策过程的最优化•动态规划的基本概念和基本原理•动态规划模型的建立与求解191、阶段:把一个问题的过程,恰当地分为若干个相互联系的阶段,以便于按一定的次序去求解。描述阶段的变量称为阶段变量。阶段的划分,一般是根据时间和空间的自然特征来进行的,但要便于问题转化为多阶段决策。2、状态:表示每个阶段开始所处的自然状况或客观条件。通常一个阶段有若干个状态,描述过程状态的变量称为状态变量。年、月、路段一个数、一组数、一个向量状态变量的取值有一定的允许集合或范围,此集合称为状态允许集合。5.2动态规划的基本概念203、决策:表示当过程处于某一阶段的某个状态时,可以作出不同的决定,从而确定下一阶段的状态,这种决定称为决策。描述决策的变量,称为决策变量。决策变量是状态变量的函数。可用一个数、一组数或一向量(多维情形)来描述。在实际问题中决策变量的取值往往在某一范围之内,此范围称为允许决策集合。系统在某一阶段的状态转移不但与系统的当前的状态和决策有关,而且还与系统过去的历史状态和决策有关。4、多阶段决策过程可以在各个阶段进行决策,去控制过程发展的多段过程;其发展是通过一系列的状态转移来实现的;21),,,,,,(),,,(),(221112211231112kkkkusususTsususTsusTs图示如下:状态转移方程是确定过程由一个状态到另一个状态的演变过程。如果第k阶段状态变量sk的值、该阶段的决策变量一经确定,第k+1阶段状态变量sk+1的值也就确定。其状态转移方程如下(一般形式)12ks1u1s2u2s3skuksk+1能用动态规划方法求解的多阶段决策过程是一类特殊的多阶段决策过程,即具有无后效性的多阶段决策过程。22),(),(),(122231112kkkkusTsusTsusTs动态规划中能处理的状态转移方程的形式。状态具有无后效性的多阶段决策过程的状态转移方程如下无后效性(马尔可夫性)如果某阶段状态给定后,则在这个阶段以后过程的发展不受这个阶段以前各段状态的影响;过程的过去历史只能通过当前的状态去影响它未来的发展;构造动态规划模型时,要充分注意是否满足无后效性的要求;状态变量要满足无后效性的要求;如果状态变量不能满足无后效性的要求,应适当地改变状态的定义或规定方法。235、策略:是一个按顺序排列的决策组成的集合。在实际问题中,可供选择的策略有一定的范围,称为允许策略集合。从允许策略集合中找出达到最优效果的策略称为最优策略。6、状态转移方程:是确定过程由一个状态到另一个状态的演变过程,描述了状态转移规律。7、指标函数和最优值函数:用来衡量所实现过程优劣的一种数量指标,为指标函数。指标函数的最优值,称为最优值函数。在不同的问题中,指标函数的含义是不同的,它可能是距离、利润、成本、产量或资源消耗等。动态规划模型的指标函数应具有可分离性,并满足递推关系。24)],,,(,,[111,1nkknkkkksusVus指标函数:指标函数形式:和、积),,,,,(111,nkkkknksususV可递推),,,()(1,,,susVoptsfnkknkkkuunk效益最优函数:25},,,{**2*1nuuu},,,{**2*1nsss解多阶段决策过程问题,求出最优策略,即最优决策序列susvoptsfnkknkkkuunk1,,,,,,f1(s1)最优轨线,即执行最优策略时的状态序列最优目标函数值),,,,(***1*1*,1*,1nnnnususVV从k到终点最优策略子策略的最优目标函数值261、动态规划方法的关键在于正确地写出基本的递推关系式和恰当的边界条件(简称基本方程)。要做到这一点,就必须将问题的过程分成几个相互联系的阶段,恰当的选取状态变量和决策变量及定义最优值函数,从而把一个大问题转化成一组同类型的子问题,然后逐个求解。即从边界条件开始,逐段递推寻优,在每一个子问题的求解中,均利用了它前面的子问题的最优化结果,依次进行,最后一个子问题所得的最优解,就是整个问题的最优解。5.3动态规划的基本思想272、在多阶段决策过程中,动态规划方法是既把当前一段和未来一段分开,又把当前效益和未来效益结合起来考虑的一种最优化方法。因此,每段决策的选取是从全局来考虑的,与该段的最优选择答案一般是不同的.最优化原理:作为整个过程的最优策略具有这样的性质:无论过去的状态和决策如何,相对于前面的决策所形成的状态而言,余下的决策序列必然构成最优子策略。”也就是说,一个最优策略的子策略也是最优的。3、在求整个问题的最优策略时,由于初始状态是已知的,而每段的决策都是该段状态的函数,故最优策略所经过的各段状态便可逐段变换得到,从而确定了最优路线。28建立动态规划模型的步骤1、划分阶段划分阶段是运用动态规划求解多阶段决策问题的第一步,在确定多阶段特性后,按时间或空间先后顺序,将过程划分为若干相互联系的阶段。对于静态问题要人为地赋予“时间”概念,以便划分阶段。2、正确选择状态变量选择变量既要能确切描述过程演变又要满足无后效性,而且各阶段状态变量的取值能够确定。一般地,状态变量的选择是从过程演变的特点中寻找。3、确定决策变量及允许决策集合通常选择所求解问题的关键变量作为决策变量,同时要给出决策变量的取值范围,即确定允许决策集合。294、确定状态转移方程根据k阶段状态变量和决策变量,写出k+1阶段状态变量,状态转移方程应当具有递推关系。5、确定阶段指标函数和最优指标函数,建立动态规划基本方程阶段指标函数是指第k阶段的收益,最优指标函数是指从第k阶段状态出发到第n阶段末所获得收益的最优值,最后写出动态规划基本方程。以上五步是建立动态规划数学模型的一般步骤。由于动态规划模型与线性规划模型不同,动态规划模型没有统一的模式,建模时必须根据具体问题具体分析,只有通过不断实践总结,才能较好掌握建模方法与技巧。2511214106104131112396581052C1C3D1AB1B3B2D2EC2一、最短路径问题求从A到E的最短路径2511214106104131112396581052C1C3D1AB1B3B2D2EC2f5(E)=02511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D1)=5f5(E)=0505)E(f)ED(d)D(f51142511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f4(D1)=5202)E(f)ED(d)D(f52242511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C1)=8f4(D1)=5112421141113DC8118min2953min)D(f)D,C()D(f)D,C(min)C(f最优决策2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2