运筹学7动态规划

1、教学要求：教学要求： 1掌握动态规划的基本概念：阶段、状态、决策、策掌握动态规划的基本概念：阶段、状态、决策、策略、状态转移方程、指标函数和最优值函数、最优策略、状态转移方程、指标函数和最优值函数、最优策略、最优轨线略、最优轨线 2了解动态规划的基本理论：最优性定理和最优性原了解动态规划的基本理论：最优性定理和最优性原理理 3掌握动态规划基本思想和基本方程掌握动态规划基本思想和基本方程 4牢固掌握动态规划的顺序解法和逆序解法。会处理牢固掌握动态规划的顺序解法和逆序解法。会处理动态与静态规划的关系动态与静态规划的关系 5了解和掌握若干典型问题的动态规划模型及求解技了解和掌握若干典型问题的动态规划

2、模型及求解技巧：如最短路线、资源分配、生产计划、货物存储、巧：如最短路线、资源分配、生产计划、货物存储、设备更新与系统可靠性问题、背包问题、推销商问题设备更新与系统可靠性问题、背包问题、推销商问题等等 6了解多维动态规划降维方法和减少离散状态点数方了解多维动态规划降维方法和减少离散状态点数方法法 7了解随机性问题的动态规划求解方法了解随机性问题的动态规划求解方法 重点：重点：动态规划顺序解法和逆序解法；若干典型问题动态规划模型及求解技巧； 难点：难点：建立动态规划数学模型的状态转移方程。 动态规划（动态规划（Dynamic Programming）是运是运筹学的一个重要分支，它是解决多阶段决策

3、过筹学的一个重要分支，它是解决多阶段决策过程最优化的一种方法。美国数学家贝尔曼（程最优化的一种方法。美国数学家贝尔曼（R. E. Bellman）等人在）等人在50年代初提出了解决多阶年代初提出了解决多阶段决策问题的段决策问题的“最优性原理最优性原理”（Principle of Optimality）。）。1957年贝尔曼出版了专著年贝尔曼出版了专著“动动态规划态规划”，该书是动态规划的第一本著作。目，该书是动态规划的第一本著作。目前动态规划已经用于解决最优路径问题、资源前动态规划已经用于解决最优路径问题、资源分配问题、生产调度问题、设备更新问题、复分配问题、生产调度问题、设备更新问题、复合系

4、统可靠性问题及生产过程最优控制等，并合系统可靠性问题及生产过程最优控制等，并且取得了显著的效果。且取得了显著的效果。回本章目录回本章目录 动态规划是求解问题的一种方法，动态规划是求解问题的一种方法，而不是算法（线性规划是一种算法），而不是算法（线性规划是一种算法），因而没有标准的数学表达式，对于具体因而没有标准的数学表达式，对于具体问题需要具体分析。问题需要具体分析。 一、多阶段决策问题一、多阶段决策问题 在生产经营活动中，某些问题决策过程可在生产经营活动中，某些问题决策过程可以划分为若干相互联系的阶段，每个阶段需要以划分为若干相互联系的阶段，每个阶段需要做出决策，从而使整个过程取得最优。由于

5、各做出决策，从而使整个过程取得最优。由于各个阶段不是孤立的，而是有机联系的，也就是个阶段不是孤立的，而是有机联系的，也就是说，本阶段的决策将影响过程下一阶段的发展，说，本阶段的决策将影响过程下一阶段的发展，从而影响整个过程效果，所以决策者在进行决从而影响整个过程效果，所以决策者在进行决策时不能够仅考虑选择的决策方案使本阶段最策时不能够仅考虑选择的决策方案使本阶段最优，还应该考虑本阶段决策对最终目标产生的优，还应该考虑本阶段决策对最终目标产生的影响，从而做出对全局来讲是最优的决策。当影响，从而做出对全局来讲是最优的决策。当每个阶段的决策确定以后，全部过程的决策就每个阶段的决策确定以后，全部过程的

6、决策就是这些阶段决策所组成的一个决策序列，所以是这些阶段决策所组成的一个决策序列，所以多阶段决策问题多阶段决策问题也称为也称为序贯决策问题序贯决策问题。 多阶段决策问题中，各个阶段一般是多阶段决策问题中，各个阶段一般是按照时间来划分的，随着时间的发展而产按照时间来划分的，随着时间的发展而产生各个阶段的决策，从而形成决策序列，生各个阶段的决策，从而形成决策序列，这就是动态的含义。在一些与时间无关的这就是动态的含义。在一些与时间无关的静态问题中（如非线性规划等），可以人静态问题中（如非线性规划等），可以人为地赋予时间的概念，使其成为一个多阶为地赋予时间的概念，使其成为一个多阶段决策问题，再用动态规

7、划方法处理。段决策问题，再用动态规划方法处理。12n状态状态决策决策状态状态决策决策状态状态状态状态决策决策二、多阶段决策问题举例二、多阶段决策问题举例属于多阶段决策类的问题很多，例如属于多阶段决策类的问题很多，例如： 工厂生产过程工厂生产过程：由于市场需求是：由于市场需求是一随着时间而变化的因素，因此，为了取一随着时间而变化的因素，因此，为了取得全年最佳经济效益，就要在全年的生产得全年最佳经济效益，就要在全年的生产过程中，逐月或者逐季度地根据库存和需过程中，逐月或者逐季度地根据库存和需求情况决定生产计划安排。求情况决定生产计划安排。 设备更新问题设备更新问题：一般企业用于生：一般企业用于生产

