运筹学第六章 动态规划

《运筹学第六章 动态规划》由会员分享，可在线阅读，更多相关《运筹学第六章 动态规划（112页珍藏版）》请在装配图网上搜索。

1、第六章 动态规划 动态规划作为运筹学的一个重要分支是解决多阶动态规划作为运筹学的一个重要分支是解决多阶段决策过程最优化的一种非常有效的方法。段决策过程最优化的一种非常有效的方法。1951年，年，美国数学家贝尔曼（美国数学家贝尔曼（R.Bellman）等人，根据一类等人，根据一类多阶段决策问题的特点，把多阶段决策问题变换为一多阶段决策问题的特点，把多阶段决策问题变换为一系列相互联系的单阶段决策问题，然后分阶段逐个加系列相互联系的单阶段决策问题，然后分阶段逐个加以解决。贝尔曼等人在研究和解决了大量实际问题之以解决。贝尔曼等人在研究和解决了大量实际问题之后，提出了解决这类问题的后，提出了解决这类问题

2、的所谓所谓“最优性原理最优性原理”，通常称为，通常称为“贝尔曼最优化原理贝尔曼最优化原理”，从而创建了解决，从而创建了解决最优化问题的一种新的方法最优化问题的一种新的方法 动态规划动态规划（Dynamic Programming ）。）。1 动态规划的方法，在工程技术、企业管理、工农动态规划的方法，在工程技术、企业管理、工农业生产及军事等部门中有着广泛的应用，并且获得了业生产及军事等部门中有着广泛的应用，并且获得了显著的效果。在经济管理方面，动态规划可以用来解显著的效果。在经济管理方面，动态规划可以用来解决最优路径问题、资源分配问题、生产调度问题、库决最优路径问题、资源分配问题、生产调度问题、

3、库存问题、装载问题、排序问题、设备更新问题、生产存问题、装载问题、排序问题、设备更新问题、生产过程最优控制问题等等，他是现代企业管理中的一种过程最优控制问题等等，他是现代企业管理中的一种重要的决策方法。重要的决策方法。许多实际问题采用动态规划方法去处理，常比线许多实际问题采用动态规划方法去处理，常比线性规划或非线性规划更加有效。特别对于离散性的问性规划或非线性规划更加有效。特别对于离散性的问题，由于解析数学无法施展其术，而动态规划的方法题，由于解析数学无法施展其术，而动态规划的方法就成为一种非常有效的工具。就成为一种非常有效的工具。2 应特别指出的是，动态规划是解决某一类问题的应特别指出的是，

4、动态规划是解决某一类问题的一种方法，是分析问题的一种途径，而不是一种特殊一种方法，是分析问题的一种途径，而不是一种特殊算法（如线性规划是一种算法）。因而，它不象线性算法（如线性规划是一种算法）。因而，它不象线性规划那样有一个标准的数学表达式和明确定义的一组规划那样有一个标准的数学表达式和明确定义的一组规则，而必须对具体问题进行具体分析处理。因此，规则，而必须对具体问题进行具体分析处理。因此，在学习动态规划时，除了对基本概念和方法正确地理在学习动态规划时，除了对基本概念和方法正确地理解外，应以丰富的想象力去建立模型，用创造性的技解外，应以丰富的想象力去建立模型，用创造性的技巧去求解。正如贝尔曼本

5、人所说：巧去求解。正如贝尔曼本人所说：“由于动态规划的由于动态规划的最优化原理仅仅是一种基本原理，正是它的某种不确最优化原理仅仅是一种基本原理，正是它的某种不确定性为你提供了发挥你创造性思维的巨大空间定性为你提供了发挥你创造性思维的巨大空间!3 本部分我们主要研究离散决策过程，介绍动本部分我们主要研究离散决策过程，介绍动态规划的基本概念、理论和方法，在通过一些典态规划的基本概念、理论和方法，在通过一些典型的应用问题来说明它的应用。型的应用问题来说明它的应用。动态规划所研究的对象是多阶段决策问题。动态规划所研究的对象是多阶段决策问题。所谓所谓多阶段决策问题是多阶段决策问题是指一类活动过程，它指一

6、类活动过程，它可以分为若干个相互联系的阶段，在每个阶段都可以分为若干个相互联系的阶段，在每个阶段都需要作出决策。这个决策不仅决定这一阶段的效需要作出决策。这个决策不仅决定这一阶段的效益，而且决定下一阶段的初始状态。益，而且决定下一阶段的初始状态。每个阶段的决策确定以后，就得到一个决策每个阶段的决策确定以后，就得到一个决策序列，称为策略。多阶段决策问题就是求一个策序列，称为策略。多阶段决策问题就是求一个策略，使各阶段的效益的总和达到最优。略，使各阶段的效益的总和达到最优。4第一节第一节 多阶段决策问题多阶段决策问题 在生产经营活动中，某些问题决策过程可以划在生产经营活动中，某些问题决策过程可以划

7、分为若干相互联系的阶段，每个阶段需要做出决策，分为若干相互联系的阶段，每个阶段需要做出决策，从而使整个过程取得最优。当每个阶段的决策确定从而使整个过程取得最优。当每个阶段的决策确定以后，全部过程的决策就是这些阶段决策所组成的以后，全部过程的决策就是这些阶段决策所组成的一个决策序列，所以多阶段决策问题也称为序贯决一个决策序列，所以多阶段决策问题也称为序贯决策问题。策问题。动态规划方法与动态规划方法与“时间时间”关系很密切，随着时关系很密切，随着时间过程的发展而决定各时段的决策，产生一个决策间过程的发展而决定各时段的决策，产生一个决策序列，这就是序列，这就是“动态动态”的意思。然而它也可以处理的意

