第六章动态规划精选文档.ppt

第六章动态规划1本讲稿第一页，共一百一十二页 动态规划的方法，在工程技术、企业管理、工农业动态规划的方法，在工程技术、企业管理、工农业生产及军事等部门中有着广泛的应用，并且获得了显著的生产及军事等部门中有着广泛的应用，并且获得了显著的效果。在经济管理方面，动态规划可以用来解决最优路径效果。在经济管理方面，动态规划可以用来解决最优路径问题、资源分配问题、生产调度问题、库存问题、装载问问题、资源分配问题、生产调度问题、库存问题、装载问题、排序问题、设备更新问题、生产过程最优控制问题等题、排序问题、设备更新问题、生产过程最优控制问题等等，他是现代企业管理中的一种重要的决策方法。等，他是现代企业管理中的一种重要的决策方法。许多实际问题采用动态规划方法去处理，常比线性规划许多实际问题采用动态规划方法去处理，常比线性规划或非线性规划更加有效。特别对于离散性的问题，由于解析数或非线性规划更加有效。特别对于离散性的问题，由于解析数学无法施展其术，而动态规划的方法就成为一种非常有效的工学无法施展其术，而动态规划的方法就成为一种非常有效的工具。具。本讲稿第二页，共一百一十二页 应特别指出的是，动态规划是解决某一类问题的一种应特别指出的是，动态规划是解决某一类问题的一种方法，是分析问题的一种途径，而不是一种特殊算法（如线方法，是分析问题的一种途径，而不是一种特殊算法（如线性规划是一种算法）。因而，它不象线性规划那样有一个标性规划是一种算法）。因而，它不象线性规划那样有一个标准的数学表达式和明确定义的一组规则，而必须对具体问题准的数学表达式和明确定义的一组规则，而必须对具体问题进行具体分析处理。因此，在学习动态规划时，除了对基本进行具体分析处理。因此，在学习动态规划时，除了对基本概念和方法正确地理解外，应以丰富的想象力去建立模型，概念和方法正确地理解外，应以丰富的想象力去建立模型，用创造性的技巧去求解。正如贝尔曼本人所说：用创造性的技巧去求解。正如贝尔曼本人所说：“由于动态由于动态规划的最优化原理仅仅是一种基本原理，正是它的某种不确规划的最优化原理仅仅是一种基本原理，正是它的某种不确定性为你提供了发挥你创造性思维的巨大空间定性为你提供了发挥你创造性思维的巨大空间!本讲稿第三页，共一百一十二页 本部分我们主要研究离散决策过程，介绍动态规划的本部分我们主要研究离散决策过程，介绍动态规划的基本概念、理论和方法，在通过一些典型的应用问题来说基本概念、理论和方法，在通过一些典型的应用问题来说明它的应用。明它的应用。动态规划所研究的对象是多阶段决策问题。动态规划所研究的对象是多阶段决策问题。所谓所谓多阶段决策问题是多阶段决策问题是指一类活动过程，它可以分指一类活动过程，它可以分为若干个相互联系的阶段，在每个阶段都需要作出决策。为若干个相互联系的阶段，在每个阶段都需要作出决策。这个决策不仅决定这一阶段的效益，而且决定下一阶段这个决策不仅决定这一阶段的效益，而且决定下一阶段的初始状态。的初始状态。每个阶段的决策确定以后，就得到一个决策序列，每个阶段的决策确定以后，就得到一个决策序列，称为策略。多阶段决策问题就是求一个策略，使各阶段称为策略。多阶段决策问题就是求一个策略，使各阶段的效益的总和达到最优。的效益的总和达到最优。本讲稿第四页，共一百一十二页第一节第一节 多阶段决策问题多阶段决策问题 在生产经营活动中，某些问题决策过程可以划分为若在生产经营活动中，某些问题决策过程可以划分为若干相互联系的阶段，每个阶段需要做出决策，从而使整个干相互联系的阶段，每个阶段需要做出决策，从而使整个过程取得最优。当每个阶段的决策确定以后，全部过程的过程取得最优。当每个阶段的决策确定以后，全部过程的决策就是这些阶段决策所组成的一个决策序列，所以多阶决策就是这些阶段决策所组成的一个决策序列，所以多阶段决策问题也称为序贯决策问题。段决策问题也称为序贯决策问题。动态规划方法与动态规划方法与“时间时间”关系很密切，随着时间过关系很密切，随着时间过程的发展而决定各时段的决策，产生一个决策序列，程的发展而决定各时段的决策，产生一个决策序列，这就是这就是“动态动态”的意思。然而它也可以处理与时间无的意思。然而它也可以处理与时间无关的静态问题，只要在问题中人为地引入关的静态问题，只要在问题中人为地引入“时段时段”因因素，就可以将其转化为一个多阶段决策问题。在本章素，就可以将其转化为一个多阶段决策问题。在本章中将介绍这种处理方法。中将介绍这种处理方法。本讲稿第五页，共一百一十二页 动态规划求解的多阶段决策问题的特点动态规划求解的多阶段决策问题的特点 通通常常多多阶阶段段决决策策过过程程的的发发展展是是通通过过状状态态的的一一系系列列变变换换来来实实现现的的。一一般般情情况况下下，系系统统在在某某个个阶阶段段的的状状态态转转移移除除与与本本阶阶段段的的状状态态和和决决策策有有关关外外，还还可可能能与与系系统统过过去去经经历历的的状状态态和和决决策策有有关关。因因此此，问问题题的的求求解解就就比比较较困困难难复复杂杂。而而适适合合于于用用动动态态规规划划方方法法求求解解的的只只是是一一类类特特殊殊的的多多阶阶段段决决策策问问题题，即即具具有有“无无后后效效性性”的的多多阶阶段段决决策策过过程程。所所谓谓无无后后效效性性，又又称称马马尔尔柯柯夫夫性性，是是指指系系统统从从某某个个阶阶段段往往后后的的发发展展，仅仅由由本本阶阶段段所所处处的的状状态态及及其其往往后后的的决决策策所所决定，与系统以前经历的状态和决策决定，与系统以前经历的状态和决策(历史历史)无关。无关。本讲稿第六页，共一百一十二页2511214106104131112396581052C1C3D1AB1B3B2D2EC2 为了说明动态规划的基本思想方法和特点，以下图所示为例，讨论求最短路问题的方法。求从A到E的最短路径本讲稿第七页，共一百一十二页 第第一一种种方方法法称称做做全全枚枚举举法法或或穷穷举举法法。它它的的基基本本思思想想是是列列举举出出所所有有可可能能发发生生的的方方案案和和结结果果，再再对对它它们们一一一一进进行行比比较较，求求出出最最优优方方案案。这这里里从从A到到E的的路路程程可可以以分分为为4个个阶阶段段。第第一一、二二阶阶段段的的走走法法有有三三种种，第第三三阶阶段段的的走走法法有有两两种种，第第四四段段的的走走法法仅仅一一种种，因因此此共共有有332118条条可可能能的的路路线线，分分别别算算出出各各条条路路线线的的距距离离，最最后后进进行行比比较较，可可知知最最优优路路线线是是AB2 C1 D1 E,最短距离是最短距离是19本讲稿第八页，共一百一十二页 显显然然，当当组组成成交交通通网网络络的的节节点点很很多多时时，用用穷穷举举法法求求最最优优路路线线的的计计算算工工作作量量将将会会十十分分庞庞大大，而而且且其其中中包包含着许多重复计算含着许多重复计算 第第二二种种方方法法即即所所谓谓“局局部部最最优优路路径径”法法，是是说说某某人人从从A出出发发，他他并并不不顾顾及及全全线线是是否否最最短短，只只是是选选择择当当前前最最短短途途径径，“逢逢近近便便走走”，错错误误地地以以为为局局部部最最优优会会致致整整体体最最优优，在在这这种种想想法法指指导导下下，所所取取决决策策必必是是AB2 C1 D1 E，全全程程长长度度是是25；显显然然，这这种种方方法法的的结结果果常常是是错误的错误的本讲稿第九页，共一百一十二页 第第三三种种方方法法是是动动态态规规划划方方法法。动动态态规规划划方方法法寻寻求求该该最最短短路路问问题题的的基基本本思思想想是是，如如果果A=S1 S2 Sk Sn E是是A到到E的的最最短短路路，则则Sk到到E的最短路一定是的最短路一定是Sk Sn E。首首先先将将问问题题划划分分为为4个个阶阶段段，每每次次的的选选择择总总是是综综合合后后继继过过程程的的一一并并最最优优进进行行考考虑虑，在在各各段段所所有有可可能能状状态态的的最最优优后后继继过过程程都都已已求求得得的的情情况况下下，全全程程的的最最优优路路线便也随之得到。线便也随之得到。为为了了找找出出所所有有可可能能状状态态的的最最优优后后继继过过程程，动动态态规规划划方方法法总总是是从从过过程程的的最最后后阶阶段段开开始始考考虑虑，然然后后逆逆着着实实际过程发展的顺序，逐段向前递推计算直至始点。际过程发展的顺序，逐段向前递推计算直至始点。本讲稿第十页，共一百一十二页2511214106104131112396581052C1C3D1AB1B3B2D2EC2f5(E)=0本讲稿第十一页，共一百一十二页2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D1)=5f5(E)=0本讲稿第十二页，共一百一十二页2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f4(D1)=5本讲稿第十三页，共一百一十二页2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C1)=8f4(D1)=5本讲稿第十四页，共一百一十二页2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C2)=7f4(D1)=5f3(C1)=8本讲稿第十五页，共一百一十二页2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f3(C1)=8f3(C2)=7本讲稿第十六页，共一百一十二页2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B1)=20f3(C2)=7f3(C1)=8本讲稿第十七页，共一百一十二页2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B2)=14f3(C2)=7f3(C1)=8f2(B1)=21本讲稿第十八页，共一百一十二页2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f2(B1)=21f2(B2)=14本讲稿第十九页，共一百一十二页2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=21本讲稿第二十页，共一百一十二页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本讲稿第二十一页，共一百一十二页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本讲稿第二十二页，共一百一十二页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本讲稿第二十三页，共一百一十二页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 本讲稿第二十四页，共一百一十二页 综综上上所所述述可可见见，全全枚枚举举法法虽虽可可找找出出最最优优方方案案，但但不不是是个个好好算算法法，局局部部最最优优法法则则完完全全是是个个错错误误方方法法，只只有有动动态态规规划划方方法法属属较较科科学学有有效效的的算算法法。它它的的基基本本思思想想是是，把把一一个个比比较较复复杂杂的的问问题题分分解解为为一一系系列列同同类类型型的的更更易易求求解解的的子子问问题题，便便于于应应用用计计算算机机。整整个个求求解解过过程程分分为为两两个个阶阶段段，先先按按整整体体最最优优的的思思想想逆逆序序地地求求出出各各个个子子问问题题中中所所有有可可能能状状态态的的最最优优决决策策与与最最优优路路线线值值，然然后后再再顺顺序序地地求求出出整整个个问问题题的的最最优优策策略略和和最最优优路路线线。计计算算过过程程中中，系系统统地地删删去去了了所所有有中中间间非非最最优优的的方方案案组组合合，从从而而使使计计算算工工作作量量比比穷穷举法大为减少。举法大为减少。本讲稿第二十五页，共一百一十二页第二节第二节 动态规划的基本概念和动态规划的基本概念和基本原理基本原理多阶段决策过程：多阶段决策过程：整个决策过程可按时间或空间顺序分解成若干整个决策过程可按时间或空间顺序分解成若干相相互联系互联系的阶段，每一阶段都需作出决策，全部过程的的阶段，每一阶段都需作出决策，全部过程的决策是一个决策序列。决策是一个决策序列。多阶段决策过程最优化的目标：多阶段决策过程最优化的目标：达到整个活动过程的总体效果最优，而非各单达到整个活动过程的总体效果最优，而非各单个阶段最优的简单总和。个阶段最优的简单总和。使使用用动动态态规规划划方方法法解解决决多多阶阶段段决决策策问问题题，首首先先要要将将实实际际问问题题写写成成动动态态规规划划模模型型，同同时时也也为为了了今今后后叙叙述述和和讨讨论论方方便便，这这里里需需要要对对动动态态规规划的下述一些基本术语进一步加以说明和定义：划的下述一些基本术语进一步加以说明和定义：本讲稿第二十六页，共一百一十二页1、阶段（阶段（stage）为为了了便便于于求求解解和和表表示示决决策策过过程程的的发发展展顺顺序序，而而把把所所给给问问题题恰恰当当地地划划分分为为若若干干个个相相互互联联系系又又有有区区别别的的子子问问题题，称称之之为为多多段段决决策策问问题题的的阶阶段段。一一个个阶阶段段，就就是是需需要要作作出出一一个个决决策策的的子子问问题题，通通常常，阶阶段段是是按按决决策策进进行行的的时时间间顺顺序序或或空空间间特特征征上上先先后后顺顺序序划划分分的的。用用以以描描述述阶阶段段的的变变量量叫叫作作阶阶段段变变量量，一一般般以以k表表示示阶阶段段变变量量阶阶段段数数等等于于多多段段决决策策过过程程从从开开始始到到结结束束所所需需作作出出决决策策的的数数目目，例例如如上上面面的的最最短短路路问问题题就就是是一一个个四四阶阶段段决决策策过过程。程。本讲稿第二十七页，共一百一十二页2、状态（状态（state）每个阶段开始时过程所处的自然状况或客观条每个阶段开始时过程所处的自然状况或客观条件。反映状态变化的量叫做状态变量，它可以用一件。反映状态变化的量叫做状态变量，它可以用一个数，一组数或一向量来描述，个数，一组数或一向量来描述，。状态变量必须包。状态变量必须包含在给定的阶段上确定全部允许决策所需要的信息。它含在给定的阶段上确定全部允许决策所需要的信息。它应能描述过程的特征并具有应能描述过程的特征并具有“无后效性无后效性”，即当前阶段，即当前阶段状态给定时，这个阶段以后过程的演变与该阶段以前各状态给定时，这个阶段以后过程的演变与该阶段以前各阶段的状态无关。用阶段的状态无关。用sk表示状态变量表示状态变量（state variable）。）。本讲稿第二十八页，共一百一十二页 一一般般状状态态变变量量的的取取值值有有一一定定的的范范围围或或允允许许集集合合，称称为为可可能能状状态态集集（set of admissible states）。可可能能状状态态集集实实际际上上是是关关于于状状态态的的约约束束条条件件。通通常常可可能能状状态态集集用用相相应应阶阶段段状状态态sk的的大大写写字字母母Sk表表示示，可可能能状状态态集集可可以以是是一一离离散散取取值值的的集集合合，也也可可以以为为一一连连续续的的取取值值区区间间，视视具具体体问问题题而而定定例例如如上上面面的的最最短短路路问问题题中中，第第一一阶阶段段状状态态为为A，状状态态变变量量s1的的状状态态集集合合S1=A；第第二二阶阶段段则则有有三三个个状状态态：B1,B2,B3,状状态态变变量量s2的的状状态态集集合合S2=B1,B2,B3 .本讲稿第二十九页，共一百一十二页3、决策（决策（decision）当一个阶段的状态确定后，可以作出不同的当一个阶段的状态确定后，可以作出不同的决定或选决定或选择择，从而演变到下一阶段的某个状态，这种决定或选择称为决，从而演变到下一阶段的某个状态，这种决定或选择称为决策。策。用以描述决策变化的量称之决策变量（用以描述决策变化的量称之决策变量（decision variable）。和状态变量一样，决策变量可以用一个数，一。和状态变量一样，决策变量可以用一个数，一组数或一向量来描述，由于各阶段的决策取决于状态变量组数或一向量来描述，由于各阶段的决策取决于状态变量sk，所以用，所以用 uk(sk)，表示阶段，表示阶段k的状态为的状态为sk时的决策变量。时的决策变量。决策变量的取值往往也有一定的允许范围，称之允许决决策变量的取值往往也有一定的允许范围，称之允许决策集合（策集合（set of admissible decision）。决策变量）。决策变量uk(sk)的允的允许决策集用许决策集用Uk(sk)表示表示,允许决策集合实际是决策的约束条允许决策集合实际是决策的约束条件。件。本讲稿第三十页，共一百一十二页 4、策略（策略（policy）一组有序的一组有序的决策序列决策序列构成一个策略，从第构成一个策略，从第k阶段至第阶段至第n阶段的一个策略称为阶段的一个策略称为k后部后部子策略记为子策略记为 pk,n(sk)=uk，uk+1，un，当，当k=1时的时的k部子策略称部子策略称为全过程策略，简称策略，记为为全过程策略，简称策略，记为p1,n(s1)。在实际问题中，由于在各个阶段可供选择的决策在实际问题中，由于在各个阶段可供选择的决策有许多个，因此，它们的不同组合就构成了许多可供有许多个，因此，它们的不同组合就构成了许多可供选择的决策序列选择的决策序列(策略策略)，由它们组成的集合，称之允许，由它们组成的集合，称之允许策略集合，记作策略集合，记作P1,n，从允许策略集中，找出具有最优，从允许策略集中，找出具有最优效果的策略称为最优策略。效果的策略称为最优策略。本讲稿第三十一页，共一百一十二页5、状态转移方程（状态转移方程（equation of state transition）反映前后阶段状态之间关系的方程称为反映前后阶段状态之间关系的方程称为状态转状态转移方程。在确定型移方程。在确定型多阶段决策过程中，一旦某阶段多阶段决策过程中，一旦某阶段的状态和决策为已知，下一阶段的的状态和决策为已知，下一阶段的 状态便完全确定，状态便完全确定，用用状态转移方程反映这种状态间的状态转移方程反映这种状态间的演变规律演变规律，记作：记作：有些问题的状态转移方程不一定存在数学表达有些问题的状态转移方程不一定存在数学表达式，但是它们的状态转移，还是有一定规律可循的。式，但是它们的状态转移，还是有一定规律可循的。本讲稿第三十二页，共一百一十二页6、阶段指标值（阶段指标值（objective value in a stage）阶段指标值是第阶段指标值是第k阶段的状态为阶段的状态为sk和采取决策和采取决策uk时的时的效益，通常表示为效益，通常表示为 dk(sk，uk)。对对不不同同问问题题，阶阶段段指指标标值值可可以以是是诸诸如如费费用用、成成本本、产产值值、利利润润、产产量量、耗耗量量、距距离离、时时间间，等等等等。例例如如上上面面的的最最短短路路问问题题中中，如如果果第第二二阶阶段段地地状状态态为为B2,采采取决策是由取决策是由B2到达到达C1,则阶段指标值为则阶段指标值为6。本讲稿第三十三页，共一百一十二页7、指标函数（指标函数（objective function）衡量在选定某策略时，其优劣的数量指标。衡量在选定某策略时，其优劣的数量指标。定义在整个过程（定义在整个过程（1到到n阶段）上的指标函数记为：阶段）上的指标函数记为：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）本讲稿第三十四页，共一百一十二页 指指标标函函数数Vk,n(sk,pk,n)通通常常是是描描述述所所实实现现的的全全过过程程或或k后后部部子子过过程程效效果果优优劣劣的的数数量量指指标标，它它是是由由各各阶阶段段的的阶阶段段指指标标函函数数dk(sk,uk)累累积积形形成成的的，适适于于用用动动态态规规划划求求解解的的问问题题的的指指标标函函数数，必必须须具具有有关关于于阶阶段段指指标标的的可分离形式对于后部子过程的指标函数可以表示为：可分离形式对于后部子过程的指标函数可以表示为：式中，式中，表示某种运算，可以是加、减、乘、除、表示某种运算，可以是加、减、乘、除、开方等。开方等。本讲稿第三十五页，共一百一十二页 总总之之，具具体体问问题题的的目目标标函函数数表表达达形形式式需需要要视视具具体体问题而定。问题而定。多阶段决策问题中，常见的目标函数形式之一是取多阶段决策问题中，常见的目标函数形式之一是取各阶段效应之和的形式，即各阶段效应之和的形式，即:有些问题，如系统可靠性问题，其目标函数是取各有些问题，如系统可靠性问题，其目标函数是取各阶段效应的连乘积形式，如：阶段效应的连乘积形式，如：本讲稿第三十六页，共一百一十二页8、最优指标函数（最优指标函数（optimal value function）指标函数的最优值称为最优指标函数，记为指标函数的最优值称为最优指标函数，记为fk(sk)，它表示从第它表示从第k阶段阶段状态状态 sk 出发，采用出发，采用最优策略最优策略到终止到终止状态状态时的后部子时的后部子过程指标函数值，即过程指标函数值，即式中式中opt即即optimization，根据具体问题可取，根据具体问题可取max或或min。与它相应的子策略称为在。与它相应的子策略称为在sk状态下的最优子状态下的最优子策略，记为策略，记为pk*(sk)；而构成该子策略的各段决策；而构成该子策略的各段决策称为该过程上的最优决策，记为称为该过程上的最优决策，记为 本讲稿第三十七页，共一百一十二页即即 简记为简记为特别当特别当k=1时，时，f1(s1)就是问题的最优值，而就是问题的最优值，而p1*就就是最优策略。例如上面的最短路问题中，有唯一是最优策略。例如上面的最短路问题中，有唯一最优值最优值f1(s1)=18，而，而就是其最优策略。就是其最优策略。本讲稿第三十八页，共一百一十二页 多阶段决策问题的数学模型多阶段决策问题的数学模型 综综上上所所述述，适适于于应应用用动动态态规规划划方方法法求求解解的的一一类类多多阶阶段段决决策策问问题题，亦亦即即具具有有无无后后效效性性的的多多阶阶段段决决策策问题的数学模型呈以下形式问题的数学模型呈以下形式:本讲稿第三十九页，共一百一十二页 则对上述策略中所隐含的任一状态而言，则对上述策略中所隐含的任一状态而言，第第k子过程上对应于该状态的最优策略必然子过程上对应于该状态的最优策略必然 包含在上述全过程最优策略包含在上述全过程最优策略p1*中，即为中，即为最优化原理最优化原理（贝尔曼最优化原理）（贝尔曼最优化原理）作为一个全过程的最优策略具有这样的性质：作为一个全过程的最优策略具有这样的性质：对于最优策略过程中的任意状态而言，无论其过对于最优策略过程中的任意状态而言，无论其过去的状态和决策如何，余下的诸决策必构成一个去的状态和决策如何，余下的诸决策必构成一个最优子策略。最优子策略。该原理的具体解释是，若某一全该原理的具体解释是，若某一全过程最优策略为：过程最优策略为：本讲稿第四十页，共一百一十二页其中，其中，表示从状态表示从状态sk到由决策到由决策uk(sk)所决定的状态所决定的状态sk+1之间之间的距离。的距离。动态规划的基本方程动态规划的基本方程 在上面最短路问题的求解过程中，在求解在上面最短路问题的求解过程中，在求解的各阶段利用了第的各阶段利用了第k阶段和第阶段和第k+1阶段的如下递阶段的如下递推关系：推关系：第三节第三节 动态规划模型的建立与求解动态规划模型的建立与求解 本讲稿第四十一页，共一百一十二页 一一般般地地，对对于于n个个阶阶段段的的决决策策过过程程，假假设设只只考考虑虑指指标标函函数数是是“和和”与与“积积”的的形形式式，第第k阶阶段段和和第第k+1阶阶段段间间的的递递推公式可表示如下：推公式可表示如下：(1)当当指指标标函函数数为为下下列列“和和”的的形形式式时时，其其相相应应的的基基本本方程为方程为是边界条件。是边界条件。本讲稿第四十二页，共一百一十二页 (2)当当过过程程指指标标函函数数为为下下列列“积积”的的形形式式时时,其其相应的基本方程为相应的基本方程为 一般来说一般来说,要用函数基本方程逆推求解要用函数基本方程逆推求解,首先要有效首先要有效地建立动态规划模型地建立动态规划模型,然后再递推求解然后再递推求解,最后得出结论最后得出结论.然然而而,要把一个实际问题用动态规划方法来求解要把一个实际问题用动态规划方法来求解,还必还必须首先根据问题的要求。把它构造成动态规划模型须首先根据问题的要求。把它构造成动态规划模型,这是非常重要的一步。正确地建立一个动态规划模这是非常重要的一步。正确地建立一个动态规划模型型,往往问题也就解决了一大半往往问题也就解决了一大半,而一个正确的动态而一个正确的动态规划模型规划模型,应该满足哪些条件呢应该满足哪些条件呢?本讲稿第四十三页，共一百一十二页建立动态规划数学模型的步骤建立动态规划数学模型的步骤 1应将实际问题恰当地分割成应将实际问题恰当地分割成n个子问题个子问题(n个阶段个阶段)。通常是根据时间或空间而划分的，或者在。通常是根据时间或空间而划分的，或者在经由静态的数学规划模型转换为动态规划模型时，经由静态的数学规划模型转换为动态规划模型时，常取静态规划中变量的个数常取静态规划中变量的个数n，即，即k=n。2正确地定义状态变量正确地定义状态变量sk，使它既能正确地，使它既能正确地描述过程的状态，又能满足无后效性动态规划中描述过程的状态，又能满足无后效性动态规划中的状态与一般控制系统中和通常所说的状态的概念的状态与一般控制系统中和通常所说的状态的概念是有所不同的，动态规划中的状态变量必须具备以是有所不同的，动态规划中的状态变量必须具备以下三个特征：下三个特征：本讲稿第四十四页，共一百一十二页 (1)要能够正确地描述受控过程的变化特征。要能够正确地描述受控过程的变化特征。(2)要满足无后效性。即如果在某个阶段状态已经要满足无后效性。即如果在某个阶段状态已经给定，那么在该阶段以后，过程的发展不受前面各给定，那么在该阶段以后，过程的发展不受前面各段状态的影响，如果所选的变量不具备无后效性，段状态的影响，如果所选的变量不具备无后效性，就不能作为状态变量来构造动态规划的模型。就不能作为状态变量来构造动态规划的模型。(3)要满足可知性。即所规定的各段状态变量的值，要满足可知性。即所规定的各段状态变量的值，可以直接或间接地测算得到。一般在动态规划模型中，可以直接或间接地测算得到。一般在动态规划模型中，状态变量大都选取那种可以进行累计的量。此外，在状态变量大都选取那种可以进行累计的量。此外，在与静态规划模型的对应关系上，通常根据经验，线性与静态规划模型的对应关系上，通常根据经验，线性与非线性规划中约束条件的个数，相当于动态规划中与非线性规划中约束条件的个数，相当于动态规划中状态变量状态变量sk的维数而前者约束条件所表示的内容，的维数而前者约束条件所表示的内容，常就是状态变量常就是状态变量sk所代表的内容。所代表的内容。本讲稿第四十五页，共一百一十二页 3正正确确地地定定义义决决策策变变量量及及各各阶阶段段的的允允许许决决策策集集合合Uk(sk)，根根据据经经验验，一一般般将将问问题题中中待待求求的的量量，选选作作动动态态规规划划模模型型中中的的决决策策变变量量。或或者者在在把把静静态态规规划划模模型型(如如线线性性与与非非线线性性规规划划)转转换换为为动动态态规规划划模模型型时时，常常取取前前者的变量者的变量xj为后者的决策变量为后者的决策变量uk。4.能能够够正正确确地地写写出出状状态态转转移移方方程程，至至少少要要能能正正确确反反映映状状态态转转移移规规律律。如如果果给给定定第第k阶阶段段状状态态变变量量sk的的值值，则则该该段段的的决决策策变变量量uk一一经经确确定定，第第k+1段段的的状状态态变变量量sk+1的值也就完全确定，即有的值也就完全确定，即有sk+1=Tk(sk,uk)本讲稿第四十六页，共一百一十二页 5根根据据题题意意,正正确确地地构构造造出出目目标标与与变变量量的的函函数数关关系系目标函数目标函数，目标函数应满足下列性质：，目标函数应满足下列性质：(1)可可分分性性，即即对对于于所所有有k后后部部子子过过程程，其其目目标标函函数数仅仅取取决决于于状状态态sk及及其其以以后后的的决决策策 uk,uk+1,un,就就是是说说它它是是定定义义在在全全过过程程和和所所有有后后部部子子过过程程上上的的数数量函数。量函数。(2)要满足递推关系，即要满足递推关系，即 (3)函函数数 对对其其变变元元Vk+1,n来来说说要要严严格格单调。单调。本讲稿第四十七页，共一百一十二页 6写出动态规划函数基本方程写出动态规划函数基本方程例如常见的指标函数是取各段指标和的形式例如常见的指标函数是取各段指标和的形式 其其中中 表表示示第第i阶阶段段的的指指标标，它它显显然然是是满满足足上上述三个性质的。所以上式可以写成述三个性质的。所以上式可以写成：本讲稿第四十八页，共一百一十二页第五节第五节 动态规划在经济管理中的应用动态规划在经济管理中的应用 一、一、资源分配问题资源分配问题 假假设设有一种有一种资资源，数量源，数量为为a，将其分配，将其分配给给n个使用个使用者，分配者，分配给给第第i个使用者数量个使用者数量xi时时，相，相应应的收益的收益为为gi（xi），），问问如何分配使得如何分配使得总总收入最大？收入最大？这这就是一就是一维维资资源分配源分配问题问题，该问题该问题的数学模型的数学模型为为：（6.23）本讲稿第四十九页，共一百一十二页式（式（6.23）是一个静态规划问题，应用动态规划方法求）是一个静态规划问题，应用动态规划方法求解时人为赋予时间概念，将其看作是一个多阶段决策问题。解时人为赋予时间概念，将其看作是一个多阶段决策问题。按变量个数划分阶段，按变量个数划分阶段，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时的收益；时的收益；本讲稿第五十页，共一百一十二页最最优优指指标标函数函数fk(sk)表示以数量表示以数量sk的的资资源分配源分配给给第第k个至第个至第n个使用者所得到的最大收益，个使用者所得到的最大收益，则动态规则动态规划基划基本方程本方程为为：由后向前逐段由后向前逐段递递推，推，f1(a)即即为为所求所求问题问题的最大收益。的最大收益。本讲稿第五十一页，共一百一十二页例例7 某公司打算在某公司打算在3个不同的地区个不同的地区设设置置4个个销销售点，售点，根据市根据市场场部部门门估估计计，在不同地区，在不同地区设设置不同数量的置不同数量的销销售售点每月可得到的利点每月可得到的利润润如表如表6.4所示。所示。试问试问在各地区如何在各地区如何设设置置销销售点可使每月售点可使每月总总利利润润最大。最大。表表6.4 利利润值润值地区地区销销售点售点01234123000161210251714302116322217本讲稿第五十二页，共一百一十二页解：解：如前所述，建立如前所述，建立动态规动态规划数学模型：划数学模型：将将问题问题分分为为3个个阶阶段，段，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个地区所得到的最大利个地区所得到的最大利润润，动态规动态规划基本划基本方程方程为为：本讲稿第五十三页，共一百一十二页数数值计值计算如表所示。算如表所示。表表6.5 k=3时计时计算算结结果果fx3s3g3（x3）f3(s3)x3*0123401234000001010101014141416161701014161701234本讲稿第五十四页，共一百一十二页表表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,3fx