第七章动态规划(第节)

1、第第1页页第第2页页1.动态规划的产生动态规划的产生动态规划是运筹学的一个重要分支，它是解决多阶动态规划是运筹学的一个重要分支，它是解决多阶段决策过程最优化的一种数学方法。段决策过程最优化的一种数学方法。 动态规划产生于动态规划产生于20世纪世纪50年代初，由美国数学家贝年代初，由美国数学家贝尔曼（尔曼（R. Bellman）等人提出。）等人提出。 第第3页页（1）把多阶段决策问题）把多阶段决策问题 多个互相联系的单阶段多个互相联系的单阶段问题，逐个解决。问题，逐个解决。 （2）提出最优性原理，并成功解决了生产管理、工）提出最优性原理，并成功解决了生产管理、工程技术等方面的多个实际问题。程技术

2、等方面的多个实际问题。 第第4页页2. 动态规划的特点动态规划的特点 （1）没有一个标准的数学表达式和明确定义的一组）没有一个标准的数学表达式和明确定义的一组规则，必须对具体问题进行具体分析处理（线性规规则，必须对具体问题进行具体分析处理（线性规划有标准的数学表达式，任何线性规划问题都可以划有标准的数学表达式，任何线性规划问题都可以利用单纯形法进行求解）。利用单纯形法进行求解）。 第第5页页（2）动态规划是考查问题的一种途径，而不是一种）动态规划是考查问题的一种途径，而不是一种特殊算法。特殊算法。 （3）许多问题，特别是离散性问题，用动态规划方）许多问题，特别是离散性问题，用动态规划方法去处理

3、，常比线性规划和非线性规划更有效。法去处理，常比线性规划和非线性规划更有效。 第第6页页3. 动态规划模型的分类动态规划模型的分类 根据动态规划模型中的时间参量是离散变量还是连根据动态规划模型中的时间参量是离散变量还是连续变量：续变量： （1）离散型。）离散型。 （2）连续型。）连续型。 第第7页页根据动态规划模型中的各类参数是已知的还是未根据动态规划模型中的各类参数是已知的还是未知的：知的： （1）确定型。）确定型。 （2）随机型。）随机型。 第第8页页动态规划模型动态规划模型离散确定型动态规划模型离散确定型动态规划模型离散随机型动态规划模型离散随机型动态规划模型连续确定型动态规划模型连续确

4、定型动态规划模型连续随机型动态规划模型连续随机型动态规划模型本章主要针对离散确定型问题和连续确定型问题，本章主要针对离散确定型问题和连续确定型问题，介绍动态规划的基本思想、原理和方法。介绍动态规划的基本思想、原理和方法。 第第9页页第第10页页在生产和科学实验中，有一类特殊的活动过程，它在生产和科学实验中，有一类特殊的活动过程，它们可以按时间顺序分解成若干个相互联系的阶段，们可以按时间顺序分解成若干个相互联系的阶段，而每一个阶段都要做出决策，当每个阶段的决策都而每一个阶段都要做出决策，当每个阶段的决策都确定后，就形成一个决策序列。确定后，就形成一个决策序列。 第第11页页这种由前后相互联系、具

5、有链状结构的多个阶段所这种由前后相互联系、具有链状结构的多个阶段所组成的活动过程称为多阶段决策过程。组成的活动过程称为多阶段决策过程。 1决策决策状态状态2决策决策状态状态n决策决策状态状态状态状态状态状态第第12页页多阶段决策过程的特点：多阶段决策过程的特点： 1. 本阶段的决策依赖于本阶段面临的状态；本阶段的决策依赖于本阶段面临的状态； 2. 本阶段的决策决定着下一阶段的状态（即引起状本阶段的决策决定着下一阶段的状态（即引起状态的转移）；态的转移）； 第第13页页决策序列就是在变化的状态中产生的，故有决策序列就是在变化的状态中产生的，故有“动态动态”的含义，从而把处理这种多阶段决策过程的方

6、法称的含义，从而把处理这种多阶段决策过程的方法称为动态规划方法。为动态规划方法。 第第14页页使用动态规划方法解决多阶段决策过程问题，首先使用动态规划方法解决多阶段决策过程问题，首先要将实际问题写成动态规划模型，此时就要用到以要将实际问题写成动态规划模型，此时就要用到以下几个概念：下几个概念：第第15页页1. 阶段阶段 （1）阶段）阶段 为了把问题转化为多阶段决策过程，一般根据时间为了把问题转化为多阶段决策过程，一般根据时间或空间的自然特征将问题分解成若干个互相联系的或空间的自然特征将问题分解成若干个互相联系的阶段，以便能按一定的次序去求解。阶段，以便能按一定的次序去求解。第第16页页（2）阶

