第六章动态规划优秀课件.ppt

《第六章动态规划优秀课件.ppt》由会员分享，可在线阅读，更多相关《第六章动态规划优秀课件.ppt（112页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第六章动态规划1第1页，本讲稿共112页 动态规划的方法，在工程技术、企业管理、工农动态规划的方法，在工程技术、企业管理、工农业生产及军事等部门中有着广泛的应用，并且获得了显业生产及军事等部门中有着广泛的应用，并且获得了显著的效果。在经济管理方面，动态规划可以用来解决最著的效果。在经济管理方面，动态规划可以用来解决最优路径问题、资源分配问题、生产调度问题、库存问题、优路径问题、资源分配问题、生产调度问题、库存问题、装载问题、排序问题、设备更新问题、生产过程最优控装载问题、排序问题、设备更新问题、生产过程最优控制问题等等，他是现代企业管理中的一种重要的决策方制问题等等，他是现代企业管理中的一种重

2、要的决策方法。法。许多实际问题采用动态规划方法去处理，常比线性规许多实际问题采用动态规划方法去处理，常比线性规划或非线性规划更加有效。特别对于离散性的问题，由于解划或非线性规划更加有效。特别对于离散性的问题，由于解析数学无法施展其术，而动态规划的方法就成为一种非常有析数学无法施展其术，而动态规划的方法就成为一种非常有效的工具。效的工具。第2页，本讲稿共112页 应特别指出的是，动态规划是解决某一类问题的应特别指出的是，动态规划是解决某一类问题的一种方法，是分析问题的一种途径，而不是一种特殊算一种方法，是分析问题的一种途径，而不是一种特殊算法（如线性规划是一种算法）。因而，它不象线性规划法（如线

3、性规划是一种算法）。因而，它不象线性规划那样有一个标准的数学表达式和明确定义的一组规则，那样有一个标准的数学表达式和明确定义的一组规则，而必须对具体问题进行具体分析处理。因此，在学习动而必须对具体问题进行具体分析处理。因此，在学习动态规划时，除了对基本概念和方法正确地理解外，应以态规划时，除了对基本概念和方法正确地理解外，应以丰富的想象力去建立模型，用创造性的技巧去求解。正丰富的想象力去建立模型，用创造性的技巧去求解。正如贝尔曼本人所说：如贝尔曼本人所说：“由于动态规划的最优化原理仅仅由于动态规划的最优化原理仅仅是一种基本原理，正是它的某种不确定性为你提供了发是一种基本原理，正是它的某种不确定

4、性为你提供了发挥你创造性思维的巨大空间挥你创造性思维的巨大空间!第3页，本讲稿共112页 本部分我们主要研究离散决策过程，介绍动态规本部分我们主要研究离散决策过程，介绍动态规划的基本概念、理论和方法，在通过一些典型的应用划的基本概念、理论和方法，在通过一些典型的应用问题来说明它的应用。问题来说明它的应用。动态规划所研究的对象是多阶段决策问题。动态规划所研究的对象是多阶段决策问题。所谓所谓多阶段决策问题是多阶段决策问题是指一类活动过程，它可以指一类活动过程，它可以分为若干个相互联系的阶段，在每个阶段都需要作出决分为若干个相互联系的阶段，在每个阶段都需要作出决策。这个决策不仅决定这一阶段的效益，而

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

6、段的决策确定以后，全部过程的过程取得最优。当每个阶段的决策确定以后，全部过程的决策就是这些阶段决策所组成的一个决策序列，所以多阶决策就是这些阶段决策所组成的一个决策序列，所以多阶段决策问题也称为序贯决策问题。段决策问题也称为序贯决策问题。动态规划方法与动态规划方法与“时间时间”关系很密切，随着时间过程的关系很密切，随着时间过程的发展而决定各时段的决策，产生一个决策序列，这就是发展而决定各时段的决策，产生一个决策序列，这就是“动态动态”的意思。然而它也可以处理与时间无关的静态问题，的意思。然而它也可以处理与时间无关的静态问题，只要在问题中人为地引入只要在问题中人为地引入“时段时段”因素，就可以将