8、思。然而它也可以处理与时间无关的静态问题，只要在问题中人为地引入与时间无关的静态问题，只要在问题中人为地引入“时段时段”因素，就可以将其转化为一个多阶段决策因素，就可以将其转化为一个多阶段决策问题。在本章中将介绍这种处理方法。问题。在本章中将介绍这种处理方法。5 动态规划求解的多阶段决策问题的特点动态规划求解的多阶段决策问题的特点 通通常常多多阶阶段段决决策策过过程程的的发发展展是是通通过过状状态态的的一一系系列列变变换换来来实实现现的的。一一般般情情况况下下，系系统统在在某某个个阶阶段段的的状状态态转转移移除除与与本本阶阶段段的的状状态态和和决决策策有有关关外外，还还可可能能与与系系统统过过

9、去去经经历历的的状状态态和和决决策策有有关关。因因此此，问问题题的的求求解解就就比比较较困困难难复复杂杂。而而适适合合于于用用动动态态规规划划方方法法求求解解的的只只是是一一类类特特殊殊的的多多阶阶段段决决策策问问题题，即即具具有有“无无后后效效性性”的的多多阶阶段段决决策策过过程程。所所谓谓无无后后效效性性，又又称称马马尔尔柯柯夫夫性性，是是指指系系统统从从某某个个阶阶段段往往后后的的发发展展，仅仅由由本本阶阶段段所所处处的的状状态态及及其其往往后后的的决决策策所所决决定定，与与系系统统以以前前经经历历的的状状态态和和决决策策(历史历史)无关。无关。625112141061041311123

10、96581052C1C3D1AB1B3B2D2EC2 为了说明动态规划的基本思想方法和特点，以下图所示为例，讨论求最短路问题的方法。求从A到E的最短路径7 第第一一种种方方法法称称做做全全枚枚举举法法或或穷穷举举法法。它它的的基基本本思思想想是是列列举举出出所所有有可可能能发发生生的的方方案案和和结结果果，再再对对它它们们一一一一进进行行比比较较，求求出出最最优优方方案案。这这里里从从A到到E的的路路程程可可以以分分为为4个个阶阶段段。第第一一、二二阶阶段段的的走走法法有有三三种种，第第三三阶阶段段的的走走法法有有两两种种，第第四四段段的的走走法法仅仅一一种种，因因此此共共有有332118条条

11、可可能能的的路路线线，分分别别算算出出各各条条路路线线的的距距离离，最最后后进进行行比比较较，可可知知最最优优路路线线是是AB2 C1 D1 E,最短距离是最短距离是198 显显然然，当当组组成成交交通通网网络络的的节节点点很很多多时时，用用穷穷举举法法求求最最优优路路线线的的计计算算工工作作量量将将会会十十分分庞庞大大，而而且其中包含着许多重复计算且其中包含着许多重复计算 第第二二种种方方法法即即所所谓谓“局局部部最最优优路路径径”法法，是是说说某某人人从从A出出发发，他他并并不不顾顾及及全全线线是是否否最最短短，只只是是选选择择当当前前最最短短途途径径，“逢逢近近便便走走”，错错误误地地以

12、以为为局局部部最最优优会会致致整整体体最最优优，在在这这种种想想法法指指导导下下，所所取取决决策策必必是是AB2 C1 D1 E，全全程程长长度度是是25；显然，这种方法的结果常是错误的；显然，这种方法的结果常是错误的9 第第三三种种方方法法是是动动态态规规划划方方法法。动动态态规规划划方方法法寻寻求求该该最最短短路路问问题题的的基基本本思思想想是是，如如果果A=S1 S2 Sk Sn E是是A到到E的的最最短短路路，则则Sk到到E的最短路一定是的最短路一定是Sk Sn E。首首先先将将问问题题划划分分为为4个个阶阶段段，每每次次的的选选择择总总是是综综合合后后继继过过程程的的一一并并最最优优

13、进进行行考考虑虑，在在各各段段所所有有可可能能状状态态的的最最优优后后继继过过程程都都已已求求得得的的情情况况下，全程的最优路线便也随之得到。下，全程的最优路线便也随之得到。为为了了找找出出所所有有可可能能状状态态的的最最优优后后继继过过程程，动动态态规规划划方方法法总总是是从从过过程程的的最最后后阶阶段段开开始始考考虑虑，然然后后逆逆着着实实际际过过程程发发展展的的顺顺序序，逐逐段段向向前前递递推推计算直至始点。计算直至始点。102511214106104131112396581052C1C3D1AB1B3B2D2EC2f5(E)=011251121410610413111239658105

14、2C1C3D1AB1B3B2D2EC2f4(D1)=5f5(E)=0122511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f4(D1)=5132511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C1)=8f4(D1)=5142511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C2)=7f4(D1)=5f3(C1)=815251121410610413111239658105

15、2C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f3(C1)=8f3(C2)=7162511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B1)=20f3(C2)=7f3(C1)=8172511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B2)=14f3(C2)=7f3(C1)=8f2(B1)=2118251121410610

16、4131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f2(B1)=21f2(B2)=14192511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=21202511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E

17、)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=21状态 最优决策 状态 最优决策 状态 最优决策 状态 最优决策 状态A （A，B2）B2212511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=21状态 最优决策 状态 最优决策 状态 最优决策 状态 最优决策 状态A （A，B2）B2 （B2，C1）C1

18、222511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=21状态 最优决策 状态 最优决策 状态 最优决策 状态 最优决策 状态A （A，B2）B2 （B2，C1）C1 （C1，D1）D1232511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8

19、f1(A)=19f2(B2)=14f2(B1)=21状态 最优决策 状态 最优决策 状态 最优决策 状态 最优决策 状态A （A，B2）B2 （B2，C1）C1 （C1，D1）D1 （D1，E）E从A到E的最短路径为19，路线为AB 2C1 D1 E 24 综综上上所所述述可可见见，全全枚枚举举法法虽虽可可找找出出最最优优方方案案，但但不不是是个个好好算算法法，局局部部最最优优法法则则完完全全是是个个错错误误方方法法，只只有有动动态态规规划划方方法法属属较较科科学学有有效效的的算算法法。它它的的基基本本思思想想是是，把把一一个个比比较较复复杂杂的的问问题题分分解解为为一一系系列列同同类类型型的