7、段变量）阶段变量描述阶段的变量，常用字母描述阶段的变量，常用字母 k 表示第表示第 k 阶段。阶段。 AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G531368766835358422123366253543第第17页页例：从例：从 A 到到 G 可以分成：可以分成： （1）从）从 A 到到 B（B有两种选择有两种选择B1，B2）（2）从）从 B 到到 C（C有四种选择有四种选择C1，C2，C3，C4）（3）从）从 C 到到 D（D有三种选择有三种选择D1，D2，D3）（4）从）从 D 到到 E（E有三种选择有三种选择E1，E2，E3）（5）从）从 E 到到 F（F有两种选择有两

8、种选择F1，F2）（6）从）从 F 到到 G 六个阶段。六个阶段。 k = 1, 2, 3, 4, 5, 6。 第第18页页2. 状态状态（1）状态）状态 各阶段开始时所处的自然状况或客观条件。各阶段开始时所处的自然状况或客观条件。通常一个阶段有若干个状态。通常一个阶段有若干个状态。 （2）状态变量）状态变量 描述各阶段状态的变量，常用描述各阶段状态的变量，常用 sk 来表示第来表示第 k 阶段的阶段的状态变量。状态变量。 第第19页页（3）状态变量集合）状态变量集合 各阶段状态变量的集合，常用各阶段状态变量的集合，常用 Sk 来表示第来表示第 k 阶段状阶段状态变量态变量 sk 的取值集合。

9、的取值集合。 第第20页页（4）状态变量的无后效性（马尔科夫性）状态变量的无后效性（马尔科夫性） 如果某阶段状态确定后，则以后各阶段的决策仅同如果某阶段状态确定后，则以后各阶段的决策仅同该阶段的状态有关，而同该阶段以前各阶段的状态该阶段的状态有关，而同该阶段以前各阶段的状态无关。（即仅仅根据该阶段的状态就可以对以后各无关。（即仅仅根据该阶段的状态就可以对以后各阶段进行决策了。）阶段进行决策了。） 注意：如果所选择的状态变量不满足无后效性，则注意：如果所选择的状态变量不满足无后效性，则不能构造动态规划模型。不能构造动态规划模型。 第第21页页例：例：设定每个阶段的出发位置为该阶段的状态变量。设定

10、每个阶段的出发位置为该阶段的状态变量。 AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G531368766835358422123366253543第第22页页因为每个阶段的出发位置选定后，从该位置以后的因为每个阶段的出发位置选定后，从该位置以后的铺管路线只与该位置有关，不受以前铺管路线的影铺管路线只与该位置有关，不受以前铺管路线的影响，所以满足状态的无后效性，故可以作为状态变响，所以满足状态的无后效性，故可以作为状态变量。量。 第第23页页从从 A 到到 G 可以的可以的 6 个阶段的状态分别为：个阶段的状态分别为：S1=A：第一阶段只有一个状态：第一阶段只有一个状态 AS2=B

11、1，B2：第二阶段有两个状态：第二阶段有两个状态B1、B2S3=C1，C2，C3，C4：第三阶段有四个状态：第三阶段有四个状态C1、C2、C3 、 C4第第24页页S4= D1，D2，D3：第四阶段有三个状态：第四阶段有三个状态D1、D2、D3S5= E1，E2，E3：第五阶段有三个状态：第五阶段有三个状态E1、E2、E3S6 = F1，F2：第六阶段有二个状态：第六阶段有二个状态 F1、F2 第第25页页3. 决策决策 （1）决策）决策当某阶段的状态确定以后，就可以作出不同的决定当某阶段的状态确定以后，就可以作出不同的决定（或选择），从而确定下一阶段的状态，这种决定（或选择），从而确定下一阶

12、段的状态，这种决定称为决策。称为决策。第第26页页（2）决策变量）决策变量描述决策的变量，常用描述决策的变量，常用 uk(sk) 表示第表示第 k 阶段状态为阶段状态为 sk 时的决策变量，它是状态变量的函数。时的决策变量，它是状态变量的函数。第第27页页（3）允许决策集合）允许决策集合决策变量的取值范围，常用决策变量的取值范围，常用 Dk(sk) 表示第表示第 k 阶段状阶段状态为态为 sk 时的允许决策集合，显然时的允许决策集合，显然 uk(sk) Dk(sk)。 第第28页页例：例：从第二阶段的状态从第二阶段的状态 B1 出发，可选择下一阶段的出发，可选择下一阶段的C1、C2、C3，即允