7、其转化因素，就可以将其转化为一个多阶段决策问题。在本章中将介绍这种处理方法。为一个多阶段决策问题。在本章中将介绍这种处理方法。第5页，本讲稿共112页 动态规划求解的多阶段决策问题的特点动态规划求解的多阶段决策问题的特点 通通常常多多阶阶段段决决策策过过程程的的发发展展是是通通过过状状态态的的一一系系列列变变换换来来实实现现的的。一一般般情情况况下下，系系统统在在某某个个阶阶段段的的状状态态转转移移除除与与本本阶阶段段的的状状态态和和决决策策有有关关外外，还还可可能能与与系系统统过过去去经经历历的的状状态态和和决决策策有有关关。因因此此，问问题题的的求求解解就就比比较较困困难难复复杂杂。而而适

8、适合合于于用用动动态态规规划划方方法法求求解解的的只只是是一一类类特特殊殊的的多多阶阶段段决决策策问问题题，即即具具有有“无无后后效效性性”的的多多阶阶段段决决策策过过程程。所所谓谓无无后后效效性性，又又称称马马尔尔柯柯夫夫性性，是是指指系系统统从从某某个个阶阶段段往往后后的的发发展展，仅仅由由本本阶阶段段所所处处的的状状态态及及其其往往后后的的决决策策所所决决定定，与系统以前经历的状态和决策与系统以前经历的状态和决策(历史历史)无关。无关。第6页，本讲稿共112页2511214106104131112396581052C1C3D1AB1B3B2D2EC2 为了说明动态规划的基本思想方法和特点

9、，以下图所示为例，讨论求最短路问题的方法。求从A到E的最短路径第7页，本讲稿共112页 第第一一种种方方法法称称做做全全枚枚举举法法或或穷穷举举法法。它它的的基基本本思思想想是是列列举举出出所所有有可可能能发发生生的的方方案案和和结结果果，再再对对它它们们一一一一进进行行比比较较，求求出出最最优优方方案案。这这里里从从A到到E的的路路程程可可以以分分为为4个个阶阶段段。第第一一、二二阶阶段段的的走走法法有有三三种种，第第三三阶阶段段的的走走法法有有两两种种，第第四四段段的的走走法法仅仅一一种种，因因此此共共有有332118条条可可能能的的路路线线，分分别别算算出出各各条条路路线线的的距距离离，

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

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

12、段所所有有可可能能状状态态的的最最优优后后继继过过程程都都已已求求得得的的情情况况下下，全全程的最优路线便也随之得到。程的最优路线便也随之得到。为为了了找找出出所所有有可可能能状状态态的的最最优优后后继继过过程程，动动态态规规划划方方法法总总是是从从过过程程的的最最后后阶阶段段开开始始考考虑虑，然然后后逆逆着着实实际际过过程发展的顺序，逐段向前递推计算直至始点。程发展的顺序，逐段向前递推计算直至始点。第10页，本讲稿共112页2511214106104131112396581052C1C3D1AB1B3B2D2EC2f5(E)=0第11页，本讲稿共112页2511214106104131112

13、396581052C1C3D1AB1B3B2D2EC2f4(D1)=5f5(E)=0第12页，本讲稿共112页2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f4(D1)=5第13页，本讲稿共112页2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C1)=8f4(D1)=5第14页，本讲稿共112页2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C2)=7f4(D

14、1)=5f3(C1)=8第15页，本讲稿共112页2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f3(C1)=8f3(C2)=7第16页，本讲稿共112页2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B1)=20f3(C2)=7f3(C1)=8第17页，本讲稿共112页2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)

15、=2f5(E)=0f3(C3)=12f4(D1)=5f2(B2)=14f3(C2)=7f3(C1)=8f2(B1)=21第18页，本讲稿共112页2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f2(B1)=21f2(B2)=14第19页，本讲稿共112页2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)

16、=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=21第20页，本讲稿共112页2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=21状态 最优决策 状态 最优决策 状态 最优决策 状态 最优决策 状态A （A，B2）B2第21页，本讲稿共112页2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C

17、3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=21状态 最优决策 状态 最优决策 状态 最优决策 状态 最优决策 状态A （A，B2）B2 （B2，C1）C1第22页，本讲稿共112页2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=21状态 最优决策 状态 最优决策 状态 最优决策 状态 最优决策 状态A （A，B