20、的更更易易求求解解的的子子问问题题，便便于于应应用用计计算算机机。整整个个求求解解过过程程分分为为两两个个阶阶段段，先先按按整整体体最最优优的的思思想想逆逆序序地地求求出出各各个个子子问问题题中中所所有有可可能能状状态态的的最最优优决决策策与与最最优优路路线线值值，然然后后再再顺顺序序地地求求出出整整个个问问题题的的最最优优策策略略和和最最优优路路线线。计计算算过过程程中中，系系统统地地删删去去了了所所有有中中间间非非最最优优的的方方案案组组合合，从从而而使使计计算工作量比穷举法大为减少。算工作量比穷举法大为减少。25第二节第二节 动态规划的基本概念和动态规划的基本概念和基本原理基本原理多阶段

21、决策过程：多阶段决策过程：整个决策过程可按时间或空间顺序分解成整个决策过程可按时间或空间顺序分解成若干若干相互联系相互联系的阶段，每一阶段都需作出决策，的阶段，每一阶段都需作出决策，全部过程的决策是一个决策序列。全部过程的决策是一个决策序列。多阶段决策过程最优化的目标：多阶段决策过程最优化的目标：达到整个活动过程的总体效果最优，而非达到整个活动过程的总体效果最优，而非各单个阶段最优的简单总和。各单个阶段最优的简单总和。使使用用动动态态规规划划方方法法解解决决多多阶阶段段决决策策问问题题，首首先先要要将将实实际际问问题题写写成成动动态态规规划划模模型型，同同时时也也为为了了今今后后叙叙述述和和讨

22、讨论论方方便便，这这里里需需要要对对动动态态规规划的下述一些基本术语进一步加以说明和定义：划的下述一些基本术语进一步加以说明和定义：261、阶段（阶段（stage）为为了了便便于于求求解解和和表表示示决决策策过过程程的的发发展展顺顺序序，而而把把所所给给问问题题恰恰当当地地划划分分为为若若干干个个相相互互联联系系又又有有区区别别的的子子问问题题，称称之之为为多多段段决决策策问问题题的的阶阶段段。一一个个阶阶段段，就就是是需需要要作作出出一一个个决决策策的的子子问问题题，通通常常，阶阶段段是是按按决决策策进进行行的的时时间间顺顺序序或或空空间间特特征征上上先先后后顺顺序序划划分分的的。用用以以描

23、描述述阶阶段段的的变变量量叫叫作作阶阶段段变变量量，一一般般以以k表表示示阶阶段段变变量量阶阶段段数数等等于于多多段段决决策策过过程程从从开开始始到到结结束束所所需需作作出出决决策策的的数数目目，例例如如上上面面的的最最短短路路问问题题就就是是一个四阶段决策过程。一个四阶段决策过程。272、状态（状态（state）每个阶段开始时过程所处的自然状况或客观条每个阶段开始时过程所处的自然状况或客观条件。件。反映状态变化的量叫做状态变量，它可以用反映状态变化的量叫做状态变量，它可以用一个数，一组数或一向量来描述，一个数，一组数或一向量来描述，。状态变量必。状态变量必须包含在给定的阶段上确定全部允许决策

24、所需要须包含在给定的阶段上确定全部允许决策所需要的信息。的信息。它应能描述过程的特征并具有它应能描述过程的特征并具有“无后效无后效性性”，即当前阶段状态给定时，这个阶段以后过，即当前阶段状态给定时，这个阶段以后过程的演变与该阶段以前各阶段的状态无关。用程的演变与该阶段以前各阶段的状态无关。用sk表示状态变量表示状态变量（state variable）。）。28 一一般般状状态态变变量量的的取取值值有有一一定定的的范范围围或或允允许许集集合合，称称为为可可能能状状态态集集（set of admissible states）。可可能能状状态态集集实实际际上上是是关关于于状状态态的的约约束束条条件件

25、。通通常常可可能能状状态态集集用用相相应应阶阶段段状状态态sk的的大大写写字字母母Sk表表示示，可可能能状状态态集集可可以以是是一一离离散散取取值值的的集集合合，也也可可以以为为一一连连续续的的取取值值区区间间，视视具具体体问问题题而而定定例例如如上上面面的的最最短短路路问问题题中中，第第一一阶阶段段状状态态为为A，状状态态变变量量s1的的状状态态集集合合S1=A；第第二二阶阶段段则则有有三三个个状状态态：B1,B2,B3,状状态态变变量量s2的的状状态态集集合合S2=B1,B2,B3 .293、决策（决策（decision）当一个阶段的状态确定后，可以作出不同的当一个阶段的状态确定后，可以作

26、出不同的决定决定或选择或选择，从而演变到下一阶段的某个状态，这种决定，从而演变到下一阶段的某个状态，这种决定或选择称为决策。或选择称为决策。用以描述决策变化的量称之决策变量用以描述决策变化的量称之决策变量（decision variable）。和状态变量一样，决策变量可以用一个。和状态变量一样，决策变量可以用一个数，一组数或一向量来描述，由于各阶段的决策取决数，一组数或一向量来描述，由于各阶段的决策取决于状态变量于状态变量sk，所以用，所以用 uk(sk)，表示阶段，表示阶段k的状态为的状态为sk时的决策变量。时的决策变量。决策变量的取值往往也有一定的允许范围，称之决策变量的取值往往也有一定的

27、允许范围，称之允许决策集合允许决策集合（set of admissible decision）。）。决策变决策变量量uk(sk)的允许决策集用的允许决策集用Uk(sk)表示表示,允许决策集合实允许决策集合实际是决策的约束条件。际是决策的约束条件。30 4、策略（策略（policy）一组有序的一组有序的决策序列决策序列构成一个策略，从第构成一个策略，从第k阶阶段至第段至第n阶段的一个策略称为阶段的一个策略称为k后部后部子策略记为子策略记为 pk,n(sk)=uk，uk+1，un，当当k=1时的时的k部子策部子策略称为全过程策略，简称策略，记为略称为全过程策略，简称策略，记为p1,n(s1)。在实

