动态规划基本概念

1、动态规划动态规划 动态规划动态规划Dynamic Programming 线性规划和非线性规划有一个共同特点线性规划和非线性规划有一个共同特点:静态性静态性,叙述和叙述和解决问题都是针对某一时刻发生的情况解决问题都是针对某一时刻发生的情况.当问题包含有与时间相关的变量时当问题包含有与时间相关的变量时,就要用到就要用到 运筹学运筹学的另一分支的另一分支:动态规划动态规划一种解决多阶段决策过程的最优化方法一种解决多阶段决策过程的最优化方法动态规划产生于动态规划产生于50年代初年代初. 是由是由美国数学家美国数学家Richard Bellman 首先提出的首先提出的. 他于他于1957年出版了第一本

2、关于动年出版了第一本关于动态规划方面的书态规划方面的书. 所以把动态规划的创始人归属于他所以把动态规划的创始人归属于他. 目前目前,动态规划在工程技术、经济、工业生产及军事动态规划在工程技术、经济、工业生产及军事等部门中有着广泛的应用等部门中有着广泛的应用,并获得显著的效果。并获得显著的效果。1.动态规划的基本概念和基本方法动态规划的基本概念和基本方法 一一.多阶段决策问题多阶段决策问题 1.多阶段决策问题：多阶段决策问题：是一类决策过程是一类决策过程,将过程分为若将过程分为若 干个互相联系的阶段干个互相联系的阶段,而在每一阶段都需要做而在每一阶段都需要做 出决策出决策,并且一个阶段的决策确定

3、以后并且一个阶段的决策确定以后,常影响下常影响下 一个阶段的决策一个阶段的决策,从而影响整个过程的活动路线从而影响整个过程的活动路线 2. 策略：策略：各个阶段所确定的决策就构成一个决策序各个阶段所确定的决策就构成一个决策序 列列,通常称谓一个通常称谓一个策略策略.由于每一阶段可供选择的决策往往不止一个由于每一阶段可供选择的决策往往不止一个,因而就形成因而就形成有许多策略可供我们选择有许多策略可供我们选择,对应一个策略就有确定的效果对应一个策略就有确定的效果,这个效果可用数量来衡量的这个效果可用数量来衡量的,这样不同策略这样不同策略,效果也不同。效果也不同。12n状态状态状态状态状态状态状态状

4、态状态状态决策决策决策决策决策决策一一.多阶段决策问题多阶段决策问题 在多阶段决策问题中在多阶段决策问题中,阶段可以用时段表示阶段可以用时段表示,在各个在各个时间阶段时间阶段,采取的决策随时间而变动采取的决策随时间而变动,这就是这就是”动态动态”的含义。的含义。动态规划在一定条件下动态规划在一定条件下也可解决一些与时间无关也可解决一些与时间无关的静态规划中的最优化问题的静态规划中的最优化问题,只要人为地引进只要人为地引进”时时段段”因素即可因素即可.多阶段决策问题多阶段决策问题,就是要在允许选择的那些策略中间就是要在允许选择的那些策略中间,选选 择一个最优策略择一个最优策略,使在确定的标准下达

5、到最好的效果使在确定的标准下达到最好的效果例例1.最短路问题最短路问题 设某公司自外国进口一台大型机床设某公司自外国进口一台大型机床,由工厂至出口港由工厂至出口港,有有三港口可供选择三港口可供选择,而进口港又有三个可供选择而进口港又有三个可供选择,进口后可进口后可经由两个城市到达目的地经由两个城市到达目的地,其间的运输路线如下图其间的运输路线如下图,试求试求总距离最短的路线总距离最短的路线? 出口港 进口港 B1 70 C1 10 20 40 D1 A 40 B2 20 C2 E 30 D2 40 B3 C3 第一阶段 | 第二阶段第二阶段 | 第三阶段第三阶段 | 第四阶段第四阶段50 30

