《运筹学》课程授课教案（讲稿）第23讲 动态规划的基本概念和基本原理

课程名称：《运筹学》第_23_讲次授课题目动态规划的基本概念和基本原理本讲目的要求及重点难点：「目的要求】通过本讲课程的学习，1：掌握动态规划的基本概念：阶段、状态、决策、策略、状态转移方程、指标函数和最优值函数、最优策略、最优轨线2.了解动态规划的基本理论：最优性定理和最优性原理【重点及难点】最优性定理和最优性原理。内容[本讲课程的引入]动态规划（DynamicProgramming）是运筹学的一个重要分支，它是解决多阶段决策过程最优化的一种方法。美国数学家贝尔曼（R.E.Bellman）等人在50年代初提出了解决多阶段决策问题的“最优性原理”（PrincipleofOptimality）。1957年贝尔曼出版了专著“动态规划”，该书是动态规划的第一本著作。目前动态规划已经用于解决最优路径问题、资源分配问题、生产调度问题、设备更新问题、复合系统可靠性问题及生产过程最优控制等，并且取得了显著的效果。动态规划是求解问题的一种方法，而不是算法（线性规划是一种算法），因而没有标准的数学表达式，对于具体问题需要具体分析。[本讲课程的内容]多阶段决策问题一、在生产经营活动中，某些问题决策过程可以划分为若干相互联系的阶段，每个阶段需要做出决策从而使整个过程取得最优。由于各个阶段不是孤立的，而是有机联系的，也就是说，本阶段的决策将影响过程下一阶段的发展，从而影响整个过程效果，所以决策者在进行决策时不能够仅考虑选择的决策方案使本阶段最优，还应该考虑本阶段决策对最终目标产生的影响，从而做出对全局来讲是最优的决策。当每个阶段的决策确定以后，全部过程的决策就是这些阶段决策所组成的一个决策序列，所以多阶段决策问题也称为序贯决策问题

课程名称：《运筹学》 第 23 讲次 授课题目 动态规划的基本概念和基本原理 本讲目的要求及重点难点： 目的要求] 通过本讲课程的学习，1．掌握动态规划的基本概念：阶段、状态、决策、 策略、状态转移方程、指标函数和最优值函数、最优策略、最优轨线 2．了解动态规划的基本理论：最优性定理和最优性原理 [重点及难点] 最优性定理和最优性原理。 内 容 [本讲课程的引入] 动态规划（Dynamic Programming）是运筹学的一个重要分支，它是解决多阶段决策 过程最优化的一种方法。美国数学家贝尔曼（R. E. Bellman）等人在 50 年代初提出了解 决多阶段决策问题的“最优性原理”（Principle of Optimality）。1957 年贝尔曼出版了专著 “动态规划”，该书是动态规划的第一本著作。目前动态规划已经用于解决最优路径问题、 资源分配问题、生产调度问题、设备更新问题、复合系统可靠性问题及生产过程最优控 制等，并且取得了显著的效果。 动态规划是求解问题的一种方法，而不是算法（线性规划是一种算法），因而没有标 准的数学表达式，对于具体问题需要具体分析。 [本讲课程的内容] 一、 多阶段决策问题 在生产经营活动中，某些问题决策过程可以划分为若干相互联系的阶段，每个阶段需要做出决策， 从而使整个过程取得最优。由于各个阶段不是孤立的，而是有机联系的，也就是说，本阶段的决策将 影响过程下一阶段的发展，从而影响整个过程效果，所以决策者在进行决策时不能够仅考虑选择的决 策方案使本阶段最优，还应该考虑本阶段决策对最终目标产生的影响，从而做出对全局来讲是最优的 决策。当每个阶段的决策确定以后，全部过程的决策就是这些阶段决策所组成的一个决策序列，所以 多阶段决策问题也称为序贯决策问题

内容多阶段决策问题中，各个阶段一般是按照时间来划分的，随着时间的发展而产生各个阶段的决策，从而形成决策序列，这就是动态的含义。在一些与时间无关的静态问题中（如非线性规划等），可以人为地赋予时间的概念，使其成为一个多阶段决策问题，再用动态规划方法处理。多阶段决策问题很多，现举例如下：例5-1最短路问题如图5-1所示，要从A地到E地铺设管线，中间需要经过三个中间站，两点之间的连线上的数字表示距离，问应该选择什么路线，使总距离最短？图5-1例5-2机器负荷问题某工厂有100台机器，拟分四个周期使用，在每一个周期有两种生产任务。据经验，把机器xi台投入第一种生产任务，则在一个生产周期中将有1/3xi台机器报废；余下的机器全部投入第二种生产任务，则有1/10的机器报废，如果千第一种生产任务每台机器可以收益10，干第二种生产任务每台机器可以收益7，问怎样分配机器使总收益最大？二、动态规划的基本概念和基本原理1、动态规划的基本概念1.阶段（stage）根据所需解决问题的特点，按照时间或空间顺序把整个过程划分为若干相互联系的阶段，以便按照一定次序求解。例5-1可以分为四个阶段来求解，k-1，2，3，4