28、际问题中，由于在各个阶段可供选择的决在实际问题中，由于在各个阶段可供选择的决策有许多个，因此，它们的不同组合就构成了许多策有许多个，因此，它们的不同组合就构成了许多可供选择的决策序列可供选择的决策序列(策略策略)，由它们组成的集合，由它们组成的集合，称之允许策略集合，记作称之允许策略集合，记作P1,n，从允许策略集中，从允许策略集中，找出具有最优效果的策略称为最优策略。找出具有最优效果的策略称为最优策略。315、状态转移方程（状态转移方程（equation of state transition）反映前后反映前后阶段状态之间关系的方程称为阶段状态之间关系的方程称为状状态转移方程。在确定型态转移

29、方程。在确定型多阶段决策过程中，多阶段决策过程中，一旦某阶段的状态和决策为已知，下一阶段一旦某阶段的状态和决策为已知，下一阶段的的 状态便完全确定，用状态便完全确定，用状态转移方程反映这状态转移方程反映这种状态间的种状态间的演变规律演变规律，记作：，记作：有些问题的状态转移方程不一定存在数学有些问题的状态转移方程不一定存在数学表达式，但是它们的状态转移，还是有一定规表达式，但是它们的状态转移，还是有一定规律可循的。律可循的。326、阶段指标值（阶段指标值（objective value in a stage）阶段指标值是第阶段指标值是第k阶段的状态为阶段的状态为sk和采取决策和采取决策uk时的

30、效益，通常表示为时的效益，通常表示为 dk(sk，uk)。对对不不同同问问题题，阶阶段段指指标标值值可可以以是是诸诸如如费费用用、成成本本、产产值值、利利润润、产产量量、耗耗量量、距距离离、时时间间，等等等等。例例如如上上面面的的最最短短路路问问题题中中，如如果果第第二二阶阶段段地地状状态态为为B2,采采取取决决策策是是由由B2到到达达C1,则则阶阶段段指指标标值为值为6。337、指标函数（指标函数（objective function）衡量在选定某策略时，其优劣的数量指标。衡量在选定某策略时，其优劣的数量指标。定义在整个过程（定义在整个过程（1到到n阶段）上的指标函数阶段）上的指标函数记为：

31、记为：V1,n（s1，u1，s2，sn，un），），定义在定义在后部子后部子过程过程（k到到n阶段）上的指标函阶段）上的指标函数记为：数记为：Vk,n（sk，uk，sn，un）。）。Vk,n（sk，uk，sn，un）表示第表示第k阶段处于阶段处于sk状态且所作决策为状态且所作决策为uk,uk+1,un时的决策效果。时的决策效果。由此可见，由此可见，Vk,n（sk，uk，sn，un）不仅不仅跟当前状态跟当前状态sk有关，还跟该子过程策略有关，还跟该子过程策略pk,n(sk)有有关，因此它是关，因此它是sk和和pk,n(sk)的函数，因此它可的函数，因此它可简记简记为：为：Vk,n（sk，pk,n

32、）34 指指标标函函数数Vk,n(sk,pk,n)通通常常是是描描述述所所实实现现的的全全过过程程或或k后后部部子子过过程程效效果果优优劣劣的的数数量量指指标标，它它是是由由各各阶阶段段的的阶阶段段指指标标函函数数dk(sk,uk)累累积积形形成成的的，适适于于用用动动态态规规划划求求解解的的问问题题的的指指标标函函数数，必必须须具具有有关关于于阶阶段段指指标标的的可可分分离离形形式式对对于于后后部部子子过过程程的指标函数可以表示为：的指标函数可以表示为：式中，式中，表示某种运算，可以是加、减、乘、表示某种运算，可以是加、减、乘、除、开方等。除、开方等。35 总总之之，具具体体问问题题的的目目

33、标标函函数数表表达达形形式式需需要要视视具体问题而定。具体问题而定。多阶段决策问题中，常见的目标函数形式之一多阶段决策问题中，常见的目标函数形式之一是取各阶段效应之和的形式，即是取各阶段效应之和的形式，即:有些问题，如系统可靠性问题，其目标函数是有些问题，如系统可靠性问题，其目标函数是取各阶段效应的连乘积形式，如：取各阶段效应的连乘积形式，如：368、最优指标函数（最优指标函数（optimal value function）指标函数的最优值称为最优指标函数，记为指标函数的最优值称为最优指标函数，记为fk(sk)，它表示，它表示从第从第k阶段阶段状态状态 sk 出发，采用出发，采用最最优策略优策

34、略到终止到终止状态状态时的后部子时的后部子过程指标函数值，过程指标函数值，即即式中式中opt即即optimization，根据具体问题可取，根据具体问题可取max或或min。与它相应的子策略称为在。与它相应的子策略称为在sk状态下的最状态下的最优子策略，记为优子策略，记为pk*(sk)；而构成该子策略的各；而构成该子策略的各段决策称为该过程上的最优决策，记为段决策称为该过程上的最优决策，记为 37即即 简记为简记为特别当特别当k=1时，时，f1(s1)就是问题的最优值，而就是问题的最优值，而p1*就是最优策略。例如上面的最短路问题中，就是最优策略。例如上面的最短路问题中，有唯一最优值有唯一最优

35、值f1(s1)=18，而，而就是其最优策略。就是其最优策略。38 多阶段决策问题的数学模型多阶段决策问题的数学模型 综综上上所所述述，适适于于应应用用动动态态规规划划方方法法求求解解的的一一类类多多阶阶段段决决策策问问题题，亦亦即即具具有有无无后后效效性性的的多多阶阶段段决策问题的数学模型呈以下形式决策问题的数学模型呈以下形式:39 则对上述策略中所隐含的任一状态而言，则对上述策略中所隐含的任一状态而言，第第k子过程上对应于该状态的最优策略必然子过程上对应于该状态的最优策略必然 包含在上述全过程最优策略包含在上述全过程最优策略p1*中，中，即为即为最优化原理最优化原理（贝尔曼最优化原理）（贝尔