6、 30 30 30 60 40 10 40 40 30 60 例例2. 生产计划问题生产计划问题 某车间需要按月在月底供应一定数量的某种部件给总某车间需要按月在月底供应一定数量的某种部件给总装车间装车间.由于生产条件的变化由于生产条件的变化,该车间在该车间在各月份中生产各月份中生产每单部件所耗工时不同每单部件所耗工时不同.各月份的生产各月份的生产,除供应该月需除供应该月需求之外求之外,余下部分存入仓库余下部分存入仓库,但因仓库容量的限制但因仓库容量的限制,库存库存部件的数量部件的数量不能超过某一给定的值不能超过某一给定的值H,已知半年的各月已知半年的各月份的需求量及在这些月份生产部件的所需工时

7、如下表份的需求量及在这些月份生产部件的所需工时如下表:月份K 0 1 2 3 4 5 6 需求量Dk 0 8 5 3 2 7 4 单位工时Ak 11 18 13 17 20 10 设设库存容量库存容量H=9,开始库存量开始库存量为为2,期末库存量期末库存量为为0,要求要求制订一个半年的逐月生产计划制订一个半年的逐月生产计划,使满足要求使满足要求,又使生产又使生产的的总耗费工时最少总耗费工时最少.二二.动态规划的基本概念动态规划的基本概念 1.阶段阶段(Stage) 2.状态状态(State)表示某阶段的出发位置表示某阶段的出发位置,也是每一个决策阶段中也是每一个决策阶段中不同的初始条件不同的初

8、始条件.状态变量状态变量 状态集合状态集合 某一阶段的所有状态构成的集合某一阶段的所有状态构成的集合,用表示用表示Sk表示表示3.决策变量决策变量决策是在某阶段状态给定后，从该阶段演变到下一决策是在某阶段状态给定后，从该阶段演变到下一阶段的某状态的选择。描述决策的变量称为决策变阶段的某状态的选择。描述决策的变量称为决策变量量 ,uk(sk )表示第表示第k阶段状态为阶段状态为sk时的决策时的决策 允许决策集合允许决策集合 决策变量的取值范围决策变量的取值范围用用Dk(sk)表示第表示第k阶段从状态阶段从状态sk 出发的允许决策集合，故出发的允许决策集合，故 uk(sk ) Dk(sk)就是事物

9、在发展过程中从一个状态开始到结束就是事物在发展过程中从一个状态开始到结束的过程的过程.通常用通常用k表示阶段变量表示阶段变量, 阶段编号一般采阶段编号一般采用顺序编号用顺序编号,也可用逆序编号也可用逆序编号.描述过程状态的变量描述过程状态的变量,通常用通常用sk表示第表示第k阶段的某一状态阶段的某一状态二二.动态规划的基本概念动态规划的基本概念(2)4.策略策略由每一阶段的决策由每一阶段的决策uk(sk ) (k=1,2,.,n)组成的决策函组成的决策函数序列称为数序列称为全过程策略全过程策略，简称为，简称为策略策略，记为，记为p1,n全过程全过程 由第一阶段开始到终点为止的过程，称为问题的全

10、过程由第一阶段开始到终点为止的过程，称为问题的全过程允许策略集合允许策略集合可供选择的策略范围。用可供选择的策略范围。用P表示表示最优策略最优策略k子过程子过程在允许策略集合中，使整个问题达到最优效果的策略在允许策略集合中，使整个问题达到最优效果的策略由第由第k阶段开始到终点为止的过程，称为阶段开始到终点为止的过程，称为原问题的原问题的k后部子过程后部子过程（或称为（或称为k子过程子过程）k子过程策略子过程策略k子过程的决策函数序列。子过程的决策函数序列。简称子策略简称子策略记作：记作：pk,n= uk(sk ) , uk+1(sk+1 ), un(sn ) 最短路最短路二二.动态规划的基本概

