天津大学：《运筹学》精品课程教学资源（电子课件）第二章 动态规划 Dynamic Programming

Q买非点藏为同课程运笑学 第二章动态规划 Dynamic Programming) 2.1动态规划的基本概念与方法 2.2动态规划应用举例 天津大学运筹学课程网站202.113.13.67/ ourse/ddg

第二章 动态规划 （Dynamic Programming） 2.1 动态规划的基本概念与方法 2.2 动态规划应用举例

运筹学 operations research 第二章动态规划 2.1动态规划的基本概念与方法 多阶段决策问题举例 1.时间阶段例子(生产负荷问题)某种机器可以 在高、低两种负荷下进行生产。高负荷年产量 8,年完好率0.7;低负荷年产量5,年完好率0.9 现有完好机器1000台,需制定一个5年计划,以 决定每年安排多少台机器投入高、低负荷生产, 使5年的总产量最大 S1=1000 ”“率” 2

http://www.tju.edu.cn 第二章 动态规划 2.1 动态规划的基本概念与方法 一、多阶段决策问题举例 1. 时间阶段例子(生产负荷问题)某种机器可以 在高、低两种负荷下进行生产。高负荷年产量 8，年完好率0.7；低负荷年产量5，年完好率0.9。 现有完好机器1000台，需制定一个5年计划，以 决定每年安排多少台机器投入高、低负荷生产， 使5年的总产量最大。 123 4 5 S1=1000 x1 x 2 x 5 x 4 x 3 s 5 v1 v 2 v 3 v 4 v 5 s 2 s 3 s 4

运筹学 operations research 第二章动态规划 -2.空间阶段的例子(最短路问题)如图为一线路 网络。现要从A点铺设一条管道到E点,图中两 点间连线上数字表示两点间距离。现需选一条 由A到B的铺管线路,使总距离最短。 B 14 A 038 B E 12 阶段1 阶段2 阶段3 阶段4

http://www.tju.edu.cn 第二章 动态规划 2.空间阶段的例子（最短路问题）如图为一线路 网络。现要从A点铺设一条管道到E点，图中两 点间连线上数字表示两点间距离。现需选一条 由A到E的铺管线路，使总距离最短。 A E B1 B 2 B 3 C1 C 2 C 3 D1 D 2 2 9 5 3 12 5 2 1 5 6 4 6 8 10 13 12 11 14 10 阶段1 阶段2 阶段3 阶段 4

运筹学 operations research 第二章动态规划 基本概念与方程 1、基本概念 阶段——分步求解的过程,用阶段变量k表示, k=1,…,n 状态—每阶段初可能的情形或位置,用状态变量 S表示。动态规划中的状态应具有无后效性。 决策—每阶段状态确定后的抉择,即从该状态演 变到下阶段某状态的选择,用决策变量x表示

http://www.tju.edu.cn 第二章 动态规划 二、基本概念与方程 1、基本概念 阶段——分步求解的过程，用阶段变量 k表示， k=1， …，n 状态——每阶段初可能的情形或位置，用状态变量 Sk表示。 动态规划中的状态应具有无后效性。 决策——每阶段状态确定后的抉择，即从该状态演 变到下阶段某状态的选择，用决策变量 xk表示

运筹学 operations research 第二章动态规划 状态转移——由S转变为S1的规律,记S=m(S,x 策略——由各阶段决策组成的序列,记乃1={x1 称{x,…,x)为阶段k至m的后部子策略 阶段指标—每阶段选定决策x后所产生的效益,记 VE V Sk. rp 指标函数—各阶段的总效益,记相应于P的指标函数 为 kn kn 其中最优的称最优指标函数,记fh=f1(S)=0ptvo

http://www.tju.edu.cn 第二章 动态规划 状态转移——由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

运筹学 operations research 第二章动态规划 问题:动态规划的最优解和最优值各是什么? 最优解:最优策略Bn 最优值:最优指标f1

http://www.tju.edu.cn 第二章 动态规划 问题：动态规划的最优解和最优值各是什么？ ——最优解：最优策略 P1 n ， 最优值：最优指标 f1

运筹学 operations research 第二章动态规划 2、基本方程 1)基本原理 定理:P=(x1…xn)是最优策略对任何k(1<k<n) 和允许状态,有f1=qpt1k+f1 pik 推论( bellman最优性原理):若P是最优策略, 则对任何k(1<k<n),子策略P对于以S;为起 点的k至n子过程来说必为最优策略

http://www.tju.edu.cn 第二章 动态规划 （1）基本原理 和允许状态 有 { }。 定理： 是最优策略 对任何 （ 11 1 1 1 1 1 , ),,( )1 + ∗∗ ∗ += = ⇔ << kk p n n fvoptfs xxP nkk k " 点的 至 子过程来说必为最优策 略。 则对任何 （ ），子策略 对于以 为起 推论（ 最优性原理）：若 是最优策略， nk nkk P s Bellman P kn k n ∗ ∗ ∗ 1 << 1 2、基本方程

运筹学 operations research 第二章动态规划 以最短路为例说明 (2)基本方程 根据最优性原理,可建立从后向前逆推求 解的递推公式—基本方程 f, =opt f +fi fn1=0,k=n2…l

http://www.tju.edu.cn 第二章 动态规划 （2）基本方程 根据最优性原理，可建立从后向前逆推求 解的递推公式——基本方程： { } ⎪⎩ ⎪⎨⎧ == = + + + ,1, 0, 1 1 nkf " fvoptf n k k x k k 以最短路为例说明

运筹学 operations research 第二章动态规划 ◆动态规划求解的一般步骤: ◆确定过程的分段,构造状态变量; ◆设置决策变量,写出状态转移; ◆列出阶段指标和指标函数: ◆写出基本方程,由此逐段递推求解

http://www.tju.edu.cn 第二章 动态规划 动态规划求解的一般步骤： ‹确定过程的分段，构造状态变量； ‹设置决策变量，写出状态转移； ‹列出阶段指标和指标函数； ‹写出基本方程，由此逐段递推求解

运筹学 operations research 第二章动态规划 中三、求解方法 1.离散型(用表格方式求解) 例1用动态规划方法求解前面的最短路问题 B 14 D A 0 E 12 B

http://www.tju.edu.cn 第二章 动态规划 三、求解方法 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