36、曼最优化原理）作为一个全过程的最优策略具有这样的性作为一个全过程的最优策略具有这样的性质：质：对于最优策略过程中的任意状态而言，对于最优策略过程中的任意状态而言，无论其过去的状态和决策如何，余下的诸决无论其过去的状态和决策如何，余下的诸决策必构成一个最优子策略。策必构成一个最优子策略。该原理的具体解该原理的具体解释是，若某一全过程最优策略为：释是，若某一全过程最优策略为：40其中，其中，表示从状态表示从状态sk到由决策到由决策uk(sk)所决定的状态所决定的状态sk+1之之间的距离。间的距离。动态规划的基本方程动态规划的基本方程 在上面最短路问题的求解过程中，在求在上面最短路问题的求解过程中，

37、在求解的各阶段利用了第解的各阶段利用了第k阶段和第阶段和第k+1阶段的如阶段的如下递推关系：下递推关系：第三节第三节 动态规划模型的建立与求解动态规划模型的建立与求解 41 一一般般地地，对对于于n个个阶阶段段的的决决策策过过程程，假假设设只只考考虑虑指指标标函函数数是是“和和”与与“积积”的的形形式式，第第k阶阶段段和和第第k+1阶段间的递推公式可表示如下：阶段间的递推公式可表示如下：(1)当当指指标标函函数数为为下下列列“和和”的的形形式式时时，其其相相应应的基本方程为的基本方程为是边界条件。是边界条件。42 (2)当当过过程程指指标标函函数数为为下下列列“积积”的的形形式式时时,其相应的

38、基本方程为其相应的基本方程为 一般来说一般来说,要用函数基本方程逆推求解要用函数基本方程逆推求解,首先首先要有效地建立动态规划模型要有效地建立动态规划模型,然后再递推求解然后再递推求解,最最后得出结论后得出结论.然而然而,要把一个实际问题用动态规划要把一个实际问题用动态规划方法来求解方法来求解,还必须首先根据问题的要求。把它构还必须首先根据问题的要求。把它构造成动态规划模型造成动态规划模型,这是非常重要的一步。正确地这是非常重要的一步。正确地建立一个动态规划模型建立一个动态规划模型,往往问题也就解决了一大往往问题也就解决了一大半半,而一个正确的动态规划模型而一个正确的动态规划模型,应该满足哪些

39、条应该满足哪些条件呢件呢?43建立动态规划数学模型的步骤建立动态规划数学模型的步骤 1应将实际问题恰当地分割成应将实际问题恰当地分割成n个子问题个子问题(n个阶段个阶段)。通常是根据时间或空间而划分的，。通常是根据时间或空间而划分的，或者在经由静态的数学规划模型转换为动态规或者在经由静态的数学规划模型转换为动态规划模型时，常取静态规划中变量的个数划模型时，常取静态规划中变量的个数n，即，即k=n。2正确地定义状态变量正确地定义状态变量sk，使它既能正，使它既能正确地描述过程的状态，又能满足无后效性动确地描述过程的状态，又能满足无后效性动态规划中的状态与一般控制系统中和通常所说态规划中的状态与一

40、般控制系统中和通常所说的状态的概念是有所不同的，动态规划中的状的状态的概念是有所不同的，动态规划中的状态变量必须具备以下三个特征：态变量必须具备以下三个特征：44 (1)要能够正确地描述受控过程的变化特征。要能够正确地描述受控过程的变化特征。(2)要满足无后效性。即如果在某个阶段状态要满足无后效性。即如果在某个阶段状态已经给定，那么在该阶段以后，过程的发展不受已经给定，那么在该阶段以后，过程的发展不受前面各段状态的影响，如果所选的变量不具备无前面各段状态的影响，如果所选的变量不具备无后效性，就不能作为状态变量来构造动态规划的后效性，就不能作为状态变量来构造动态规划的模型。模型。(3)要满足可知

41、性。即所规定的各段状态变量要满足可知性。即所规定的各段状态变量的值，可以直接或间接地测算得到。一般在动态的值，可以直接或间接地测算得到。一般在动态规划模型中，状态变量大都选取那种可以进行累规划模型中，状态变量大都选取那种可以进行累计的量。此外，在与静态规划模型的对应关系上，计的量。此外，在与静态规划模型的对应关系上，通常根据经验，线性与非线性规划中约束条件的通常根据经验，线性与非线性规划中约束条件的个数，相当于动态规划中状态变量个数，相当于动态规划中状态变量sk的维数而的维数而前者约束条件所表示的内容，常就是状态变量前者约束条件所表示的内容，常就是状态变量sk所代表的内容。所代表的内容。45

42、3正正确确地地定定义义决决策策变变量量及及各各阶阶段段的的允允许许决决策策集集合合Uk(sk)，根根据据经经验验，一一般般将将问问题题中中待待求求的的量量，选选作作动动态态规规划划模模型型中中的的决决策策变变量量。或或者者在在把把静静态态规规划划模模型型(如如线线性性与与非非线线性性规规划划)转转换换为为动动态态规规划划模模型型时时，常常取取前前者者的的变变量量xj为为后后者者的的决策变量决策变量uk。4.能能够够正正确确地地写写出出状状态态转转移移方方程程，至至少少要要能能正正确确反反映映状状态态转转移移规规律律。如如果果给给定定第第k阶阶段段状状态态变变量量sk的的值值，则则该该段段的的决