11、念动态规划的基本概念(3)5.指标函数指标函数:是用来衡量所实现过程的优劣的一种数量指标。是用来衡量所实现过程的优劣的一种数量指标。(或称效益函数或称效益函数) 阶段指标阶段指标(或阶段效益或阶段效益)： 在每一阶段的每一状态作出一决策时都对在每一阶段的每一状态作出一决策时都对 应一个效果值应一个效果值,此效果值此效果值称为阶段效益称为阶段效益.记记vk(sk,uk) 表示在状态表示在状态sk下取定决策下取定决策uk时时,第第k阶段的效益阶段的效益指标函数或效益函数是指标函数或效益函数是定义在全过程和后部子过程上的一定义在全过程和后部子过程上的一个确定的数量函数个确定的数量函数,用用Vk,n表

12、示表示,即即最优指标函数最优指标函数：Vk,n=Vk,n(sk,uk,sk+1,uk+1,sn,un) k=1,2,n指标函数指标函数Vk,n的最优值称为相应的最优指标函数或最优效益的最优值称为相应的最优指标函数或最优效益函数函数,记作记作fk( sk),*,()(,)(,)k nk nkkk nkk nk nkk npPfsVspopt Vsp二二.动态规划的基本概念动态规划的基本概念(4)6.状态转移方程：状态转移方程：确定由一个状态到另一个状态的演变过程确定由一个状态到另一个状态的演变过程.若若给定第给定第k阶段状态变量阶段状态变量sk的值的值,且该阶段的决策变量且该阶段的决策变量uk一

13、经确定一经确定 ,则第则第k+1阶段的状态变量阶段的状态变量sk+1也随之确定也随之确定,即即sk+1是是sk和和uk的函数的函数,记为记为sk+1=Tk(sk,uk),它描述了由第它描述了由第k阶段到第阶段到第k+1阶段的状态转移规律阶段的状态转移规律,称为称为状态转移方程状态转移方程.在不同问题中在不同问题中,最优指标函数最优指标函数fk( sk)表示的意义不一样表示的意义不一样,可以是费用可以是费用,成本成本,距离距离三三.动态规划求解的思想和方法动态规划求解的思想和方法 我们以最短路问题为例，分析动态规划求解多阶我们以最短路问题为例，分析动态规划求解多阶段决策过程的方法。段决策过程的方

14、法。将问题分成四个阶段：将问题分成四个阶段：k=1，2，3，4阶段指标为阶段指标为dk(sk,uk)表示从点表示从点sk到点到点uk(sk)的距离；的距离；fk(sk)表示从第表示从第k阶段状态阶段状态sk出发到终点出发到终点E的最短距离；的最短距离；uk*(sk)表示第表示第k阶段状态为阶段状态为sk时的最优决策时的最优决策则该最短路问题是则该最短路问题是求求f1(s1) ：从：从A点到点到E点的最短距离点的最短距离我们从最后一个阶段开始，往前递推。我们从最后一个阶段开始，往前递推。 称为逆序递推法称为逆序递推法例例1.设状态变量设状态变量sk表示第表示第k阶段的始点；阶段的始点；设决策变量

15、设决策变量uk(sk)表示第表示第k阶段的终点；阶段的终点；状态转移方程为：状态转移方程为：sk+1=uk(sk)；最短路问题（最短路问题（2） 第四阶段第四阶段 k=4状态变量状态变量s4可取可取D1，D2d4(D1，E)=30d4(D2，E)=40f4（D1）=30f4（D2）=40 s4 u4(s4) f4(s4)=d4 D1 E 30 E D2 E 40 Eu4*(s4)例例1.最短路问题（最短路问题（3）第三阶段第三阶段 k=3状态变量状态变量s3可取可取C1，C2，C3s3u3d3(s3,u3)s4d3+f4f3u*3C1D110D110+30D240D240+4040D1C2D1

