文档介绍：4 动态规划 多阶段决策问题与动态规划 动态规划的基本概念 动态规划的步骤 动态规划的应用 1 求解静态规划问题 2 资源分配问题 3 不确定性采购问题 4 排序问题例2 ,产品的年产量 g 和投入生产的机器数量 u 的关系为 g=g(u), 这时机器的年完好率为 a(0<a<1) . 在低负荷下生产时,产品的年产量 h 和投入生产的机器数量 v 的关系为 h =h(v), 这时机器的年完好率为 b(a<b<1 ). 假定开始生产时完好的机器数量为 s 1, 要求制定一个五年计划, 在每年开始时决定机器在两种不同负荷下生产的数量, 使五年内产品的总产量最高。 多阶段决策问题与动态规划例1 最短路问题以上两个问题都可以划分为先后多个决策阶段。这类问题就称为多阶段决策问题。多阶段决策问题的过程如下图所示: 状态状态状态状态... 1 2 n 决策决策决策状态多阶段决策问题和我们前面遇到的决策问题不同,它是和时间有关的。与时间有关的活动过程称为动态过程,其优化方法称为动态规划。而与时间无关的活动过程称为静态过程,相应的的优化方法称为静态规划。 (1) 阶段( stage ) 把所研究的决策问题,按先后顺序划分为若干相互联系的决策步骤,以便按一定的次序进行求解。描述阶段的变量称阶段变量,常用 k表示。 (2) 状态( state )状态表示每个阶段开始时所处的自然状况或客观条件,它描述了影响决策的因素随决策进程的变化情况,它既是前面阶段所作决策的结果,又是本阶段作出决策的出发点和依据。描述状态的变量称为状态变量,第 k阶段的状态变量常用 s k表示。通常, 在第一阶段状态变量 s 1是确定的,称初始状态。 (3) 决策( decision )决策表示在某一阶段处于某种状态时,决策者在若干种方案中作出的选择决定。描述决策的变量称决策变量,第 k阶段的决策变量常用 u k表示。决策变量的取值会受到状态变量的制约,被限制在某一范围之内。 动态规划的基本概念(一) (4) 策略( policy ) 把从第一阶段开始到最后阶段终止的整个决策过程,称为问题的全过程;而把从第 k 阶段开始到最后阶段终止的决策过程,或称为 k 子过程。在全过程上,各阶段的决策按顺序排列组成的决策序列 p 1,n={u 1,u 2, ……,u n } 称为全过程策略,简称策略;而在 k 子过程上的决策序列 p k,n= {u k,u k+1,……,u n }称为 k子过程策略,也简称子策略。 (5) 状态转移方程若第 k 阶段的状态变量值为 s k,当决策变量 u k 的取值决定后,下一阶段状态变量 s k+1的值也就完全确定。即 s k+1 的值对应于 s k和u k 的值。这种对应关系记为 s k+1=T k(s k,u k), 称为状态转移方程。状态转移方程描述了由一个阶段的状态到下一阶段的状态的演变规律。 动态规划的基本概念(二) (6) 指标函数和最优值函数指标函数分为阶段指标函数和过程指标函数。阶段指标函数是对某一阶段的状态和决策产生的效益值的度量,用 v k(s k,u k) 表示。过程指标函数是指过程所包含的各阶段的状态和决策所产生的总的效益值,记为 V k,n=V k,n(s k,u k,s k+1,u k+1,……,s n,u n) 动态规划所要求的过程指标函数应具有可分离性,即可表达为它所包含的各阶段指标函数的函数形式。常见的两种过程指标函数形式是: ①各阶段指标函数的和 V k,n=∑v j(s j,u j); ②各阶段指标函数的积 V k,n=∏v j(s j,u j)。把过程指标函数 V k,n对k 子过程策略 p k,n 求最优,得到一个关于状态 s k的函数,称为最优值函数,记为 f k(s k)。即 f k(s k)= opt V k,n(s k,u k,……,s n,u n) u k,…,u n式中的“opt ”(optimization )可根据具体问题而取 min 或max 。 (7) 基本方程通常动态规划问题的最优值函数满足递推关系式。设过程指标函数为各阶段指标函数的和的形式,即V k,n=∑v j(s j,u j),则有 f k(s k)= opt {v k(s k,u k)+f k+1(s k+1)} u k∈D k(s k) ( k=n,n-1, …,1) 递推方程 f n+1(s n+1)=0 边界条件递推方程和边界条件一起称为动态规划的基本方