43、决策策变变量量uk一一经经确确定定，第第k+1段段的的状状态态变变量量sk+1的的值值也也就就完完全全确确定定，即即有有sk+1=Tk(sk,uk)46 5根根据据题题意意,正正确确地地构构造造出出目目标标与与变变量量的的函函数数关系关系目标函数目标函数，目标函数应满足下列性质：，目标函数应满足下列性质：(1)可可分分性性，即即对对于于所所有有k后后部部子子过过程程，其其目目标标函函数数仅仅取取决决于于状状态态sk及及其其以以后后的的决决策策 uk,uk+1,un,就就是是说说它它是是定定义义在在全全过过程程和和所所有有后后部子过程上的数量函数。部子过程上的数量函数。(2)要满足递推关系，即要

44、满足递推关系，即 (3)函函数数 对对其其变变元元Vk+1,n来来说说要严格单调。要严格单调。47 6写出动态规划函数基本方程写出动态规划函数基本方程例如常见的指标函数是取各段指标和的形式例如常见的指标函数是取各段指标和的形式 其其中中 表表示示第第i阶阶段段的的指指标标，它它显显然然是是满足上述三个性质的。所以上式可以写成满足上述三个性质的。所以上式可以写成：48第五节第五节 动态规划在经济管理中的应用动态规划在经济管理中的应用 一、一、资源分配问题资源分配问题 假假设设有一种有一种资资源，数量源，数量为为a，将其分配，将其分配给给n个个使用者，分配使用者，分配给给第第i个使用者数量个使用者

45、数量xi时时，相，相应应的收的收益益为为gi（xi），），问问如何分配使得如何分配使得总总收入最大？收入最大？这这就就是一是一维资维资源分配源分配问题问题，该问题该问题的数学模型的数学模型为为：（6.23）49式（式（6.23）是一个静态规划问题，应用动态规划）是一个静态规划问题，应用动态规划方法求解时人为赋予时间概念，将其看作是一个方法求解时人为赋予时间概念，将其看作是一个多阶段决策问题。多阶段决策问题。按变量个数划分阶段，按变量个数划分阶段，k=1，2，n；设决策变量设决策变量uk=xk，表示分配给第，表示分配给第k个使用者的资个使用者的资源数量；源数量；设状态变量为设状态变量为sk，表示

46、分配给第，表示分配给第k个至第个至第n个使个使用者的总资源数量；用者的总资源数量；状态转移方程：状态转移方程：sk+1=skxk，其中，其中s1=a；允许决策集合：允许决策集合：Dk(sk)=xk|0 xksk阶段指标函数：阶段指标函数：vk(sk，uk)=gk(xk)表示分配给第表示分配给第k个使用者数量个使用者数量xk时的收益；时的收益；50最最优优指指标标函数函数fk(sk)表示以数量表示以数量sk的的资资源分配源分配给给第第k个至第个至第n个使用者所得到的最大收益，个使用者所得到的最大收益，则动态则动态规规划基本方程划基本方程为为：由后向前逐段由后向前逐段递递推，推，f1(a)即即为为

47、所求所求问题问题的最大收益。的最大收益。51例例7 某公司打算在某公司打算在3个不同的地区个不同的地区设设置置4个个销销售售点，根据市点，根据市场场部部门门估估计计，在不同地区，在不同地区设设置不同数置不同数量的量的销销售点每月可得到的利售点每月可得到的利润润如表如表6.4所示。所示。试试问问在各地区如何在各地区如何设设置置销销售点可使每月售点可使每月总总利利润润最大。最大。表表6.4 利利润值润值地区地区销销售点售点0123412300016121025171430211632221752解：解：如前所述，建立如前所述，建立动态规动态规划数学模型：划数学模型：将将问题问题分分为为3个个阶阶段

48、，段，k=1，2，3；决策决策变变量量xk表示分配表示分配给给第第k个地区的个地区的销销售点数；售点数；状状态变态变量量为为sk表示分配表示分配给给第第k个至第个至第3个地区的个地区的销销售点售点总总数；数；状状态转态转移方程：移方程：sk+1=skxk，其中，其中s1=4；允允许许决策集合：决策集合：Dk（sk）=xk|0 xksk阶阶段指段指标标函数：函数：gk（xk）表示）表示xk个个销销售点分配售点分配给给第第k个地区所个地区所获获得的利得的利润润；最最优优指指标标函数函数fk（sk）表示将数量）表示将数量为为sk的的销销售点售点分配分配给给第第k个至第个至第3个地区所得到的最大利个地

49、区所得到的最大利润润，动动态规态规划基本方程划基本方程为为：53数数值计值计算如表所示。算如表所示。表表6.5 k=3时计时计算算结结果果fx3s3g3（x3）f3(s3)x3*012340123400000101010101414141616170101416170123454表表6.6 k=2时计时计算算结结果果g2(x2)+f3(s2x2)f2(s2)x2*012340123400+100+140+160+1712+012+1012+1412+1617+017+1017+1421+021+10 22+001222273101122,3fx3s3fx3s3表表6.7 k=1时计时计算算结结

50、果果g1(x1)+f2(s1x1)f1(s1)x1*0123440+3116+2725+22 30+12 32+047255 所以最优解为：所以最优解为：x1*=2，x2*=1，x3*=1，f1(4)=47，即在第，即在第1个地区设置个地区设置2个销售点，第个销售点，第2个个地区设置地区设置1个销售点，第个销售点，第3个地区设置个地区设置1个销售点，个销售点，每月可获利润每月可获利润47。这个例子是决策变量取离散值的一类分配这个例子是决策变量取离散值的一类分配问题，在实际问题中，相类似的问题还有设备或问题，在实际问题中，相类似的问题还有设备或人力资源的分配问题等。在资源分配问题中，还人力资源的

51、分配问题等。在资源分配问题中，还有一种决策变量为连续变量的资源分配问题，见有一种决策变量为连续变量的资源分配问题，见下面例子。下面例子。56例例8 机器机器负负荷荷问题问题 某种机器可在高低两种不同的某种机器可在高低两种不同的负负荷下荷下进进行行生生产产，设设机器在高机器在高负负荷下生荷下生产产的的产产量（件）函量（件）函数数为为g1=8x，其中，其中x为投入高负荷生产的机器数为投入高负荷生产的机器数量，年度完好率量，年度完好率=0.7（年底的完好设备数等（年底的完好设备数等于年初完好设备数的于年初完好设备数的70%）；在低负荷下生产）；在低负荷下生产的产量（件）函数为的产量（件）函数为g2=