8、活动的设备，刚买来时故障少，经济效益产活动的设备，刚买来时故障少，经济效益高，即使进行转让，处理价值也高，随着使高，即使进行转让，处理价值也高，随着使用年限的增加，就会逐渐变为故障多，维修用年限的增加，就会逐渐变为故障多，维修费用增加，可正常使用的工时减少，加工质费用增加，可正常使用的工时减少，加工质量下降，经济效益差，并且，使用的年限越量下降，经济效益差，并且，使用的年限越长、处理价值也越低，自然，如果卖去旧的长、处理价值也越低，自然，如果卖去旧的买新的，还需要付出更新费因此就需要综买新的，还需要付出更新费因此就需要综合权衡决定设备的使用年限，使总的经济效合权衡决定设备的使用年限，使总的经济

9、效益最好。益最好。 例例 3 3 连续生产过程的控制问题连续生产过程的控制问题：一般：一般化工生产过程中，常包含一系列完成生产过化工生产过程中，常包含一系列完成生产过程的设备，前一工序设备的输出则是后一工程的设备，前一工序设备的输出则是后一工序设备的输入，因此，应该如何根据各工序序设备的输入，因此，应该如何根据各工序的运行工况，控制生产过程中各设备的输入的运行工况，控制生产过程中各设备的输入和输出，以使总产量最大和输出，以使总产量最大。 以上所举问题的发展过程都与时间因素以上所举问题的发展过程都与时间因素有关，因此在这类多阶段决策问题中，阶段有关，因此在这类多阶段决策问题中，阶段的划分常取时间

10、区段来表示，并且各个阶的划分常取时间区段来表示，并且各个阶段上的决策往往也与时间因素有关，这就段上的决策往往也与时间因素有关，这就使它具有了使它具有了“动态动态”的含义，所以把处理的含义，所以把处理这类动态问题的方法称为动态规划方法。这类动态问题的方法称为动态规划方法。不过，实际中尚有许多不包含时间因素的不过，实际中尚有许多不包含时间因素的一类一类“静态静态”决策问题，就其本质而言是决策问题，就其本质而言是一次决策问题，是非动态决策问题，但是一次决策问题，是非动态决策问题，但是也可以人为地引入阶段的概念当作多阶段也可以人为地引入阶段的概念当作多阶段决策问题，应用动态规划方法加以解决。决策问题，

11、应用动态规划方法加以解决。 资源分配问题：资源分配问题：便属于这类静态便属于这类静态问题。如：某工业部门或公司，拟对其所问题。如：某工业部门或公司，拟对其所属企业进行稀缺资源分配，为此需要制定属企业进行稀缺资源分配，为此需要制定出收益最大的资源分配方案。这种问题原出收益最大的资源分配方案。这种问题原本要求一次确定出对各企业的资源分配量，本要求一次确定出对各企业的资源分配量，它与时间因素无关，不属动态决策，但是，它与时间因素无关，不属动态决策，但是，我们可以人为地规定一个资源分配的阶段我们可以人为地规定一个资源分配的阶段和顺序，从而使其变成一个多阶段决策问和顺序，从而使其变成一个多阶段决策问题题

12、( (后面我们将详细讨论这个问题后面我们将详细讨论这个问题) )。 运输网络问题：运输网络问题：如图如图7-17-1所示的所示的运输网络，点间连线上的数字表示两地距运输网络，点间连线上的数字表示两地距离离( (也可是运费、时间等也可是运费、时间等) )，要求从，要求从f fk k( (s sk k) )至至v v1010的最短路线。的最短路线。 这种运输网络问题也是静态决策问题。这种运输网络问题也是静态决策问题。但是，按照网络中点的分布，可以把它分但是，按照网络中点的分布，可以把它分为为4 4个阶段，而作为多阶段决策问题来研究。个阶段，而作为多阶段决策问题来研究。 v2 5 5 6 14 10

13、 9 3 8 8 7 7 8 8 6 5 6 11 7 9 5 v1 v3 v4 v6 v5 v7 v9 v8 v10 1234图图7-17-1 运输网络图示运输网络图示（10）（14）（16）（15）（17）（22）（22）（21）（27）特别注意：特别注意：动态规划求解的多阶段决策问题的特点：动态规划求解的多阶段决策问题的特点：适合于用动态规划方法求解的只是一类特殊的多适合于用动态规划方法求解的只是一类特殊的多阶段决策问题，即具有阶段决策问题，即具有“无后效性无后效性”的多阶段决的多阶段决策过程。所谓无后效性，又称策过程。所谓无后效性，又称马尔柯夫性马尔柯夫性，是指，是指系统从某个阶段往后

14、的发展，仅由本阶段所处的系统从某个阶段往后的发展，仅由本阶段所处的状态及其往后的决策所决定，与系统以前经历的状态及其往后的决策所决定，与系统以前经历的状态和决策状态和决策( (历史历史) )无关。无关。 引言引言 为了说明动态规划的基本思想方法为了说明动态规划的基本思想方法和特点，以下面的例题来讨论求最短路和特点，以下面的例题来讨论求最短路问题的方法。问题的方法。回本章目录回本章目录 第一种方法第一种方法称做称做全枚举法或穷举法全枚举法或穷举法。它的基本。它的基本思想是列举出所有可能发生的方案和结果，再对思想是列举出所有可能发生的方案和结果，再对它们一一进行比较，求出最优方案。这里从它们一一进