18、2）B2 （B2，C1）C1 （C1，D1）D1第23页，本讲稿共112页2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(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）D1 （D1，E）E从A到E的最短路径为19，路线为AB 2C1 D1 E 第24页，本讲稿共112页 综综上上所所述述可可见见，全全枚枚举举法

19、法虽虽可可找找出出最最优优方方案案，但但不不是是个个好好算算法法，局局部部最最优优法法则则完完全全是是个个错错误误方方法法，只只有有动动态态规规划划方方法法属属较较科科学学有有效效的的算算法法。它它的的基基本本思思想想是是，把把一一个个比比较较复复杂杂的的问问题题分分解解为为一一系系列列同同类类型型的的更更易易求求解解的的子子问问题题，便便于于应应用用计计算算机机。整整个个求求解解过过程程分分为为两两个个阶阶段段，先先按按整整体体最最优优的的思思想想逆逆序序地地求求出出各各个个子子问问题题中中所所有有可可能能状状态态的的最最优优决决策策与与最最优优路路线线值值，然然后后再再顺顺序序地地求求出出

20、整整个个问问题题的的最最优优策策略略和和最最优优路路线线。计计算算过过程程中中，系系统统地地删删去去了了所所有有中中间间非非最最优优的的方方案案组组合合，从而使计算工作量比穷举法大为减少。从而使计算工作量比穷举法大为减少。第25页，本讲稿共112页第二节第二节 动态规划的基本概念和动态规划的基本概念和基本原理基本原理多阶段决策过程：多阶段决策过程：整个决策过程可按时间或空间顺序分解成若干整个决策过程可按时间或空间顺序分解成若干相互相互联系联系的阶段，每一阶段都需作出决策，全部过程的阶段，每一阶段都需作出决策，全部过程的决策是一个决策序列。的决策是一个决策序列。多阶段决策过程最优化的目标：多阶段

21、决策过程最优化的目标：达到整个活动过程的总体效果最优，而非各达到整个活动过程的总体效果最优，而非各单个阶段最优的简单总和。单个阶段最优的简单总和。使使用用动动态态规规划划方方法法解解决决多多阶阶段段决决策策问问题题，首首先先要要将将实实际际问问题题写写成成动动态态规规划划模模型型，同同时时也也为为了了今今后后叙叙述述和和讨讨论论方方便便，这这里里需需要要对对动动态态规规划划的的下下述述一一些些基基本本术术语进一步加以说明和定义：语进一步加以说明和定义：第26页，本讲稿共112页1、阶段（阶段（stage）为为了了便便于于求求解解和和表表示示决决策策过过程程的的发发展展顺顺序序，而而把把所所给给

22、问问题题恰恰当当地地划划分分为为若若干干个个相相互互联联系系又又有有区区别别的的子子问问题题，称称之之为为多多段段决决策策问问题题的的阶阶段段。一一个个阶阶段段，就就是是需需要要作作出出一一个个决决策策的的子子问问题题，通通常常，阶阶段段是是按按决决策策进进行行的的时时间间顺顺序序或或空空间间特特征征上上先先后后顺顺序序划划分分的的。用用以以描描述述阶阶段段的的变变量量叫叫作作阶阶段段变变量量，一一般般以以k表表示示阶阶段段变变量量阶阶段段数数等等于于多多段段决决策策过过程程从从开开始始到到结结束束所所需需作作出出决决策策的的数数目目，例例如如上上面面的的最最短短路问题就是一个四阶段决策过程。

23、路问题就是一个四阶段决策过程。第27页，本讲稿共112页2、状态（状态（state）每个阶段开始时过程所处的自然状况或客观条件。每个阶段开始时过程所处的自然状况或客观条件。反映状态变化的量叫做状态变量，它可以用一个数，反映状态变化的量叫做状态变量，它可以用一个数，一组数或一向量来描述，一组数或一向量来描述，。状态变量必须包含在给定。状态变量必须包含在给定的阶段上确定全部允许决策所需要的信息。它应能描述的阶段上确定全部允许决策所需要的信息。它应能描述过程的特征并具有过程的特征并具有“无后效性无后效性”，即当前阶段状态给，即当前阶段状态给定时，这个阶段以后过程的演变与该阶段以前各阶定时，这个阶段以

24、后过程的演变与该阶段以前各阶段的状态无关。用段的状态无关。用sk表示状态变量表示状态变量（state variable）。）。第28页，本讲稿共112页 一一般般状状态态变变量量的的取取值值有有一一定定的的范范围围或或允允许许集集合合，称称为为可可能能状状态态集集（set of admissible states）。可可能能状状态态集集实实际际上上是是关关于于状状态态的的约约束束条条件件。通通常常可可能能状状态态集集用用相相应应阶阶段段状状态态sk的的大大写写字字母母Sk表表示示，可可能能状状态态集集可可以以是是一一离离散散取取值值的的集集合合，也也可可以以为为一一连连续续的的取取值值区区间间

25、，视视具具体体问问题题而而定定例例如如上上面面的的最最短短路路问问题题中中，第第一一阶阶段段状状态态为为A，状状态态变变量量s1的的状状态态集集合合S1=A；第第二二阶阶段段则则有有三三个个状状态态：B1,B2,B3,状状态态变变量量s2的的状状态态集集合合S2=B1,B2,B3 .第29页，本讲稿共112页3、决策（决策（decision）当一个阶段的状态确定后，可以作出不同的当一个阶段的状态确定后，可以作出不同的决定或选决定或选择择，从而演变到下一阶段的某个状态，这种决定或选择称，从而演变到下一阶段的某个状态，这种决定或选择称为决策。为决策。用以描述决策变化的量称之决策变量（用以描述决策变

26、化的量称之决策变量（decision variable）。和状态变量一样，决策变量可以用一个数，。和状态变量一样，决策变量可以用一个数，一组数或一向量来描述，由于各阶段的决策取决于状态一组数或一向量来描述，由于各阶段的决策取决于状态变量变量sk，所以用，所以用 uk(sk)，表示阶段，表示阶段k的状态为的状态为sk时的决策变量。时的决策变量。决策变量的取值往往也有一定的允许范围，称之允许决策决策变量的取值往往也有一定的允许范围，称之允许决策集合（集合（set of admissible decision）。决策变量）。决策变量uk(sk)的允许决的允许决策集用策集用Uk(sk)表示表示,允许决

27、策集合实际是决策的约束条件。允许决策集合实际是决策的约束条件。第30页，本讲稿共112页 4、策略（策略（policy）一组有序的一组有序的决策序列决策序列构成一个策略，从第构成一个策略，从第k阶段至第阶段至第n阶段的一个策略称为阶段的一个策略称为k后部后部子策略记为子策略记为 pk,n(sk)=uk，uk+1，un，当，当k=1时的时的k部子策略称为部子策略称为全过程策略，简称策略，记为全过程策略，简称策略，记为p1,n(s1)。在实际问题中，由于在各个阶段可供选择的决策有许在实际问题中，由于在各个阶段可供选择的决策有许多个，因此，它们的不同组合就构成了许多可供选择的决多个，因此，它们的不同

28、组合就构成了许多可供选择的决策序列策序列(策略策略)，由它们组成的集合，称之允许策略集合，记，由它们组成的集合，称之允许策略集合，记作作P1,n，从允许策略集中，找出具有最优效果的策略称，从允许策略集中，找出具有最优效果的策略称为最优策略。为最优策略。第31页，本讲稿共112页5、状态转移方程（状态转移方程（equation of state transition）反映前后阶段状态之间关系的方程称为反映前后阶段状态之间关系的方程称为状态状态转移方程。在确定型转移方程。在确定型多阶段决策过程中，一旦某阶多阶段决策过程中，一旦某阶段的状态和决策为已知，下一阶段的段的状态和决策为已知，下一阶段的 状

29、态便完全确状态便完全确定，用定，用状态转移方程反映这种状态间的状态转移方程反映这种状态间的演变规律演变规律，记作：记作：有些问题的状态转移方程不一定存在数学表达有些问题的状态转移方程不一定存在数学表达式，但是它们的状态转移，还是有一定规律可循的。式，但是它们的状态转移，还是有一定规律可循的。第32页，本讲稿共112页6、阶段指标值（阶段指标值（objective value in a stage）阶段指标值是第阶段指标值是第k阶段的状态为阶段的状态为sk和采取决策和采取决策uk时时的效益，通常表示为的效益，通常表示为 dk(sk，uk)。对对不不同同问问题题，阶阶段段指指标标值值可可以以是是诸

30、诸如如费费用用、成成本本、产产值值、利利润润、产产量量、耗耗量量、距距离离、时时间间，等等等等。例例如如上上面面的的最最短短路路问问题题中中，如如果果第第二二阶阶段段地地状状态态为为B2,采取决策是由采取决策是由B2到达到达C1,则阶段指标值为则阶段指标值为6。第33页，本讲稿共112页7、指标函数（指标函数（objective function）衡量在选定某策略时，其优劣的数量指标。衡量在选定某策略时，其优劣的数量指标。定义在整个过程（定义在整个过程（1到到n阶段）上的指标函数记为：阶段）上的指标函数记为：V1,n（s1，u1，s2，sn，un），），定义在定义在后部子后部子过程过程（k到到

31、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）第34页，本讲稿共112页 指指标标函函数数Vk,n(sk,pk,n)通通常常是是描描述

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

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

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

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

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

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

38、42页，本讲稿共112页 (2)当当过过程程指指标标函函数数为为下下列列“积积”的的形形式式时时,其其相相应应的的基本方程为基本方程为 一般来说一般来说,要用函数基本方程逆推求解要用函数基本方程逆推求解,首先要有效首先要有效地建立动态规划模型地建立动态规划模型,然后再递推求解然后再递推求解,最后得出结论最后得出结论.然而然而,要把一个实际问题用动态规划方法来求解要把一个实际问题用动态规划方法来求解,还必还必须首先根据问题的要求。把它构造成动态规划模型须首先根据问题的要求。把它构造成动态规划模型,这是非常重要的一步。正确地建立一个动态规划模型这是非常重要的一步。正确地建立一个动态规划模型,往往问

39、题也就解决了一大半往往问题也就解决了一大半,而一个正确的动态规划而一个正确的动态规划模型模型,应该满足哪些条件呢应该满足哪些条件呢?第43页，本讲稿共112页建立动态规划数学模型的步骤建立动态规划数学模型的步骤 1应将实际问题恰当地分割成应将实际问题恰当地分割成n个子问题个子问题(n个阶段个阶段)。通常是根据时间或空间而划分的，或者在经。通常是根据时间或空间而划分的，或者在经由静态的数学规划模型转换为动态规划模型时，常取由静态的数学规划模型转换为动态规划模型时，常取静态规划中变量的个数静态规划中变量的个数n，即，即k=n。2正确地定义状态变量正确地定义状态变量sk，使它既能正确，使它既能正确地

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

41、面各段状态的影响，如果所选的变量不具备无后效性，就不能作为状态变量来构造动态规划的模效性，就不能作为状态变量来构造动态规划的模型。型。(3)要满足可知性。即所规定的各段状态变量的要满足可知性。即所规定的各段状态变量的值，可以直接或间接地测算得到。一般在动态规值，可以直接或间接地测算得到。一般在动态规划模型中，状态变量大都选取那种可以进行累计划模型中，状态变量大都选取那种可以进行累计的量。此外，在与静态规划模型的对应关系上，的量。此外，在与静态规划模型的对应关系上，通常根据经验，线性与非线性规划中约束条件的通常根据经验，线性与非线性规划中约束条件的个数，相当于动态规划中状态变量个数，相当于动态规

42、划中状态变量sk的维数而前的维数而前者约束条件所表示的内容，常就是状态变量者约束条件所表示的内容，常就是状态变量sk所代表所代表的内容。的内容。第45页，本讲稿共112页 3正正确确地地定定义义决决策策变变量量及及各各阶阶段段的的允允许许决决策策集集合合Uk(sk)，根根据据经经验验，一一般般将将问问题题中中待待求求的的量量，选选作作动动态态规规划划模模型型中中的的决决策策变变量量。或或者者在在把把静静态态规规划划模模型型(如如线线性性与与非非线线性性规规划划)转转换换为为动动态态规规划划模模型型时时，常常取取前前者者的的变量变量xj为后者的决策变量为后者的决策变量uk。4.能能够够正正确确地

43、地写写出出状状态态转转移移方方程程，至至少少要要能能正正确确反反映映状状态态转转移移规规律律。如如果果给给定定第第k阶阶段段状状态态变变量量sk的的值值，则则该该段段的的决决策策变变量量uk一一经经确确定定，第第k+1段段的的状状态态变变量量sk+1的的值值也也就就完完全全确确定定，即即有有sk+1=Tk(sk,uk)第46页，本讲稿共112页 5根根据据题题意意,正正确确地地构构造造出出目目标标与与变变量量的的函函数数关关系系目标函数目标函数，目标函数应满足下列性质：，目标函数应满足下列性质：(1)可可分分性性，即即对对于于所所有有k后后部部子子过过程程，其其目目标标函函数数仅仅取取决决于于

44、状状态态sk及及其其以以后后的的决决策策 uk,uk+1,un,就就是是说说它它是是定定义义在在全全过过程程和和所所有有后后部部子过程上的数量函数。子过程上的数量函数。(2)要满足递推关系，即要满足递推关系，即 (3)函函数数 对对其其变变元元Vk+1,n来来说说要要严严格格单调。单调。第47页，本讲稿共112页 6写出动态规划函数基本方程写出动态规划函数基本方程例如常见的指标函数是取各段指标和的形式例如常见的指标函数是取各段指标和的形式 其其中中 表表示示第第i阶阶段段的的指指标标，它它显显然然是是满满足足上述三个性质的。所以上式可以写成上述三个性质的。所以上式可以写成：第48页，本讲稿共1

45、12页第五节第五节 动态规划在经济管理中的应用动态规划在经济管理中的应用 一、一、资源分配问题资源分配问题 假假设设有一种有一种资资源，数量源，数量为为a，将其分配，将其分配给给n个使用者个使用者，分配，分配给给第第i个使用者数量个使用者数量xi时时，相，相应应的收益的收益为为gi（xi），），问问如何分配使得如何分配使得总总收入最大？收入最大？这这就是一就是一维资维资源分配源分配问问题题，该问题该问题的数学模型的数学模型为为：（6.23）第49页，本讲稿共112页式（式（6.23）是一个静态规划问题，应用动态规划方法）是一个静态规划问题，应用动态规划方法求解时人为赋予时间概念，将其看作是一个

46、多阶段决策求解时人为赋予时间概念，将其看作是一个多阶段决策问题。问题。按变量个数划分阶段，按变量个数划分阶段，k=1，2，n；设决策变量设决策变量uk=xk，表示分配给第，表示分配给第k个使用者的资源数个使用者的资源数量；量；设状态变量为设状态变量为sk，表示分配给第，表示分配给第k个至第个至第n个使用者个使用者的总资源数量；的总资源数量；状态转移方程：状态转移方程：sk+1=skxk，其中，其中s1=a；允许决策集合：允许决策集合：Dk(sk)=xk|0 xksk阶段指标函数：阶段指标函数：vk(sk，uk)=gk(xk)表示分配给第表示分配给第k个个使用者数量使用者数量xk时的收益；时的收

47、益；第50页，本讲稿共112页最最优优指指标标函数函数fk(sk)表示以数量表示以数量sk的的资资源分配源分配给给第第k个个至第至第n个使用者所得到的最大收益，个使用者所得到的最大收益，则动态规则动态规划基本方程划基本方程为为：由后向前逐段由后向前逐段递递推，推，f1(a)即即为为所求所求问题问题的最大收益。的最大收益。第51页，本讲稿共112页例例7 某公司打算在某公司打算在3个不同的地区个不同的地区设设置置4个个销销售点，售点，根据市根据市场场部部门门估估计计，在不同地区，在不同地区设设置不同数量的置不同数量的销销售点每月可得到的利售点每月可得到的利润润如表如表6.4所示。所示。试问试问在

48、各在各地区如何地区如何设设置置销销售点可使每月售点可使每月总总利利润润最大。最大。表表6.4 利利润值润值地区地区销销售点售点01234123000161210251714302116322217第52页，本讲稿共112页解：解：如前所述，建立如前所述，建立动态规动态规划数学模型：划数学模型：将将问题问题分分为为3个个阶阶段，段，k=1，2，3；决策决策变变量量xk表示分配表示分配给给第第k个地区的个地区的销销售点数；售点数；状状态变态变量量为为sk表示分配表示分配给给第第k个至第个至第3个地区的个地区的销销售点售点总总数；数；状状态转态转移方程：移方程：sk+1=skxk，其中，其中s1=4

49、；允允许许决策集合：决策集合：Dk（sk）=xk|0 xksk阶阶段指段指标标函数：函数：gk（xk）表示）表示xk个个销销售点分配售点分配给给第第k个地区所个地区所获获得的利得的利润润；最最优优指指标标函数函数fk（sk）表示将数量）表示将数量为为sk的的销销售点分配售点分配给给第第k个至第个至第3个地区所得到的最大利个地区所得到的最大利润润，动态规动态规划基本方划基本方程程为为：第53页，本讲稿共112页数数值计值计算如表所示。算如表所示。表表6.5 k=3时计时计算算结结果果fx3s3g3（x3）f3(s3)x3*0123401234000001010101014141416161701

50、014161701234第54页，本讲稿共112页表表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时计时计算算结结果果g1(x1)+f2(s1x1)f1(s1)x1*0123440+3116+2725+22 30+12 32+0472第55页，本讲稿共112页 所以最优解为：所以最优解为：x1*=2，x2*=1，x3*=1，f1(4)=47，