52、5y，其中，其中y为投入低为投入低负荷生产的机器数量，年度完好率负荷生产的机器数量，年度完好率=0.9。假定。假定开始生产时完好的机器数量为开始生产时完好的机器数量为1000台，试问每台，试问每年应如何安排机器在高、低负荷下的生产，才年应如何安排机器在高、低负荷下的生产，才能使能使5年生产的产品总量最多？年生产的产品总量最多？57解：解：设阶设阶段段k表示年度（表示年度（k=1,2,3,4,5）；状）；状态变态变量量Sk为为第第k年度初年度初拥拥有的完好机器数量（同有的完好机器数量（同时时也是第也是第k-1年度末年度末时时的完好机器数量）。决策的完好机器数量）。决策变变量量xk为为第第k年年度

53、分配高度分配高负负荷下生荷下生产产的机器数量，于是的机器数量，于是Sk-xk为该为该年年度分配在低度分配在低负负荷下生荷下生产产的机器数量。的机器数量。这这里的里的Sk和和xk均均为连续变为连续变量，它量，它们们的非整数的非整数值值可以可以这样这样理解：如理解：如Sk=0.6就表示一台机器在第就表示一台机器在第k年度中正常工作年度中正常工作时间时间只占全部只占全部时间时间的的60%；xk=0.3就表示一台机器在第就表示一台机器在第k年度中只有年度中只有30%的工作的工作时间时间在高在高负负荷下运荷下运转转。状。状态转态转移方程移方程为为：58允允许许决策集合：决策集合：设阶设阶段指段指标标Qk

54、(Sk,xk)为为第第k年度的年度的产产量，量，则则：过过程指程指标标是是阶阶段指段指标标的和，即：的和，即：令最令最优值优值函数函数fk(Sk)表示从表示从资资源量源量Sk出出发发，采取最，采取最优优子策略所生子策略所生产产的的产产品品总总量，因而有逆推关系式：量，因而有逆推关系式：边边界条件界条件f6(S6)=0。59当当k=5时时：因因f5(S5)是关于是关于x5的的单调递单调递增函数，故取增函数，故取x5*=S5，相相应应有有f5(S5)=8 S5。当当k=4时时：60因因f4(S4)是关于是关于x4的的单调递单调递增函数，故取增函数，故取x4*=S4，相相应应有有f4(S4)=13.

55、6 S4；依次；依次类类推，可求得：推，可求得：当当k=3时时：x3*=S3，f3(S3)=17.5 S3当当k=2时时：x2*=0，f2(S2)=20.8 S2当当k=1时时：x1*=0，f1(S1=1000)=23.7 S1=23700计计算算结结果表明最果表明最优优策略策略为为：x1*=0，x2*=0，x3*=S3，x4*=S4，x5*=S5；即前两年将全部；即前两年将全部设备设备都投入都投入低低负负荷生荷生产产，后三年将全部，后三年将全部设备设备都投入高都投入高负负荷生荷生产产，这样这样可以使可以使5年的年的总产总产量最大，最大量最大，最大产产量是量是23700件。件。有了上述最有了上

56、述最优优策略，各策略，各阶阶段的状段的状态态也就随之确定也就随之确定了，即按了，即按阶阶段段顺顺序序计计算出各年年初的完好算出各年年初的完好设备设备数数量。量。61上面所上面所讨论讨论的的过过程始端状程始端状态态S1是固定的，而是固定的，而终终端状端状态态S6是自由的，是自由的，实现实现的目的目标标函数是函数是5年的年的总总产产量最高。量最高。62二、二、生产与存贮问题生产与存贮问题 在生产和经营管理中，经常遇到要合在生产和经营管理中，经常遇到要合理地安排生产（或购买）与库存问题，达到理地安排生产（或购买）与库存问题，达到既要满足社会的需要，又要尽量降低成本费既要满足社会的需要，又要尽量降低成

57、本费用，因此，正确制定生产（后采购）策略，用，因此，正确制定生产（后采购）策略，确定不同时期的生产量（或采购量）和库存确定不同时期的生产量（或采购量）和库存量，以使总的生产成本费和库存费用之和最量，以使总的生产成本费和库存费用之和最小，这就是生产与存贮问题的最有目标小，这就是生产与存贮问题的最有目标631.生产计划问题生产计划问题例例9 （生产（生产库存问题）库存问题）某工厂要对一种产品制定今后四个时期的某工厂要对一种产品制定今后四个时期的生产计划，据估计在今后四个时期内，市场生产计划，据估计在今后四个时期内，市场对该产品的需求量分别为对该产品的需求量分别为2，3，2，4单位，单位，假设每批产

58、品固定成本为假设每批产品固定成本为3千元，若不生产为千元，若不生产为0，每单位产品成本为，每单位产品成本为1千元，每个时期最大千元，每个时期最大生产能力不超过生产能力不超过6个单位，每期期末未出售产个单位，每期期末未出售产品，每单位需付存贮费品，每单位需付存贮费0.5千元，假定第千元，假定第1期期初和第初和第4期末库存量均为期末库存量均为0，问该厂如何安排，问该厂如何安排生产与库存，可在满足市场需求的前提下总生产与库存，可在满足市场需求的前提下总成本最小。成本最小。64解解:以每个以每个时时期作期作为为一个一个阶阶段，段，该问题该问题分分为为4个个阶阶 段，段，k=1，2，3，4；决策决策变变