13、许决策集合为：，即允许决策集合为：D2(B1)= C1，C2，C3；若选择点若选择点C2，则该决策可表示为：，则该决策可表示为：u2(B1)=C2 第第29页页4. 策略策略 （1）全过程）全过程一个一个 n 阶段决策过程，从第阶段决策过程，从第 1 阶段开始到第阶段开始到第 n 阶段阶段终止的过程。终止的过程。（2）后部子过程或）后部子过程或 k 子过程子过程一个一个 n 阶段决策过程，从第阶段决策过程，从第 k 阶段开始到第阶段开始到第 n 阶段阶段终止的过程。终止的过程。第第30页页（3）全过程策略（简称策略）全过程策略（简称策略）一个一个 n 阶段决策过程，从第阶段决策过程，从第 1

14、阶段开始到第阶段开始到第 n 阶段阶段为止的各阶段的决策按顺序排列组成的集合，记作为止的各阶段的决策按顺序排列组成的集合，记作p1,n ( s1 ) = u1(s1) , u2(s2) , ，un(sn) = s1 , u1 , s2 , u2 , , sn , un , sn+1 。 第第31页页（4）后部子过程策略或）后部子过程策略或 k 子过程策略子过程策略(简称子策略简称子策略)一个一个 n 阶段决策过程，从第阶段决策过程，从第 k 阶段开始到第阶段开始到第 n 阶段阶段为止的各阶段的决策按顺序排列组成的集合，记作为止的各阶段的决策按顺序排列组成的集合，记作pk,n ( sk ) =

15、uk(sk) , uk+1(sk+1) , , un(sn) = sk , uk+1 , sk+1 , uk+1 , , sn , un , sn+1。第第32页页（5）允许策略集合）允许策略集合在实际问题中，可供选择的策略有一定的范围，此在实际问题中，可供选择的策略有一定的范围，此范围称为允许策略集合。范围称为允许策略集合。（6）最优策略）最优策略从允许策略集合中找出达到最优效果的策略称为最从允许策略集合中找出达到最优效果的策略称为最优策略。优策略。第第33页页5. 状态转移方程状态转移方程 状态转移方程状态转移方程 由一个阶段的状态到下一个阶段由一个阶段的状态到下一个阶段的状态的演变过程。

16、的状态的演变过程。动态规划中，本阶段的状态往往是上一阶段状态和动态规划中，本阶段的状态往往是上一阶段状态和上一阶段决策的结果。上一阶段决策的结果。第第34页页由第由第 k 阶段到第阶段到第 k+1 阶段的状态转移方程：阶段的状态转移方程：第第 k 阶段的状态阶段的状态 sk 和决策和决策 uk(sk) 一旦确定，则第一旦确定，则第 k+1 阶段的状态阶段的状态 sk+1 也就完全确定，即也就完全确定，即sk+1 = Tk ( sk , uk(sk) )，其中，其中 Tk 称为状态转移函数。称为状态转移函数。第第35页页例：例：状态转移方程为：状态转移方程为： sk+1 = uk(sk)AB1B