15、行比较，求出最优方案。这里从A A到到G G的路程可以分为的路程可以分为6 6个阶段。第一段的走法有个阶段。第一段的走法有2 2种，种，第二、三、四、五、六段的走法各第二、三、四、五、六段的走法各6 6、8 8、6 6、6 6、2 2，因此共有，因此共有2 23 32 22 22 24848条可能的路线，条可能的路线，分别算出各条路线的距离，最后进行比较求优。分别算出各条路线的距离，最后进行比较求优。AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G531368763685338422213335256643最优路径长度最优路径长度1818第二种方法第二种方法即所谓即所谓“局部最优路

16、径局部最优路径”法，是说某人从法，是说某人从k k阶段出发，他并不顾及全线是否最短，只是选择当前最阶段出发，他并不顾及全线是否最短，只是选择当前最短途径，短途径，“逢近便走逢近便走”，错误地以为局部最优会致整体，错误地以为局部最优会致整体最优，在这种想法指导下，所取决策必是下图所示，全最优，在这种想法指导下，所取决策必是下图所示，全程长度是程长度是2525；显然，这种方法的结果常是错误的；显然，这种方法的结果常是错误的AB1B2C1C2C3D1D2D3E1E2E3F1F2G531368763685338422213335256643C4第三种方法第三种方法是是动态规划方法动态规划方法。动态规划

17、。动态规划方法寻求该最短路问题的基本思想是，方法寻求该最短路问题的基本思想是，首先将问题划分为首先将问题划分为6 6个阶段，每次的选择个阶段，每次的选择总是综合后继过程的一并最优进行考虑，总是综合后继过程的一并最优进行考虑，在各段所有可能状态的最优后继过程都在各段所有可能状态的最优后继过程都已求得的情况下，全程的最优路线便也已求得的情况下，全程的最优路线便也随之得到。随之得到。 运用动态规划求解多阶段决策问题，运用动态规划求解多阶段决策问题，首先要将该问题写成动态规划模型，再首先要将该问题写成动态规划模型，再进行求解，动态规划模型中用到的概念进行求解，动态规划模型中用到的概念及符号如下：及符号

18、如下：12n状态状态决策决策状态状态决策决策状态状态状态状态决策决策12ks1u1s2u2s3skuksk+1例例6 最短路问题最短路问题 如图如图7-2所示，要从所示，要从A地到地到E地铺设管线，中间地铺设管线，中间需要经过三个中间站，两点之间的连线上的数字表需要经过三个中间站，两点之间的连线上的数字表示距离，问应该选择什么路线，使总距离最短？示距离，问应该选择什么路线，使总距离最短？35256321737562254321B1AB2B3C1C2C3C4ED2D11.阶段（阶段（stage） 根据所需解决问题的特点，按照时间或根据所需解决问题的特点，按照时间或空间顺序把整个过程划分为若干相互

19、联系的阶空间顺序把整个过程划分为若干相互联系的阶段，以便按照一定次序求解。描述阶段的变量段，以便按照一定次序求解。描述阶段的变量称为称为阶段变量阶段变量，通常用字母，通常用字母k表示阶段变量。表示阶段变量。例如例例如例6中，从中，从A到到E可以划分为四个阶段，第可以划分为四个阶段，第一阶段一阶段k=1，从，从A到到B（B有三种选择，有三种选择，B1，B2，B3）；第二阶段）；第二阶段k=2，从，从B到到C（C有四种选择，有四种选择，C1，C2，C3，C4）；第三阶段）；第三阶段k=3，从，从C到到D（D有两种选择，有两种选择，D1，D2）；第四阶段）；第四阶段k=4，从从D到到E。 例例6可以

20、分为四个阶段来求解，可以分为四个阶段来求解，k=1，2，3，4。上海上海A伊犁伊犁 EB1B245C1C2C3425D1D356753D243654546第一阶段第一阶段第二阶段第二阶段第三阶段第三阶段第四阶段第四阶段2.状态（状态（state） 状态状态表示各阶段开始所处的自然状况或客表示各阶段开始所处的自然状况或客观条件，它既是某阶段过程演变的起点，又是观条件，它既是某阶段过程演变的起点，又是前一阶段某种决策的结果。描述状态的变量称前一阶段某种决策的结果。描述状态的变量称为为状态变量状态变量，常用，常用sk表示第表示第k阶段的状态变量。阶段的状态变量。状态变量状态变量sk的取值集合称为的取

21、值集合称为状态集合状态集合，第，第k阶段阶段的状态集合记为的状态集合记为Sk ，例如例，例如例6中，第一阶段状中，第一阶段状态为态为A，第二阶段有三个状态：，第二阶段有三个状态：B1，B2，B3；第三阶段有四个状态：第三阶段有四个状态：C1，C2，C3，C4；第四；第四阶段有两个状态：阶段有两个状态：D1，D2；各阶段状态集合分；各阶段状态集合分别为：别为： S1=A S2=B1，B2，B3 S3=C1，C2，C3，C4 S4=D1，D2上海上海A伊犁伊犁 EB1B245C1C2C3425D1D356753D243654546第一阶段第一阶段第二阶段第二阶段第三阶段第三阶段第四阶段第四阶段S1