内 容 多阶段决策问题中，各个阶段一般是按照时间来划分的，随着时间的发展而产生各个 阶段的决策，从而形成决策序列，这就是动态的含义。在一些与时间无关的静态问题中（如 非线性规划等），可以人为地赋予时间的概念，使其成为一个多阶段决策问题，再用动态 规划方法处理。 多阶段决策问题很多，现举例如下： 例 5-1 最短路问题 如图 5-1 所示，要从 A 地到 E 地铺设管线，中间需要经过三个中间站，两点之间的连 线上的数字表示距离，问应该选择什么路线，使总距离最短？ 图 5-1 例 5-2 机器负荷问题 某工厂有 100 台机器，拟分四个周期使用，在每一个周期有两种生产任务。据经验， 把机器 x1台投入第一种生产任务，则在一个生产周期中将有 1/3x1 台机器报废；余下的机 器全部投入第二种生产任务，则有 1/10 的机器报废，如果干第一种生产任务每台机器可以 收益 10，干第二种生产任务每台机器可以收益 7，问怎样分配机器使总收益最大？ 二、动态规划的基本概念和基本原理 1、动态规划的基本概念 1.阶段（stage） 根据所需解决问题的特点，按照时间或空间顺序把整个过程划分为若干相互联系的阶 段，以便按照一定次序求解。 例 5-1 可以分为四个阶段来求解，k=1，2，3，4。 3 5 2 5 6 3 2 1 7 3 7 5 6 2 2 5 4 3 2 1 B1 A B2 B3 C1 C2 C3 C4 E D2 D1

内容2.状态（state）状态表示各阶段开始所处的自然状况或客观条件，它既是某阶段过程演变的起点，又是前一阶段某种决策的结果。描述状态的变量称为状态变量，常用s表示第k阶段的状态变量。状态变量ss的取值集合称为状态集合，第k阶段的状态集合记为Sk，例如例7-1中，第一阶段状态为A，第二阶段有三个状态：Bi，B2，B3；第三阶段有四个状态：Ci，C2，C3，C4；第四阶段有两个状态：D1，D2；各阶段状态集合分别为：S= (A)S2=(B,B2,B,]Ss= (Ci, C2, C3, C4)S= (D, D,)这里状态的选取应当满足无后效性：系统从某个阶段往后的发展演变，完全由系统本阶段所处的状态及决策所决定，与系统以前的状态及决策无关。只有具有无后效性的多阶段决策过程才适合于用动态规划方法求解。3.决策（decision）当各阶段的状态选定以后，可以做出不同的决定（或选择）从而确定下一个阶段的状态，这种决定（或选择）称为决策。表述决策的变量称为决策变量，常用uk（sk）表示第k阶段当状态为ss时的决策变量。实际问题中，决策变量的取值往往限制在某一范围内，此范围称为允许决策集合，常用Dk（s）表示第k阶段从状态s#出发的允许决策集合，显然uk（Sk）EDK（Sk)。例如例5-1中，第二阶段若从B2出发，可以选择Ci，C2，C3，C4，即允许决策集合为：D2 (B2) = (Ci, C2, C3, C4)当决定选择C时，可以表示为：2 (B) =C34.策略（policy）当各个阶段的决策确定以后，各阶段的决策形成一个决策序列，称此决策序列为一个策略。使系统达到最优效果的策略称为最优策略。在n阶段决策过程中，从第k阶段到终止状态的过程，称为k后部子过程（或称为k子过程），k后部子过程相应的决策序列称为

