运筹学动态规划

1、第五章 动态规划,动态规划是解决多阶段决策过程最优化 问题的一种方法。 根据决策变量时间上的变化连续型,离散型 根据决策过程性质确定型,随机型 根据决策的相互关系动态型，静态型 此外还有阶段的个数是有限的与无限的， 确定与不确定等。 本章研究：动态与静态确定型的决策过程,第一节 多阶段决策过程的最优化,一、多阶段决策问题 根据问题本身的特点，可以将其求解的全过程划分为若干个相互联系的阶段（即将问题划分为许多个相互联系的子问题），在它的每一阶段都需要做出决策，并且在一个阶段的决策确定以后再转移到下一阶段。往往前一个阶段的决策要影响到后一个阶段的决策，从而影响整个过程。这样的决策过程称作多阶段决策

2、过程。,二、多阶段决策问题举例,（1）生产与存贮过程。 某工厂每月需供应市场一定数量的产品，并将所余产品存入仓库。一般某月适当增加产品可降低生产成本，但超产部分存入仓库会增加库存费用。要求确定一个逐月的生产计划，在满足需求条件下，使一年的生产与存贮费用之和最小。 可以把每个月作为一个阶段，全年分为12个阶段逐次决策。,上述问题的发展过程都与时间因素有关，因此在这类多阶段决策问题中，阶段的划分常取时间区段来表示，并且各个阶段上的决策往往也与时间有关，这就使它具有了“动态”的含义，所以把处理这类动态问题的方法称为动态规划方法。 但在实际中，一些不含时间的一类“静态”决策问题，其本质是一次决策问题，

3、是非动态决策问题，但可以人为地引入阶段的概念，当作阶段决策问题，应用动态规划方法加以解决。,（4）资源分配问题 某工业部门或公司，拟对其所属企业进行稀缺资源分配，为此需要制订出收益最大的资源分配方案。 （5）运输网络问题,图5-11 运输网络图示,多阶段决策过程最优化的目标： 要达到整个活动过程的总体效果最优。,第二节 动态规划的基本概念和基本原理,图5-11 运输网络图示,1.阶段和阶段变量 阶段把所给问题按时间或空间先后顺序划分 为若干个相互联系又有区别的子问题 一个阶段就是需要作出一个决策的子问题。 描述阶段的变量叫做阶段变量，一般以k表示 阶段变量。,用以描述事物在某特定的时间与空间域

4、中所处位置 及运动特征的量,图5-11 运输网络图示,图5-11 运输网络图示,三、动态规划求解的多阶段决策问题的特点 1.无后效性又称马尔柯夫性，是指系统从某个阶段往后的发展，仅由本阶段所处的状态及其往后的决策所决定，与系统以前经历的状态和决策无关。 2. 适合于用动态规划方法求解的只是这类“无后效性”的多阶段决策过程。,5.状态转移方程：,(5-1),6. 指标函数 指标函数用来衡量策略或子策略或决策的效果优劣的某种数量指标 它分为阶段指标函数和过程指标函数两种。,(2)过程指标函数（也称目标函数） 用Rk(sk,uk)表示k部子过程的指标函数，指k部子过程效果优劣的数量指标 Rk(sk,uk)不仅跟当前状态sk有关，还跟该子过程策略pk(sk)有关，因此它是sk和pk(sk)的函数，严格说来，应表示为:,实际应用中往往表示为Rk(sk,uk)或Rk(sk) 过程指标函数Rk(sk) 是由各阶段的阶段指标函数gk(sk,uk)累积形成