22、=AS2=B1,B2S3=C1, C2, C3.n n个阶段的决策过程有个阶段的决策过程有n+1n+1个状态变量个状态变量 这里状态的选取应当满足这里状态的选取应当满足无后效性无后效性：系统：系统从某个阶段往后的发展演变，完全由系统本阶从某个阶段往后的发展演变，完全由系统本阶段所处的状态及决策所决定，与系统以前的状段所处的状态及决策所决定，与系统以前的状态及决策无关。也就是说，过去的历史只能通态及决策无关。也就是说，过去的历史只能通过当前的状态去影响未来的发展，当前的状态过当前的状态去影响未来的发展，当前的状态是过去历史的一个完整总结。只有具有无后效是过去历史的一个完整总结。只有具有无后效性的

23、多阶段决策过程才适合于用动态规划方法性的多阶段决策过程才适合于用动态规划方法求解。求解。 例例6中，当某个阶段已经选定某个点时，中，当某个阶段已经选定某个点时，这个点以后的管线铺设只与该点有关，而与该这个点以后的管线铺设只与该点有关，而与该点以前的管线铺设无关，所以满足无后效性。点以前的管线铺设无关，所以满足无后效性。3.决策（决策（decision） 当各阶段的状态选定以后，可以做出不同的决定当各阶段的状态选定以后，可以做出不同的决定（或选择）从而确定下一个阶段的状态，这种决定（或选择）从而确定下一个阶段的状态，这种决定（或选择）称为（或选择）称为决策决策。表述决策的变量称为。表述决策的变量

24、称为决策变量决策变量，常用常用uk（sk）表示第表示第k阶段当状态为阶段当状态为sk时的决策变量。时的决策变量。实际问题中，决策变量的取值往往限制在某一范围内，实际问题中，决策变量的取值往往限制在某一范围内，此范围称为此范围称为允许决策集合允许决策集合，常用，常用Dk（sk）表示第表示第k阶段阶段从状态从状态sk出发的允许决策集合，显然出发的允许决策集合，显然uk（sk）Dk（sk）。）。 例如例例如例6中，第二阶段若从中，第二阶段若从B2出发，可以选择出发，可以选择C1，C2，C3，C4，即允许决策集合为：，即允许决策集合为： D2（B2）=C1，C2，C3，C4 当决定选择当决定选择C3时

25、，可以表示为：时，可以表示为：u2（B2）=C3上海上海A伊犁伊犁 EB1B245C1C2C3425D1D356753D243654546第一阶段第一阶段S1=Au1(A)= B1 或 u1(A)= B2 , D1(A)=B1, B24.策略（策略（policy） 当各个阶段的决策确定以后，各阶段的决策形成一当各个阶段的决策确定以后，各阶段的决策形成一个决策序列，称此决策序列为一个个决策序列，称此决策序列为一个策略策略。使系统达到最。使系统达到最优效果的策略称为优效果的策略称为最优策略最优策略。在。在n阶段决策过程中，从阶段决策过程中，从第第k阶段到终止状态的过程，称为阶段到终止状态的过程，称

26、为k后部子过程后部子过程（或称为（或称为k子过程），子过程），k后部子过程相应的决策序列称为后部子过程相应的决策序列称为k后部子后部子过程策略过程策略，简称，简称子策略子策略，记为，记为p k，n（sk），即：），即：P k，n（sk）=uk（sk），），uk+1（sk+1），），un（sn）当当k=1时，即由第一阶段某个状态出发做出的决策序列称时，即由第一阶段某个状态出发做出的决策序列称为全过程策略，简称策略，记为为全过程策略，简称策略，记为p1，n（s1），即：），即：p1，n（s1）=u1（s1），），u2（s2），），un（sn）上海上海A伊犁伊犁 EB1B245C1C2C3425D1

27、D356753D243654546P1,5(A)=A, B1, C2 , D2 , E P1,5(A)=A, B2, C3 , D3 , E P2,5(A)=B2, C2 , D1 , E 5.状态转移方程（状态转移方程（state transfer equation） 动态规划中，本阶段的状态往往是上一个阶段状态和动态规划中，本阶段的状态往往是上一个阶段状态和上一个阶段决策作用的结果。设第上一个阶段决策作用的结果。设第k阶段状态为阶段状态为sk，做，做出的决策为出的决策为uk（sk），则第），则第k+1阶段的状态阶段的状态sk+1随之确随之确定，他们之间的关系可以表示为：定，他们之间的关系可

