1、第八章第八章 动态规划动态规划Ch8 Dynamic Programming8-1 多阶段决策过程最优化多阶段决策过程最优化8-2 动态规划基本概念动态规划基本概念8-3 动态规划基本原理动态规划基本原理8-4 动态规划的应用动态规划的应用8-1 多阶段决策过程最优化多阶段决策过程最优化一、多阶段决策问题一、多阶段决策问题v动态规划是把多阶段决策问题作为研究对象。动态规划是把多阶段决策问题作为研究对象。v多阶段决策问题：多阶段决策问题：根据问题本身的特点，可以将其求解的全过程划分为若干个相互联系的阶段(即将问题划分为许多个相互联系的子问题)，在它的每一阶段都需要作出决策，并且在一个阶段的决策确
2、定以后再转移到下一个阶段。v多阶段决策过程多阶段决策过程(Multi-Multi-StagedecisionStagedecision process)process)：前一个阶段的决策要影响到后一个阶段的决策，从而影响整个过程。各个阶段所确定的决策就构成了一个决策序列，称为一个策略。一般来说，由于每一阶段可供选择的决策往往不止一个，因此，对于整个过程，就会有许多可供选择的策略。2022年7月29日11时39分Page 2 of 77 8-1 多阶段决策过程最优化多阶段决策过程最优化v最优策略：最优策略：若对应于一个策略，可以由一个量化的指标来确定这个策略所对应的活动过程的效果，那么不同的策略
3、就有各自的效果。在所有可供选择的策略中，对应效果最好的策略称为最优策略。把一个问题划分成若干个相互联系的阶段选取其最优策略，这类问题就是多阶段决策问题。v多阶段决策过程最优化的目标是要达到整个活动过程的总体效果最优。由于各段决策间有机地联系着，本段决策的执行将影响到下一段的决策，以至于影响总体效果，所以决策者在每段决策时不应仅考虑本阶段最优，还应考虑对最终目标的影响，从而作出对全局来讲是最优的决策。动态规划就是符合这种要求的一种决策方法。2022年7月29日11时39分Page 3 of 77 8-1 多阶段决策过程最优化多阶段决策过程最优化二、多阶段决策问题举例二、多阶段决策问题举例 1)1
4、)工厂生产过程工厂生产过程：由于市场需求是一随着时间而变化的因素，因此，为了取得全年最佳经济效益，就要在全年的生产过程中，逐月或者逐季度地根据库存和需求情况决定生产计划安排。2)2)设备更新问题设备更新问题：一般企业用于生产活动的设备，刚买来时故障少，经济效益高，即使进行转让，处理价值也高，随着使用年限的增加，就会逐渐变为故障多，维修费用增加，可正常使用的工时减少，加工质量下降，经济效益差，并且，使用的年限越长、处理价值也越低，自然，如果卖去旧的买新的，还需要付出更新费因此就需要综合权衡决定设备的使用年限，使总的经济效益最好。2022年7月29日11时39分Page 4 of 77 8-1 多
5、阶段决策过程最优化多阶段决策过程最优化3)3)连续生产过程的控制问题连续生产过程的控制问题：一般化工生产过程中，常包含一系列完成生产过程的设备，前一工序设备的输出则是后一工序设备的输入，因此，应该如何根据各工序的运行工况，控制生产过程中各设备的输入和输出，以使总产量最大。v以上所举问题的发展过程都与时间因素有关，因此在这类多阶段决策问题中，阶段的划分常取时间区段来表示，并且各个阶段上的决策往往也与时间因素有关，这就使它具有了“动态”的含义，所以把处理这类动态问题的方法称为动态规划方法。不过，实际中尚有许多不包含时间因素的一类“静态”决策问题，就其本质而言是一次决策问题，是非动态决策问题，但是也
6、可以人为地引入阶段的概念当作多阶段决策问题，应用动态规划方法加以解决。2022年7月29日11时39分Page 5 of 77 8-1 多阶段决策过程最优化多阶段决策过程最优化4 4）资源分配问题）资源分配问题：属于这类静态问题。如：某工业部门或公司，拟对其所属企业进行稀缺资源分配，为此需要制定出收益最大的资源分配方案。这种问题原本要求一次确定出对各企业的资源分配量，它与时间因素无关，不属动态决策，但是，我们可以人为地规定一个资源分配的阶段和顺序，从而使其变成一个多阶段决策问题(后面我们将详细讨论这个问题)。5 5）运输网络问题）运输网络问题：如下页图1所示的运输网络，点间连线上的数字表示两地
7、距离(也可是运费、时间等)，要求从v1 至v10的最短路线。这种运输网络问题也是静态决策问题。但是，按照网络中点的分布，可以把它分为4个阶段，而作为多阶段决策问题来研究。2022年7月29日11时39分Page 6 of 77 8-1 多阶段决策过程最优化多阶段决策过程最优化图8-1 运输网络图示2022年7月29日11时39分Page 7 of 77 8-1 多阶段决策过程最优化多阶段决策过程最优化三、动态规划求解的多阶段决策问题的特点三、动态规划求解的多阶段决策问题的特点 通常多阶段决策过程的发展是通过状态的一系列变换来实现的。一般情况下，系统在某个阶段的状态转移除与本阶段的状态和决策有关
8、外，还可能与系统过去经历的状态和决策有关。因此，问题的求解就比较困难复杂。而适合于用动态规划方法适合于用动态规划方法求解的只是一类特殊的多阶段决策问题，即具有求解的只是一类特殊的多阶段决策问题，即具有“无后效性无后效性”的多阶段决策过程。所谓的多阶段决策过程。所谓无后效性无后效性，又称马尔柯夫性，是指系，又称马尔柯夫性，是指系统从某个阶段往后的发展，仅由本阶段所处的状态及其往后的统从某个阶段往后的发展，仅由本阶段所处的状态及其往后的决策所决定，与系统以前经历的状态和决策决策所决定，与系统以前经历的状态和决策(历史历史)无关。无关。状态状态 x x1 1阶段阶段1 1T T1 1决策决策u u1
9、 1状态状态 x x2 2决策决策u u2 2阶段阶段2 2T T2 2状态状态 x x3 3.状态状态 x xk k决策决策u uk k阶段阶段k kT Tk k状态状态 x xk k+1+1.状状态态 x xn n决策决策u un n阶段阶段n nTnTn状状态态 x xn n+1+1要点：要点：阶段，状态，决策，状态转移方程，阶段，状态，决策，状态转移方程，k k-后部子过程后部子过程多阶段决策过程特点多阶段决策过程特点:2022年7月29日11时39分Page 8 of 77 8-1 多阶段决策过程最优化多阶段决策过程最优化四、动态规划方法导引四、动态规划方法导引：为了说明动态规划的基
10、本思想方法和特点，下面以图8-1所示为例讨论的求最短路问题的方法。第一种方法第一种方法称做全枚举法或穷举法。它的基本思想是列举出所有可能发生的方案和结果，再对它们一一进行比较，求出最优方案。这里从v1到v10的路程可以分为4个阶段。第一段的走法有三种，第二三两段的走法各有两种，第四段的走法仅一种，因此共有322112条可能的路线，分别算出各条路线的距离，最后进行比较，可知最优路线是v1 v3 v7 v9 v10,最短距离是18显然，当组成交通网络的节点很多时，用穷举法求最优路线的计算工作量将会十分庞大，而且其中包含着许多重复计算 第二种方法第二种方法即所谓“局部最优路径”法，是说某人从k出发，
11、他并不顾及全线是否最短，只是选择当前最短途径，“逢近便走”，错误地以为局部最优会致整体最优，在这种想法指导下，所取决策必是v1 v3 v5 v8 v10，全程长度是20；显然，这种方法的结果常是错误的2022年7月29日11时39分Page 9 of 77 8-1 多阶段决策过程最优化多阶段决策过程最优化v第三种方法第三种方法是动态规划方法。动态规划方法寻求该最短路问题的基本思想是，首先将问题划分为4个阶段，每次的选择总是综合后继过程的一并最优进行考虑，在各段所有可能状态的最优后继过程都已求得的情况下，全程的最优路线便也随之得到。为了找出所有可能状态的最优后继过程，动态规划方法总是从过程的最后
12、阶段开始考虑，然后逆着实际过程发展的顺序，逐段向前递推计算直至始点。2022年7月29日11时39分Page 10 of 77 8-1 多阶段决策过程最优化多阶段决策过程最优化v具体说，此问题先从v10开始，因为v10是终点。再无后继过程，故可以接着考虑第4阶段上所有可能状态v8,v9的最优后续过程因为从v8,v9 到v10的路线是唯一的，所以v8,v9 的最优决策和最优后继过程就是到v10，它们的最短距离分别是5和3。接着考虑阶段3上可能的状态v5,v6,v7,到v10的最优决策和最优后继过程在状态V5上，虽然到v8是8，到v9是9，但是综合考虑后继过程整体最优，取最优决策是到v9,最优后继
13、过程是v5v9 v10，最短距离是12同理，状态v6的最优决策是至v8；v7的最优决策是到v9。v同样，当阶段3上所有可能状态的最优后继过程都已求得后，便可以开始考虑阶段2上所有可能状态的最优决策和最优后继过程，如v2的最优决策是到v5,最优路线是v2v5v9v10，最短距离是15依此类推，最后可以得到从初始状态v1的最优决策是到v3最优路线是v1v3v7v9v10，全程的最短距离是18。图1中粗实线表示各点到的最优路线，每点上方括号内的数字表示该点到终点的最短路距离。2022年7月29日11时39分Page 11 of 77 8-1 多阶段决策过程最优化多阶段决策过程最优化v结论：结论：v全
14、枚举法全枚举法虽可找出最优方案，但不是个好算法；虽可找出最优方案，但不是个好算法；v局部最优法则局部最优法则完全是个错误方法；完全是个错误方法；v动态规划方法动态规划方法属较科学有效的算法：属较科学有效的算法：它的基本思想是，把一个比较复杂的问题分解为一系列同类型的更易求解的子问题，便于应用计算机。整个求解过程分为两个阶段，先按整体最优的思想逆序地求出各个子问题中所有可能状态的最优决策与最优路线值，然后再顺序地求出整个问题的最优策略和最优路线。计算过程中，系统地删去了所有中间非最优的方案组合，从而使计算工作量比穷举法大为减少。2022年7月29日11时39分Page 12 of 77 8-2
15、动态规划基本概念动态规划基本概念v使用动态规划方法解决多阶段决策问题，首先要将实际问题写成动态规划模型，同时也为了今后叙述和讨论方便，这里需要对动态规划的下述一些基本术语进一步加以说明和定义：2022年7月29日11时39分Page 13 of 77 8-2 动态规划基本概念动态规划基本概念(一一)阶段和阶段变量阶段和阶段变量 为了便于求解和表示决策及过程的发展顺序，而把所给问题恰当地划分为若干个相互联系又有区别的子问题，称之为多段决策问题的阶段。一个阶段，就是需要作出一个决策的子问题，通常，阶段是按决策进行的时间或空间上先后顺序划分的。用以描述阶段的变量叫作阶段变量，一般以k表示阶段变量阶段
16、数等于多段决策过程从开始到结束所需作出决策的数目，图51所示的最短路问题就是一个四阶段决策过程。（二）状态、状态变量和可能状态集（二）状态、状态变量和可能状态集 1.状态与状态变量。用以描述事物(或系统)在某特定的时间与空间域中所处位置及运动特征的量，称为状态。反映状态变化的量叫做状态变量。状态变量必须包含在给定的阶段上确定全部允许决策所需要的信息。按照过程进行的先后，每个阶段的状态可分为初始状态和终止状态，或称输入状态和输出状态，阶段k的初始状态记作sk，终止状态记为sk+1。但为了清楚起见，通常定义阶段的状态即指其初始状态。2022年7月29日11时39分Page 14 of 77 8-2
17、 动态规划基本概念动态规划基本概念v2可能状态集 一般状态变量的取值有一定的范围或允许集合，称为可能状态集，或可达状态集。可能状态集实际上是关于状态的约束条件。通常可能状态集用相应阶段状态sk的大写字母Sk表示，skSk，可能状态集可以是一离散取值的集合，也可以为一连续的取值区间，视具体问题而定在图51所示的最短路问题中，第一阶段状态为v1，状态变量s1的状态集合S1=v1；第二阶段则有三个状态：v2,v3,v4,状态变量s2的状态集合S2=v2,v3,v4；第三阶段也有三个状态:v5,v6,v7，状态变量s3的状态集合S3=v5,v6,v7；第四阶段则有二个状态：v8,v9,状态变量s4的状
18、态集合S4=v8,v9；2022年7月29日11时39分Page 15 of 77 8-2 动态规划基本概念动态规划基本概念（三）决策、决策变量和允许决策集合三）决策、决策变量和允许决策集合 所谓决策，就是确定系统过程发展的方案。决策的实质是关于状态的选择，是决策者从给定阶段状态出发对下一阶段状态作出的选择。用以描述决策变化的量称之决策变量和状态变量一样，决策变量可以用一个数，一组数或一向量来描述，也可以是状态变量的函数，记以uk=uk(sk)，表示于阶段k状态sk时的决策变量。决策变量的取值往往也有一定的允许范围，称之允许决策集合。决策变量uk(sk)的允许决策集用Uk(sk)表示,uk(s
19、k)Uk(sk)允许决策集合实际是决策的约束条件。2022年7月29日11时39分Page 16 of 77 8-2 动态规划基本概念动态规划基本概念（四）、策略和允许策略集合（四）、策略和允许策略集合 策略(Policy)也叫决策序列策略有全过程策略和k部子策略之分，全过程策略是指具有n个阶段的全部过程，由依次进行的n个阶段决策构成的决策序列，简称策略，表示为p1,nu1,u2,un。从k阶段到第n阶段，依次进行的阶段决 策 构 成 的 决 策 序 列 称 为k部 子 策 略,表 示 为pk,nuk,uk+1,un，显然当k=1时的k部子策略就是全过程策略。在实际问题中，由于在各个阶段可供选
20、择的决策有许多个，因此，它们的不同组合就构成了许多可供选择的决策序列(策略)，由它们组成的集合，称之允许策略集合，记作P1,n，从允许策略集中，找出具有最优效果的策略称为最优策略。2022年7月29日11时39分Page 17 of 77 8-2 动态规划基本概念动态规划基本概念（五）状态转移方程（五）状态转移方程 系统在阶段k处于状态sk，执行决策uk(sk)的结果是系统状态的转移，即系统由阶段k的初始状态sk转移到终止状态sk+1，或者说，系统由k阶段的状态sk转移到了阶段k+1的状态sk+1，多阶段决策过程的发展就是用阶段状态的相继演变来描述的。对于具有无后效性的多阶段决策过程,系统由阶
21、段k到阶段k+1的状态转移完全由阶段k的状态sk和决策uk(sk)所确定，与系统过去的状态s1,s2,sk-1及其决策u1(s1),u2(s2)uk-1(sk-1)无关。系统状态的这种转移，用数学公式描述即有：通常称式(1)为多阶段决策过程的状态转移方程。有些问题的状态转移方程不一定存在数学表达式，但是它们的状态转移，还是有一定规律可循的。)(,(1kkkkksusTs(1)2022年7月29日11时39分Page 18 of 77 8-2 动态规划基本概念动态规划基本概念(六六)指标函数指标函数 用来衡量策略或子策略或决策的效果的某种数量指标，就称为指标函数。它是定义在全过程或各子过程或各阶
22、段上的确定数量函数。对不同问题，指标函数可以是诸如费用、成本、产值、利润、产量、耗量、距离、时间、效用，等等。例如：图10-1的指标就是运费。v (1)阶段指标函数（也称阶段效应）。用gk(sk,uk)表示第k段处于sk状态且所作决策为uk(sk)时的指标，则它就是第k段指标函数，简记为gk。图1的gk值就是从状态sk到状态sk+1的距离。譬如，gk(v2,v5)=3,即v2到v5的距离为3。v (2)过程指标函数（也称目标函数）。用Rk(sk,uk)表示第k子过程的指标函数。如图10-1的Rk(sk,uk)表示处于第k段sk状态且所作决策为uk时，从sk点到终点v10的距离。由此可见，Rk(
23、sk,uk)不仅跟当前状态sk有关，还跟该子过程策略pk(sk)有关，因此它是sk和pk(sk)的函数，严格说来，应表示为:)(,(kkkkspsR2022年7月29日11时39分Page 19 of 77 8-2 动态规划基本概念动态规划基本概念v不过实际应用中往往表示为Rk(sk,uk)或Rk(sk)。还跟第k子过程上各段指标函数有关，过程指标函数Rk(sk)通常是描述所实现的全过程或k后部子过程效果优劣的数量指标，它是由各阶段的阶段指标函数gk(sk,uk)累积形成的，适于用动态规划求解的问题的过程指标函数（即目标函数），必须具有关于阶段指标的可分离形式对于部子过程的指标函数可以表示为：
24、式中，表示某种运算，可以是加、减、乘、除、开方等。v多阶段决策问题中，常见的目标函数形式之一是取各阶段效应之和的形式，即:v总之，具体问题的目标函数表达形式需要视具体问题而定。),(),(),(),(,nnn1k1k1kkkknn1k1kkknknkusgusgusgusususRR(2)nkiiiikusgR),(（3）nkiiiikusgR),(4)2022年7月29日11时39分Page 20 of 77 8-2 动态规划基本概念动态规划基本概念(七七)最优解最优解 用fk(sk)表示第k子过程指标函数 在状态sk下的最优值,即 称fk(sk)为第k子过程上的最优指标函数；与它相应的子策
25、略称为sk状态下的最优子策略，记为pk*(sk)；而构成该子策赂的各段决策称为该过程上的最优决策，记为:简记为)(,(kkkkspsRn21kspsRoptsfkkkksPpkkkKk,),(,()()()(,),(),(nn1k1kkksususun21ksusususpnn1k1kkkkk,),(,),(),()(n21kuuupn1kkk,2022年7月29日11时39分Page 21 of 77 8-2 动态规划基本概念动态规划基本概念v特别当k=1且s1取值唯一时，f1(s1)就是问题的最优值，而p1*就是最优策略。如例10-1只有唯一始点v1即s1取值唯一,故f1(s1)=18就是
26、例10-1的最优值，而:就是例10-1的最优策略。但若取值不唯一,则问题的最优值记为f0有 最优策略即为s1=s1*状态下的最优策略：我们把最优策略和最优值统称为问题的最优解。,109731vvvvp)()(11111Ss0ssfsfoptf11,),()(n211111uusussp2022年7月29日11时39分Page 22 of 77 8-2 动态规划基本概念动态规划基本概念v按上述定义，所谓最优决策 是指它们在全过程上整体最优(即所构成的全过程策略为最优)，而不一定在各阶段上单独最优。(八八)多阶段决策问题的数学模型多阶段决策问题的数学模型 综上所述，适于应用动态规划方法求解的一类多
27、阶段决策问题，亦即具有无后效性的多阶段决策问题的数学模型呈以下形式:),(n21kukn21kUuSsusTstsusususRRoptfkkkkkkk1knn2211uun1,),(.),(（5）2022年7月29日11时39分Page 23 of 77 8-2 动态规划基本概念动态规划基本概念v式中“OPT”表示最优化，视具体问题取max或min。v 上述数学模型说明了对于给定的多阶段决策过程，求取一个(或多个)最优策略或最优决策序列，使之既满足式(5)给出的全部约束条件，又使式(5)所示的目标函数取得极值，并且同时指出执行该最优策略时，过程状态演变序列即最优路线,n21uuu,1nn21
28、ssss2022年7月29日11时39分Page 24 of 77 8-3 动态规划基本原理动态规划基本原理一。最优化原理（贝尔曼最优化原理）作为一个全过程的最优策略具有这样的性质：对于最优策略过程中的任意状态而言，无论其过去的状态和决策如何，余下的诸决策必构成一个最优子策略。该原理的具体解释是，若某一全过程最优策略为：则对上述策略中所隐含的任一状态而言，第k子过程上对应于该状态的最优策略必然 包含在上述全过程最优策略p1*中，即为：)(),(,),(),()(nnkk221111sususususp)(,),(),()(11nnkkkkkksusususp2022年7月29日11时39分Pa
29、ge 25 of 77 8-3 动态规划基本原理动态规划基本原理二。动态规划方法的基本步骤二。动态规划方法的基本步骤1.应将实际问题恰当地分割成n个子问题(n个阶段)。通常是根据时间或空间而划分的，或者在经由静态的数学规划模型转换为动态规划模型时，常取静态规划中变量的个数n，即k=n。2.正确地定义状态变量sk，使它既能正确地描述过程的状态，又能满足无后效性动态规划中的状态与一般控制系统中和通常所说的状态的概念是有所不同的，动态规划中的状态变量必须具备以下三个特征：(1)要能够正确地描述受控过程的变化特征。(2)要满足无后效性。即如果在某个阶段状态已经给定，那么在该阶段以后，过程的发展不受前面
30、各段状态的影响，如果所选的变量不具备无后效性，就不能作为状态变量来构造动态规划的模型。(3)要满足可知性。即所规定的各段状态变量的值，可以直接或间接地测算得到。一般在动态规划模型中，状态变量大都选取那种可以进行累计的量。此外，在与静态规划模型的对应关系上，通常根据经验，线性与非线性规划中约束条件的个数，相当于动态规划中状态变量sk的维数而前者约束条件所表示的内容，常常就是状态变量sk所代表的内容。2022年7月29日11时39分Page 26 of 77 8-3 动态规划基本原理动态规划基本原理3正确地定义决策变量及各阶段的允许决策集合Uk(sk)，根据经验，一般将问题中待求的量，选作动态规划
31、模型中的决策变量。或者在把静态规划模型(如线性与非线性规划)转换为动态规划模型时，常取前者的变量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)函数 对其
32、变元Rk+1来说要严格单调。),(,),(,1n1k1kkkk1n1k1kkknkssRussususR),(,1n1k1kkkkssRus2022年7月29日11时39分Page 27 of 77 8-3 动态规划基本原理动态规划基本原理6写出动态规划函数基本方程例如常见的指标函数是取各段指标和的形式 其中 表示第i阶段的指标，它显然是满足上述三个性质的。所以上式可以写成：nkiiiikkusgsR),()(),(),(1n1k1kkkkkssRusgR),(iiiusg2022年7月29日11时39分Page 28 of 77 8-4 动态规划的应用动态规划的应用最短路问题最短路问题一一.
33、求最短路径问题求最短路径问题v例例8-28-2BACBDBCDEC212312312511214106104131211396581052 阶段 1 阶段 2 阶段 3 阶段 4 阶段 5 2022年7月29日11时39分Page 29 of 77 8-4 动态规划的应用动态规划的应用最短路问题最短路问题v将问题分成五个阶段，第k阶段到达的具体地点用状态变量xk表示，例如：x2=B3表示第二阶段到达位置B3，等等。这里状态变量取字符值而不是数值。v将决策定义为到达下一站所选择的路径，例如目前的状态是x2=B3，这 时 决 策 允 许 集 合 包 含 三 个 决 策，它 们 是D2(x2)=D2
34、(B3)=B3C1,B3C2,B3C3v最优指标函数最优指标函数fk(xk)表示从目前状态到表示从目前状态到E E的最短路径。终端条件的最短路径。终端条件为为 f5(x5)=f5(E)=0v其含义是从其含义是从E E到到E E的最短路径为的最短路径为0 0。第四阶段的递推方程为:f xv x df xdDx4444455444()min(,)()()2022年7月29日11时39分Page 30 of 77 8-4 动态规划的应用动态规划的应用最短路问题最短路问题v其中*表示最优值，在上表中，由于决策允许集合D4(x4)中的决策是唯一的，因此这个值就是最优值。v由此得到f4(x4)的表达式。由
35、于这是一个离散的函数，取值用列表表示：x4D4(x4)x5v4(x4,d4)v4(x4,d4)+f5(x5)f4(x4)最优决策 d4*D1D1E E55+0=5*5D1ED2D2E E22+0=2*2D2Ef4(x4)的表达式 x4 f4(x4)最优决策 d4*D1 5 D1E D2 2 D2E 2022年7月29日11时39分Page 31 of 77 8-4 动态规划的应用动态规划的应用最短路问题最短路问题v第三阶段的递推方程为：第三阶段的递推方程为：)(),(min)(44333)(33333xfdxvxfxDd 从 f4(x4)到 f3(x3)的递推过程用表格表示如下：x3 D3(x
36、3)x4 v3(x3,d3)v3(x3,d3)+f4(x4)f3(x3)最优决策d3*C1 C1D1 C1D2 D1 D2 3 9 3+5=8*9+2=11 8 C1D1 C2 C2D1 C2D2 D1 D2 6 5 6+5=11 5+2=7*7 C2D2 C3 C3D1 C3D2 D1 D2 8 10 8+5=13 10+2=12*12 C3D2 2022年7月29日11时39分Page 32 of 77 8-4 动态规划的应用动态规划的应用最短路问题最短路问题v由此得到由此得到f f3 3(x x3 3)的表达式：的表达式：x3 f3(x3)最 优 决 策d3*C1 8 C1D1 C2 7
37、 C2D2 C3 12 C3D2 第二阶段的递推方程为：)(),(min)()(33222xDd22xfdxvxf222从f3(x3)到f2(x2)的递推过程用表格表示如下：2022年7月29日11时39分Page 33 of 77 8-4 动态规划的应用动态规划的应用最短路问题最短路问题x2 D2(x2)x3 v2(x2,d2)v2(x2,d2)+f3(x3)f2(x2)最优决策d2*B1 B1C1 B1C2 B1C3 C1 C2 C3 12 14 10 12+8=20*14+7=21 10+12=22 20 B1C1 B2 B2C1 B2C2 B2C3 C1 C2 C3 6 10 4 6+
38、8=14*10+7=17 4+12=16 14 B2C1 B3 B3C1 B3C2 B3C3 C1 C2 C3 13 12 11 13+8=21 12+7=19*11+12=23 19 B3C2 2022年7月29日11时39分Page 34 of 77 8-4 动态规划的应用动态规划的应用最短路问题最短路问题v由此得到由此得到f f2 2(x x2 2)的表达式：的表达式：x2 f2(x2)最优决策 d2*B1 20 B1C1 B2 14 B2C1 B3 19 B3C2 第一阶段的递推方程为：第一阶段的递推方程为：)(),(min)(22111)(11111xfdxvxfxDd 2022年7
39、月29日11时39分Page 35 of 77 8-4 动态规划的应用动态规划的应用最短路问题最短路问题v从f2(x2)到f1(x1)的递推过程用表格表示如下：x1 D1(x1)x2 v1(x1,d1)v1(x1,d1)+f2(x2)f1(x1)最优决策d1*A A B1 A B2 AB3 B1 B2 B3 2 5 1 2+20=22 5+14=19*1+19=20 19 A B 2 由此得到f1(x1)的表达式x1 f1(x1)最优决策 d1*A 19 A B2 从表达式f1(x1)可以看出，从A到E的最短路径长度为19。由f1(x1)向f4(x4)回朔，得到最短路径为：A B2 C1 D1
40、 E 2022年7月29日11时39分Page 36 of 77 8-4 动态规划的应用动态规划的应用资源分配问题资源分配问题二二.资源分配问题资源分配问题所谓资源分配问题，就是将供应量有限的一种或若干种资源（例如原材料、资金、机器设备、劳动、食品等），分配给若干个使用者，而使目标函数为最优。问题的提出：设有某种原材料，总量为a，用于生产n种产品。若分配数量为yi的原材料生产第i种产品，其效益为g(yi)。问应如何分配，才能使生产n种产品的总收入最大?问题的求解：在应用动态规划方法求解资源分配问题时，通常以把资源分配给一个或几个使用者的过程作为一个阶段；把规划问题中的变量取为决策变量；把累计的
41、量或随递推过程变化的量选为状态变量。2022年7月29日11时39分Page 37 of 77 8-4 动态规划的应用动态规划的应用资源分配问题资源分配问题v例例8-3:8-3:有资金有资金4 4万元，投资万元，投资A A、B B、C C三个项目，每个项目的投三个项目，每个项目的投资效益与投入该项目的资金有关。三个项目资效益与投入该项目的资金有关。三个项目A A、B B、C C的投资效的投资效益（万吨）和投入资金（万元）关系见下表：益（万吨）和投入资金（万元）关系见下表：v求对三个项目的最优投资分配，使总投资效益最大。1.阶段k：每投资一个项目作为一个阶段；2.状态变量xk：投资第k个项目前的
42、资金数；3.决策变量dk：第k个项目的投资；4.决策允许集合：0dkxk状态转移方程：xk+1=xk-dk阶段指标：vk(xk,dk)见表中所示；5.递推方程：fk(xk)=maxvk(xk,dk)+fk+1(xk+1)6.终端条件：f4(x4)=0 项目 投入资金 A B C 1 万元 15 万吨 13 万吨 11 万吨 2 万元 28 万吨 29 万吨 30 万吨 3 万元 40 万吨 43 万吨 45 万吨 4 万元 51 万吨 55 万吨 58 万吨 2022年7月29日11时39分Page 38 of 77 8-4 动态规划的应用动态规划的应用资源分配问题资源分配问题vk=4，f4(
43、x4)=0k=3，0d3x3，x4=x3-d3x3 D3(x3)x4 v3(x3,d3)v3(x3,d3)+f4(x4)f3(x3)d3*0 0 0 0 0+0=0 0 0 0 1 0 0+0=0 1 1 0 11 11+0=11*11 1 0 2 0 0+0=0 1 1 11 11+0=11 2 2 0 30 30+0=30*30 2 0 3 0 0+0=0 1 2 11 11+0=11 2 1 30 30+0=30 3 3 0 45 45+0=45*45 3 0 4 0 0+0=0 1 3 11 11+0=11 2 2 30 30+0=30 3 1 45 45+0=45 4 4 0 58
44、58+0=58*58 4 2022年7月29日11时39分Page 39 of 77 8-4 动态规划的应用动态规划的应用资源分配问题资源分配问题K=2:x2 D2(x2)x3 v2(x2,d2)v2(x2,d2)+f3(x3)f2(x2)d2*0 0 0 0 0+0=0 0 0 0 1 0 0+11=11 1 1 0 13 13+0=13*13 1 0 2 0 0+30=30*1 1 13 13+11=24 2 2 0 29 29+0=29 30 0 0 3 0 0+45=45*1 2 13 13+30=43 2 1 29 29+11=40 3 3 0 43 43+0=43 45 0 0 4
45、 0 0+58=58 1 3 13 13+45=58 2 2 29 29+30=59*3 1 43 43+11=54 4 4 0 55 55+0=55 59 2 2022年7月29日11时39分Page 40 of 77 8-4 动态规划的应用动态规划的应用资源分配问题资源分配问题vk=1，0d1x1，x2=x1-d1x1 D1(x1)x2 v1(x1,d1)v1(x1,d1)+f2(x2)f1(x1)d1*0 4 0 0+59=59 1 3 15 15+45=60*2 2 28 28+30=58 3 1 40 40+13=53 4 4 0 51 51+0=51 60 1 最优解为x1=4,d
46、1*=1,x2=x1-d1=3,d2*=0,x3=x2-d2*=3,d3=3,x4=x3-d3=0，即项目A投资1万元，项目B投资0万元，项目C投资3万元，最大效益为60万吨。2022年7月29日11时39分Page 41 of 77 8-4 动态规划的应用动态规划的应用生产与库存问题生产与库存问题三三.生产与库存问题生产与库存问题问题的提出：一个生产项目，在生产批量、生产成本费用、存储费用以及市场对产品的要求情况都是确定数值的条件下，为了根据需要制订计划，必须正确决定不同时期的生产量和库存量，以期在满足市场需求的条件下使生产与库存的费用最低。一般的解决方法：以计划的不同时期为不同的阶段 k；
47、状态变量 xk 取为第k阶段开始时的库存量；决策变量k为第k阶段（时期）的生产量；状态转移方程为：为第k阶段的阶段指标，代表这一时期的成本。则此问题的动态规划递推关系式为：kkkkduxx1),(kkkuxC2022年7月29日11时39分Page 42 of 77 8-4 动态规划的应用动态规划的应用生产与库存问题生产与库存问题例例8-4:8-4:一个工厂生产某种产品,1-7月份生产成本和产品需求量的变化情 况如下表：为了调节生产生产和需求，工厂设有一个产品仓库，库容量H=9。已知期初库存量为2，要求期末（七月低）库存量为0。每个月生产的产品在月末入库，月初根据当月需求发货。求七个月的生产量
48、，能满足各月的需求，并使生产成本最低。0)(1,2,.,1,),(),(min)(1110nnkkkkkkkdukkxfnnkduxfxucxfkk月份(k)1 2 3 4 5 6 7 生产成本(ck)11 18 13 17 20 10 15 需求量(rk)0 8 5 3 2 7 4 2022年7月29日11时39分Page 43 of 77 8-4 动态规划的应用动态规划的应用生产与库存问题生产与库存问题v阶段k：月份，k=1,2,7,8；v状态变量xk：第k个月初（发货以前）的库存量；v决策变量dk：第k个月的生产量；v状态转移方程：xk+1=xk-rk+dk；v决策允许集合：vDk(xk
49、)=dk|dk0,rk+1xk+1H =dk|dk0,rk+1xk-rk+dkH；v阶段指标：vk(xk,dk)=ckdk；终端条件：f8(x8)=0,x8=0；v递推方程：递推方程：f fk k(x xk k)=)=minminv vk k(x xk k ,d,dk k)+)+f fk k+1+1(x xk k+1+1)d dk k D Dk k(x(xk k)=min =minc ck kd dk k+f fk k+1+1(x xk k-r rk k+d dk k)d dk k D Dk k(x xk k)2022年7月29日11时39分Page 44 of 77 8-4 动态规划的应用动
50、态规划的应用生产与库存问题生产与库存问题v对于k=7v因为 x8=0 有:d7=0v递推方程为:v f7(x7)=minc7d7+f8(x8)=0 d7=0v对于对于k k=6=6 因为d7=0，所以x7=r7=4 而x6-r6+d6=x7=4 因此有d6=x7+r6-x6=4+7-x6=11-x6也是唯一的决策。因此递推方程为：f6(x6)=minc6d6+f7(x7)d6=11-x6=10d6=10(11-x6)=110-10 x62022年7月29日11时39分Page 45 of 77 8-4 动态规划的应用动态规划的应用生产与库存问题生产与库存问题v对于对于k k=5=5vf f5
