九章一节动态规划的基本概念与方法.ppt

* 第一节 动态规划的基本概念与方法 一、多阶段决策问题 1. 时间阶段的例子（机器负荷问题） 某厂有1000台机器，现需作一个五年计划，以决定每年安排多少台机器投入高负荷生产（产量大但损耗也大）可使五年的总产量最大。 1 2 3 4 5 S1=1000 x1 x2 x5 x4 x3 s5 v1 v2 v3 v4 v5 s2 s3 s4 2. 空间阶段的例子（最短路问题） 如图为一线路网络。现要从A点铺设一条管道到E点，图中两点间连线上数字表示两点间距离。现需选一条由A到E的铺管线路，使总距离最短。 A E B1 B2 B3 C1 C2 C3 D1 D2 2 9 5 3 12 2 5 1 5 6 4 6 8 10 13 12 11 14 10 阶段1 阶段2 阶段3 阶段4 二、基本概念与方程 1.基本概念 阶段——分步求解的过程，用阶段变量k表示，k=1，…，n 状态——每阶段初可能的情形或位置，用状态变量Sk表示。 按状态的取值是离散或连续，将动态规划问题分为 离散型和连续型。 决策——每阶段状态确定后的抉择，即从该状态演变到下阶 段某状态的选择，用决策变量xk表示。 状态转移——由Sk转变为Sk+1的规律，记Sk+1=T(Sk， xk)。 策略——由各阶段决策组成的序列，记P1n={x1，…， xn}， 称Pkn={xk，…， xn}为阶段k至n的后部子策略。 阶段指标——每阶段选定决策xk后所产生的效益，记 vk= vk(Sk， xk)。 指标函数——各阶段的总效益，记相应于Pkn的指标函数 为vkn= vkn(Sk， Pkn )。其中最优的称最优 指标函数，记 fk = fk（ Sk ）=opt vkn。 问题：动态规划的最优解和最优值各是什么？ ——最优解：最优策略P1n ， 最优值：最优指标f1。 2.基本原理与基本方程 （1）基本原理 以最短路为例说明 （2）基本方程 根据最优性原理，可建立从后向前逆推求解的递推公式——基本方程： 动态规划求解的一般步骤： - 确定过程的分段，构造状态变量； - 设置决策变量，写出状态转移； - 列出阶段指标和指标函数； - 写出基本方程，由此逐段递推求解。 三、求解方法1. 离散型（用表格方式求解） 例1 用动态规划方法求解前面的最短路问题。 A E B1 B2 B3 C1 C2 C3 D1 D2 2 9 5 3 12 2 5 1 5 6 4 6 8 10 13 12 11 14 10 A E B1 B2 B3 C1 C2 C3 D1 D2 2 9 5 3 12 2 5 1 5 6 4 6 8 10 13 12 11 14 10 解：设阶段k=1，2，3，4依次表示4个阶段选路的过程； 状态sk表示k阶段初可能处的位置； 决策xk表示k阶段初可能选择的路； 阶段指标vk表示k阶段与所选择的路段相应的路长； 指标函数 vk4 = 表示k至4阶段的总路长； A E B1 B2 B3 C1 C2 C3 D1 D2 2 9 5 3 12 2 5 1 5 6 4 6 8 10 13 12 11 14 10 4 k Sk xk vk vkn=vk+fk+1 fk 3 C1 C2 C3 8 7 12 C1D1E C2D2E C3D2E k Sk xk vk vkn=vk+fk+1 fk A E B1 B2 B3 C1 C2 C3 D1 D2 2 9 5 3 12 2 5 1 5 6 4 6 8 10 13 12 11 14 10 2 B1 B2 B3 20 B1C1D1E 14 B2C1D1E 19 B3C2D2E