28、以表示为： sk+1=Tk（sk，uk） 这种表示从第这种表示从第k阶段到第阶段到第k+1阶段状态转移规律的方程阶段状态转移规律的方程称为称为状态转移方程状态转移方程，它反映了系统状态转移的递推规，它反映了系统状态转移的递推规律。例如例律。例如例6中，上一阶段的决策就是下一阶段的状态，中，上一阶段的决策就是下一阶段的状态，所以状态转移方程为：所以状态转移方程为： sk+1= uk（sk） 状态转移方程是建立动态规划数学模型的难点之一。状态转移方程是建立动态规划数学模型的难点之一。),(),(),(122231112kkkkusTsusTsusTs12ks1u1s2u2s3skuksk+1一旦某

29、阶段的状态一旦某阶段的状态和决策为已知，下和决策为已知，下阶段的状态便完全阶段的状态便完全确定确定无后效性。无后效性。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） 动态规划数学模型的指标函数

30、应该具有可分离性，并满动态规划数学模型的指标函数应该具有可分离性，并满足递推关系，即：足递推关系，即： Vk，n（sk，uk，sk+1，sn+1）=ksk，uk，Vk+1，n（sk+1，sn+1） 在阶段在阶段k状态为状态为sk，决策为，决策为uk（sk）时得到的反映第）时得到的反映第k阶阶段的数量指标段的数量指标vk（sk，uk）称为）称为k阶段的指标函数阶段的指标函数。常见的指标函数形式有两种：常见的指标函数形式有两种：（1）任一后部子过程的指标函数是它所包含的各）任一后部子过程的指标函数是它所包含的各阶段指标的和，即：阶段指标的和，即： Vk,n（sk，uk，sn+1）= 写成递推关系：

31、写成递推关系：Vk,n（sk，uk，sn+1）= vk（sk，uk）+ Vk+1,n（sk+1，uk+1，sn+1）nkjjjjusv),(（2）任一后部子过程的指标函数是它所包含的）任一后部子过程的指标函数是它所包含的各阶段指标的积，即：各阶段指标的积，即： Vk,n（sk，uk，sn+1）= 写成递推关系：写成递推关系：Vk,n（sk，uk，sn+1）= vk（sk，uk）Vk+1,n（sk+1，uk+1，sn+1）nkjjjjusv),( 指标函数的最优值记为指标函数的最优值记为fk（sk），它表示从第），它表示从第k阶阶段状态段状态sk出发，采取最优策略出发，采取最优策略p*k，n（s

32、k）到第）到第n阶阶段的终止状态时的最佳指标函数值，即：段的终止状态时的最佳指标函数值，即： opt 是英文是英文optimization（优化）的缩写，根据问（优化）的缩写，根据问题的性质取题的性质取max或或min。 kksf n,kkn,k*p,sV n,kkn,kPpp,sVoptn,kn,k 当当k=1时，时，f1（s1）就是从初始状态）就是从初始状态s1出发出发到终止状态的最优函数。在不同的问题到终止状态的最优函数。在不同的问题中，指标函数可以是利润、成本、距离、中，指标函数可以是利润、成本、距离、产品质量或资源消耗等。在最短路线问产品质量或资源消耗等。在最短路线问题中，第题中，第

33、k阶段的指标函数阶段的指标函数vk（sk，uk）通常也用通常也用dk（sk，uk）表示。）表示。 例如例例如例6中，中，d2（B2，C3）表示第二阶段）表示第二阶段中由点中由点B2到点到点C3的距离，的距离，fk（sk）表示从）表示从第第k阶段点阶段点sk到终点到终点E的最短距离，的最短距离，f1（A）就是所求从就是所求从A到到E的最短距离。的最短距离。AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G531368763685338422213335256643的的最最优优策策略略（最最短短路路）到到是是若若GCGFEDC22212则不论前面则不论前面A如何到达如何到达B，B又如何到

34、达又如何到达C2，对于对于C2来说：来说：的的最最优优策策略略（最最短短路路）到到是是GDGFED1221的的最最优优策策略略（最最短短路路）到到是是GEGFE222的的最最优优策策略略（最最短短路路）到到是是GFGF22二、最优化原理二、最优化原理 一个过程的最优策略具有这样的性质：一个过程的最优策略具有这样的性质：即无论初始状态及初始决策如何，对于先前决即无论初始状态及初始决策如何，对于先前决策所形成的状态而言，其以后的所有决策必构策所形成的状态而言，其以后的所有决策必构成最优策略，即一个最优策略的子策略也是最成最优策略，即一个最优策略的子策略也是最优的。优的。AB1B2C1C2C3C4D

35、1D2D3E1E2E3F1F2G531368763685338422213335256643路路线线得得由由起起点点到到终终点点的的最最短短点点的的最最短短路路线线，最最后后求求的的方方法法，求求出出各各点点到到终终逆逆序序由由后后向向前前从从最最后后一一阶阶段段开开始始，用用找找最最短短路路线线的的方方法法)(： kksf点点的的最最短短距距离离到到阶阶段段状状态态为为从从第第Gskk Af,1求求 1k1kkkusfu,sdmink kksfk=4,3,2,1 0sf77 E1E2E3F1F2G33525664k=6k=6,F1 G f f6 6(F1)=4(F1)=4F F2 2 G ,

36、f,f6 6(F2)=3(F2)=3k=5k=5，出发点，出发点E1E1、E2E2、E3E3 73543minFfF,EdFfF,Edmin2621516115 u5(E1)=F1E1 F1 G 53245minFfF,EdFfF,Edminf262251612525E )E(f15u5(E2)=F2E2 F2 G 93646minFfF,EdFfF,Edminf262351613535E u5(E3)=F2E3 F2 Gk=4，f4(D1)=7 u4(D1)=E2f4(D2)=6 u4(D2)=E2f4(D3)=8 u4(D3)=E2D1D2D3E1E2E3F1F2G222133352566

37、43525Ef7)(15Ef935Efk=2, f2(B1)=13 u2(B1)=C2 f2(B2)=16 u2(B2)=C3= 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)=E2f3(C1)=13 u3(C1)=D1f3(C2)=10 u3(C2)=D1f3(C3)=9 u3(C3)=D1f3(C4)=12 u3(C4)=D3k=3,u1(A)=B1u2(B1)=C2u3(C2)=D1u4(D1)=E2 u5(E2)=F2u6(F2)=G最优策略最优策

38、略 路长路长1818AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G531368763685338422213335256643AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G537363421333264动态规划方法明显优于穷举法动态规划方法明显优于穷举法（计算次数及结果数量）（计算次数及结果数量）1 1、动态规划方法的关键在于正确地写出基本的、动态规划方法的关键在于正确地写出基本的。要做。要做到这一点，就必须将问题的过程分成几个相互联系到这一点，就必须将问题的过程分成几个相互联系的的，恰当的选取，恰当的选取，从而把一个大问题转化成，从而把一个大问题转化成，然后逐个求