16、60D160+30D230D230+4070D2C3D130D130+30D230D230+4060D1例例1.f4（D1）=30f4（D2）=40最短路问题（最短路问题（4）第二阶段第二阶段 k=2状态变量状态变量s2可取可取B1，B2，B3f3(C1)=40，f3(C2)=70，f3(C3)=60s2u2d2(s2,u2)s3d2+f3f2u*2B1C170C170+40C240C240+70110C1C2B2C130C130+40C220C220+7070C1B3C140C140+40C210C210+7080C1C2C360C360+60C340C340+60C350C350+60例例

17、1.最短路问题（最短路问题（5）第一阶段第一阶段 k=1状态变量状态变量s1可取可取A1f2(B1)=110，f2(B2)=70，f2(B3)=80最短路最短路 ：f1(A)=110用顺向追踪：用顺向追踪：最优路径为最优路径为AB2 C1 D1 E或：或：A B3 C1 D1 E或：或：A B3 C2 D2 E例例1.s1u1d1(s1,u1)s2d1+f2f1u*1AB120B120+110B240B240+70110B330B330+80B2B3最短路问题（最短路问题（6）动态规划的方法比穷举法有以下优点：动态规划的方法比穷举法有以下优点：(1) 减少了计算量，而且随着段数的增加，计算量将

18、大减少了计算量，而且随着段数的增加，计算量将大大地减少；大地减少；(2)丰富了计算结果。在逆序解法中，我们得到的不仅仅丰富了计算结果。在逆序解法中，我们得到的不仅仅是由是由A点到点到E点的最短路线及相应的距离，而且得到了点的最短路线及相应的距离，而且得到了从所有各中间点出发到从所有各中间点出发到E点的最短路线及相应的距离。点的最短路线及相应的距离。这对许多实际问题来讲，是很有意义的。这对许多实际问题来讲，是很有意义的。四四. 动态规划的基本方程和最优化原理动态规划的基本方程和最优化原理我们在求最短路的例子中可看出我们在求最短路的例子中可看出首先首先从最后一个阶段从最后一个阶段(k=4)计算最短

19、距离计算最短距离其次其次考虑第三个阶段考虑第三个阶段(k=3),计算最短距离计算最短距离很明显很明显,上述求解过程利用了上述求解过程利用了第第k阶段与第阶段与第k+1阶段之间的关系阶段之间的关系:f4(s4)=d4(s4,E)f3(s3)=mind3(s3,u3)+f4(s4), u3(s3) D3(s3)再次再次考虑第二个阶段考虑第二个阶段(k=2),计算最短距离计算最短距离f2(s2)=mind2(s2,u2)+f3(s3), u2(s2) D2(s2)最后最后考虑第一个阶段考虑第一个阶段(k=1),计算最短距离计算最短距离fk(sk)=mindk(sk,uk)+fk+1(sk+1), k

20、=4,3,2,1f1(s1)=mind1(s1,u1)+f2(s2), u1(s1) D1(s1)f5(s5)=0四四. 动态规划的基本方程和最优化原理动态规划的基本方程和最优化原理(2) fk(sk)=mindk(sk,uk)+fk+1(sk+1), uk(sk) Dk(sk) k=4,3,2,1f5(s5)=0或或 f4(s4)=d4(s4, E)这种递推关系这种递推关系,称为称为动态规划的基本方程动态规划的基本方程一般的动态规划基本方程可以表为：一般的动态规划基本方程可以表为：fk(sk)=optvk(sk,uk)+fk+1(sk+1), uk(sk) Dk(sk) k=n,n-1,1f

21、n+1(sn+1)=0或称为或称为动态规划的函数基本方程动态规划的函数基本方程式中式中opt可根据题意取可根据题意取min或或max,vk(sk,uk)为状态为状态sk,决策决策uk时对应的第时对应的第k阶段的指标函数值阶段的指标函数值四四. 动态规划的基本方程和最优化原理动态规划的基本方程和最优化原理(3)动态规划最优化原理动态规划最优化原理：“作为整个过程的最优策略具有这样的性质：无论过去作为整个过程的最优策略具有这样的性质：无论过去的状态和决策如何，对前面的决策所形成的状态而言，的状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。余下的诸决策必须构成最优策略。”

