1第八章 动态规划2引引 言言动态规划是解决动态规划是解决多阶段决策过程多阶段决策过程最优化的一种方法。最优化的一种方法。该方法是由美国数学家该方法是由美国数学家贝尔曼贝尔曼（R. E. Bellman）等人在）等人在20世世纪纪50年代初提出的。并成功地解决了生产管理、工程技术等方年代初提出的。并成功地解决了生产管理、工程技术等方面的许多问题，从而建立了运筹学的一个新的分支，即动态规面的许多问题，从而建立了运筹学的一个新的分支，即动态规划。划。Bellman在在1957年出版了年出版了Dynamic Programming一一书，是动态规划领域中的第一本著作。书，是动态规划领域中的第一本著作。3动态规划与其他规划方法的不同之处在于：动态规划与其他规划方法的不同之处在于： 动态规划是求解某类问题（动态规划是求解某类问题（多阶段决策问题多阶段决策问题）的一种方法，）的一种方法，是考察问题的一种途径，而不是一种特定算法。是考察问题的一种途径，而不是一种特定算法。 因此，它不像线性规划那样有一个标准的数学表达式和明确因此，它不像线性规划那样有一个标准的数学表达式和明确定义的一组（算法）规则，而必须对具体问题进行具体分析处定义的一组（算法）规则，而必须对具体问题进行具体分析处理。因此，学习动态规划时，除对基本概念和基本方法正确理解理。因此，学习动态规划时，除对基本概念和基本方法正确理解外，还应在一定经验积累基础上，以丰富的想像力去建立模型，外，还应在一定经验积累基础上，以丰富的想像力去建立模型，用创造性的技巧去求解。用创造性的技巧去求解。4提提 纲纲1 动态规划实例动态规划实例2 动态规划的基本概念动态规划的基本概念3 动态规划的基本思想与基本原理动态规划的基本思想与基本原理4 逆序解法与顺序解法逆序解法与顺序解法5学习目标：学习目标：1 明确什么是明确什么是多阶段的决策问题多阶段的决策问题，特别要注意没有明显，特别要注意没有明显 的时段背景的问题如何化归为多阶段的决策问题。的时段背景的问题如何化归为多阶段的决策问题。1 动态规划实例动态规划实例6P156 例例2 机器负荷分配问题（时间阶段问题）机器负荷分配问题（时间阶段问题）设有某种机器设备，用于完成两类工作设有某种机器设备，用于完成两类工作A和和B。若。若第第k年初完好年初完好机器的数量为机器的数量为 xk ，若以数量，若以数量 uk 用于用于A，余下的（，余下的（xkuk）用于）用于工作工作B，则该年的预期收入为，则该年的预期收入为 g( uk ) + h( xkuk )。这里。这里g( uk )和和 h( xkuk )是已知函数，且是已知函数，且 g( 0 ) = h( 0 ) = 0。又机器设备在使用中会有损坏，设机器用于工作又机器设备在使用中会有损坏，设机器用于工作A时，一年后时，一年后能继续使用的完好机器数占年初投入量的能继续使用的完好机器数占年初投入量的70%；若用于工作；若用于工作B时，一年后能继续使用的完好机器数占年初投入量的时，一年后能继续使用的完好机器数占年初投入量的90%。则在。则在下一年初下一年初能继续用于能继续用于A、B工作的设备数为工作的设备数为 xk+1uk+0.9(xkuk)。设第设第1年初完好的机器总数为年初完好的机器总数为1000台，问在连续台，问在连续5年内每年应如年内每年应如何分配用于何分配用于A、B两项工作的机器数，使两项工作的机器数，使5年的总收益为最大。年的总收益为最大。1 动态规划实例动态规划实例7相应的问题称为相应的问题称为多阶段决策问题多阶段决策问题。这是一个这是一个多阶段决策过程多阶段决策过程。该过程可以分为相互联系的若干阶段，每一阶段都需作出决该过程可以分为相互联系的若干阶段，每一阶段都需作出决 策，从而形成全过程的决策。策，从而形成全过程的决策。第第1年年x1=1000u1第第2年年x2u1+ 0.9(x1-u1)u2第第3年年x3u2+ 0.9(x2-u2)u3第第4年年u4第第5年年x5u4+ 0.9(x4-u4)u5x4=0.7u3+ 0.9(x3-u3)x6P156 例例1 最短路线问题（空间阶段的例子）最短路线问题（空间阶段的例子） 设有一个旅行者从下图中的设有一个旅行者从下图中的A点出发，途中要经过点出发，途中要经过B、C、D等等处，最后到达终点处，最后到达终点E。从从A到到E有很多条路线可以选择有很多条路线可以选择，各点之间的距，各点之间的距离如图所示，问该旅行者应选择哪一条路线，使从离如图所示，问该旅行者应选择哪一条路线，使从A到达到达E的总的路程的总的路程为最短。为最短。25375632455114633334C1C3D1AB1B3B2D2EC21234状态状态1决策决策1状态状态2状态状态3状态状态4状态状态5决策决策2决策决策3决策决策4可看成可看成 4阶段阶段 的决策的决策 问题。问题。9从以上两个例子，可以知道从以上两个例子，可以知道 所谓所谓多阶段多阶段决策问题决策问题是指这样的决策问题：其过程可分为若是指这样的决策问题：其过程可分为若干个相互联系的阶段，每一阶段都对应着一组可供选择的决策，干个相互联系的阶段，每一阶段都对应着一组可供选择的决策，每一决策的选定既依赖于当前面临的状态，又影响以后总体的效每一决策的选定既依赖于当前面临的状态，又影响以后总体的效果。果。 当每一阶段的决策选定以后，就构成一个决策序列，称为一当每一阶段的决策选定以后，就构成一个决策序列，称为一个个策略策略，它对应着一个确定的效果。它对应着一个确定的效果。多阶段决策问题就是寻找使多阶段决策问题就是寻找使此效果最好的策略。此效果最好的策略。10多阶段决策过程的特点多阶段决策过程的特点1.各阶段的决策相互关联各阶段的决策相互关联多阶段决策过程最优化的目的多阶段决策过程最优化的目的，是要达到整个活动过程的总体，是要达到整个活动过程的总体效果最优，而不是某个阶段效果最优，而不是某个阶段“局部局部”的效果最优。因此，的效果最优。因此，各个阶各个阶段段决策的选取不是任意确定的决策的选取不是任意确定的。前一个决策的选取决定了当前状态，当前状态进行决策后又影前一个决策的选取决定了当前状态，当前状态进行决策后又影响到下一阶段的状态和决策，以至于影响总体效果。所以决策者响到下一阶段的状态和决策，以至于影响总体效果。所以决策者在每个阶段决策时，不应仅考虑本阶段最优，还应考虑对最终目在每个阶段决策时，不应仅考虑本阶段最优，还应考虑对最终目标的影响，从而做出对全局而言是最优的决策。标的影响，从而做出对全局而言是最优的决策。动态规划就是符合这一要求的一种最优化方法。动态规划就是符合这一要求的一种最优化方法。112.各个阶段的决策一般与各个阶段的决策一般与“时间时间”有关有关动态规划方法与动态规划方法与“时间时间”关系很密切，随着时间过程的发展而关系很密切，随着时间过程的发展而决决定各阶段的决策，从而产生一个决策序列，这就是定各阶段的决策，从而产生一个决策序列，这就是“动态动态”的意的意思。思。但是，一些与时间无关的静态问题，只要在问题中但是，一些与时间无关的静态问题，只要在问题中人为引人为引入入“时间时间”因素因素，也可将其看成是多阶段的决策问题，用动态规，也可将其看成是多阶段的决策问题，用动态规划划方法去处理。方法去处理。12学习目标：学习目标：1 准确、熟练地掌握动态规划的基本概念、特别是状态准确、熟练地掌握动态规划的基本概念、特别是状态 变量、决策变量、状态转移律、指标函数、基本方程变量、决策变量、状态转移律、指标函数、基本方程 等。等。2 动态规划的基本概念动态规划的基本概念为了便于求解和表示决策及过程的发展顺序，而把所给问题恰为了便于求解和表示决策及过程的发展顺序，而把所给问题恰当地划分为若干个相互联系又有区别的子问题，称之为多段决策当地划分为若干个相互联系又有区别的子问题，称之为多段决策问题的问题的阶段阶段。一个阶段，就是需要作出一个决策的子问题一个阶段，就是需要作出一个决策的子问题。 通常，通常，阶段是按决策进行的阶段是按决策进行的时间或空间时间或空间上先后顺序划分的上先后顺序划分的。描述阶段的变量称为描述阶段的变量称为阶段变量阶段变量，常记为，常记为k，k=1,2, ,n。如本例可按空间分为如本例可按空间分为4个个 阶段来求解，阶段来求解， k=1, 2, 3, 4。（1）阶段（）阶段（stage）14状态状态：每阶段初每阶段初的客观条件。描述各阶段状态的变量称为的客观条件。描述各阶段状态的变量称为状态状态变量变量，常用，常用xk表示第表示第k阶段的状态。阶段的状态。（2）状态（）状态（state）例例1中，中，状态状态就是某就是某阶段的出发位置。阶段的出发位置。x1x2x3x4x5按状态变量的取值是连续还是离散，可将动态规划问题分为按状态变量的取值是连续还是离散，可将动态规划问题分为离离 散型散型和和连续型连续型。15动态规划中的动态规划中的状态应满足状态应满足无后效性（马尔科夫性）无后效性（马尔科夫性）： 所谓所谓无后效性无后效性指系统到达某个状态前的过程的决策将不影响指系统到达某个状态前的过程的决策将不影响到该状态以后的决策。到该状态以后的决策。指系统从某个阶段往后的发展，仅由本指系统从某个阶段往后的发展，仅由本阶段所处的状态及其往后的决策所决定，与系统以前经历的状态阶段所处的状态及其往后的决策所决定，与系统以前经历的状态和决策（历史）无关。和决策（历史）无关。过程的过去历史只能通过当前的状态去影过程的过去历史只能通过当前的状态去影响它未来的发展响它未来的发展例例1中，当某阶段的状态已选定某个点时，从这个点以后的路中，当某阶段的状态已选定某个点时，从这个点以后的路线只与该点有关，不受该点以前的路线的影响，所以满足状态的线只与该点有关，不受该点以前的路线的影响，所以满足状态的无后效性。无后效性。16状态集合状态集合：状态变量：状态变量 xk 的取值集合称为的取值集合称为状态集合状态集合，状态集合状态集合实际上是关于状态的约束条件。实际上是关于状态的约束条件。通常用通常用Sk表示状态集合表示状态集合，xk Sk。第第1阶段阶段 S1=A；第第2阶段具有阶段具有3个状个状态态B1、B2和和B3，故，故 S2=B1, B2, B3。x1x2x3x4x5（3）决策）决策（decision）当过程处于某一阶段的某状态时，可以做出不同的决定，从而当过程处于某一阶段的某状态时，可以做出不同的决定，从而确定下一阶段的状态确定下一阶段的状态，这种决定称为，这种决定称为决策决策。 描述决策的变量称为描述决策的变量称为决策变量决策变量，常用，常用uk( xk )表示第表示第k阶段当状阶段当状态处于态处于xk时的时的决策变量，它是状态变量的函数。决策变量，它是状态变量的函数。例例1中，从第中，从第2阶段的阶段的状态状态B1出发，可以选择出发，可以选择下一阶段的下一阶段的C1、C2、C3。如我们决定选择如我们决定选择C1，则可表示为：则可表示为：u2( B1 ) = C1。B1C1C2C3x218决策集合决策集合：第第k阶段当状态处于阶段当状态处于xk时决策变量时决策变量uk( xk )的取值范的取值范称为称为决策集合决策集合，常用，常用Dk( xk ) 表示。表示。例例1中，从第中，从第2阶段的阶段的状态状态B1出发，可以选择出发，可以选择下一阶段的下一阶段的C1、C2、C3。即即 D2( B1 ) = C1、C2、C3 ；B1C1C2C3决策集合实际上是决策的约束条件，决策集合实际上是决策的约束条件，uk( xk ) Dk( xk ) 。19小结小结 阶段阶段 k、 状态状态 xk、 状态集合状态集合 Sk、 决策决策 uk( xk )、 决策集合决策集合 Dk( xk )。x1x2x3x4x520（4）状态转移律（方程）状态转移律（方程）状态转移律状态转移律：从：从xk的某一状态值出发，当决策变量的某一状态值出发，当决策变量uk(xk) 的的取值决定后，下一阶段状态变量取值决定后，下一阶段状态变量xk+1的取值也随之确定。描述的取值也随之确定。描述从从 xk 转变为转变为 xk+1 的规律称为的规律称为状态转移规律（方程）状态转移规律（方程）。从第从第2阶段的状态阶段的状态B1出发，如我们决出发，如我们决定选择定选择C2（也即确（也即确定了下一阶段的状定了下一阶段的状态）。态）。B1C2B1C2上例中，上例中， u2( B1 ) = C2状态转移律为：状态转移律为： xk+1 = uk( xk )一般来说，下一阶段状态变量一般来说，下一阶段状态变量xk+1的取值是上阶段的某一状态的取值是上阶段的某一状态变量变量xk和上阶段决策变量和上阶段决策变量uk(xk)的函数，记为的函数，记为 xk+1=Tk( xk, uk(xk) )12nx1u1x2u2x3xnunxn+1（5）策略（）策略（policy）和子策略）和子策略（subpolicy）策略策略：由依次进行的由依次进行的n个阶段决策构成的个阶段决策构成的决策序列决策序列就构成一个就构成一个 策略策略，用，用 p1n u1(x1), u2(x2), , un(xn) 表示。表示。25375632455114633334C1C3D1AB1B3B2D2EC2本例中，如本例中，如p14 u1(A)=B1, u2(B1) = C2, u3(C2) = D1, u4(D1) = E 表示其中一个表示其中一个策略，其总距离为策略，其总距离为2+5+6+3=16。23策略集合：策略集合：在实际问题中，由于在各个阶段可供选择的决策有在实际问题中，由于在各个阶段可供选择的决策有许多个，因此，它们的不同组合就构成了许多可供选择的决策序许多个，因此，它们的不同组合就构成了许多可供选择的决策序列（策略），由它们组成的集合，称为列（策略），由它们组成的集合，称为策略集合策略集合，记作，记作 P1n。从策略集合中，找出具有最优效果的策略称为从策略集合中，找出具有最优效果的策略称为最优策略最优策略。24子策略：子策略：从从k阶段到第阶段到第n阶段，依次进行的阶段决策构成的阶段，依次进行的阶段决策构成的决策序列称为决策序列称为k部子策略，表示为部子策略，表示为 pkn = uk(xk), uk+1(xk+1), , un(xn) 如从第如从第3阶段的阶段的C2状态开始的一个子策状态开始的一个子策略可表示：略可表示： p34=u3(C2) = D1, u4(D1) = E C225（6）指标函数）指标函数用来衡量策略或子策略或决策的效果的某种用来衡量策略或子策略或决策的效果的某种数量指标数量指标，就称，就称为为指标函数指标函数。 它是定义在全过程或各子过程或各阶段上的确定数量函数。它是定义在全过程或各子过程或各阶段上的确定数量函数。对不同问题，指标函数可以是诸如费用、成本、产值、利润、对不同问题，指标函数可以是诸如费用、成本、产值、利润、产量、耗量、距离、时间、效用，等等。产量、耗量、距离、时间、效用，等等。阶段阶段指标函数指标函数过程过程指标函数指标函数26阶段指标函数阶段指标函数：是指第：是指第 k 阶段从状态阶段从状态 xk 出发，采取决策出发，采取决策 uk 时产生的效益，用时产生的效益，用 vk(xk, uk) 表示。表示。例例1中，指标函数是中，指标函数是距离距离。如如 v2(B1, C2) 表示表示由由B1 出发，采用决策出发，采用决策到到C2 点的两点间距点的两点间距离，即离，即 v2( B1, C2) = 5。B1C227过程指标函数过程指标函数：是指从第：是指从第 k 阶段的某状态阶段的某状态 xk 出发，采取子策出发，采取子策略略 pkn 时所得到的时所得到的效益效益，记作，记作 Vkn( xk, uk, xk+1, uk+1, , xn )例例1中，如中，如V34( C2, u3(C2)=D1, D1, u4(D1)= E, E ) = 6+3 =9C228过程指标函数过程指标函数Vkn通常是描述所实现的全过程或通常是描述所实现的全过程或k后部子过程效后部子过程效果果优优劣劣的的数数量量指指标标，它它是是由由各各阶阶段段的的阶阶段段指指标标函函数数vk(xk,uk)累累积积形形成的成的。（1）可分性：可分性：适于用动态规划求解的问题的过程指标函数（即目适于用动态规划求解的问题的过程指标函数（即目标函数），必须具有关于阶段指标的可分离形式，即对于后部子标函数），必须具有关于阶段指标的可分离形式，即对于后部子过程的指标函数可以表示为：过程的指标函数可以表示为： Vkn( xk, uk, xk+1, uk+1, , xn ) = vk(xk, uk) vk+1(xk+1, uk+1) vn(xn, un) 式中，式中， 表示某种运算，可以是加、减、乘、除、开方等。表示某种运算，可以是加、减、乘、除、开方等。29多阶段决策问题中，常见的目标函数形式之一是取多阶段决策问题中，常见的目标函数形式之一是取各阶段效应各阶段效应 之和之和的形式，即的形式，即: 有些问题，如系统可靠性问题，其目标函数是取有些问题，如系统可靠性问题，其目标函数是取各阶段效应的各阶段效应的 连乘积连乘积形式，如：形式，如： 总之，具体问题的目标函数表达形式需要视具体问题而定。总之，具体问题的目标函数表达形式需要视具体问题而定。Vkn = vi（xi, ui）i=kn (8.3a) Vkn = vi（xi, ui）i=kn (8.3b) 30（2）可递推：可递推：过程指标函数过程指标函数Vkn要要满足递推关系满足递推关系，即，即可递推可递推Vkn( xk, uk, xk+1, uk+1, , xn )k xk, uk, V(k+1)n(xk+1, uk+1, , xn ) vk(xk,uk) vk+1(xk+1, uk+1) vn(xn,un) vk(xk,uk) V(k+1)n( xk+1, uk+1, , xn )31最优指标函数最优指标函数：表示从第表示从第 k 阶段状态为阶段状态为 xk 时采用时采用最优策略最优策略 pkn*到过程终止时的最佳效益值。记为到过程终止时的最佳效益值。记为 fk( xk )。 fk( xk ) = Vkn( xk , pkn*) = opt Vkn( xk , pkn )例例1中，如中，如 f3( C2 ) = 3+4 = 7。其中其中 opt 可根据具体情况取可根据具体情况取max 或或min。C2动态规划的目标？动态规划的目标？最优解：最优解：最优策略最优策略 p1n最优值：最优值：最优指标最优指标 f1(A)32多阶段决策问题的数学模型多阶段决策问题的数学模型 综上所述，适于应用动态规划方综上所述，适于应用动态规划方法求解的一类多阶段决策问题的数学模型呈以下形式法求解的一类多阶段决策问题的数学模型呈以下形式: f1 = opt V1n( x1 , p1n ) 最优指标函数最优指标函数 xk+1=Tk( xk, uk(xk) ) 状态转移方程状态转移方程 ukDk 决策变量决策变量 xkSk 状态变量状态变量 k=1,2,n 阶段变量阶段变量st.上述数学模型说明了对于给上述数学模型说明了对于给定的多阶段决策过程，求取一定的多阶段决策过程，求取一个个(或或多多个个)最最优优策策略略或或最最优优决决策策序序列列 u1, u2, , un ，使使之之既既满满足左式给出的全部约束条件，足左式给出的全部约束条件，又使左式所示的目标函数取得又使左式所示的目标函数取得极值，并且同时指出执行该最极值，并且同时指出执行该最优策略时，过程状态演变序列优策略时，过程状态演变序列即是最优路线。即是最优路线。小结小结: :概念概念 : :阶段变量阶段变量k状态变量状态变量xk决策变量决策变量uk; ;动态规划本质上是多阶段决策过程动态规划本质上是多阶段决策过程; ; 效益效益指标函数形式指标函数形式: :和、积和、积无后效性无后效性可递推可递推方程方程 : :状态转移方程状态转移方程xk+1=Tk( xk, uk(xk) )指标指标 : : Vkn( xk, uk, xk+1, uk+1, , xn )fk( xk ) = Vkn( xk , pkn*) = opt Vkn( xk , pkn )Vkn( xk, uk, xk+1, uk+1, , xn )k xk, uk, V(k+1)n(xk+1, uk+1, , xn ) 34解多阶段决策过程问题，求出解多阶段决策过程问题，求出 最优策略最优策略，即最优，即最优决策序列决策序列 最优轨线最优轨线，即执行最优策略时的即执行最优策略时的状态序列状态序列 u1*, u2*, , un* x1*, x2*, , xn* 最优目标函数值最优目标函数值p1nP1nf1( x1 ) = V1n( x1 , p1n*) = opt V1n( x1 , p1n )1.划分阶段划分阶段2.正确选择状态变量正确选择状态变量 3.确定决策变量及允确定决策变量及允许决策集合许决策集合4.确定状态转移方程确定状态转移方程 5.确定阶段指标函确定阶段指标函数和最优指标函数和最优指标函数，建立动态规划数，建立动态规划基本方程基本方程划分阶段是运用动态规划求解多阶段决策问题的第一划分阶段是运用动态规划求解多阶段决策问题的第一步，在确定多阶段特性后，按时间或空间先后顺序，步，在确定多阶段特性后，按时间或空间先后顺序，将过程划分为若干相互联系的阶段。对于静态问题要将过程划分为若干相互联系的阶段。对于静态问题要人为地赋予人为地赋予“时间时间”概念，以便划分阶段。概念，以便划分阶段。建立动态规划模型的步骤建立动态规划模型的步骤 选择状态变量既要能确切描述过程演变又要满足无后选择状态变量既要能确切描述过程演变又要满足无后效性，而且各阶段状态变量的取值能够确定。效性，而且各阶段状态变量的取值能够确定。通常选择所求解问题的关键变量作为决策变量，同时通常选择所求解问题的关键变量作为决策变量，同时要给出决策变量的取值范围，即确定允许决策集合。要给出决策变量的取值范围，即确定允许决策集合。根据根据k 阶段状态变量和决策变量，写出阶段状态变量和决策变量，写出k+1阶段状态变阶段状态变量，状态转移方程应当具有递推关系。量，状态转移方程应当具有递推关系。阶段指标函数是指第阶段指标函数是指第k 阶段的收益，最优指标函数是阶段的收益，最优指标函数是指从第指从第k 阶段状态出发到第阶段状态出发到第n 阶段末所获得收益的最阶段末所获得收益的最优值，最后写出动态规划基本方程。优值，最后写出动态规划基本方程。36 以上五步是建立动态规划数学模型的一般步骤。以上五步是建立动态规划数学模型的一般步骤。由于动态规划模型与线性规划模型不同，动态规划模由于动态规划模型与线性规划模型不同，动态规划模型没有统一的模式，建模时必须根据具体问题具体分型没有统一的模式，建模时必须根据具体问题具体分析，只有通过不断实践总结，才能较好掌握建模方法析，只有通过不断实践总结，才能较好掌握建模方法与技巧。与技巧。 下面我们看一个具体的例子下面我们看一个具体的例子 P156 例例2 机器负荷分配问题（时间阶段问题）机器负荷分配问题（时间阶段问题）37P156 例例2 机器负荷分配问题（时间阶段问题）机器负荷分配问题（时间阶段问题）设有某种机器设备，用于完成两类工作设有某种机器设备，用于完成两类工作A和和B。若。若第第k年初完好年初完好机器的数量为机器的数量为 xk ，若以数量，若以数量 uk 用于用于A，余下的（，余下的（xkuk）用于）用于工作工作B，则该年的预期收入为，则该年的预期收入为 g( uk ) + h( xkuk )。其中其中g( uk ) 8uk ， h( xkuk ) = 5（xkuk）。又机器设备在使用中会有损坏，设机器用于工作又机器设备在使用中会有损坏，设机器用于工作A时，一年后时，一年后能继续使用的完好机器数占年初投入量的能继续使用的完好机器数占年初投入量的70%；若用于工作；若用于工作B时，一年后能继续使用的完好机器数占年初投入量的时，一年后能继续使用的完好机器数占年初投入量的90%。则在。则在下一年初下一年初能继续用于能继续用于A、B工作的设备数为工作的设备数为 xk+1uk+0.9(xkuk)。设第设第1年初完好的机器总数为年初完好的机器总数为1000台，问在连续台，问在连续5年内每年应如年内每年应如何分配用于何分配用于A、B两项工作的机器数，使两项工作的机器数，使5年的总收益为最大。年的总收益为最大。1.划分阶段划分阶段按年度来划分阶段，按年度来划分阶段，k=1,2,3,4,52.正确选择状态变量正确选择状态变量状态变量状态变量xk为第为第k年度初拥有的完好机器数量年度初拥有的完好机器数量 3.确定决策变量及允许决策集合确定决策变量及允许决策集合决策变量决策变量uk为第为第k年度中分配于年度中分配于A工作的机器数量，则工作的机器数量，则xkuk为为用于用于B工作的机器数量。工作的机器数量。第第k阶段阶段决策集合决策集合Dk( xk ) = uk | 0ukxk 这里这里xk和和uk均取连续变量，它们的非整数值可以这样理均取连续变量，它们的非整数值可以这样理解，如解，如xk，就表示一台机器在第，就表示一台机器在第k年度中正常工作时间只年度中正常工作时间只占占6/10；uk，就表示一台机器在该年度只有，就表示一台机器在该年度只有3/10的时间能的时间能正常用于正常用于A工作。工作。394.确定状态转移方程确定状态转移方程状态转移方程为状态转移方程为 xk+1uk+0.9(xkuk) 5.确定阶段指标函数和最优指标函数，建立动态规划基本方程确定阶段指标函数和最优指标函数，建立动态规划基本方程指标函数为指标函数为V1,5 = vi（xi, ui）i=15 = g( ui ) + h( xiui )i=15令最优指标函数令最优指标函数fk( xk ) 表示由资源量表示由资源量xk出发，从第出发，从第k年开始到年开始到第第5年结束时所取得的最大预期收入。因而有：年结束时所取得的最大预期收入。因而有： fk( xk ) = max Vk,5 = vi（xi, ui）i=k5 = 8ui + 5( xiui )i=k5 = 8ui +5(xiui)i=1540学习目标：学习目标：1 掌握最优化原理的内容掌握最优化原理的内容2 掌握逆序解法掌握逆序解法3 动态规划的基本思想与基本原理动态规划的基本思想与基本原理多阶段决策过程的最优化一般有三种思路求解多阶段决策过程的最优化一般有三种思路求解1.全枚举法或穷举法：全枚举法或穷举法：它的基本思想是列举出所有可能发生的它的基本思想是列举出所有可能发生的方案和结果，再对它们一一进行比较，求出最优方案。方案和结果，再对它们一一进行比较，求出最优方案。 可以计算：从可以计算：从A到到E的路程可分为的路程可分为4个阶段。第一段走法有个阶段。第一段走法有3种，第二段走法有种，第二段走法有3种，第三段走法有种，第三段走法有2种，第四段走法仅种，第四段走法仅1种，种，共有共有332118条可能的路线，分别算出各条路线的距离，条可能的路线，分别算出各条路线的距离，最后进行比较，可知最优路线是最后进行比较，可知最优路线是AB3C2 D2E，最短距离，最短距离是是11。 用穷举法求最优路线的计算用穷举法求最优路线的计算 工作量将会十分庞大，而且工作量将会十分庞大，而且 其中包含着许多重复计算。其中包含着许多重复计算。2.局部最优路径法：局部最优路径法：某人从某人从k点出发，并不顾及全线是否最短，点出发，并不顾及全线是否最短，只只是是选选择择当当前前最最短短途途径径，“逢逢近近便便走走”，错错误误地地以以为为局局部部最最优优会会致整体最优致整体最优，在这种想法指导下，所取决策必是，在这种想法指导下，所取决策必是AB1C2D2E，全程长度是，全程长度是14；显然，这种方法的结果常；显然，这种方法的结果常是错误的。是错误的。43小结：小结： 全枚举法全枚举法虽可找出最优方案，但不是个好算法，虽可找出最优方案，但不是个好算法， 局部最优法局部最优法则完全是个错误方法，则完全是个错误方法， 只有只有动态规划方法动态规划方法属较科学有效的算法属较科学有效的算法作为一个全过程的最优策略具有这样的性质：作为一个全过程的最优策略具有这样的性质：对于最优策略对于最优策略过程中的任意状态而言，无论其过去的状态和决策如何，余下过程中的任意状态而言，无论其过去的状态和决策如何，余下的诸决策必构成一个最优子策略。的诸决策必构成一个最优子策略。（一个最优策略的子策略总一个最优策略的子策略总是最优的是最优的）3. 贝尔曼最优化原理（动态规划方法）贝尔曼最优化原理（动态规划方法）作该原理的具体解释是，若某一作该原理的具体解释是，若某一全过程最优策略全过程最优策略为：为： p1n*( x1 )= u1*(x1), , uk*(xk), uk+1*(xk+1), , un*(xn) 则对上述策略中所隐含的任一状态（则对上述策略中所隐含的任一状态（xk）而言，第）而言，第k子过程上子过程上对应于对应于 xk 的最优策略必然包含在上述全过程最优策略的最优策略必然包含在上述全过程最优策略p1n*中，中，即为即为 pkn*( xk )= uk*(xk), uk+1*(xk+1), , un*(xn) 45C1D1AB3D2EC2反证法反证法进行证明进行证明最优性原理在最短路线中的应用最优性原理在最短路线中的应用 在最短路线中，若找到了在最短路线中，若找到了AB3C2D2E是由是由A到到E的最的最短路线，则短路线，则B3C2D2E必是由必是由B3出发到出发到E点的所有可能选择的点的所有可能选择的不同路线中的最短路线。（不同路线中的最短路线。（一个最优策略的子策略总是最优的一个最优策略的子策略总是最优的）464.函数基本方程函数基本方程 基于这个原理，提出了一种基于这个原理，提出了一种逆序递推法逆序递推法；该法的关键在于给；该法的关键在于给出一种递推关系。一般把这种递推关系称为出一种递推关系。一般把这种递推关系称为动态规划的函数基本动态规划的函数基本方程方程。对于求最小的加法的基本方程为（如例对于求最小的加法的基本方程为（如例1）：）： fk( xk ) = min vk(xk, uk ) + fk+1(xk+1) fn+1( xn+1 ) = 0边界条件边界条件ukDk47用函数基本方程逆推求解是常用的方法：用函数基本方程逆推求解是常用的方法： 首先要有效地首先要有效地建立动态规划模型建立动态规划模型， 然后再然后再递推求解递推求解， 最后最后得出结论得出结论。正确地建立一个动态规划模型，是解决问题的关键。正确地建立一个动态规划模型，是解决问题的关键。485.标号法标号法（只适用于一类最优路线问题的特殊解法）（只适用于一类最优路线问题的特殊解法） 标号法是借助网络图通过分段标号来求出最优路线的一种标号法是借助网络图通过分段标号来求出最优路线的一种简便、直观的方法。通常标号法采取简便、直观的方法。通常标号法采取“逆序求解逆序求解”的方法来寻找的方法来寻找问问题的最优解，即从最后阶段开始，逐次向阶段数小的方向推算，题的最优解，即从最后阶段开始，逐次向阶段数小的方向推算，最终求得全局最优解。最终求得全局最优解。行进方向行进方向动态规划寻优途径动态规划寻优途径EA标号法的一般步骤：标号法的一般步骤： （1）给最后一段标号，该段各状态（即各始点）到终点的距给最后一段标号，该段各状态（即各始点）到终点的距离用数字分别标在各点上方的方格内，并用粗箭线连接各点和终离用数字分别标在各点上方的方格内，并用粗箭线连接各点和终点。点。 （2）向前递推，给前一阶段的各个状态标号。向前递推，给前一阶段的各个状态标号。每个状态上方每个状态上方方格内的数字表示该状态到终点的最短距离。方格内的数字表示该状态到终点的最短距离。将刚标号的点沿着将刚标号的点沿着最短距离用粗箭线连接起来，表示出各刚标号的点到终点的最短最短距离用粗箭线连接起来，表示出各刚标号的点到终点的最短路线。路线。 （3 3）逐次向前递推，直到将第一阶段的状态（即起点）标逐次向前递推，直到将第一阶段的状态（即起点）标号，号，起点方格内的数字就是起点到终点的最短距离起点方格内的数字就是起点到终点的最短距离，从起点开始，从起点开始连接终点的粗箭线就是最短路线。连接终点的粗箭线就是最短路线。50第（第（1）步）步 k=5 f5( x5 ) = f5( E ) = 0 这是这是边界条件边界条件0Efk( xk ) 表示从第表示从第 k 阶段状态阶段状态 xk 到到 E 点的的最短距离点的的最短距离51第（第（2）步）步 k=4状态变量状态变量 x4 可取两种状态可取两种状态 D1、D2。 由由D1到终点到终点E只有一条路线，路长为只有一条路线，路长为3，即，即 f4( D1 ) = 3。 同理，同理， f4( D2 ) = 4 。3表示由表示由D1点至点至E点的最短路长点的最短路长为为3。40D1第（第（3）步）步 k=3状态变量状态变量 x3 可取三个值：可取三个值：C1、C2、C3。由由C1到终点到终点E有有2条路线，分别为经过条路线，分别为经过D1、D2到达到达E点（由点（由D1、D2到达到达E点的最短路长在第一步已计算得出），需加以比较，取其中最短的。点的最短路长在第一步已计算得出），需加以比较，取其中最短的。路线路线1 v3(C1, D1)+ f4(D1) = 1+3=4路线路线2 v3(C1, D2)+ f4(D2) = 4+4=834则由则由C1到终点到终点E的最短距离的最短距离 f3( C1 ) = minv3(C1, D1)+ f4(D1), v3(C1, D2)+ f4(D2) = 44C1第（第（3）步）步 k=3由由C2到终点到终点E有有2条路线，分别为经过条路线，分别为经过D1、D2到达到达E点（由点（由D1、D2到达到达E点的最短路长在第一步已计算得出），需加以比较，取其中最短的。点的最短路长在第一步已计算得出），需加以比较，取其中最短的。路线路线1 v3(C2, D1)+ f4(D1) = 6+3=9路线路线2 v3(C2, D2)+ f4(D2) = 3+4=734则由则由C2到终点到终点E的最短距离的最短距离 f3( C2 ) = minv3(C2, D1)+ f4(D1), v3(C2, D2)+ f4(D2) = 7C274第（第（3）步）步 k=3由由C3到终点到终点E有有2条路线，分别为经过条路线，分别为经过D1、D2到达到达E点（由点（由D1、D2到达到达E点的最短路长在第一步已计算得出），需加以比较，取其中最短的。点的最短路长在第一步已计算得出），需加以比较，取其中最短的。路线路线1 v3(C3, D1)+ f4(D1) = 3+3=6路线路线2 v3(C3, D2)+ f4(D2) = 3+4=734则由则由C3到终点到终点E的最短距离的最短距离 f3( C3 ) = minv3(C3, D1)+ f4(D1), v3(C3, D2)+ f4(D2) = 6C3746第（第（4）步）步 k=2状态变量状态变量 x2 可取三个值：可取三个值：B1、B2、B3。由由B1到终点到终点E，可分别经过，可分别经过C1、C2、C3到达到达E点（由点（由C1、C2、C3到到E点点 的最短距离在第二步已计算出），需加以比较，取其中最短的。的最短距离在第二步已计算出），需加以比较，取其中最短的。路线路线1 v2(B1, C1)+ f3(C1) = 7+4=11路线路线2 v2(B1, C2)+ f3(C2) = 5+7=12路线路线3 v2(B1, C3)+ f3(C3) = 6+6=1234则由则由B1到终点到终点E的最短距离的最短距离 f2( B1 ) = minv2(B1, C1)+ f3(C1), v2(B1, C2)+ f3(C2) v2(B1, C3)+ f3(C3) = 114B17611第（第（4）步）步 k=2由由B2到终点到终点E，可分别经过，可分别经过C1、C2、C3到达到达E点（由点（由C1、C2、C3到到E点点 的最短距离在第二步已计算出），需加以比较，取其中最短的。的最短距离在第二步已计算出），需加以比较，取其中最短的。路线路线1 v2(B2, C1)+ f3(C1) = 3+4=7路线路线2 v2(B2, C2)+ f3(C2) = 2+7=9路线路线3 v2(B2, C3)+ f3(C3) = 4+6=1034则由则由B2到终点到终点E的最短距离的最短距离 f2( B2 ) = minv2(B2, C1)+ f3(C1), v2(B2, C2)+ f3(C2) v2(B2, C3)+ f3(C3) = 74B276117第（第（4）步）步 k=2由由B3到终点到终点E，可分别经过，可分别经过C1、C2、C3到达到达E点（由点（由C1、C2、C3到到E点点 的最短距离在第二步已计算出），需加以比较，取其中最短的。的最短距离在第二步已计算出），需加以比较，取其中最短的。路线路线1 v2(B3, C1)+ f3(C1) = 5+4=9路线路线2 v2(B3, C2)+ f3(C2) = 1+7=8路线路线3 v2(B3, C3)+ f3(C3) = 5+6=1134则由则由B3到终点到终点E的最短距离的最短距离 f2( B3 ) = minv2(B3, C1)+ f3(C1), v2(B3, C2)+ f3(C2) v2(B3, C3)+ f3(C3) = 84B3761178第（第（5）步）步 k=1状态变量状态变量 x1 只取一个值：只取一个值：A。 由由A到终点到终点E，可分别经过，可分别经过B1、B2、B3到达到达E点（由点（由B1、B2、B3到到E点点 的最短距离在第三步已计算出），需加以比较，取其中最短的。的最短距离在第三步已计算出），需加以比较，取其中最短的。经过经过B1点点 v1(A, B1)+ f2(B1) = 2+11=13经过经过B2点点 v1(A, B2)+ f2(B2) = 5+7=12经过经过B3点点 v1(A, B3)+ f2(B3) = 3+8=1134则由则由A到终点到终点E的最短距离的最短距离 f1( A ) = minv1(A, B1)+ f2(B1), v1(A, B2)+ f2(B2) v1(A, B3)+ f2(B3) = 114A7611781159从下图从下图反推反推可得到最优路线。可得到最优路线。344A76117811因此，由因此，由A到终点到终点E的的最优解最优解为：为： AB3C2D2E由点由点A到终点到终点E的的最优值最优值为为11。60小结：小结：在求解的各阶段，都利用了第在求解的各阶段，都利用了第k阶和第阶和第k+1段的如下关段的如下关 系：系： fk( xk ) = min vk( xk, uk ) + fk+1( xk+1 ) (1) f5( x5 = E ) = 0 (2)上述递推关系上述递推关系称为称为动态规划的动态规划的基本方程。基本方程。其中（其中（2）式称）式称为为边界条件。边界条件。344A7611781161动态规划方法的优点动态规划方法的优点1.减少计算量减少计算量 动态规划方法减少了计算量，而且随着阶段数的增加，计动态规划方法减少了计算量，而且随着阶段数的增加，计算量将大大减少。算量将大大减少。2.丰富了计算结果丰富了计算结果 在动态规划的解法中，得到的不仅仅是由在动态规划的解法中，得到的不仅仅是由A点出发到点出发到E点的点的最短路线及相应距离，最短路线及相应距离，而且得到了从所有中间点出发到而且得到了从所有中间点出发到E点的最点的最短路线及相应距离短路线及相应距离。这对于许多实际问题来说是很有用的，有。这对于许多实际问题来说是很有用的，有利于帮助分析所得的结果。利于帮助分析所得的结果。62动态规划方法的基本思想动态规划方法的基本思想1. 将多阶段决策过程划分阶段，恰当地选择状态变量、决策变将多阶段决策过程划分阶段，恰当地选择状态变量、决策变 量，定义最优指标函数，从而把问题化成一簇同类型的子问量，定义最优指标函数，从而把问题化成一簇同类型的子问 题，然后逐个求解。题，然后逐个求解。2. 求解时从边界条件开始，逆过程方向行进，逐段递推寻优，求解时从边界条件开始，逆过程方向行进，逐段递推寻优， 在每一个子问题求解时，都要使用它前面已求出的子问题的在每一个子问题求解时，都要使用它前面已求出的子问题的 最优结果，最后一个子问题的最优解，就是整个问题的最优最优结果，最后一个子问题的最优解，就是整个问题的最优 解。解。63学习目标：学习目标：1 了解顺序解法了解顺序解法4 逆序解法和顺序解法逆序解法和顺序解法64动态规划的求解有动态规划的求解有两种基本方法两种基本方法 逆序解法（后向动态规划方法）逆序解法（后向动态规划方法） 如例如例1所使用的方法，寻优的方向与多阶段决策过程的实际所使用的方法，寻优的方向与多阶段决策过程的实际行进方向相反，从最后一段开始计算逐段前推，求得全过程的行进方向相反，从最后一段开始计算逐段前推，求得全过程的最优策略。最优策略。 顺序解法（前向动态规划方法）顺序解法（前向动态规划方法） 与逆序解法相反，顺序解法的寻优的方向与过程的行进方向与逆序解法相反，顺序解法的寻优的方向与过程的行进方向相同，计算时从第一段开始逐段向后递推，计算后一段要用到相同，计算时从第一段开始逐段向后递推，计算后一段要用到前一段的求优结果，最后一段计算的结果就是全过程的最优结前一段的求优结果，最后一段计算的结果就是全过程的最优结果。果。65我们再次用例我们再次用例1来说明顺序解法。来说明顺序解法。由于此问题的始点由于此问题的始点A与终点与终点E都是固定的，计算由都是固定的，计算由A点到点到E点点的最短路线与由的最短路线与由E点到点到A点的最短路线没有什么不同。点的最短路线没有什么不同。若设若设 fk( xk+1 ) 表示从起点表示从起点A到第到第k阶段末状态点阶段末状态点xk+1的最短距离的最短距离 就可以由前向后逐步求出起点就可以由前向后逐步求出起点A到各阶段末状态点的最短距到各阶段末状态点的最短距离，最后求出起点离，最后求出起点A到到E点的最短距离及路线。点的最短距离及路线。动态规划的目标：动态规划的目标：最优指标最优指标 f4( E )66第一步第一步 k=0 f0( x1 ) = f0( A ) = 0 这是这是边界条件边界条件0Afk( xk+1 ) 表示从起点表示从起点A到第到第k阶段阶段末状态点末状态点xk+1的最短距离的最短距离第二步第二步 k=12350按按 f1( x2 ) 的定义有的定义有 f1( B1 ) = v( B1, A ) + f0( A ) = 2 f1( B2 ) = v( B2, A ) + f0( A ) = 5 f1( B3 ) = v( B3, A ) + f0( A ) = 3 B1B2B3第三步第三步 k=22350按按 f2( x3 ) 的定义有的定义有 v( C1, B1 ) + f1( B1 ) = 7+2 = 9 f2( C1 ) = min v( C1, B2 ) + f1( B2 ) = 3+5 = 8 v( C1, B3 ) + f1( B3 ) = 5+3 = 8 u2( C1 ) = B2 或或B38C1状态转移方程：状态转移方程： xk=Tk( xk+1, uk )第三步第三步 k=22350按按 f2( x3 ) 的定义有的定义有 v( C2, B1 ) + f1( B1 ) = 5+2 = 7 f2( C2 ) = min v( C2, B2 ) + f1( B2 ) = 2+5 = 7 v( C2, B3 ) + f1( B3 ) = 1+3 = 4 u2( C2 ) = B384C2第三步第三步 k=22350按按 f2( x3 ) 的定义有的定义有 v( C3, B1 ) + f1( B1 ) = 6+2 = 8 f2( C3 ) = min v( C3, B2 ) + f1( B2 ) = 4+5 = 9 v( C3, B3 ) + f1( B3 ) = 5+3 = 8 84u2( C3 ) = B1 或或B38C3第四步第四步 k=32350按按 f3( x4 ) 的定义有的定义有 v( D1, C1 ) + f2( C1 ) = 1+8 = 9 f3( D1 ) = min v( D1, C2 ) + f2( C2 ) = 6+4 = 10 v( D1, C3 ) + f2( C3 ) = 3+8 = 11 84u3( D1 ) = C189D1第四步第四步 k=32350按按 f3( x4 ) 的定义有的定义有 v( D2, C1 ) + f2( C1 ) = 4+8 = 12 f3( D2 ) = min v( D2, C2 ) + f2( C2 ) = 3+4 = 7 v( D2, C3 ) + f2( C3 ) = 3+8 = 11 84u3( D2 ) = C2897D2第五步第五步 k=42350按按 f4( x5 ) 的定义有的定义有 v( E, D1 ) + f3( D1 ) = 3+9 = 12 f4( E ) = min v( E, D2 ) + f3( D2 ) = 4+7 = 11 84u4( E ) = D289711E74235084897即可得到最优路线。即可得到最优路线。因此，由因此，由A到终点到终点E的的最优解最优解为：为： AB3C2D2E由点由点A到终点到终点E的的最优值最优值为为11。1175课堂练习l从A 地到D 地要铺设一条煤气管道,其中需经过两级中间站，两点之间的连线上的数字表示距离，如图所示。问应该选择什么路线，使总距离最短？AB1B2C1C2C3D2433332111476解：整个计算过程分三个阶段，从最后一个阶段开始解：整个计算过程分三个阶段，从最后一个阶段开始第一阶段（第一阶段（C D）：）： C 有三条路线到终点有三条路线到终点D 。l显然有显然有 f3 (C1 ) = 1 ； f3(C2 ) = 3 ； f3 (C3 ) = 4AB1B2C1C2C3D2433321114C1C2C377l第二阶段（第二阶段（B C）：）： B 到到C 有六条路线。有六条路线。l d( B1,C1 ) + f3 (C1 ) 3+1l f2 ( B1 ) = min d( B1,C2 ) + f3 (C2 ) = min 3+3 l d( B1,C3 ) + f3 (C3 ) 1+4l 4l = min 6 = 4 l 5AB1B2C1C2C3D24333321114B1B278l d( B2,C1 ) + f3 (C1 ) 2+1l f2 ( B2 ) = min d( B2,C2 ) + f3 (C2 ) = min 3+3 l d( B2,C3 ) + f3 (C3 ) 1+4l 3l = min 6 = 3l 5AB1B2C1C2C3D24333321114B1B279l第三阶段（第三阶段（ A B ）：）： A 到到B 有二条路线。有二条路线。f1 (A) = min = min6,7=6AB1B2C1C2C3D24333321114Ad(A, B1 ) f2 ( B1 )d(A, B2 ) f2 ( B2 )(最短路线为最短路线为AB1C1 D)80l练习练习 P156 例例2 机器负荷分配问题（时间阶段问题）机器负荷分配问题（时间阶段问题）l设有某种机器设备，用于完成两类工作设有某种机器设备，用于完成两类工作A和和B。若。若第第k年初完好年初完好l机器的数量为机器的数量为 xk ，若以数量，若以数量 uk 用于用于A，余下的（，余下的（xkuk）用于）用于l工作工作B，则该年的预期收入为，则该年的预期收入为 g( uk ) + h( xkuk )。其中其中lg( uk ) 8uk ， h( xkuk ) = 5（xkuk）。l又机器设备在使用中会有损坏，设机器用于工作又机器设备在使用中会有损坏，设机器用于工作A时，一年后时，一年后l能继续使用的完好机器数占年初投入量的能继续使用的完好机器数占年初投入量的70%；若用于工作；若用于工作Bl时，一年后能继续使用的完好机器数占年初投入量的时，一年后能继续使用的完好机器数占年初投入量的90%。则在。则在l下一年初下一年初能继续用于能继续用于A、B工作的设备数为工作的设备数为 xk+1uk+0.9(xkluk)。l设第设第1年初完好的机器总数为年初完好的机器总数为1000台，问在连续台，问在连续5年内每年应如年内每年应如l何分配用于何分配用于A、B两项工作的机器数，使两项工作的机器数，使5年的总收益为最大。年的总收益为最大。81l构造动态规划模型如下：构造动态规划模型如下：阶段阶段k：运行年份（运行年份（k = 1,2,6）, 其中其中k=1表示第一年表示第一年初，初， 依次类推；依次类推；k=6表示第表示第5年末（即第年末（即第6年初）。年初）。状态变量状态变量xk：第第k年初完好的机器数（年初完好的机器数（k=1,2, ,4），其中），其中x6表表 示第示第5年末（即第年末（即第6年初）的完好机器数。年初）的完好机器数。决策变量决策变量uk：第第k年度中分配于年度中分配于A工作的机器数量，则工作的机器数量，则xkuk为为 用于用于B工作的机器数量。工作的机器数量。状态转移方程：状态转移方程：xk+1uk + 0.9( xkuk )决策允许集合：决策允许集合：Dk( xk ) = uk | 0ukxk 阶段指标：阶段指标：vk( xk , uk ) = 8uk + 5( xkuk )终端条件：终端条件：f6( x6 ) = 082递推方程：递推方程：fk( xk ) = max vk( xk, uk ) + fk+1( xk+1 ) dk Dk(xk) =max 8uk+5(xk - uk)+fk+1uk+0.9(xk-uk) 0dkxk这里这里xk和和uk均取连续变量，它们的非整数值可以这样理均取连续变量，它们的非整数值可以这样理解，如解，如xk，就表示一台机器在第，就表示一台机器在第k年度中正常工作时间只年度中正常工作时间只占占6/10；uk，就表示一台机器在该年度只有，就表示一台机器在该年度只有3/10的时间能的时间能正常用于正常用于A工作。工作。83f5(x5) = max 8u5+5(x5u5) + f6( x6 ) 0 u5 x5u5*=x5= max 3u5+5x5 0 u5 x5= 8x5f4(x4) = max 8u4+5(x4u4) + f5( x5 ) 0 u4 x4=max 8u4+5(x4u4)+8x5 0 u4 x4状态转移方程：状态转移方程：xk+1uk + 0.9( xkuk )=max 8u4+5(x4u4)+u4+0.9( x4u4 ) 0 u4 x4=maxu4+x4 0 u4 x4u4*=x4=x484f3(x3) = max 8u3+5(x3u3) + f4( x4 ) 0 u3 x3=max 8u3+5(x3u3)+x4 0 u3 x3状态转移方程：状态转移方程：xk+1uk + 0.9( xkuk )=max 8u3+5(x3u3)+u3+0.9( x3u3 ) 0 u3 x3=maxu3+x3 0 u3 x3u3*=x3=x385f2(x2) = max 8u2+5(x2u2) + f3( x3 ) 0 u2 x2=max 8u2+5(x2u2)+x3 0 u2 x2状态转移方程：状态转移方程：xk+1uk + 0.9( xkuk )=max 8u2+5(x2u2)+u2+0.9( x2u2 ) 0 u2 x2=max u2+x2 0 u2 x2u2*= 0=x286f1(x1) = max 8u1+5(x1u1) + f2( x2 ) 0 u1 x1=max 8u1+5(x1u1)+x2 0 u1 x1状态转移方程：状态转移方程：xk+1uk + 0.9( xkuk )=max 8u1+5(x1u1)+u1+0.9( x1u1 ) 0 u1 x1=max u1+x1 0 u1 x1u1*= 0=x187由此可以得到：由此可以得到：lf1(x1x1,u1*=0lf2(x2x2,u2*=0lf3(x3x3,u3*=x3lf4(x4x4,u4*=x4lf5(x5)=8x5 u5*=x5用用x1=1000代入，得到五年最大总收入为代入，得到五年最大总收入为 f1(x1)=f1(1000)=2370088年年度度年初完好机器数年初完好机器数用于工作用于工作A的数的数量量用于工作用于工作B的数的数量量1x1 = 1000u1*=02x2=0.7u1 + 0.9( x1u1 )u2*=03x3=0.7u2 + 0.9( x2u2 )u3*=x34x4=0.7u3 + 0.9( x3u3 )u4*=x45x5=0.7u4 + 0.9( x4u4 )u5*=x5x1u1 =1000x2 = 900x2u2 =900x3 = 810u3= 810x3u3 =0x4 = 567u4= 567x4u4 =0x5 = 397u5= 397x5u5 =089l例例4 某一警卫部门共有某一警卫部门共有12支巡逻队，负责支巡逻队，负责4个要害部位个要害部位A、B、C、Dde警卫巡逻。对每个部位可分别派出警卫巡逻。对每个部位可分别派出24支支巡逻队，并且由于派出巡逻队队数不同，各部位预期在巡逻队，并且由于派出巡逻队队数不同，各部位预期在一段时间内可能造成的损失由差别，具体数字见表。问一段时间内可能造成的损失由差别，具体数字见表。问该警卫部门分别派多少支巡逻队，使总的预期损失为最该警卫部门分别派多少支巡逻队，使总的预期损失为最小。小。ABCD21838243431435223141031212590l解解 把把1212支巡逻队伍往支巡逻队伍往4 4部位看成依次分部位看成依次分4 4个阶段（用个阶段（用k k表示，表示，k=1,2,3,4)k=1,2,3,4)l(1)(1)逆序解法逆序解法l每每个阶段初拥有的可派遣的巡逻队数是前面阶段决策的结果，用状态变量个阶段初拥有的可派遣的巡逻队数是前面阶段决策的结果，用状态变量 来表示。来表示。各阶段的决策变量就是对各部位派出的巡逻队数，用各阶段的决策变量就是对各部位派出的巡逻队数，用 表示表示 ，显然个阶段允许的，显然个阶段允许的决策集合为决策集合为l英每阶段初拥有可派遣的巡逻队数等于上阶段初拥有的数量减去上阶段排出的数，英每阶段初拥有可派遣的巡逻队数等于上阶段初拥有的数量减去上阶段排出的数，故状态转移律为故状态转移律为l若用若用 表示阶段表示阶段 派出的巡逻队数为派出的巡逻队数为 时，该阶段的部位的预期损失值，时，该阶段的部位的预期损失值，因此指标函数可写为因此指标函数可写为91l设用设用 表示表示 阶段状态为阶段状态为 ，以此出发采用最优子策略到过程结，以此出发采用最优子策略到过程结束时的预期损失值，因此有束时的预期损失值，因此有l先考虑给先考虑给D部位派巡逻队，即部位派巡逻队，即 ，上式可写为，上式可写为 l因问题中只有因问题中只有4个要害部门，故第个要害部门，故第5阶段初拥有的未派出的巡逻队数队前阶段初拥有的未派出的巡逻队数队前4个部位的预期损失不再起影响，故边界条件个部位的预期损失不再起影响，故边界条件 ，因此有，因此有l因因 ，又，又 的可能值为的可能值为 ，故由表故由表1的数的数据可得表据可得表2的结果。的结果。92 表表2 2 3 4 2 34 _ _ 34 2 3 34 31 _ 31 3 4 34 31 25 25 4 5 34 31 25 25 4 6 34 31 25 25 493再联合考虑对再联合考虑对C、D两个部位派巡逻队，即两个部位派巡逻队，即 ，这是有，这是有因有因有 ，又，又 ，故可得表故可得表3的结果的结果 表表3 2 3 4 4 24+34 58 2 5 24+31 22+34 55 2 6 24+25 22+31 21+34 49 2 7 24+25 22+25 21+31 47 3 8 24+25 22+25 31+25 46 494l下面考虑对下面考虑对B、C、D三个部位派巡逻队，即三个部位派巡逻队，即 ，这时有，这时有l同样有同样有 又又 ，故计算得表，故计算得表4。 表表4 2 3 4 8 38+49 35+55 31+58 87 2 9 38+47 35+49 31+55 84 3 10 38+46 35+47 31+49 80 495l最后考虑对最后考虑对A、B、C、D四个部位派巡逻队，即四个部位派巡逻队，即 时，有时，有l因因 有有 故计算得表故计算得表5 2 3 4 12 18+80 14+84 10+87 97 496l由表由表5知，最优策略是：知，最优策略是：A部位部位4支，支，B部位部位2支，支，C部位部位2支，支，D部部位位4支，总预期损失为支，总预期损失为97单位。单位。97动态规划动态规划l动态规划问题实例动态规划问题实例l动态规划的基本概念与原理动态规划的基本概念与原理l动态规划应用举例动态规划应用举例98例 Wyndor Glass Company Problem使用动态规划进行求解9912一、动态规划问题建模一、动态规划问题建模这个问题需要对两个相关活动(activity)确定其活动水平(level of activity)，因此我们可以将这两个活动看作动态规划中的阶段。决策变量 ：第 k 个活动的活动水平（ level ofactivity ）状态变量 ：可用于第k阶段生产的资源量（右端项）。即100状态转移方程：阶段指标函数 ：第 k 阶段确定 时所产生的利润即最优指标函数 ：第 k 阶段状态为 且采取最佳投资策略，从第 k 个活动以及以后的最大总利润。 逆序法基本递推方程： 101二、动态规划问题求解二、动态规划问题求解（1）k=2 时因为故有k=2 时决策表102（2）k=1 时因为初时状态确定且103k=2 时决策表104在可行区间 上105因为和都在x1=2时获得最大值36 2k=1 时决策表所以10636 2k=1 时决策表k=2 时决策表107背背 包包 问问 题题 一般的提法为：一旅行者携带背包去登山。已知他所能承受 的背包重量的极限为a (千克)，现有n种物品可供他选择装入背包。第i种物品的单位重量为 (千克)，其价值（可以是表明本物品对登山者的重要性指标）是携带数量 的函数 （i=1，2，n）.问旅行者应如何选择携带物品的件数，以使总价值最大？此模型解决的是运输工具包括卫星的最优装载问题。其数学模型为：108设 为第 i 种物品装入的件数，则背包问题可归结为如下 形式的整数规划模型：下面从一个例子来分析动态规划建模。例例 有一辆最大货运量为10 t 的卡车，用以装载3种货物，每种货物的单位重量及相应单位价值如表7-4 所示。应如何装载可使总价值最大？109货物物编号号i 1 2 3单位重量（位重量（t） 3 4 5单位价位价值 ci 4 5 6表 7- 4 设第 种货物装载的件数为 则问题可表为：阶段阶段k: 将可装入物品按1，2，3的顺序排序，每段装入一种物品，共划分3个阶段，即k=1,2,3.110状态变量状态变量 ：在第k段开始时，背包中允许装入前k种物品的总重量。决策变量决策变量 ：装入第k种物品的件数。状态转移方程：状态转移方程：最优指标函数最优指标函数 ：在背包中允许装入物品的总重量不超过 kg，采取最优策略只装前k种物品时的最大使用价值货物1货物2货物3111由此可得动态规划的顺序递推方程为：K=1 时货物1货物2货物3112K=1 时注意到：例如：时，其它计算结果见表7-5：货物1货物2货物31130 1 2 3 0 1 2 3 4 5 6 7 8 9 104040 40 40 41 40 41 4240 41 42 430004812000123表 7- 5114K=2 时其中例如：时，货物1货物2货物3115表 7- 50 1 2 3 0 1 2 3 4 5 6 7 8 9 104040 40 40 41 40 41 4240 41 42 430004812000123116其它计算结果见表7-6： 0 1 2 0 1 2 3 4 5 6 7 8 9 10500 504 510 5012 518 520 0513011表 7- 6117K=3 时货物1货物2货物3118 0 1 2 0 1 2 3 4 5 6 7 8 9 10500 504 510 5012 518 520 0513011表 7- 6119从再由状态转移方程表 7- 6货物1货物2货物3 0 1 2 0 1 2 3 4 5 6 7 8 9 10500 504 510 5012 518 520 0513011120再由状态转移方程表 7- 5最大装载价值为 0 1 2 3 0 1 2 3 4 5 6 7 8 9 104040 40 40 41 40 41 4240 41 42 430004812000123121总结：今后解背包问题应先从k=3入手：k=3时 下面应有重点地从k=2中求解三个最优函数值： 122K=2 时123所以从第一阶段应有重点地求以下四个数： K=1 时124由此逐一逆推代回上式：125由此逐一逆推代回上式：126由此逐一逆推代回上式：127最后最优策略：再由状态转移方程再由状态转移方程最大装载价值为 128用动态规划方法求解：解：我们用背包问题顺序解的思路：人为的划分三个阶段：k=1,2,3阶段指标函数及其他分配情况如下图：123129123动态规划的顺序递推方程为：130123131132123133134135136137最优决策为所对应的最优解为138例（二维背包） 有一辆最大货运量为13t、最大容量为10件的卡车，用以装载3种货物，每种货物的单位重量及相应单位价值如下表所示。应如何装载可使总价值最大？货物编号货物编号i i 1 1 2 2 3 3单位重量（单位重量（t t） 1 1 3 3 6 6单位价值单位价值 c ci i 4 4 5 5 8 8解：设装载第i种货物的件数为 （i=1,2,3），则问题可表述为139123关于件数的约束:关于重量的约束:基本方程式：140123141问题就是求：123142143144123145同理可求得 146147所以最优决策方案为 ：最优装载价值为：148例 货郎担问题货郎担问题也叫推销商问题（traveling salesman problem）,其一般提法为：有n个城市，用1，2，n表示，城i, j之间的距离为 ，有一个货郎从城1出发到其他城市一次且仅一次，最后回到城市1，怎样选择行走路线使总路程最短？123645789101112452368775845348435623113345149一。动态规划解阶段变量k：按所经过的城市个数划分阶段k, k=1,2,n-1.状态变量 ：设第k 阶段到达城市i 时途中所经过的k个城市集合为S，则其中 123645789101112452368775845348435623113345150例如： ，表示推销商从城1出发途径城市2,3,4到达城市5时，须先途经城市2,4到达城市3，再奔城市5。决策变量 ：第k 阶段到达城市i 的最短路线上邻接i 的前一个城市 。123645789101112452368775845348435623113345151阶段指标函数 : 设从城市1出发，第k-1阶段到达到城市j,则城市j与下一阶段（第k阶段）的目的地城市i之间的距离为 最优指标函数 ：从城市1出发，经过S中k个城市,到达城市i的最短距离.123645789101112452368775845348435623113345152则动态规划的顺序递推关系为:最后算出 ,即为全程的最短距离,同时可得最优策略,即最优行走路线.例1 已知 4个城市间距离如表1，求从城市1出发，经其与城市一次且仅一次最优回到城市1的最短路与距离。12345153 城城城城 市市 市市 1 12 23 34 41 12 23 34 40 08 85 56 66 60 08 85 57 79 90 05 59 97 78 80 0解：由边界条件知：154 城城城城 市市 市市 1 12 23 34 41 12 23 34 40 08 85 56 66 60 08 85 57 79 90 05 59 97 78 80 0当k=1时，从城市1出发，经过1个城市到达城市i的最短距离为： 即从城市1出发，途经1个城市奔城2，应先到4，再到2。155 城城城城 市市 市市 1 12 23 34 41 12 23 34 40 08 85 56 66 60 08 85 57 79 90 05 59 97 78 80 0即从城市1出发，途经1个城市奔城3，应先到4，再到3。156 城城城城 市市 市市 1 12 23 34 41 12 23 34 40 08 85 56 66 60 08 85 57 79 90 05 59 97 78 80 0即从城市1出发，途经1个城市奔城4，应先到2，再到4。157 城城城城 市市 市市 1 12 23 34 41 12 23 34 40 08 85 56 66 60 08 85 57 79 90 05 59 97 78 80 0当k=2时，从城市1出发，途经2个城市到达城市i的最短距离为即从城市1出发，途经2个城市3，4奔城2，应先到4，再到2。158即从城市1出发，途经2个城市2，4奔城3，应先到4，再到3。 城城城城 市市 市市 1 12 23 34 41 12 23 34 40 08 85 56 66 60 08 85 57 79 90 05 59 97 78 80 0159 城城城城 市市 市市 1 12 23 34 41 12 23 34 40 08 85 56 66 60 08 85 57 79 90 05 59 97 78 80 0即从城市1出发，途经2个城市2，3奔城4，应先到2，再到4。160当k=3时，从城市1出发，途经3个城市到达城市1的最短距离货郎担的最短路线是1 2431。 城城城城 市市 市市 1 12 23 34 41 12 23 34 40 08 85 56 66 60 08 85 57 79 90 05 59 97 78 80 0逆推回去行走距离为23。161 第七讲：设备更新问题企业中经常会遇到一台设备应该使用多少年更新最合算的问题。一般来说，一台设备在比较新时，年运转量大，经济收入高，故障少，维修费用少，但随着使用年限的增加，年运转量减少因而收入减少，故障变多，维修费用增加。如果更新可提 高年净收入，但是当年要支出一笔数额较大的购买费。设备更新的一般提法为：在已知一台设备的效益函数 ，维修费用函数 及更新费用函数 条件下，要求在n年内的每年年初作出决策，是继续使用旧设备还是更换一台新的，使使n年总效益最大。 162 例11 某台新设备的年效益及年均维修费、更新净费用如表7-15所示。试确定今后5年内的更新策略，使总收益最大。表 7-15 单位：万元 役龄役龄项目项目012345效益效益54.543.7532.5维修费维修费0.511.522.53更新费更新费0.51.52.22.533.5163解：以年限划分阶段k：1，2，3，4，512345决策变量 : 第k年初保留使用(keep)第k年初更新(replacement)状态变量 : 第k年初，设备已使用过的年数，称役龄。状态转移方程： 164在第k年设备已使用过t年（或役龄为t年），再使用1年时的效益。 在第k年设备已使用过t年（或役龄为t年），再使用1年时的维修费用。在第k年卖掉一台役龄为t年的设备，买进一台新的设备的更新净费用。 役龄役龄项目项目012345效益效益54.543.7532.5维修费维修费0.511.522.53更新费更新费0.51.52.22.533.5165 役龄役龄项目项目012345效益效益54.543.7532.5维修费维修费0.511.522.53更新费更新费0.51.52.22.533.5即： “买一部新机器的费用”“卖一部t年役龄的旧机器的收益”。 阶段指标函数：166最优指标函数 ：第k年初，使用一台已用了 年的设备，到第5年末的最大效益，有按逆序建立递推式：下面用逆序法求解： 167K=5时：此时， 的所有可能取值为：1，2，3，4。下分别求最优指标函数值：12345168 役龄役龄项目项目012345效益效益54.543.7532.5维修费维修费0.511.522.53更新费更新费0.51.52.22.533.5 此时， 169 役龄役龄项目项目012345效益效益54.543.7532.5维修费维修费0.511.522.53更新费更新费0.51.52.22.533.5 此时， 170 役龄役龄项目项目012345效益效益54.543.7532.5维修费维修费0.511.522.53更新费更新费0.51.52.22.533.5 此时， 171 役龄役龄项目项目012345效益效益54.543.7532.5维修费维修费0.511.522.53更新费更新费0.51.52.22.533.5 此时， 172 1 2 3 4 3.5 3 2.5 2.3 1.75 2 0.5 1.53.52.521.5173 1 2 3 43.52.521.5K=5时最优值表174K=4时：此时， 的所有可能取值为：1，2，3。下分别求最优指标函数值：12345175 1 2 3 43.52.521.5K=5时最优值表 役龄役龄项目项目012345效益效益54.543.7532.5维修费维修费0.511.522.53更新费更新费0.51.52.22.533.5 此时， 176 1 2 3 43.52.521.5K=5时最优值表 役龄役龄项目项目012345效益效益54.543.7532.5维修费维修费0.511.522.53更新费更新费0.51.52.22.533.5 此时， 177 1 2 3 43.52.521.5K=5时最优值表 役龄役龄项目项目012345效益效益54.543.7532.5维修费维修费0.511.522.53更新费更新费0.51.52.22.533.5 此时， 178 1 2 36.55.85.5K=4时最优值表179K=3时：此时， 的所有可能取值为：1，2。下分别求最优指标函数值：12345180 役龄役龄项目项目012345效益效益54.543.7532.5维修费维修费0.511.522.53更新费更新费0.51.52.22.533.5 此时， 1 2 36.55.85.5K=4时最优值表181 役龄役龄项目项目012345效益效益54.543.7532.5维修费维修费0.511.522.53更新费更新费0.51.52.22.533.5 此时， 1 2 36.55.85.5K=4时最优值表182 1 2 9.58.8K=3时最优值表183K=2时：此时， 只能取1。所以12345184 役龄役龄项目项目012345效益效益54.543.7532.5维修费维修费0.511.522.53更新费更新费0.51.52.22.533.5 此时， 1 2 9.58.8K=3时最优值表185K=1时：此时， 只能取0。所以12345186 役龄役龄项目项目012345效益效益54.543.7532.5维修费维修费0.511.522.53更新费更新费0.51.52.22.533.5 此时， 18712345状态转移方程： 上述计算递推回去，当 时，由状态转移方程： 知 查得 18812345状态转移方程： 有知 1 2 9.58.8K=3时最优值表查 知18912345状态转移方程： 查 知 1 2 36.55.85.5K=4时最优值表19012345状态转移方程： 查 1 2 3 43.52.521.5K=5时最优值表191故本题最优策略为 ，即第一年初购买的设备到第二、三、四、年初各更新一次，用到第5年末，其总效益为17万元。