39、解。即从边界条件开始，逐段，然后逐个求解。即从边界条件开始，逐段递推寻优，在每一个子问题的求解中，均利用了它递推寻优，在每一个子问题的求解中，均利用了它前面的子问题的最优化结果，依次进行，最后一个前面的子问题的最优化结果，依次进行，最后一个子问题所得的最优解，就是整个问题的最优解。子问题所得的最优解，就是整个问题的最优解。结论：结论：2 2、在多阶段决策过程中，动态规划方法是既把当前、在多阶段决策过程中，动态规划方法是既把当前一段和未来一段分开，又把当前效益和未来效益结合一段和未来一段分开，又把当前效益和未来效益结合起来考虑的一种最优化方法。因此，起来考虑的一种最优化方法。因此，。3 3、在求

40、整个问题的最优策略时，由于边界（初始或、在求整个问题的最优策略时，由于边界（初始或结果）状态是已知的，而每段的决策都是该段状态结果）状态是已知的，而每段的决策都是该段状态的函数，故最优策略便可通过的函数，故最优策略便可通过递推递推逐段变换得到，从而确定最优路线。（请看下例）逐段变换得到，从而确定最优路线。（请看下例）AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G531368763685338422213335256643例：请用顺序法求解下列最短路问题例：请用顺序法求解下列最短路问题123456 ;B,BS;AS2121 ：状态状态 221111U;B)A(u,B)A(uU：决策

41、决策 )B(f)C,B(r)B(f)C,B(rmin)C(f; 3)B(f ; 5)B(f2122211212222111：最最优优值值函函数数 ;B,BS;AS2121 ：状状态态 221111U;B)A(u,B)A(uU：决决策策 0)s (f，0)A(f)s (f)s ,u(rmin)s (f100k-1k1kkk1kk即即动动态态规规划划方方程程：通常情况下，当初始状态给定时用逆序解法较方便。通常情况下，当初始状态给定时用逆序解法较方便。当终止状态给定时用顺序解法较方便。当终止状态给定时用顺序解法较方便。但若初始状态虽已给定，然而终点状态较多（需比较但若初始状态虽已给定，然而终点状态较

42、多（需比较到达不同终点状态的各个路径）到达不同终点状态的各个路径）及指标函数值以选取总效益最佳的终点状态时及指标函数值以选取总效益最佳的终点状态时, ,以使以使用顺序解法比较方便。用顺序解法比较方便。三、动态规划的基本思想与基本原理三、动态规划的基本思想与基本原理 下面求解下面求解例例6 35256321737562254321B1AB2B3C1C2C3C4ED2D1 k=4时，时，状态变量状态变量s4可取两种状态可取两种状态D1，D2，他们到，他们到终点终点E的最短路长为：的最短路长为： f4（D1）= d4（D1，E）=3 u4（D1）=E f4（D2）= d4（D2，E）=5u4（D2）

43、=E k=3时，时，状态变量状态变量s3可取四种状态可取四种状态C1，C2，C3，C4，当当s3= C1时，到达点可以有两种选择：时，到达点可以有两种选择：D1或或D2，则：则： u3（C1）=D1 说明说明C1点至终点点至终点E的最短距离是的最短距离是5，最短路线为：，最短路线为：C1D1E。55532min)(),()(),(min)(242131411313DfDCdDfDCdCf 同理，从同理，从C2，C3，C4出发，有：出发，有：u3（C2）=D2u3（C3）=D1 f3（C4）= d3（C4，D2）+ f4（D2）=7+5=12u3（C4）=D285336min)(),()(),(

44、min)(242231412323DfDCdDfDCdCf55132min)(),()(),(min)(242331413333DfDCdDfDCdCfk=2时时，类似地有：，类似地有：u2（B1）=C1u2（B2）=C3u2（B3）=C3108455min)(),()(),(min)(232121311212CfCBdCfCBdBf10123558657min)(),()(),()(),()(),(min)(4342233322232221312222CfCBdCfCBdCfCBdCfCBdBf712252min)(),()(),(min)(434323333232CfCBdCfCBdBf

45、k=1时，时，有：有：u1（A）=B3 于是得到从于是得到从A点到点到E点的最短距离为点的最短距离为10，按计，按计算顺序反向追踪，得到最优决策序列算顺序反向追踪，得到最优决策序列uk，即，即，u1（A）=B3，u2（B3）=C3，u3（C3）=D1，u4（D1）=E；最优路线为：；最优路线为： AB3C3D1E1073101102min)(),()(),()(),(min)(3231222112111BfBAdBfBAdBfBAdAf 从上面计算过程可以看出，在各阶段求解中，从上面计算过程可以看出，在各阶段求解中，都用到了第都用到了第k阶段和第阶段和第k+1阶段的递推关系：阶段的递推关系：

46、这种递推关系称为动态规划的基本方程。其中这种递推关系称为动态规划的基本方程。其中（7.1b）式称为边界条件，（）式称为边界条件，（7.1b）也可以写）也可以写作，作，f4（s4）= d4（s4，E）)1 . 7( 0)()1 . 7( 1 , 2 , 3 , 4 )(),(min)(5511bsfaksfusdsfkkkkkkk 上述计算最短路线的过程也可以直接在上述计算最短路线的过程也可以直接在图上直观表示出来，如图图上直观表示出来，如图7-3，节点上方，节点上方方格内数字表示该点到方格内数字表示该点到E点的最短距离。点的最短距离。各点到各点到E点之间的连线表示最短路线，这点之间的连线表示最

47、短路线，这种直接在图上求解的方法称为标号法，种直接在图上求解的方法称为标号法，这种方法的最大优点是不仅可以得到从这种方法的最大优点是不仅可以得到从点点A到点到点E的最短路，而且得到了中间任的最短路，而且得到了中间任意一点到意一点到E点的最短路，即得到了一族最点的最短路，即得到了一族最优解，这对于许多实际问题来讲是很有优解，这对于许多实际问题来讲是很有意义的。意义的。3523275253B1AB2B3C1C2C3C4ED2D1075853510121010图图7-3 如果规定从如果规定从A点到点到E点为顺行方向，则由点为顺行方向，则由E点到点到A点为逆行方向，图点为逆行方向，图7-3是由是由E点

48、开始，由后向点开始，由后向前标号，这种以前标号，这种以A为始端，为始端，E为终端，从为终端，从E到到A的解法称为逆序解法。的解法称为逆序解法。 标号也可以由标号也可以由A点开始，从前向后标号，如图点开始，从前向后标号，如图7-4，这种以，这种以E为始端，为始端，A为终端，从为终端，从A到到E的解的解法称为顺序解法。方格内数字表示该点到法称为顺序解法。方格内数字表示该点到A点点的最短距离。连接的最短距离。连接A点和该点的折线表示该点点和该点的折线表示该点到起点到起点A的最短路线。的最短路线。3213254321B1AB2B3C1C2C3C4ED2D1100213765476图图7-4 动态规划的

49、基本思想概括归结如下：动态规划的基本思想概括归结如下： 1. 将多阶段决策问题按照空间或时间顺序划分成相互将多阶段决策问题按照空间或时间顺序划分成相互联系的阶段，即把一个大问题分解成一族同类型的子联系的阶段，即把一个大问题分解成一族同类型的子问题，选取恰当的状态变量和决策变量，写出状态转问题，选取恰当的状态变量和决策变量，写出状态转移方程，定义最优指标函数，写出递推关系式和边界移方程，定义最优指标函数，写出递推关系式和边界条件。条件。 2. 从边界条件开始，由后向前逐段递推寻找最优，在从边界条件开始，由后向前逐段递推寻找最优，在每一个阶段的计算中都要用到前一阶段的最优结果，每一个阶段的计算中都

50、要用到前一阶段的最优结果，依次进行，求得最后一个子问题的最优解就是整个问依次进行，求得最后一个子问题的最优解就是整个问题的最优解。题的最优解。 3. 在多阶段决策过程中，确定阶段在多阶段决策过程中，确定阶段k的最优决策时，不的最优决策时，不是只考虑本阶段最优，而是要考虑本阶段及其所有后是只考虑本阶段最优，而是要考虑本阶段及其所有后部子过程的整体最优，也就是说，它是把当前效益和部子过程的整体最优，也就是说，它是把当前效益和未来效益结合起来考虑的一种方法。未来效益结合起来考虑的一种方法。 R. Bellman等人在深入研究多阶段决策问题的等人在深入研究多阶段决策问题的基础上，提出了著名的基础上，提

51、出了著名的最优性原理最优性原理：“作为整作为整个过程的最优策略具有这样的性质：无论过去个过程的最优策略具有这样的性质：无论过去的状态和决策如何，相对于前面的决策所形成的状态和决策如何，相对于前面的决策所形成的状态而言，余下的决策序列必然构成最优子的状态而言，余下的决策序列必然构成最优子策略。策略。”也就是说，一个最优策略的子策略也也就是说，一个最优策略的子策略也是最优的。这一原理是动态规划方法的核心，是最优的。这一原理是动态规划方法的核心，根据最优原理可以将一个多阶段决策过程化为根据最优原理可以将一个多阶段决策过程化为若干个单阶段决策过程，当然这种转化要满足若干个单阶段决策过程，当然这种转化要

52、满足两个基本条件，这就是前文所述的指标函数的两个基本条件，这就是前文所述的指标函数的可分离性和状态变量的无后效性。可分离性和状态变量的无后效性。一、动态规划问题的解法动态规划问题的解法二、动态规划的数学模型二、动态规划的数学模型回本章目录回本章目录一、动态规划问题的解法一、动态规划问题的解法二、动态规划的数学模型二、动态规划的数学模型1 1、理论依据、理论依据-最优化原理最优化原理 最优化原理：一个过程的最优策略具最优化原理：一个过程的最优策略具有这样的性质，即无论初始状态及初始有这样的性质，即无论初始状态及初始决策如何，对于先前决策所形成的状态决策如何，对于先前决策所形成的状态而言，其以后的

53、所有决策必构成最优策而言，其以后的所有决策必构成最优策略。略。2 2、动态规划模型的几个要素：、动态规划模型的几个要素：1) 1)阶段数阶段数k k2) 2)状态变量状态变量s sk k S Sk k3) 3)决策变量决策变量u uk k( s( sk k) ) U Uk k4) 4)指标函数指标函数V Vk,nk,n 状态转移方程状态转移方程 kk1ku,sTs 5) 5)最优值函数最优值函数f fk k(s (sk k) )6）动态规划的基本方程）动态规划的基本方程 动态规划的基本方程是建立动态规划模型的关键。动态规划的基本方程是建立动态规划模型的关键。设第设第k阶段处于状态阶段处于状态s

