1、第第6章章 动态规划动态规划动态规划的基本理论动态规划的基本理论 （2学时）学时）确定型动态规划确定型动态规划 （2学时）学时）随机型动态规划随机型动态规划 （1学时）学时）动态规划的软件计算动态规划的软件计算（1学时）学时）第13讲 动态规划的基本理论(6.1)多阶段决策过程多阶段决策过程动态规划的基本概念和基本方程动态规划的基本概念和基本方程动态规划的最优性原理动态规划的最优性原理最短路问题（逆推法、顺推法）最短路问题（逆推法、顺推法）引例：引例：如图给定一个线路网络，两点之间连线上的数字表示两点间的距离(或费用)。试求一条从A到G的铺管线路，使总距离最短(或总费用最小)。AC1E3E2E
2、1F2F1GD3D2D1C4C3C2B2B1531366822354876533312526638433多阶段决策过程（6.1.1)多阶段决策过程最优化问题：多阶段决策过程最优化问题：有一些活动，它在时间有一些活动，它在时间或空间上可以分成若干个阶段，需要对每个阶段进行决或空间上可以分成若干个阶段，需要对每个阶段进行决策，使得活动的策，使得活动的整体效果最好整体效果最好。每个阶段的决策都不是可以任意确定的，它依赖于当每个阶段的决策都不是可以任意确定的，它依赖于当前的状况，同时，它的决策结果又影响到以后的决策。前的状况，同时，它的决策结果又影响到以后的决策。组成了一个决策序列。组成了一个决策序列
3、。这样的决策过程是在变化的过程中产生的，故有这样的决策过程是在变化的过程中产生的，故有动态动态的含义。处理它的方法称为动态规划的方法。的含义。处理它的方法称为动态规划的方法。方法：方法：多阶段问题转化成一系列互相联系的较容易的多阶段问题转化成一系列互相联系的较容易的单阶段问题。单阶段问题。12n.状态状态决策决策状态状态决策决策决策决策状态状态状态状态状态状态即在系统发展的不同时刻（或阶段）根据系统即在系统发展的不同时刻（或阶段）根据系统所处的状态，不断地做出决策；所处的状态，不断地做出决策；每个阶段都要进行每个阶段都要进行决策决策,目的是使整个过程的决策目的是使整个过程的决策 达到最优效果。
4、达到最优效果。动态决策问题的特点：动态决策问题的特点：系统所处的状态和时刻是进行决策的重要因素；系统所处的状态和时刻是进行决策的重要因素；找到不同时刻的最优决策以及整个过程的最优策略。找到不同时刻的最优决策以及整个过程的最优策略。多阶段决策问题：多阶段决策问题：是动态决策问题的一种特殊形式；是动态决策问题的一种特殊形式；在多阶段决策过程中在多阶段决策过程中,系统的动态过程可以按照时间系统的动态过程可以按照时间进程分为进程分为状态状态相互相互联系联系而又相互而又相互区别区别的各个的各个阶段阶段；（一）、基本概念（一）、基本概念 1、阶段：、阶段：把一个问题的过程，恰当地分为若干个相互联系把一个问
5、题的过程，恰当地分为若干个相互联系的的阶段阶段，以便于按一定的次序去求解。，以便于按一定的次序去求解。描述阶段的变量称为描述阶段的变量称为阶段变量阶段变量,常用常用k表示。阶段表示。阶段的划分，一般是根据时间和空间的自然特征来进行的，的划分，一般是根据时间和空间的自然特征来进行的，但要便于问题转化为多阶段决策。但要便于问题转化为多阶段决策。年、月、年、月、路段路段 K1，2，3，4，5，6动态规划的基本概念（6.1.2)2、状态：表示每个阶段开始所处的、状态：表示每个阶段开始所处的自然状况或客自然状况或客观条件观条件。通常一个阶段有若干个状态，描述过程状。通常一个阶段有若干个状态，描述过程状态
6、的变量称为态的变量称为状态变量，状态变量，常用常用Sk表示。表示。一个数、一个数、一组数、一组数、一个向量一个向量 状态变量的取值有一定的允许集合或范围，此集状态变量的取值有一定的允许集合或范围，此集合称为合称为状态允许集合状态允许集合。注意：注意：要明确每个阶段状态的集合或者范围。要明确每个阶段状态的集合或者范围。“状态状态”具有具有“无后效性无后效性”（“马尔科夫性马尔科夫性”）：）：如果某阶段的状态给定后，当前的状态是以往历史如果某阶段的状态给定后，当前的状态是以往历史的总结，则在这阶段以后过程的发展不受这阶段以的总结，则在这阶段以后过程的发展不受这阶段以前各阶段的影响。前各阶段的影响。
7、如：如：S2=B1，B2；S3=C1，C2，C3，C4 3、决策：表示当过程处于某一阶段的某个状态时，、决策：表示当过程处于某一阶段的某个状态时，可以作出不同的决定，从而确定下一阶段的状态可以作出不同的决定，从而确定下一阶段的状态，这这种决定称为种决定称为决策决策。描述决策的变量，称为描述决策的变量，称为决策变量决策变量。决策变量是状态变。决策变量是状态变量的函数。可用一个数、一组数或一向量（多维情形）量的函数。可用一个数、一组数或一向量（多维情形）来描述。来描述。Uk(Sk)表示第表示第k阶段处于阶段处于Sk状态时的决策变量。状态时的决策变量。如：如：U2(B1)C2，表示处于第二阶段，以，
8、表示处于第二阶段，以B1为始点为始点选择选择C2作为第二阶段的终点。作为第二阶段的终点。Dk(Sk)表示第表示第k k阶段处于阶段处于S Sk k状态时的状态时的允许决策集合。允许决策集合。D2(B1)C1,C2,C3。Uk(Sk)Dk(Sk)。在实际问题中决策变量的取值往往在某一范围之内，在实际问题中决策变量的取值往往在某一范围之内，此范围称为此范围称为允许决策集合允许决策集合。4 4、策略：是一个按顺序排列的决策组成的集合。在、策略：是一个按顺序排列的决策组成的集合。在实际问题中，可供选择的策略有一定的范围，称为实际问题中，可供选择的策略有一定的范围，称为允允许策略集合，许策略集合，用用P
9、来表示来表示。从允许策略集合中找出达到。从允许策略集合中找出达到最优效果的策略称为最优效果的策略称为最优策略最优策略。把从第一阶段开始到最后阶段终止的整个决策过程，把从第一阶段开始到最后阶段终止的整个决策过程，称为问题的全过程；而把从第称为问题的全过程；而把从第k k阶段开始到最后阶段阶段开始到最后阶段终止的决策过程，称为终止的决策过程，称为k k子过程。子过程。在全过程上，各阶段的决策按顺序排列组成的决策序在全过程上，各阶段的决策按顺序排列组成的决策序列列p p1,n1,n u u1 1,u,u2 2,u,un n 称为全过程策略，简称策称为全过程策略，简称策略；略；而在而在k k子过程上的
10、决策序列子过程上的决策序列p pk,nk,n u uk k,u,uk+1k+1,u,un n 称为称为k k子过程策略，也简称子策略。子过程策略，也简称子策略。5 5、状态转移方程：、状态转移方程：若第若第k k阶段的状态变量值为阶段的状态变量值为s sk k，当决策变量当决策变量u uk k的取值决定后，下一阶段状态变量的取值决定后，下一阶段状态变量s sk+1k+1的值也就完全确定。即的值也就完全确定。即s sk+1k+1的值对应于的值对应于s sk k和和u uk k的值。的值。这种对应关系记为这种对应关系记为s sk+1k+1T Tk k(s(sk k,u,uk k)，称为状态转移方称
11、为状态转移方程。状态转移方程描述了由一个阶段的状态到下一程。状态转移方程描述了由一个阶段的状态到下一阶段的状态的演变规律。阶段的状态的演变规律。如：如：S3=T2(S2,U2)C2T2(B1，C2),(),(),(221112211231112kkkkusususTsususTsusTs 图示如下：图示如下：状态转移方程是确定状态转移方程是确定过程由一个状态到另过程由一个状态到另一个状态的演变过程。一个状态的演变过程。如果第如果第k阶段状态变量阶段状态变量sk的值、该阶段的决策的值、该阶段的决策变量一经确定，第变量一经确定，第k+1阶段状态变量阶段状态变量sk+1的值的值也就确定。也就确定。状
12、态转移方程（一般形式）状态转移方程（一般形式）12ks1u1s2u2s3skuksk+1 能用动态规划方法求解的多阶段决策过程是一类能用动态规划方法求解的多阶段决策过程是一类特殊的多阶段决策过程，即特殊的多阶段决策过程，即具有无后效性具有无后效性的多阶段的多阶段决策过程。决策过程。如果状态变量不能满足无后效性的要求，应适当如果状态变量不能满足无后效性的要求，应适当地改变状态的定义或规定方法。地改变状态的定义或规定方法。),(),(),(122231112kkkkusTsusTsusTs 动态规划中能动态规划中能处理的状态转移处理的状态转移方程的形式方程的形式。状态具有无后效性的多阶段决策过程的
13、状态转状态具有无后效性的多阶段决策过程的状态转移方程如下移方程如下无后效性无后效性(马尔可夫性马尔可夫性)如果某阶段状态给定后，则在这个阶段以后过如果某阶段状态给定后，则在这个阶段以后过程的发展不受这个阶段以前各段状态的影响；程的发展不受这个阶段以前各段状态的影响；过程的过去历史只能通过当前的状态去影响它未过程的过去历史只能通过当前的状态去影响它未来的发展；来的发展；构造动态规划模型时，要充分注意是否满足构造动态规划模型时，要充分注意是否满足无后效性的要求；无后效性的要求；状态变量要满足无后效性的要求状态变量要满足无后效性的要求；6 6、指标函数和最优值函数：用来衡量所实现过程、指标函数和最优
14、值函数：用来衡量所实现过程优劣的一种数量指标，为优劣的一种数量指标，为指标函数指标函数。常用Vk,n表示。Vk,nVk,n(Sk，Uk，Sk1，,Sn+1)k=1,2,n 在不同的问题中，指标函数的含义是不同的，它在不同的问题中，指标函数的含义是不同的，它可能是距离、利润、成本、产量或资源消耗等。可能是距离、利润、成本、产量或资源消耗等。动态规划模型的指标函数，应具有动态规划模型的指标函数，应具有可分离性可分离性，并，并满足满足递推递推关系关系。即即Vk,n可表示为可表示为Sk，Uk，Vk1,n的函数。的函数。Vk,n(Sk，Uk，Sk1，Sn+1)k(Sk，Uk，Vk1,n(Sk1，Uk1,
15、Sn+1)常见的指标函数有常见的指标函数有：1)整个过程和它的任一子过程的指标函数是它所包含的各阶段的指标的和和。Vk,n（Sk，Uk，Sk1，,Sn+1）Vk,n（Sk，Uk，Sk1，,Sn+1）vk(sk,uk)+Vk+1,n（Sk+1，Uk+1，Sk2，,Sn+1）2)整个过程和它的任一子过程的指标函数是它所包含的各阶段的指标的乘积乘积，即：Vk,n（Sk，Uk，Sk1，,Sn+1）nkjjjjusv),(nkjjjjusv),(Vk,n(Sk，Uk，Sk1，,Sn+1)vk(sk,uk)Vk+1,n(Sk+1，Uk+1，Sk2，,Sn+1)指标函数的最优值称为指标函数的最优值称为最优值
16、函数，最优值函数，记为记为f fk k(s(sk k)。表示从第k阶段的状态s sk k开始到第n阶段的终止状态的过程，采取最优策略所得到的指标函数值。如：f1(A)18，f2(B1)13。即即 f fk k(s(sk k)opt V opt Vk,nk,n(s(sk k,u,uk k,s,sn n,u,un n)（u uk k,u,un n）式中式中的的“optopt”（optimizationoptimization）可根据具体问题而取可根据具体问题而取minmin或或maxmax。一般情况下，k阶段和k+1阶段之间的递推关系式递推关系式可写成：fk(Sk)opt vk(Sk,Uk(Sk)
17、+fk+1(Sk+1)k=n,n-1,2,1 fk(Sk)opt vk(Sk,Uk(Sk)+fk+1(Uk(Sk)k=n,n-1,2,1 边界条件为:fn+1(Sn+1)=0这种递推关系式称为动态规划的基本方程动态规划的基本方程。12ks1u1s2u2s3skuksk+1v1(s1,u1)v2(s2,u2)vk(sk,uk)小结小结:),()(1,susVoptsfnkknkkkuunk),(,111,1nkknkkkksusVus方程方程 :状态转移方程状态转移方程),(1kkkkusTs概念概念 :阶段变量阶段变量k k状态变量状态变量s sk k决策变量决策变量u uk k;指标指标:)
18、,(111,nkkkknknksususVV动态规划本质上是多阶段决策过程动态规划本质上是多阶段决策过程;效益效益指标函数形式指标函数形式:和、和、积积无后效性无后效性),(111,nkkkknksususV可递推可递推,*2*1nuuu,*2*1nsss解多阶段决策过程问题，求出解多阶段决策过程问题，求出 最优策略最优策略，即最优，即最优决策序列决策序列 susvoptsfnkknkkkuunk1,f1(s1)最优轨线最优轨线，即执行最优策略时的即执行最优策略时的状态序列状态序列 最优目标函数值最优目标函数值),(*1*1*,1*,1nnnnususVV从从 k 到终点最优策略到终点最优策略
19、子策略的最优目标函数值子策略的最优目标函数值 1、动态规划方法的关键在于正确地写出基本的递推、动态规划方法的关键在于正确地写出基本的递推关系式和恰当的边界条件（简称基本方程）。要做到关系式和恰当的边界条件（简称基本方程）。要做到这一点，就必须将问题的过程分成几个相互联系的阶这一点，就必须将问题的过程分成几个相互联系的阶段，恰当的选取状态变量和决策变量及定义最优值函段，恰当的选取状态变量和决策变量及定义最优值函数，从而把一个大问题转化成一组同类型的子问题，数，从而把一个大问题转化成一组同类型的子问题，然后逐个求解。即从边界条件开始，逐段递推寻优，然后逐个求解。即从边界条件开始，逐段递推寻优，在每
20、一个子问题的求解中，均利用了它前面的子问题在每一个子问题的求解中，均利用了它前面的子问题的最优化结果，依次进行，最后一个子问题所得的最的最优化结果，依次进行，最后一个子问题所得的最优解，就是整个问题的最优解。优解，就是整个问题的最优解。（二）、动态规划的基本思想和基本方程（二）、动态规划的基本思想和基本方程 2、在多阶段决策过程中，动态规划方法是既把当前、在多阶段决策过程中，动态规划方法是既把当前一段和未来一段分开，又把当前效益和未来效益结合一段和未来一段分开，又把当前效益和未来效益结合起来考虑的一种最优化方法。因此，每段决策的选取起来考虑的一种最优化方法。因此，每段决策的选取是从全局来考虑的
21、，与该段的最优选择答案一般是不是从全局来考虑的，与该段的最优选择答案一般是不同的同的.最优化原理：作为整个过程的最优策略具有这样的最优化原理：作为整个过程的最优策略具有这样的性质：无论过去的状态和决策如何，相对于前面的决性质：无论过去的状态和决策如何，相对于前面的决策所形成的状态而言，余下的决策序列必然构成最优策所形成的状态而言，余下的决策序列必然构成最优子策略。子策略。”也就是说，一个最优策略的子策略也是最也就是说，一个最优策略的子策略也是最优的。优的。3、在求整个问题的最优策略时，由于初始状态是、在求整个问题的最优策略时，由于初始状态是已知的，而每段的决策都是该段状态的函数，故最优已知的，
22、而每段的决策都是该段状态的函数，故最优策略所经过的各段状态便可逐段变换得到，从而确定策略所经过的各段状态便可逐段变换得到，从而确定了最优路线。了最优路线。最短路问题最短路问题：如图给定一个线路网络，两点之间连线上如图给定一个线路网络，两点之间连线上的数字表示两点间的距离的数字表示两点间的距离(或费用或费用)。试求一条从。试求一条从A到到G的铺的铺管线路，使总距离最短管线路，使总距离最短(或总费用最小或总费用最小)。AC1E3E2E1F2F1GD3D2D1C4C3C2B2B1531366822354876533312526638433从A点到G点可分成6个阶段。以A为起点，终点有两个B1、B2，
23、有两个选择。若选择B2，则B2为第一阶段决策的结果。同时它又是第二阶段的开始状态。当每个阶段做出决策的结果，直接影响到后面的选择和决策的结果。最短路线有一个重要特性最短路线有一个重要特性：如果从起点A经过C2点和D1点到达终点G是一条最短的路线，则由C2 点经过D1 点到达G点的这条子路线，是由C2 点出发到达G点所有路线中的最短路线。寻找最短路线的方法寻找最短路线的方法，从最后一段开始，由后向前逐步推进，找出各点到G点的最短路线，最后就能确定一条从A点到G点的最短路线。阶阶 段段 6 本阶段始点本阶段始点（状态）（状态）本阶段各终点本阶段各终点（决策）（决策）到到G点的最短点的最短距离距离本
24、阶段最优终本阶段最优终点点（最优决策）（最优决策）G F14 4 GF233G 最短路线F1G 最短路线F2G阶阶 段段 5本阶段始点本阶段始点（状态）（状态）本阶段各终点本阶段各终点（决策）（决策）到到G点的最短点的最短距离距离本阶段最优终本阶段最优终点点（最优决策）（最优决策）F1F2E13475387F1E25492355F2E364106399F2 最短路线E1F1G 最短路线E2F2G 最短路线E3F2G阶阶 段段 4本阶段始本阶段始点点(状态状态)本阶段各终点（决策）本阶段各终点（决策）到到G点的点的最短距离最短距离本阶段最优本阶段最优终点终点（最优决策）（最优决策）E1E2E3D
25、1279257 7E2D215629116E2D335839128E2 最短路线D1E2F2G 最短路线D2E2F2G 最短路线D3E2F2G阶阶 段段 3本阶段始本阶段始点点(状态状态)本阶段各终点（决策）本阶段各终点（决策）到到G点的点的最短距离最短距离本阶段最优本阶段最优终点终点（最优决策）（最优决策）D1D2D3C16+7=138+6=14 13D1C23+7=10 5+6=11 10D1C3 3+6=93+8=119D2C4 8+6=144+8=1212D3C1D1E2F2GC2D1E2F2GC3D2E2F2GC4D3E2F2G阶阶 段段 2本阶段本阶段始点始点(状状态态)本阶段各终
26、点（决策）本阶段各终点（决策）到到G点的点的最短距离最短距离本阶段最优本阶段最优终点终点（最优决策）（最优决策）C1C2C3C4B11+13=143+10=136+9=15 13C2B2 8+10=187+9=166+12=1816C3B1C2D1E2F2GB2C3D2E2F2G阶阶 段段 1 本阶段始点本阶段始点（状态）（状态）本阶段各终点（决本阶段各终点（决策）策）到到G点的最短点的最短距离距离本阶段最优终本阶段最优终点点（最优决策）（最优决策）B1B2A5+13=183+16=1918B1AB1C2D1E2F2G 最短路线为AB1C2D1E2F2GAC1E3E2E1F2F1GD3D2D1
27、C4C3C2B2B10349578671291013161318 基本方程基本方程 ：通常：通常动态规划问题动态规划问题的的最优值函数最优值函数满足满足递推关系式递推关系式。设过程指标函数为各阶段指标函数的设过程指标函数为各阶段指标函数的和的形式，即和的形式，即V Vk,nk,nvvj j(s(sj j,u,uj j)，则有则有 f fk k(s(sk k)opt v opt vk k(s(sk k,u,uk k)+f)+fk+1k+1(s(sk+1k+1)u uk kDDk k(s(sk k)(k kn,n-1,n,n-1,1),1)递推方程递推方程 f fn+1n+1(s(sn+1n+1)
28、0 0 边界条件边界条件递推方程和边界条件一起称为动态规划基本方程递推方程和边界条件一起称为动态规划基本方程.可根据边界条件，从可根据边界条件，从k=n开始，由后向前逆推，逐步开始，由后向前逆推，逐步求得各阶段的最优决策和相应的最优值，最后求出求得各阶段的最优决策和相应的最优值，最后求出f1(s1)时，就得到整个问题的最优解。时，就得到整个问题的最优解。（三）、建立动态规划模型的步骤（三）、建立动态规划模型的步骤 1 1、划分阶段、划分阶段划分阶段是运用动态规划求解多阶段决策问题的第一划分阶段是运用动态规划求解多阶段决策问题的第一步，在确定多阶段特性后，按时间或空间先后顺序，步，在确定多阶段特
29、性后，按时间或空间先后顺序，将过程划分为若干相互联系的阶段。对于静态问题要将过程划分为若干相互联系的阶段。对于静态问题要人为地赋予人为地赋予“时间时间”概念，以便划分阶段。概念，以便划分阶段。2 2、正确选择状态变量、正确选择状态变量Sk选择变量既要能确切描述过程演变又要满足无后效性，选择变量既要能确切描述过程演变又要满足无后效性，而且各阶段状态变量的取值能够确定。一般地，状态而且各阶段状态变量的取值能够确定。一般地，状态变量的选择是从过程演变的特点中寻找。变量的选择是从过程演变的特点中寻找。3 3、确定决策变量、确定决策变量Uk及允许决策集合及允许决策集合Dk通常选择所求解问题的关键变量作为
30、决策变量，同时通常选择所求解问题的关键变量作为决策变量，同时要给出决策变量的取值范围，即确定允许决策集合。要给出决策变量的取值范围，即确定允许决策集合。4 4、确定状态转移方程、确定状态转移方程Sk+1=Tk(Sk,Uk)根据根据k 阶段状态变量和决策变量，写出阶段状态变量和决策变量，写出k+1阶段状态变量，阶段状态变量，状态转移方程应当具有递推关系。状态转移方程应当具有递推关系。5 5、正确写出指标函数、正确写出指标函数V Vk,n的关系，它应满足下面三个的关系，它应满足下面三个性质：性质：V Vk,n是定义在全过程和所有后部子过程上的数量函数是定义在全过程和所有后部子过程上的数量函数具有可
31、分离性，并满足递推关系，即具有可分离性，并满足递推关系，即Vk,n(Sk,Uk,Sk1,Sn+1)=k(Sk,Uk,Vk1,n(Sk1,Uk1,Sn+1)函数函数k（Sk，Uk，Vk1,n）对于变量对于变量Vk1,n要严格单调。要严格单调。6 6、恰当地定义最优指标函数、恰当地定义最优指标函数 阶段指标函数是指第阶段指标函数是指第k 阶段的收益，最优指标函数是阶段的收益，最优指标函数是指从第指从第k 阶段状态出发到第阶段状态出发到第n 阶段末所获得收益的最优值。阶段末所获得收益的最优值。动态规划模型分类 过程过程变量变量确定确定随机随机离散离散连续连续离散确定型离散确定型离散随机型离散随机型连
32、续确定型连续确定型连续随机型连续随机型7、写出恰当的边界条件、写出恰当的边界条件，从边界条件开始，逐段递推寻优，在每一个子问题的求解中，均用了它前面的子问题的最优化结果，依次进行，最后一个子问题所得的最优结果，就是这个问题的最优解，并找到相应的最优策略最优策略。f fk k(s(sk k)MindMindk k(u(uk k)+f)+fk+1k+1(s(sk+1k+1)u uk kDDk k(s(sk k)k k6,5,4,3,2,16,5,4,3,2,1f f7 7(s(s7 7)0 0AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G53136876683533842212333
33、5526643用用dk(sk,uk)vk(sk,uk)表示从点表示从点Sk到到Sk1的距离。的距离。Vk,n表表示在第示在第k阶段从点阶段从点Sk到终点的距离。到终点的距离。fk(Sk)表示第表示第k阶段状阶段状态为态为Sk时，从第时，从第k阶段开始到第阶段开始到第n阶段的最短距离。阶段的最短距离。f7(S7)0此问题的基本方程为此问题的基本方程为k=5k=5，出发点，出发点E1E1、E2E2、E3E3 73543min,min2621516115FfFEdFfFEdu5(E1)=F1E1 F1 G 53245min,min262251612525FfFEdFfFEdfEAB1B2C1C2C3
34、C4D1D2D3E1E2E3F1F2G531368766835338422123335526643)(15Efu5(E2)=F2E2 F2 G 93646min,min262351613535FfFEdFfFEdfEu5(E3)=F2E3 F2 Gk=6k=6,F1 G f f6 6(F1)=4(F1)=4F F2 2 G ,f,f6 6(F2)=3(F2)=3k=4，f4(D1)=7 u4(D1)=E2f4(D2)=6 u4(D2)=E2f4(D3)=8 u4(D3)=E2k=2,f2(B1)=13 u2(B1)=C2 f2(B2)=16 u2(B2)=C3f3(C1)=13 u3(C1)=
35、D1f3(C2)=10 u3(C2)=D1f3(C3)=9 u3(C3)=D1f3(C4)=12 u3(C4)=D3k=3,=minf1(A)=mind1(A,B1)+f2(B1)d1(A,B2)+f2(B2)5+133+16=18k=1,u1(A)=B1u2(B1)=C2u3(C2)=D1u4(D1)=E2u1(A)=B1u2(B1)=C2u3(C2)=D1u4(D1)=E2u5(E1)=F1E1 F1 Gu5(E2)=F2E2 F2 Gu5(E3)=F2E3 F2 G7 5 9 u5(E2)=F2u6(F2)=G最优策略最优策略AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G5
36、31368763685338422213335256643状态转移图状态转移图Au1(A)B1u2(B1)C2u6(F2)G 最短路线为AB1C2D1E2F2GAC1E3E2E1F2F1GD3D2D1C4C3C2B2B10349578671291013161318标号法标号法逆序解法逆序解法逆着阶段顺序的方向，由后向前推算。逆着阶段顺序的方向，由后向前推算。把寻求最优策略看作连续递推过程，从最终阶把寻求最优策略看作连续递推过程，从最终阶段开始，逆着实际过程的进展方向逐段求解；段开始，逆着实际过程的进展方向逐段求解；在每一阶段求解过程中都是其后部子过程最优在每一阶段求解过程中都是其后部子过程最优
37、策略的基础上，再考虑本阶段的指标函数，求策略的基础上，再考虑本阶段的指标函数，求出本阶段的最优策略；出本阶段的最优策略；直到第一阶段为止直到第一阶段为止。f fk k(s(sk k)opt v opt vk k(s(sk k,u,uk k)+f)+fk+1k+1(s(sk+1k+1)u uk kDDk k(s(sk k)(k kn,n-1,n,n-1,1),1)f fn+1n+1(s(sn+1n+1)0 0AC1E3E2E1F2F1GD3D2D1C4C3C2B2B118151615131313131191086350顺序解法顺序解法顺序解法顺序解法0)(sfn1,2,.,k)(sf)u,(sv
38、opt)(sf10k1kk1kk(sDu1kk1)kkk f fk k(S(Sk+1k+1)含义含义:表示第表示第K K阶段的结束状态为阶段的结束状态为S Sk+1k+1,从第从第一阶段到一阶段到K K阶段的最优指标值阶段的最优指标值.一般的，当初始状态给定时，用逆推法比较方便；当终止状态给定时，用顺推法比较方便。后向法求出了各点到目标地的最短路线；而前向法求出了起点到各目的地的最短路线。最优性原理：美国运筹学家贝尔曼提出最优性原理：美国运筹学家贝尔曼提出无论过去的状态和决策如何，对前面的决策所形成的无论过去的状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。状态而言
39、，余下的诸决策必须构成最优策略。将决策问题划分为若干个阶段，全过程的优化问题就将决策问题划分为若干个阶段，全过程的优化问题就分解为子过程的优化问题，由后向前逐步倒推，最优化分解为子过程的优化问题，由后向前逐步倒推，最优化的子过程逐渐成为全过程最优。的子过程逐渐成为全过程最优。作为全过程的最优策略作为全过程的最优策略P*1,n的组成部分的任一子策略的组成部分的任一子策略P*k,n(Sk)，一定是从状态，一定是从状态Sk 出发直至终点的最优策略。出发直至终点的最优策略。3、动态规划的最优性原理、动态规划的最优性原理“最优性原理最优性原理”仅仅是策略最优性的必要条件必要条件，非充分条件非充分条件。充
40、分条件应是动态规划的基本方程基本方程。运筹学运筹学 第八、九章第八、九章 动态规划动态规划第14讲 确定型性动态规划(6.2)最短路问题最短路问题资源分配问题资源分配问题生产与存储问题生产与存储问题动态规划和静态规划的关系动态规划和静态规划的关系自学背包问题、排序问题、货郎担问题自学背包问题、排序问题、货郎担问题运筹学运筹学 第八、九章第八、九章 动态规划动态规划 资源分配问题：资源分配问题：把有限的资源把有限的资源(如资金、材料、设备、人力等如资金、材料、设备、人力等)分分配给若干使用者，而使某一指标为最优的问题即配给若干使用者，而使某一指标为最优的问题即为资源分配问题。为资源分配问题。资源
41、可以有一种或若干种，资源可以有一种或若干种，只有一种资源可供分配的问题称之为一维资源分只有一种资源可供分配的问题称之为一维资源分配问题。配问题。资源分配问题(6.2.2)运筹学运筹学 第八、九章第八、九章 动态规划动态规划例例1：某工业部门按国家计划的安排，拟将某高效率某工业部门按国家计划的安排，拟将某高效率的设备五台，分配给所属的甲、乙、丙三个工厂，各工的设备五台，分配给所属的甲、乙、丙三个工厂，各工厂若获得这种设备之后，可以为国家提供的盈利如下表厂若获得这种设备之后，可以为国家提供的盈利如下表所示。问：这五台设备如何分配给各工厂，才能使国家所示。问：这五台设备如何分配给各工厂，才能使国家得
42、到的盈利最大。得到的盈利最大。1 1、一维资源分配问题、一维资源分配问题运筹学运筹学 第八、九章第八、九章 动态规划动态规划 动态规划的数学模型动态规划的数学模型将三个分厂看作是三个阶段，即阶段变量将三个分厂看作是三个阶段，即阶段变量 k=1,2,3k=1,2,3;状态变量状态变量s sk k 表示第表示第k k 阶段初可分配的设备台数阶段初可分配的设备台数,0s0sk k 55;决策变量决策变量x xk k 表示第表示第k k 阶段分配给分厂阶段分配给分厂k k 的设备台数，的设备台数，允许决策集合允许决策集合X Xk k(s sk k)=)=x xk k 00 x xk k ssk k;状
43、态转移方程为状态转移方程为 s sk+1k+1=s sk k-x xk k;阶段指标阶段指标P Pk k(s sk k,x xk k)表示第表示第k k 阶段从阶段从s sk k台设备中分配给台设备中分配给k k 分厂分厂x xk k 台设备的阶段效益台设备的阶段效益;最优指数函数最优指数函数f fk k(s sk k)表示第表示第k k阶段从阶段从s sk k 开始到最后阶段采开始到最后阶段采用最优分配策略取得的最大的效益值用最优分配策略取得的最大的效益值;递推方程函数式递推方程函数式 0)()(),()(4411)(maxsfsfxsPsfkkkkkSXxkkkkk边界条件：基本方程：运筹
44、学运筹学 第八、九章第八、九章 动态规划动态规划第三阶段第三阶段：设将S3台设备（S30,1,2,3,4,5）全部分配给丙厂时，最大盈利值为：f3(S3)maxP3(X3)其中X3S30,1,2,3,4,5 X3*表示使得表示使得f3(S3)为最大值时的最优决策。为最大值时的最优决策。X3S3 P3(X3)f3(S3)X3*01234500 0014 4126 62311 113412 124512125逆序求解逆序求解表表9 91 1运筹学运筹学 第八、九章第八、九章 动态规划动态规划第二阶段第二阶段：设将设将S2台设备（台设备（S20,1,2,3,4,5）分配给乙厂和）分配给乙厂和丙厂时，
45、对每一个丙厂时，对每一个S2值，都有一种最优分配方案，使得最大盈值，都有一种最优分配方案，使得最大盈利值为：利值为：f2(S2)max P2(X2)+f3(S2X2)，X20,1,2,3,4,5X2S2P2(X2)f3(S2X2)f2(S2)X2*01234500 0010450 5120654100 102301156104110 1424012511106114110 161,250125121011116114110212表表9 92 2运筹学运筹学 第八、九章第八、九章 动态规划动态规划第一阶段第一阶段：设将S1台设备（S15）分配给甲厂、乙厂和丙厂时，则最大盈利值为：f1(S1)ma
46、x P1(X1)+f2(5X1)其中，X10,1,2,3,4,5X1S1P1(X1)f2(5X1)f1(5)X1*0123455021 316 714 910 125 130210,2按计算表格的顺序反推，可知最优分配方案有两个：按计算表格的顺序反推，可知最优分配方案有两个：1 1）由）由X X1 1*0 0，S S2 2S S1 1X X1 1*5 50 05 5。再由。再由表表9 92 2，可知，可知X X2 2*2 2。S S3 3S S2 2X X2 2*5 52 23 3，故，故X X3 3*S S3 33 3。即得甲厂。即得甲厂分得分得0 0台，乙厂分得台，乙厂分得2 2台，丙厂分
47、得台，丙厂分得3 3台。台。2 2）由）由X X1 1*2 2，S S2 2S S1 1X X1 1*5 52 23 3。再由表。再由表9 92 2，可知，可知X X2 2*2 2。S S3 3S S2 2X X2 2*3 32 21 1，故，故X X3 3*S S3 31 1。即得甲厂。即得甲厂分得分得2 2台，乙厂分得台，乙厂分得2 2台，丙厂分得台，丙厂分得1 1台。台。以上两种最优方案的总盈利均为以上两种最优方案的总盈利均为2121万元。万元。运筹学运筹学 第八、九章第八、九章 动态规划动态规划例例2 2 机器负荷问题机器负荷问题某种机器可在高低两种不同的某种机器可在高低两种不同的负荷
48、下进行生产，设机器在高负荷下生产的产量函数为负荷下进行生产，设机器在高负荷下生产的产量函数为g=8u1，其中，其中u u1 1为投入生产的机器数量，年完好率为为投入生产的机器数量，年完好率为a=0.7=0.7；在低负荷下生产的产量函数为在低负荷下生产的产量函数为h=5y，其中，其中y y为投入生产的为投入生产的机器数量，年完好率为机器数量，年完好率为b=0.9。假定开始生产时完好的机。假定开始生产时完好的机器数量器数量S S1 110001000台，试问每年如何安排机器在高低负荷下台，试问每年如何安排机器在高低负荷下的生产，使在五年内生产的产品总产量最高。的生产，使在五年内生产的产品总产量最高
49、。2 2、资源连续分配问题、资源连续分配问题运筹学运筹学 第八、九章第八、九章 动态规划动态规划 动态规划的数学模型动态规划的数学模型每年为一个阶段，即阶段变量每年为一个阶段，即阶段变量 k=1,2,3,4,k=1,2,3,4,5;5;状态变量状态变量s sk k 表示第表示第k k年初所拥有的完好机器台数，年初所拥有的完好机器台数，s s1 1=1000=1000;决策变量决策变量u uk k 表示第表示第k k年投入高负荷生产的机器数年投入高负荷生产的机器数 ，允许决策集合允许决策集合U Uk k(s sk k)=)=u uk k 00 u uk k s sk k;skuk表示为第表示为第
50、k年初分配在低负荷下生产的机器数量。年初分配在低负荷下生产的机器数量。状态转移方程为状态转移方程为 s sk+1k+1=au uk k+b b(s sk ku uk k)=)=0.7u0.7uk k+0.90.9(s sk ku uk k)=0.9s0.9sk k 0.2 0.2u uk k;阶段指标阶段指标v vk k(s sk k,x xk k)表示第表示第k k年的产量年的产量 ：v vk k(s sk k,u uk k)=)=8u8uk k +5 5(s sk ku uk k)=)=5s5sk k+3u3uk k;最优指数函数最优指数函数f fk k(s sk k)表示第表示第k k阶