内 容 2.状态（state） 状态表示各阶段开始所处的自然状况或客观条件，它既是某阶段过程演变的起点，又 是前一阶段某种决策的结果。描述状态的变量称为状态变量，常用 sk 表示第 k 阶段的状态 变量。状态变量 sk 的取值集合称为状态集合，第 k 阶段的状态集合记为 Sk ，例如例 7-1 中，第一阶段状态为 A，第二阶段有三个状态：B1，B2，B3；第三阶段有四个状态：C1， C2，C3，C4；第四阶段有两个状态：D1，D2；各阶段状态集合分别为： S1=｛A｝ S2=｛B1，B2，B3｝ S3=｛C1，C2，C3，C4｝ S4=｛D1，D2｝ 这里状态的选取应当满足无后效性：系统从某个阶段往后的发展演变，完全由系统本 阶段所处的状态及决策所决定，与系统以前的状态及决策无关。只有具有无后效性的多阶 段决策过程才适合于用动态规划方法求解。 3.决策（decision） 当各阶段的状态选定以后，可以做出不同的决定（或选择）从而确定下一个阶段的状 态，这种决定（或选择）称为决策。表述决策的变量称为决策变量，常用 uk（sk）表示第 k 阶段当状态为 sk时的决策变量。实际问题中，决策变量的取值往往限制在某一范围内， 此范围称为允许决策集合，常用 Dk（sk）表示第 k 阶段从状态 sk出发的允许决策集合，显 然 uk（sk）∈Dk（sk）。 例如例 5-1 中，第二阶段若从 B2 出发，可以选择 C1，C2，C3，C4，即允许决策集合 为： D2（B2）=｛C1，C2，C3，C4｝ 当决定选择 C3时，可以表示为： u2（B2）=C3 4.策略（policy） 当各个阶段的决策确定以后，各阶段的决策形成一个决策序列，称此决策序列为一个 策略。使系统达到最优效果的策略称为最优策略。在 n 阶段决策过程中，从第 k 阶段到终 止状态的过程，称为 k 后部子过程（或称为 k 子过程），k 后部子过程相应的决策序列称为

