天津大学管理学院：《管理科学基础》课程PPT教学课件（运筹学）第九章 动态规划（9.1）动态规划的基本概念与方法

第一节动态规划的基本概念与方法 多阶段决策问题 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 以最短路为例说明

(2)基本方程 根据最优性原理,可建立从后向前逆推求解 的递推公式基本方程: f, =opt t, +f) f=0,k=n,…,1 动态规划求解的一般步骤: 确定过程的分段,构造状态变量; 设置决策变量,写出状态转移; -列出阶段指标和指标函数; 写出基本方程,由此逐段递推求解

（2）基本方程 根据最优性原理，可建立从后向前逆推求解 的递推公式——基本方程：       = = = + + + 1 0, , ,1 1 f k n  f opt v f 动态规划求解的一般步骤： - 确定过程的分段，构造状态变量； - 设置决策变量，写出状态转移； - 列出阶段指标和指标函数； - 写出基本方程，由此逐段递推求解

求解方法 1.离散型(用表格方式求解) 例1用动态规划方法求解前面的最短路问题。 D

三、求解方法 1. 离散型（用表格方式求解） 例1 用动态规划方法求解前面的最短路问题。 A E B1 B2 B3 C1 C2 C3 D1 D2 2 9 5 3 12 5 2 1 5 6 4 6 8 10 13 12 11 14 10

B 14 A B E 10 B 解:设阶段k=1,2,3,4依次表示4个阶段选路的过程; 状态表示k阶段初可能处的位置; 决策x表示k阶段初可能选择的路; 阶段指标v表示k阶段与所选择的路段相应的路长; 指标函数4=∑表示k至4阶段的总路长 递推公式:f=Mm+fn} f,=0,k=4

A E B1 B2 B3 C1 C2 C3 D1 D2 2 9 5 3 12 5 2 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阶段的总路长； = v   0, 4, ,1 5 1 = =  = + + f k f Min v f 递推公式： k k k

B 14 2 A B2)10 E B k k kn= tfk+l f& p k D E 5+0 DE D E 2+0 DE 3+5 CD,E D k5239658 9+2 一一 3 6+5 5+2 C2D,E D 8+5 12 CDE 10 10+2

A E B1 B2 B3 C1 C2 C3 D1 D2 2 9 5 3 12 5 2 1 5 6 4 6 8 10 13 12 11 14 10 4 k Sk xk vk vkn=vk+fk+1 fk  P 2 1 D D E E 2 0 5 0 + + 2 5 2 5 D E D E 2 1 3 2 1 D D 2 1 D D 2 1 D D C1 C2 C3 9 3 5 6 10 8 9 2 3 5 + + 5 2 6 5 + + 10 2 8 5 + + 8 7 12 C1D1E C2D2E C3D2E

k k k kn-vk+fk+ fk P C.12 12+8 20 B,CD,E 14 14+7 6+8 B 10 10+7 4 4+12 BCD,E 13 13+8 12 12+7 19 B,CD,E 11 11+12 、12 4 5 A 10 E 19 B

k Sk xk vk vkn=vk+fk+1 fk  P A E B1 B2 B3 C1 C2 C3 D1 D2 2 9 5 3 12 5 2 1 5 6 4 6 8 10 13 12 11 14 10 2 B1 B2 B3 2 1 C C 14 12 14 7 12 8 + + 20 B1C1D1E C C C 4 10 6 4 12 10 7 6 8 + + + 14 B2C1D1E C C C 11 12 13 11 12 12 7 13 8 + + + 19 B3C2D2E