第一节动态规划的基本概念与方法 多阶段决策问题 1.时间阶段的例子(机器负荷问题) 某厂有1000台机器,现需作一个五年计划, 以决定每年安排多少台机器投入高负荷生产(产 量大但损耗也大)可使五年的总产量最大。 S1=1000 w $313 4
第一节 动态规划的基本概念与方法 一、多阶段决策问题 1. 时间阶段的例子（机器负荷问题） 某厂有1000台机器，现需作一个五年计划， 以决定每年安排多少台机器投入高负荷生产（产 量大但损耗也大）可使五年的总产量最大。 1 2 3 4 5 S1=1000 x1 x2 x3 x4 x5 s5 v1 v2 v3 v4 v5 s2 s3 s4
2.空间阶段的例子(最短路问题) 如图为一线路网络。现要从A点铺设一条管 道到点,图中两点间连线上数字表示两点间距 离。现需选一条由A到E的铺管线路,使总距离 最短。 B D A B 12 B311 阶段1 阶段2 阶段3 阶段4
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 状态——每阶段初可能的情形或位置,用状态变量S表示。 按状态的取值是离散或连续,将动态规划问题分为 离散型和连续型 决策——每阶段状态确定后的抉择,即从该状态演变到下阶 段某状态的选择,用决策变量xk表示 状态转移——由S转变为Sk+1的规律,记S+1=7(S,x) 策略——由各阶段决策组成的序列,记Pn={x,,xn} 称Pm={ xn}为阶段k至n的后部子策略
二、基本概念与方程 1.基本概念 阶段——分步求解的过程，用阶段变量k表示，k=1，…，n 状态——每阶段初可能的情形或位置，用状态变量Sk表示。 按状态的取值是离散或连续，将动态规划问题分为 离散型和连续型。 决策——每阶段状态确定后的抉择，即从该状态演变到下阶 段某状态的选择，用决策变量xk表示。 状态转移——由Sk转变为Sk+1的规律，记Sk+1 =T(Sk，xk )。 策略——由各阶段决策组成的序列，记P1n={x1，…， xn }， 称Pkn={xk，…， xn }为阶段k至n的后部子策略
阶段指标—每阶段选定决策x后所产生的效益,记 Vk= V Sk. xk) 指标函数各阶段的总效益,记相应于Pn的指标函数 为V2=vm(S,Pn)。其中最优的称最优 指标函数,记f=f(Sk)= opt v 问题:动态规划的最优解和最优值各是什么? —最优解:最优策略Pn 最优值:最优指标f
阶段指标——每阶段选定决策xk后所产生的效益，记 vk= vk (Sk， xk )。 指标函数——各阶段的总效益，记相应于Pkn的指标函数 为vkn= vkn(Sk， Pkn )。其中最优的称最优 指标函数，记 fk = fk（ Sk ）=opt vkn。 问题：动态规划的最优解和最优值各是什么？ ——最优解：最优策略P1n ， 最优值：最优指标f1
2基本原理与基本方程 (1)基本原理 定理: I n =(x x")是最优策略兮对任何k(1<k<n 和允许状态s1,有1=op{1g+f1 Ak 推论(Bεlma最优性原理):若P是最优策略, 则对任何k(1<k<n),子策略P对于以s为起 点的至n子过程来说必为最优策略 以最短路为例说明
2.基本原理与基本方程 （1）基本原理 和允许状态 有 。 定理： 是最优策略 对任何 （ 1 1 1 1 1 1 1 , ( , , ) 1 ) + = + = s f opt v f P x x k k n 点的 至 子过程来说必为最优策略。 则对任何 （ ），子策略 对于以 为起 推论（ 最优性原理）：若 是最优策略， k n k k n P s B ellm an P 1 1 以最短路为例说明