22、这一原理是由这一原理是由美国运筹学家美国运筹学家Richard Bellman首先提首先提出来的。出来的。 利用这一原理利用这一原理,可以可以 把多阶段决策问题的求解过程看作把多阶段决策问题的求解过程看作是一个连续的递推过程是一个连续的递推过程,由后向前逐步推算由后向前逐步推算,在求解时在求解时,各各状态前面的状态和决策状态前面的状态和决策,对其后的子过程来说对其后的子过程来说,只不过相只不过相当于初始条件而已当于初始条件而已,并不影响后面过程的最优策略并不影响后面过程的最优策略.动态规划的最优化原理的数学表达式如下动态规划的最优化原理的数学表达式如下:四四. 动态规划的基本方程和最优化原理动

23、态规划的基本方程和最优化原理(4)fk(sk)=optvk(sk,uk(sk)+fk+1(sk+1), uk(sk) Dk(sk)Opt是最优化是最优化optimization的缩写的缩写uk-是第是第k阶段的决策变量阶段的决策变量sk-是第是第k阶段的状态变量阶段的状态变量fk(sk)-是第是第k阶段状态为阶段状态为sk时的最优效益值时的最优效益值 fk+1(sk+1)-是第是第k+1阶段状态为阶段状态为sk+1时的最优效益值时的最优效益值 sk+1=Tk(sk,uk) ,故故 sk+1是由是由sk和和uk所确定所确定 由最优化原理的数学表达式可知由最优化原理的数学表达式可知, 当某一决策选

24、定后当某一决策选定后,它有两方面的影响它有两方面的影响: (1)是直接影响本阶段的效益是直接影响本阶段的效益vk(sk,xk) (2)是影响后面第是影响后面第k+1阶段的初始状态阶段的初始状态,因而因而影响影响 第第k+1阶段的最优效益阶段的最优效益fk+1(sk+1). 最优策略的选取是综合两者统一考虑而决定的最优策略的选取是综合两者统一考虑而决定的 五五. 动态规划模型的建立与求解动态规划模型的建立与求解1.按问题所处的按问题所处的时间或空间恰当地分成若干个阶段时间或空间恰当地分成若干个阶段 一般地一般地,建立动态规划模型的步骤建立动态规划模型的步骤:2.正确地选择状态变量正确地选择状态变

25、量sk:它必须有两个特征它必须有两个特征(1)可知性可知性:即过程演变的各个阶段状态变量的取值即过程演变的各个阶段状态变量的取值, 能直接或间接地确定能直接或间接地确定 3.确定决策确定决策uk,及每个阶段的允许决策集合及每个阶段的允许决策集合Dk(sk)4.写出状态转移方程写出状态转移方程: sk+1=Tk(sk,uk )5.列出阶段效益列出阶段效益vk(sk,uk)及效益函数及效益函数 fk(sk)6.写出递推方程写出递推方程(2)无后效性无后效性:即在给定某阶段的状态时即在给定某阶段的状态时,以后各阶段以后各阶段 的行进不受以前各阶段状态的影响的行进不受以前各阶段状态的影响. 五五. 动

26、态规划模型的求解动态规划模型的求解(2)常用的两种基本方法常用的两种基本方法: 逆序解法逆序解法-寻优的方向与多阶段决策过程的实际行进寻优的方向与多阶段决策过程的实际行进 方向相反方向相反,从最后一个阶段开始计算逐段前从最后一个阶段开始计算逐段前 推推,求得全过程的最优策略求得全过程的最优策略.顺序解法顺序解法-寻优的方向与多阶段决策过程的实际行进寻优的方向与多阶段决策过程的实际行进 方向相同方向相同,从第一个阶段开始计算逐段向后从第一个阶段开始计算逐段向后 递推递推,计算后一阶段要用到前一阶段的求优结计算后一阶段要用到前一阶段的求优结 果果,最后一段的结果就是全过程的最优结果最后一段的结果就

27、是全过程的最优结果.逆序解法与顺序解逆序解法与顺序解 法法. 顺序解法求解例顺序解法求解例1我们以最短路问题为例，分析动态规划的顺序解我们以最短路问题为例，分析动态规划的顺序解法：法：将问题分成四个阶段：将问题分成四个阶段：k=1，2，3，4dk(sk+1,uk,)表示从点表示从点uk(sk+1) 到点到点sk+1的距离的距离fk(sk+1)表示从起点表示从起点A出发到第出发到第k阶段状态阶段状态sk+1的最短距离；的最短距离；uk*(sk+1)表示第表示第k阶段状态为阶段状态为sk+1时的最优决策时的最优决策则该最短路问题是则该最短路问题是求求f4(E) ：从：从A点到点到E点的最短距离点的

28、最短距离我们从第一个阶段开始，往后递推。我们从第一个阶段开始，往后递推。 称为顺序递推法称为顺序递推法例例1.设状态变量设状态变量sk+1表示第表示第k阶段的终点；阶段的终点；设决策变量设决策变量uk(sk+1)表示第表示第k阶段的始点；阶段的始点；状态转移方程为：状态转移方程为：sk=uk(sk+1)；顺序解法求解例顺序解法求解例1 （2）例例1.d1(A，B2)=40f1（B1）=20f1（B2）=40d1(A，B3)=30f1（B3）=30d1(A，B1)=20s2u1f1u*1AB1B220B3AA4030AAA k=2时，时，状态变量状态变量s3可取可取C1，C2，C3 k=0时，时

29、，f0(s1)=f0(A)=0,这是边界条件。这是边界条件。 k=1时，时，状态变量状态变量s2可取可取B1，B2，B3顺序解法求解例顺序解法求解例1 （3）f1(B1)=20，f1(B2)=40，f1(B3)=30s3u2d2(s3,u2)s2d2+f1f2u*2C1B170B170+20B230 B230+4070B2B3C2B140B140+20B220B220+4040B3C3B160B160+20B240B240+4080B1B2B3B340B340+30B310B310+30B350B350+30例例1.顺序解法求解例顺序解法求解例1 （4）例例1.s4u3d3(s4,u3)s3d

30、3+f2f3u*2D1C110C110+70C260C260+4080C1D2C140C140+70C230C230+4070C2C330C330+80C330C330+80 k=3时，时， 状态变量状态变量s4可取可取D1，D2f2(C1)=70，f2(C2)=40，f2(C3)=80 k=4时，时， 状态变量状态变量s5只能取只能取Ef3(D1)=80，f3(D2)=70顺序解法求解例顺序解法求解例1 （5）s5u4d4(s5,u4)s4d4+f3f4u*4ED130D130+80D240D240+70110D1D2最短路最短路 ：f4(E)=110最优路径为最优路径为 AB2 C1 D1

31、 E或：或：A B3 C1 D1 E或：或：A B3 C2 D2 E顺序解法的基本方程顺序解法的基本方程我们在求最短路的例子中可看出我们在求最短路的例子中可看出:上述求解过程利用了上述求解过程利用了第第k阶段与第阶段与第k+1阶段之间的关系阶段之间的关系:fk(sk+1)=mindk(sk+1,uk)+fk-1(sk), k=1,2,3,4f0(s1)=0一般的动态规划基本方程可以表为：一般的动态规划基本方程可以表为：fk(sk+1)=optvk(sk+1,uk)+fk-1(sk), uk(sk) Dk(sk) k=1,2,nf0(s1)=0式中式中opt可根据题意取可根据题意取min或或ma

32、x,vk(sk+1,uk)为状态为状态sk+1,决策决策uk时对应的第时对应的第k阶段的指标函数值阶段的指标函数值五五. 动态规划模型的求解动态规划模型的求解(3)逆序解法与顺序解法本质上并无区别逆序解法与顺序解法本质上并无区别一般地一般地,当初始状态给定时可用逆序解法当初始状态给定时可用逆序解法当终止状态给定时可用顺序解当终止状态给定时可用顺序解 法法什么时侯用逆序解法或用顺序解法较好什么时侯用逆序解法或用顺序解法较好?若若问题给定了一个初始状态与一个终止状态问题给定了一个初始状态与一个终止状态,则则两种方法均可使用两种方法均可使用.使用上述两种方法求解时，除了求解的行进方向不同使用上述两种

33、方法求解时，除了求解的行进方向不同外，在建模时要注意以下区别：外，在建模时要注意以下区别：逆序解法与顺序解法在建模时的区别：逆序解法与顺序解法在建模时的区别：(1) 状态转移方程不同：状态转移方程不同：逆序算法：逆序算法： sk+1=Tk(sk,uk),称为由状态称为由状态sk到到sk+1的顺序转移方程的顺序转移方程顺序算法：顺序算法： sk=Tk(sk+1,uk),称为由状态称为由状态sk+1到到sk的逆序转移方程的逆序转移方程n ns1nsnu(,)nnnvsun1k 1s1(,)kkkvsu1u2sku121(,)v suks1ksns1nsnu1(,)nnnvsu 顺序解法顺序解法1k

34、 1s状态(,)kkkvsu1u决策2sku111( ,)v s u效益ks1ks 逆序解法逆序解法逆序解法与顺序解法在建模时的区别逆序解法与顺序解法在建模时的区别:(2)(2) 指标函数的定义不同：指标函数的定义不同：逆序解法：逆序解法： 顺序解法：顺序解法： 出发，到终点后部子过程最优效益值。出发，到终点后部子过程最优效益值。 最优指标函数最优指标函数 ks11( )f s():kkfs第第k阶段从状态阶段从状态 整体最优函数值：整体最优函数值： 最优指标函数最优指标函数 1()nnfs1():kkfs1ks第第k阶段时从起阶段时从起 点到状态点到状态 的前部子过程最优效益的前部子过程最优

35、效益值。值。整体最优函数值：整体最优函数值： 逆序解法与顺序解法在建模时的区别逆序解法与顺序解法在建模时的区别:(3)(3) 基本方程形式不同：基本方程形式不同：指标函数为指标函数为阶段指标和阶段指标和形式形式 逆序解法：逆序解法： ,nk njjjj kVvs u11()11()(,)(),1,1()0kkkkkkkkkkuDsnnfsoptv s ufskn nfs顺序解法：顺序解法： 1,11,kkjjjjVvsu111()01()(,)(),1,2,( )0kkkkkkkkkkuDsfsoptv sufsknfs逆序解法与顺序解法在建模时的区别逆序解法与顺序解法在建模时的区别:(4)指

36、标函数为指标函数为阶段指标积阶段指标积形式形式 逆序解法：逆序解法： ,nk njjjj kVvs u11()11()(,)(),1,1()1kkkkkkkkkkuDsnnfsoptv s ufskn nfs顺序解法：顺序解法： 1,11,kkjjjjVvsu111()01()(,)(),1,2,( )1kkkkkkkkkkuDsfsoptv sufsknfs例例3例例3 某公司某公司有资金有资金10万元万元,若投资于若投资于i(i=1,2,3)的投资额为的投资额为 xi时时,其收益分别为其收益分别为g1(x1)=4x1, g2(x2)=9x2 , g3(x3)=2x23, 问应如何分配投资数

37、额才能使总收益最大问应如何分配投资数额才能使总收益最大?这是一个与时间无明显关系的静态最优化问题这是一个与时间无明显关系的静态最优化问题第一阶段第一阶段考虑对项目考虑对项目1的投资的投资,第二阶段考虑对项目第二阶段考虑对项目2的投资的投资,第三阶段第三阶段考虑对项目考虑对项目3的投资的投资 每个阶段只决定对一个项目应投资的金额每个阶段只决定对一个项目应投资的金额 2123123max49210. .0,1,2,3jzxxxxxxstxj这问题也可用动态规划方法求解这问题也可用动态规划方法求解其静态模型其静态模型:可以人为地引入时段的概念可以人为地引入时段的概念,将投资项目排序将投资项目排序:例

38、例3基本方程基本方程决策变量决策变量uk=xk表示对第表示对第k阶段对第阶段对第k个项目的个项目的投资金额投资金额设设状态变量状态变量sk表示在第表示在第k阶段阶段初可供使用的资金数量；初可供使用的资金数量；故故s1=10万元万元 状态转移方程状态转移方程：阶段效益：阶段效益：最优指标函数最优指标函数 fk(sk)则基本方程为则基本方程为11044( )max ( ,)()3,2,1( )0kkkkkkkkkxsf sv s xfskf s sk+1=sk-xk v1(s1,x1)=4x1, v2(s2,x2)=9x2, v3(s3,x3)=2x23表示当表示当可用资金为可用资金为sk时投资第

39、时投资第k个至第个至第3个项目所得的最大收益个项目所得的最大收益逆序解法求解例逆序解法求解例3: (2)k=3时，时， 332233330max 22xsfsxsk=2时时， 222222223322200max 9()max 92()xsxsfsxf sxsx若令若令 2222222(,)92()h sxxsx并令并令 220,dhdx得到得到 229,4xs且有且有 222240,d hdx故故 2294xs为极小点，为极小点， 因而极大值只可能在因而极大值只可能在 20,s端点取得，即端点取得，即 22222222(0)29 299 2fssfsss*33xs逆序解法求解例逆序解法求解例

40、3: (3)此时此时 *20 x或 *22.xsk=1时，时， 11111220max 4()xsfsxfs29 2s 211100109 2,ssx11111010111010max 49()max 959xxxsxsxs211,ssx 11112010max 49xfsxs222()9,fss29 2s 若若 时，时， 注意到注意到 所以所以 但是但是 这与这与 矛盾，矛盾， 因而舍去。因而舍去。 逆序解法求解例逆序解法求解例3: (4)111xs若若 212110,d hdx 2111111( ,)42()h s xxsx111.xs110,dhdx 121112010max 42xfs

41、xs12111010max 42()xxsx2222()2,fss29 2,s 则则 令令 由由 可得可得 因为因为 所以所以 为极小点。为极小点。 比较比较0,10两个端点两个端点 , 1(10)40.f10 x 时，时， 110 x 1(10)200;f时，时， 逆序解法求解例逆序解法求解例3: (5)故故 *10.x 再由状态转移方程顺推再由状态转移方程顺推 *21110010ssx因因 29 2,s 故故 *20,x*32210010.ssx因而因而 *3310.xs故最优投资方案为全部投资于第三个项目，可得最大收益故最优投资方案为全部投资于第三个项目，可得最大收益200万元。万元。

42、顺序解法求解例顺序解法求解例3： 决策变量决策变量uk=xk表示对第表示对第k阶段对第阶段对第k个项目的个项目的投资金额；投资金额；设设状态变量状态变量sk+1表示可以投资于第表示可以投资于第1到第到第k个项目的资金；个项目的资金； 故故s4=10万元万元 状态转移方程状态转移方程：阶段效益：阶段效益：最优指标函数最优指标函数 fk(sk+1)则基本方程为则基本方程为1111001()max (,)( )1,2,3( )0kkkkkkkkkxsf sv sxfskf s sk=sk+1-xk v1(s2,x1)=4x1, v2(s3,x2)=9x2, v3(s4,x3)=2x23表示当表示当可用资金为可用资金为sk+1时投资第时投资第1个至第个至第k个项目所得的最大收益个项目所得的最大收益顺序解法求解例顺序解法求解例3:(2)k=1时，时， 1212121010max(,)( )xsfsv s xfs12120max 44xsxs即即 *12.xsk=2时，时， 23232120max 9()xsfsxf s232323202330max 94()max 549xsxsxsxxss即