59、量量xk表示第表示第k阶阶段生段生产产的的产产品数；品数；状状态变态变量量sk表示第表示第k阶阶段初的段初的库库存量；存量；以以dk表示第表示第k阶阶段的需求，段的需求，则则状状态转态转移方程：移方程：sk+1=sk+xkdk；k=4，3，2，1由于期初及期末由于期初及期末库库存存为为0，所以，所以s1=0，s5=0；允允许许决策集合决策集合Dk（sk）的确定：当）的确定：当skdk时时，xk可可以以为为0，当，当skdk时时，至少，至少应应生生产产dksk，故，故xk的下限的下限为为max（0，dksk）每期最大生）每期最大生产产能力能力为为6，xk最大最大不超不超过过6，由于期末，由于期末

60、库库存存为为0，xk还应还应小于本期至小于本期至4期期需求之和减去本期的需求之和减去本期的库库存量，存量，65所以所以xk的上限的上限为为故有：故有：阶阶段指段指标标函数函数rk（sk，xk）表示第）表示第k期的生期的生产费产费用用 与存与存贮费贮费用之和：用之和：最最优优指指标标函数函数fk（sk）表示第）表示第k期期库库存存为为sk到第到第4期末的生期末的生产产与存与存贮贮最低最低费费用，用，动态规动态规划基本方程划基本方程为为：66先求出各状先求出各状态态允允许许状状态态集合及允集合及允许许决策集合，如决策集合，如表表6.8所示。所示。表表6.8 状状态态允允许许状状态态集合及允集合及允

61、许许决策集合决策集合s10D1(s1)2,3,4,5,6s201234D2(s2)3,4,5,62,3,4,5,61,2,3,4,5,60,1,2,3,4,5,60,1,2,3,4,5s30123456D3(s3)2,3,4,5,61,2,3,4,50,1,2,3,40,1,2,30,1,20,10s401234D4(s4)4321067由基本方程由基本方程计计算各算各阶阶段策略，段策略，结结果如下表所示。果如下表所示。表表6.9 k=4时计时计算算结结果果s4x4r4(s4,x4)f4(s4)x4*012344321076.565.527*6.5*6*5.5*2*4*3*2*1*0*68表表

62、6.10 k=3时计时计算算结结果果 x3s3r3（s3,x3）+f4(s4)f3(s3)x3*012345601234561+71.5+6.52+62.5+5.53+24.5+75+6.55.5+66+5.56.5+25+75.5+6.56+66.5+5.57+26+6.56.5+67+5.57.5+27+67.5+5.58+28+5.58.5+29+21110.588885650000069表表6.11 k=2时计时计算算结结果果x2s2r2（s2,x2）+f3(s3)f2(s2)x2*0123456012341.5+112+10.55+115.5+10.56+85.5+116+10.56

63、.5+87+86+116.5+10.57+87.5+88+87+10.57.5+88+88.5+89+88+88.5+89+89.5+810+59+89.5+810+810.5+51615.51512.585430070表表6.12 k=1时计时计算算结结果果 x1s1r1（s1,x1）+f2(s2)f1(s1)x1*2345605+166+15.57+158+12.59+12.520.55逆向追踪可得：逆向追踪可得：x1*=5，s2=3，x2*=0，s3=0，x3*=6，s4=4，x4*=0，即第，即第1时时期生期生产产5个个单单位，位，第第3时时期生期生产产6个个单单位，第位，第2，4时时

64、期不生期不生产产，可使，可使总费总费用最小，最小用最小，最小费费用用为为20.5千元。千元。71例例11某鞋店某鞋店销销售一种雪地防潮鞋，以往的售一种雪地防潮鞋，以往的销销售售经历经历表明，此种鞋的表明，此种鞋的销销售季售季节节是从是从10月月1日至日至3月月31日。下个日。下个销销售季售季节节各月的需求各月的需求预测值预测值如表如表6.14所示。所示。表表6.14 需求需求预测值预测值 (单单位：双位：双)月份月份101112123需求需求402030403020该该鞋店的此种鞋完全从外部生鞋店的此种鞋完全从外部生产产商商进货进货，进货进货价每双价每双4 4美元。美元。进货进货批量的基本批量

65、的基本单单位是箱，每箱位是箱，每箱1010双。由于存双。由于存贮贮空空间间的限制，每次的限制，每次进货进货不超不超过过5 5箱。箱。对应对应不同的不同的订货订货批量，批量，进进价享受一定的数价享受一定的数量折扣，具体数量折扣，具体数值值如表如表6.156.15所示。所示。72表表6.15 数量折扣数数量折扣数值值表表进货进货批量批量1箱箱2箱箱3箱箱4箱箱5箱箱数量折扣数量折扣4%5%10%20%25%假假设设需求是按一定速度均匀需求是按一定速度均匀发发生的，生的，订货订货不不需需时间时间，但，但订货订货只能在月初只能在月初办办理一次，每次理一次，每次订订货货的采的采购费购费（与采（与采购购数

66、量无关）数量无关）为为10美元。月美元。月存存贮费贮费按每月月底鞋的存量按每月月底鞋的存量计计，每双，每双0.2美元。美元。由于由于订货订货不需不需时间时间，所以，所以销销售季售季节节外的其他月外的其他月份的存份的存贮贮量量为为“0”。试试确定最佳的确定最佳的进货进货方案，方案，以使以使总总的的销销售售费费用最小。用最小。73解：解：阶阶段：将段：将销销售季售季节节6个月中的每一个月作个月中的每一个月作为为一一个个阶阶段，即段，即k=1,2,6；状状态变态变量：第量：第k阶阶段的状段的状态变态变量量Sk代表第代表第k个月初鞋个月初鞋的存量；的存量；决策决策变变量：决策量：决策变变量量xk代表第代表第k个月的采个月的采购购批量；批量；状状态转态转移律：移律：sk+1=sk+xkdk（dk是第是第k个月的需求个月的需求量）；量）；边边界条件：界条件：s1=s7=0，f7(s7)=0；阶阶段指段指标标函数：函数：rk(sk,xk)代表第代表第k个月所个月所发发生的全部生的全部费费用，即与采用，即与采购购数量无关的采数量无关的采购费购费Ck、与采、与采购购数量成数量成正比的正比的购购置置费费G