54、k，决策是，决策是uk(sk)，状态转移，状态转移方程为方程为sk+1=Tk（sk，uk），），k阶段和阶段和k+1阶段的递阶段的递推关系式可以写为：推关系式可以写为：)2 . 7 ( 10)()2 . 7 ( 1 , 1, )(),()(1111)(bsfannksfusvoptsfnnkkkkksDukkkkk或 式式(7.2a)中运算符号中运算符号*表示加表示加“”或乘或乘“”。当运算符号取加法时，边界条件当运算符号取加法时，边界条件fn+1（sn+1）=0，当运算符号取乘法时，边界条件当运算符号取乘法时，边界条件fn+1（sn+1）=1。求解时，根据边界条件从求解时，根据边界条件从k=

55、n开始，由后向前开始，由后向前逆推，逐步求得各段最优决策和相应的最优值，逆推，逐步求得各段最优决策和相应的最优值，最后求得最后求得f1（s1），得到整个问题的最优解。），得到整个问题的最优解。这种由后向前计算最优解的方法称为这种由后向前计算最优解的方法称为逆序解法逆序解法（backward induction method），相应的基本），相应的基本方程称为逆序解法基本方程。方程称为逆序解法基本方程。3、建立动态规划模型的步骤、建立动态规划模型的步骤（1）划分阶段：）划分阶段： 划分阶段是运用动态规划求解多阶段决策问题的第一步，在确划分阶段是运用动态规划求解多阶段决策问题的第一步，在确定多阶段

56、特性后，按时间或空间先后顺序，将过程划分为若干相互定多阶段特性后，按时间或空间先后顺序，将过程划分为若干相互联系的阶段。对于静态问题要人为地赋予联系的阶段。对于静态问题要人为地赋予“时间时间”概念，以便划分概念，以便划分阶段。阶段。（2）正确选择状态变量）正确选择状态变量 sk, 满足满足:可知性可知性: 正确描述动态过程演变正确描述动态过程演变, 可直接或间接确定状态变量的值可直接或间接确定状态变量的值;无后效性无后效性: 后面的决策与前面的决策无关后面的决策与前面的决策无关;（3）确定决策变量）确定决策变量uk及允许决策集合及允许决策集合Dk（sk） 通常选择所求解问题的关键变量作为决策变

57、量，通常选择所求解问题的关键变量作为决策变量，同时要给出决策变量的取值范围，即确定允许决策集同时要给出决策变量的取值范围，即确定允许决策集合。合。（4）确定状态转移方程）确定状态转移方程 根据根据k阶段状态变量阶段状态变量sk和决策变量和决策变量uk（sk）写出）写出k+1阶段状态变量阶段状态变量sk+1，即，即sk+1=Tk（sk，uk），状态转移），状态转移方程应当具有递推关系。方程应当具有递推关系。（5）确定阶段指标函数和最优指标函数，建立）确定阶段指标函数和最优指标函数，建立动态规划基本方程动态规划基本方程 阶段指标函数阶段指标函数vk（sk，uk）是指第）是指第k阶段的收益，阶段的收

58、益，最优指标函数最优指标函数fk（sk）是指从第）是指从第k阶段状态阶段状态sk出出发到第发到第n阶段末所获得收益的最优值，最后写阶段末所获得收益的最优值，最后写出动态规划基本方程。出动态规划基本方程。 以上五步是建立动态规划数学模型的一般步骤。以上五步是建立动态规划数学模型的一般步骤。由于动态规划模型与线性规划模型不同，动态由于动态规划模型与线性规划模型不同，动态规划模型没有统一的模式，建模时必须根据具规划模型没有统一的模式，建模时必须根据具体问题具体分析，只有通过不断实践总结，才体问题具体分析，只有通过不断实践总结，才能较好掌握建模方法与技巧。能较好掌握建模方法与技巧。 学习方法建议：学习

59、方法建议： 第一步第一步 先看问题，充分理解问题的条件、先看问题，充分理解问题的条件、情况及求解目标。情况及求解目标。 第二步第二步 结合前面讲到的理论和解题过程，结合前面讲到的理论和解题过程，考虑如何着手进行求解该问题的工作。分析考虑如何着手进行求解该问题的工作。分析针对该动态规划问题的针对该动态规划问题的“四大要素，一个方四大要素，一个方程程”这一步在开始时会感到困难，但是这一步在开始时会感到困难，但是一定要下决心去思考，在思考过程中深入理一定要下决心去思考，在思考过程中深入理解前文讲到的概念和理论。解前文讲到的概念和理论。第三步第三步 动手把求解思路整理出来，或者说，把动手把求解思路整理

60、出来，或者说，把该问题作为习题独立的来做。该问题作为习题独立的来做。第四步第四步 把自己的求解放到一边，看书中的求解把自己的求解放到一边，看书中的求解方法，要充分理解教材中的论述。方法，要充分理解教材中的论述。第五步第五步 对照自己的求解，分析成败。对照自己的求解，分析成败。 1. 1.动态规划的四大要素动态规划的四大要素 状态变量及其可能集合状态变量及其可能集合 s sk k S Sk k 决策变量及其允许集合决策变量及其允许集合 u uk k U Uk k 状态转移方程状态转移方程 s sk k+1+1= = T Tk k ( (s sk k , ,u uk k ) ) 阶段效应阶段效应