17、2C1C2C3C4D1D2D3E1E2E3F1F2G531368766835358422123366253543第第36页页6. 指标函数指标函数 （1）过程指标函数定义）过程指标函数定义用于衡量所选定策略优劣的数量指标，常用用于衡量所选定策略优劣的数量指标，常用 Vk,n 表表示之，即示之，即Vk,n= ，k=1,2,n ),.,(111, nnnkkkknksusususV第第37页页 表示从第表示从第 k 阶段阶段的状态的状态 sk 开始，到第开始，到第 n 阶段终止的过程，采取策阶段终止的过程，采取策略略 pk, n = 时的数量指时的数量指标值。标值。 ),.,(111, nnnkk

18、kknksusususV,.,111 nnnkkkksususus第第38页页（2）过程指标函数的含义）过程指标函数的含义 注意：不同的问题中，指标函数的含义是不同的，注意：不同的问题中，指标函数的含义是不同的，它可能是距离、利润、成本、产品的产量或资源消它可能是距离、利润、成本、产品的产量或资源消耗等。耗等。例 ： 在 最 短 路 线 问 题 中 过 程 指 标 函 数例 ： 在 最 短 路 线 问 题 中 过 程 指 标 函 数 Vk , n(sk,uk,sn+1) 表示在第表示在第 k 阶段由点阶段由点 sk 至终点至终点 sn+1 的的距离。距离。 第第39页页（3）过程指标函数的可分

19、离性和递推关系）过程指标函数的可分离性和递推关系 构成动态规划模型的过程指标函数要具有可分离性，构成动态规划模型的过程指标函数要具有可分离性，必须满足递推关系，即必须满足递推关系，即 Vk, n 可以表示为可以表示为 sk、uk、Vk+1,n的函数，记为：的函数，记为： ),.,(,),.,(111, 11, nkknkkkknkknksusVussusV 第第40页页（4）常见过程指标函数的形式）常见过程指标函数的形式 过程指标函数为阶段指标函数的和形式过程指标函数为阶段指标函数的和形式，即，即 式中式中 表示第表示第 j 阶段的指标函数值。阶段的指标函数值。 nkjjjjnkknkusvs

20、usV),(),.,(1,),(jjjusv第第41页页满足递推关系满足递推关系 ),.,(),(),.,(111, 11, nkknkkkknkknksusVusvsusV第第42页页 过程指标函数为阶段指标函数的积形式过程指标函数为阶段指标函数的积形式，即，即 nkjjjjnkknkusvsusV),(),.,(1,),.,(),(),.,(111, 11, nkknkkkknkknksusVusvsusV满足递推关系满足递推关系 第第43页页例：在最短路线问题中：例：在最短路线问题中：过程指标函数过程指标函数 Vk, n(sk, uk, sn+1)：表示从第：表示从第 k 阶段的阶段的点

21、点 sk 到终点到终点 sn+1 的距离。的距离。第第44页页阶段指标函数阶段指标函数 dk (sk , uk) ：第：第 k 阶段由点阶段由点 sk 到点到点 uk(sk) = sk+1 的距离。的距离。Vk, n(sk, uk, sn+1)= dk(sk , uk)+ Vk+1,n(sk+1, uk+1, sn+1) 第第45页页7. 最优指标函数最优指标函数 最优指标函数：过程指标函数的最优值，记为最优指标函数：过程指标函数的最优值，记为 fk(sk)，它表示从第它表示从第 k 阶段的状态阶段的状态 sk 开始，到第开始，到第 n 阶段终止阶段终止的过程，采取最优策略时的数量指标值。的过

22、程，采取最优策略时的数量指标值。第第46页页式中式中 opt（optimum）表示最优化，根据具体问题取）表示最优化，根据具体问题取min或或max。 ),.,(min),.,(max ),.,()1,1,1,.,nnnkknknnnkknknnnkknkuukksususVsususVsususVopt(sfnk第第47页页例：在最短路线问题中用最优指标函数例：在最短路线问题中用最优指标函数 fk(sk) 表示表示从第从第 k阶段点阶段点 sk 到终点到终点 G 的最短距离。的最短距离。f4(D1) 表示从第表示从第 4 阶段中的点阶段中的点 D1 到点到点 G 的最短距离。的最短距离。 第

23、第48页页AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G1. 例子例子 531368766835358422123366253543第第49页页求解：求解： 第一步：第一步：当当 k = 7，S7 = G f7(G)=0第二步：第二步：当当 k = 6，S6=F1, F2 第第50页页s6=F1时：时：f6(F1) = F1 到到 G 最短距离为最短距离为 4 u6(F1)=G，s7=G 线路为线路为F1G404)(),(716 GfGFd第第51页页s6=F2时：时：f6(F2) = F2 到到 G 最短距离为最短距离为 3 u6(F1)=G，s7=G 线路为线路为F2G 30

24、3)(),(726 GfGFd第第52页页第三步：第三步：当当k = 5，S5=E1, E2, E3 s5=E1时：时：f5(E1)= E1 到到 G 最短距离为最短距离为 7 u5(E1)=F1，s6=F1 线路为线路为E1 F1G73543min)(),()(),(min2621516115 FfFEdFfFEd第第53页页s5=E2时：时：f5(E2)= E2 到到 G 最短距离为最短距离为 5 u5(E2)=F2，s6=F2 线路为线路为E2 F2G 53245min)(),()(),(min2622516125 FfFEdFfFEd第第54页页s5=E3时：时：f5(E3)= E3到

25、到G最短距离为最短距离为9 u5(E3)=F2，s6=F2 线路为线路为E3 F2G 93646min)(),()(),(min2623516135 FfFEdFfFEd第第55页页第四步：第四步：当当 k = 4，S4= D1, D2, D3 s4=D1时：时：f4(D1)= D1 到到 G 最短距离为最短距离为 7 u4(D1)=E2，s5= E2 线路为线路为D1E2 F2G 75272min)(),()(),(min2521415114 EfEDdEfEDd第第56页页s4=D2 时：时：f4(D2)= D2 到到 G 最短距离为最短距离为6 u4(D2)=E2，s5= E2 线路为线

26、路为D2E2 F2G 69251min)(),()(),(min3532425224 EfEDdEfEDd第第57页页s4=D3 时：时：f4(D3)= D3到到G最短距离为最短距离为 8 u4(D3)=E2，s5= E2 线路为线路为D3 E2 F2G 89353min)(),()(),(min2533425234 EfEDdEfEDd第第58页页第五步：第五步：当当 k =3，S3=C1,C2,C3,C4 s3=C1时：时：f3(C1)= C1 到到 G 最短距离为最短距离为 13 u3(C1)=D1，s4= D1， 线路为线路为C1D1E2 F2G136876min)(),()(),(m

27、in2421314113 DfDCdDfDCd第第59页页s3 = C2 时：时：f3(C2)= C2 到到 G 最短距离为最短距离为10 u3(C2)=D1，s4= D1 线路为线路为C2 D1E2 F2G 106573min)(),()(),(min2422314123 DfDCdDfDCd第第60页页s3= C3时：时：f3(C3)= C3 到到 G 最短距离为最短距离为9 u3(C3)=D2，s4= D2 线路为线路为C3D2E2 F2G 98363min)(),()(),(min3433324233 DfDCdDfDCd第第61页页s3= C4 时：时：f3(C4)= C4 到到 G

28、 最短距离为最短距离为12 u3(C4)=D3，s4= D3 线路为线路为C4D3 E2 F2G 128468min)(),()(),(min3434324243 DfDCdDfDCd第第62页页第六步：第六步：当当k=2，S2=B1,B2 s2=B1时：时：f2(B1)= B1到到G最短距离为最短距离为13 u2(B1)=C2，s3= C2 线路为线路为B 1C2 D1E2 F2G1396103131min)(),()(),()(),(min333122321213112 CfCBdCfCBdCfCBd第第63页页s2=B2时：时：f2(B2)= B2到到G最短距离为最短距离为16 u2(B

29、2)=C3，s3= C3 线路为线路为B2C3D2E2 F2G 1612697108min)(),()(),()(),(min434223332223222 CfCBdCfCBdCfCBd第第64页页第七步：第七步：当当k=1，S1=A s1=A时：时：f1(A)= A到到G最短距离为最短距离为18 u1(A)=B1，s2= B1 线路为线路为AB 1C2 D1E2 F2G18163135min)(),()(),(min22211211 BfBAdBfBAd第第65页页结结 论论最优决策最优决策=s1，u1，s2，u2，s3，u3，s4，u4，s5，u5，s6，u6，s7= s1=A，u1(A

30、)=B1，s2=B1，u2(B1)=C2，s3=C2，u3(C2)=D1，s4=D1，u4(D1)=E2，s5=E2，u5(E2)=F2，s6=F2，u6(F2)=G，s7=G 第第66页页求解过程分析求解过程分析从上面的计算过程中可以看出，在各个阶段求解过从上面的计算过程中可以看出，在各个阶段求解过程中，利用了程中，利用了k 阶段与阶段与 k+1 阶段的递推关系：阶段的递推关系： 0)()(1 , 2 , 3 , 4 , 5 , 6),()(,(min)(77711Gfsfksfsusdsfkkkkkkkk第第67页页2. 动态规划的基本方程动态规划的基本方程 一般情况，一般情况，k 阶段与

31、阶段与 k+1 阶段的递推关系式可以写阶段的递推关系式可以写成：成： 上述递推关系称为动态规划的基本方程，其中第二上述递推关系称为动态规划的基本方程，其中第二个式子称为边界条件。个式子称为边界条件。 0)(1,.,1,),()(,()(1111nnkkkkkkkksfnnksfsusvoptsf第第68页页现在把动态规划方法的基本思想总结如下：现在把动态规划方法的基本思想总结如下： 1. 将多阶段决策过程划分阶段，恰当地选取状态变将多阶段决策过程划分阶段，恰当地选取状态变量量sk、决策变量、决策变量uk(sk)、最优指标函数、最优指标函数 fk(sk)，从，从而把问题化成一族同类型的子问题，然后逐个而把问题化成一族同类型的子问题，然后逐个求解。求解。