1、动态规划（Dynamic Programming）,动态规划是解决复杂系统优化问题的一种方法。是解决动态系统多阶段决策过程的基本方法之一。,教学大纲:,理解动态规划基本概念、最优化原理和基本方程，通过资源分配和生产与存储等问题,学习应用动态规划解决多阶段决策问题。 重点 : 掌握动态规划模型结构、逆序法算法原理、资源分配、设备更新、生产于存贮等问题。难点为动态规划中状态变量等的确定。,1. 多阶段的决策问题,引例1 最短路问题,例2：生产与投入问题,例3：将一个单数C（C 0)分成 n 个部分C1,C2 ,Cn之和，且Ci 0（i=1,n），问如何分割使其乘积为最大,包含随时间变化的因素和变量
2、的系统。,系统在某个时刻的状态，往往要依某种形式受过去某些决策的影响；,将时间作为决策变量之一的决策问题称为动态决策问题。,如经济系统,生产系统等。,动态系统：,线性系统、非线性系统。,动态系统的特点：,动态决策 问题：,而系统的当前状态和决策又会影响系统今后的发展。,动态规划的研究对象,即在系统发展的不同时刻（或阶段）根据系统所处的状态，不断地做出决策；,每个阶段都要进行决策,目的是使整个过程的决策 达到最优效果。,动态决策问题的特点：,系统所处的状态和时刻是进行决策的重要因素；,找到不同时刻的最优决策以及整个过程的最优策略。,多阶段决策问题：,是动态决策问题的一种特殊形式；,在多阶段决策过
3、程中,系统的动态过程可以按照时间进程分为状态相互联系而又相互区别的各个阶段；,多阶段决策问题的典型例子： 1 . 生产决策问题：企业在生产过程中，由于需求是随时间变化的，因此企业为了获得全年的最佳生产效益，就要在整个生产过程中逐月或逐季度地根据库存和需求决定生产计划。,2. 机器负荷分配问题：某种机器可以在高低两种不同的负荷下进行生产。在高负荷下进行生产时，产品的年产量g和投入生产的机器数量u1的关系为g=g(u1),这时，机器的年完好率为a，即如果年初完好机器的数量为u，到年终完好的机器就为au, 0a1。,在低负荷下生产时，产品的年产量h和投入生产的机器数量u2的关系为 h=h(u2),假定开始生产时完好的机器数量为s1。要求制定一个五年计划，在每年开始时，决定如何重新分配完好的机器在两种不同的负荷下生产的数量，使在五年内产品的总产量达到最高。,相应的机器年完好率b, 0 b9/2,当,当,时,时,矛盾，舍去。,（最优决策）,S20,一般动态规划应用,精品课件！,精品课件！,动态规划的优缺点,优点: . 最优解是全局最优解。 . 能得到一系列（包括子过程）的最优解。 . 不需要对系统状态转移方程、阶段效应函数等的解析性质作任何假设。,缺点： .没有统一的标准模型和标准的算法可供使用。 .应用的局限性，要求满足“无后效性”。 . “维数灾难”问题。,