内容k后部子过程策略，简称子策略，记为pkn（s），即：Pkn(sk）=uk(sk),uk+1(sk+1),"*,Un(sn))当k=1时，即由第一阶段某个状态出发做出的决策序列称为全过程策略，简称策略，记为pin（si），即：Pl.n (si)= (u(st), u2 (s2),**, un (sn))5.状态转移方程（statetransferequation）动态规划中，本阶段的状态往往是上一个阶段状态和上一个阶段决策作用的结果。设第k阶段状态为Sk，做出的决策为uk（sk），则第k+1阶段的状态S+i随之确定，他们之间的关系可以表示为：Sk+I=Tk(Skuk）这种表示从第k阶段到第k+1阶段状态转移规律的方程称为状态转移方程，它反映了系统状态转移的递推规律。例如例5-1中，上一阶段的决策就是下一阶段的状态，所以状态转移方程为：Sk+I= uk (Sk)6.指标函数和最优指标函数衡量所选策略优劣的数量指标称为指标函数。它定义在全过程和所有后部子过程，常用Vk表示，即：Vkw=Vkn (sk,uk Sh1,., Sn+)当k=1时，Vin表示初始状态为st，采用策略pi.，时的指标函数值。Vi.n=Vi.n (S,ui,S2,**,Sn+1)动态规划数学模型的指标函数应该具有可分离性，并满足递推关系，即：Vk n (Sk, uk, Sh+1, .*, Sh+1) =Vr[Sk, uk, V1,n (Sk+1, *, Sn+1) ]在阶段k状态为Sk，决策为uk（sk）时得到的反映第k阶段的数量指标vk（sk，us）称为k阶段的指标函数。常见的指标函数形式有两种：（1）任一后部子过程的指标函数是它所包含的各阶段指标的和，即：Vk.n (Sk, Uks *, Sh+) =Zy,(s,u,)Jk

内 容 k 后部子过程策略，简称子策略，记为 pk，n（sk），即： pk，n（sk）=｛uk（sk），uk+1（sk+1），.，un（sn）｝ 当 k=1 时，即由第一阶段某个状态出发做出的决策序列称为全过程策略，简称策略， 记为 p1，n（s1），即： p1，n（s1）=｛u1（s1），u2（s2），.，un（sn）｝ 5.状态转移方程（state transfer equation） 动态规划中，本阶段的状态往往是上一个阶段状态和上一个阶段决策作用的结果。设 第 k 阶段状态为 sk，做出的决策为 uk（sk），则第 k+1 阶段的状态 sk+1随之确定，他们之间 的关系可以表示为： sk+1=Tk（sk，uk） 这种表示从第 k 阶段到第 k+1 阶段状态转移规律的方程称为状态转移方程，它反映了 系统状态转移的递推规律。例如例 5-1 中，上一阶段的决策就是下一阶段的状态，所以状 态转移方程为： sk+1= uk（sk） 6.指标函数和最优指标函数 衡量所选策略优劣的数量指标称为指标函数。它定义在全过程和所有后部子过程，常 用 Vk，n 表示，即： Vk，n=Vk，n（sk，uk，sk+1，.，sn+1） 当 k=1 时，V1，n 表示初始状态为 s1，采用策略 p1，n时的指标函数值。 V1，n=V1，n（s1，u1，s2，.，sn+1） 动态规划数学模型的指标函数应该具有可分离性，并满足递推关系，即： Vk，n（sk，uk，sk+1，.，sn+1）=Ψk[sk，uk，Vk+1，n（sk+1，.，sn+1）] 在阶段 k 状态为 sk，决策为 uk（sk）时得到的反映第 k 阶段的数量指标 vk（sk，uk）称 为 k 阶段的指标函数。 常见的指标函数形式有两种： （1）任一后部子过程的指标函数是它所包含的各阶段指标的和，即： Vk，n（sk，uk，.，sn+1）=  n j k j j u j v (s , )

内容写成递推关系：Vkn（SkUk,***,Sn+1)=Vk(Sh,Uk）+Vh+1n(Sh+1,Uk+1,*",Sn+1)（2）任一后部子过程的指标函数是它所包含的各阶段指标的积，即：Ve, (sk u, *, Sm) = Iy,(s,u,)j=h写成递推关系：Vk.n (sk, uk, ***, S+1) =Vk (sk, uk). Vh1.n (s+1, uk+1, *", Sn+1)指标函数的最优值记为f（se），它表示从第k阶段状态s出发，采取最优策略pkn（s）到第n阶段的终止状态时的最佳指标函数值，即：fr(sx)=,optVkn(Sk,uk,"",Sn+)(uk",un)当k-1时，fi（s）就是从初始状态s:出发到终止状态的最优函数。在不同的问题中，指标函数可以是利润、成本、距离、产品质量或资源消耗等。在最短路线问题中，第k阶段的指标函数vk（sk，uk）通常也用dk（sk，uk）表示。例如例7-1中，d2（B2，C3）表示第二阶段中由点B2到点Cs的距离，f（s）表示从第k阶段点s到终点E的最短距离，f（A）就是所求从A到E的最短距离。2、动态规划的基本思想与基本原理结合例7-1的最短路线问题来阐述动态规划的基本思想。B:图7-2所以求解最短路问题，就可以从最后一段开始，由后向前逐步递推，逐段求各点到终点的最短路线，每段都要用到上一步得到的最短路线，一直到求出从始点到终点的最短路线。下面求解例7-1。k=4时，状态变量s4可取两种状态Di，D2，他们到终点E的最短路长为：f4(D,)=d4 (Di,E)=3u4 (D,) =Eu4（D2)=Ef4(D2)=d4(D2,E)=5

内 容 写成递推关系： Vk，n（sk，uk，.，sn+1）= vk（sk，uk）+ Vk+1，n（sk+1，uk+1，.，sn+1） （2）任一后部子过程的指标函数是它所包含的各阶段指标的积，即： Vk，n（sk，uk，.，sn+1）=  n j k j j u j v (s , ) 写成递推关系： Vk，n（sk，uk，.，sn+1）= vk（sk，uk）·Vk+1，n（sk+1，uk+1，.，sn+1） 指标函数的最优值记为 fk（sk），它表示从第 k 阶段状态 sk 出发，采取最优策略 p * k，n （sk）到第 n 阶段的终止状态时的最佳指标函数值，即：   ( ) ( , , , ) , 1 , ,  k n k k n u u k k f s opt V s u s k n   当 k=1 时，f1（s1）就是从初始状态 s1出发到终止状态的最优函数。在不同的问题中， 指标函数可以是利润、成本、距离、产品质量或资源消耗等。在最短路线问题中，第 k 阶 段的指标函数 vk（sk，uk）通常也用 dk（sk，uk）表示。 例如例 7-1 中，d2（B2，C3）表示第二阶段中由点 B2 到点 C3 的距离，fk（sk）表示从 第 k 阶段点 sk 到终点 E 的最短距离，f1（A）就是所求从 A 到 E 的最短距离。 2、动态规划的基本思想与基本原理 结合例 7-1 的最短路线问题来阐述动态规划的基本思想。 图 7-2 所以求解最短路问题，就可以从最后一段开始，由后向前逐步递推，逐段求各点到终 点的最短路线，每段都要用到上一步得到的最短路线，一直到求出从始点到终点的最短路 线。 下面求解例 7-1。 k=4 时，状态变量 s4可取两种状态 D1，D2，他们到终点 E 的最短路长为： f4（D1）= d4（D1，E）=3 u4（D1）=E f4（D2）= d4（D2，E）=5 u4（D2）=E A B C