第十章动态规划ppt课件.ppt

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

1、第第1页页4 10 7 52 7 6 33 3 4 44 6 6 3-4-2-3-30 6 3 10 5 4 10 0 1 11 3 3 0行行变变换换列列变变换换-10 6 2 10 5 3 10 0 0 11 3 2 0 -1-1+10 5 1 00 4 2 01 0 0 12 3 2 0 -1-10 4 0 00 3 1 02 0 0 22 2 1 0+1+1-10 0 1 01 0 0 00 1 0 00 0 0 1X*=Z*=7+2+3+3=15复习指派问题的匈牙利解法复习指派问题的匈牙利解法: :第第2页页运运 筹筹 帷帷 幄幄 之之 中中决决 胜胜 千千 里里 之之 外外第十章动

2、动 态态 规规 划划Dynamic ProgrammingDynamic Programming第第3页页概概 述述 动态规划是解决多阶段决策过程最优动态规划是解决多阶段决策过程最优化问题的一种方法，该方法是由美国数学化问题的一种方法，该方法是由美国数学家贝尔曼（家贝尔曼（R Bellman)等人等人20世纪世纪50年代初年代初提出的。他们针对多阶段决策问题的特点，提出的。他们针对多阶段决策问题的特点，提出了解决这类问题的最优化原理，并成提出了解决这类问题的最优化原理，并成功地解决了生产管理、工程技术等方面的功地解决了生产管理、工程技术等方面的许多实际问题，从而建立了运筹学的一个许多实际问题，

3、从而建立了运筹学的一个新分支，即动态规划。新分支，即动态规划。第第4页页2511214106104131112396581052C1C3D1AB1B3B2D2EC2例例1 1、最短路径问题、最短路径问题求从求从A到到E的最短距离和最短路径的最短距离和最短路径第第5页页例例2 2 多阶段资源分配问题多阶段资源分配问题 设有数量为设有数量为x的某种资源，将它投入两种生产方的某种资源，将它投入两种生产方式式A和和B中：以数量中：以数量y投入生产方式投入生产方式A，剩下的量，剩下的量投入生产方式投入生产方式B，则可得到收入，则可得到收入g(y)+h(x-y)，其，其中中g(y)和和h(x-y)是已知函

4、数，并且是已知函数，并且g(0)=h(0)=0；同时假设以同时假设以y与与x-y分别投入两种生产方式分别投入两种生产方式A，B后可以回收再生产，回收率分别为后可以回收再生产，回收率分别为a与与b。试求。试求进行进行n个阶段后的最大总收入？个阶段后的最大总收入？第第6页页 若以若以y与与x-y分别投入生产方式分别投入生产方式A与与B，在第一阶段，在第一阶段生产后回收的总资源为生产后回收的总资源为x1=ay+b(x-y)，再将，再将x1投投入生产方式入生产方式A和和B，则可得到收入，则可得到收入:g(y1)+h(x1-y1) 继续回收资源继续回收资源x2=ay1+b(x1-y1)， 若上面的过程进

5、行若上面的过程进行n个阶段，我们希望选择个阶段，我们希望选择n个变量个变量y,y1,y2,yn-1，使这，使这n个阶段的总收入最大。个阶段的总收入最大。 分分 析析第第7页页 因此，我们的问题就变成：求因此，我们的问题就变成：求y,y1,y2,yn-1，以，以使使g(y)+h(x-y)+ g(y1)+h(x1-y1)+ +g(yn-1)+h(xn-1-yn-1) 达到最大，且满足条件达到最大，且满足条件 x1=ay+b(x-y) x2=ay1+b(x1-y1) xn-1=ayn-2+b(xn-2-yn-2) yi与与xi均非负均非负 (i=1,2, ,n-1 )分分 析析第第8页页多阶段决策问

6、题多阶段决策问题 所谓所谓多阶段决策问题是多阶段决策问题是指一类活动过程，它指一类活动过程，它可以分为若干个相互联系的阶段，在每个阶段都可以分为若干个相互联系的阶段，在每个阶段都需要作出决策。这个决策不仅决定这一阶段的效需要作出决策。这个决策不仅决定这一阶段的效益，而且决定下一阶段的初始状态。益，而且决定下一阶段的初始状态。 动态规划的研究对象动态规划的研究对象第第9页页动态规划是现代企业管理中的一种重要决策方法：动态规划是现代企业管理中的一种重要决策方法：最优路径问题最优路径问题资源分配问题资源分配问题生产计划与库存问题生产计划与库存问题装载问题装载问题生产过程的最优控制问题生产过程的最优控

7、制问题独特的解独特的解题思路题思路离散决策过程离散决策过程连续决策过程连续决策过程时间参量时间参量确定性决策过程确定性决策过程随机性决策过程随机性决策过程决策过程决策过程离散确定性决策过程离散确定性决策过程离散随机性决策过程离散随机性决策过程连续确定性决策过程连续确定性决策过程连续随机性决策过程连续随机性决策过程动态规划模型的分类：动态规划模型的分类：第第10页页第十章第十章 动态规划动态规划第一节第一节 动态规划基本概念动态规划基本概念第二节第二节 动态规划基本原理动态规划基本原理第三节第三节 动态规划模型的建立与求解动态规划模型的建立与求解第四节第四节 动态规划在经济管理中的应用动态规划在

8、经济管理中的应用第第11页页（1 1）阶段：）阶段：将所给问题的全过程按照时间或空间将所给问题的全过程按照时间或空间特征分解成若干相互联系的部分，以便按次序去特征分解成若干相互联系的部分，以便按次序去求解每部分的解，称为阶段，一般用求解每部分的解，称为阶段，一般用n表示表示阶段总阶段总数数，用，用k表示表示阶段变量阶段变量，k=1,2,n。第一节第一节 动态规划基本概念动态规划基本概念2511214106104131112396581052C1C3D1AB1B3B2D2EC2k=1k=2k=3k=4第第12页页（2 2）状态）状态：每个阶段开始时所处的自然状况：每个阶段开始时所处的自然状况或客

9、观条件称为该阶段的状态。或客观条件称为该阶段的状态。 描述各阶段状态的变量称为描述各阶段状态的变量称为状态变量状态变量，常，常用用sk表示；状态变量的取值集合称为表示；状态变量的取值集合称为状态状态集合集合，用，用Sk表示表示第一节第一节 动态规划基本概念动态规划基本概念第第13页页2511214106104131112396581052C1C3D1AB1B3B2D2EC2k=1k=2k=3k=4当当k=1时，时，s1=A S1=A当当k=2时，时，s2= B1或或B2或或B3 S2=B1, B2, B3 当当k=3时，时，s3= C1或或C2或或C3 S3=C1, C2, C3 当当k=4时

10、，时，s4= D1或或D2 S4=D1, D2第一节第一节 动态规划基本概念动态规划基本概念第第14页页第一节第一节 动态规划基本概念动态规划基本概念（3）决策）决策：某一阶段内的选择。当各阶段的：某一阶段内的选择。当各阶段的状态取定以后，就可以作出不同的决策（或选状态取定以后，就可以作出不同的决策（或选择），从而确定下一阶段的状态，这种决定称择），从而确定下一阶段的状态，这种决定称为决策。为决策。 表示决策的变量称为表示决策的变量称为决策变量决策变量，常用，常用xk(sk)表示第表示第k阶段当状态为阶段当状态为sk时的决策变量；时的决策变量； 在实际问题中在实际问题中,决策变量的取值往往限制

11、在决策变量的取值往往限制在一定范围内一定范围内,称此范围为称此范围为允许决策集合允许决策集合，常用，常用Dk(sk)表示第表示第k阶段从状态阶段从状态sk出发的允许决策集出发的允许决策集合，显然有：合，显然有：xk(sk) Dk(sk) 第第15页页2511214106104131112396581052C1C3D1AB1B3B2D2EC2k=1k=2k=3k=4x1(s1) ： x1(A) = B1或或B2或或B3 D1(A)=B1,B2,B3 x2(s2) ： x2(B1) = C1或或C2或或C3 D2(B1)=C1,C2,C3 x2(B2) = C1或或C2或或C3 D2(B2)=C1

12、,C2,C3 x2(B3) = C1或或C2或或C3 D2(B3)=C1,C2,C3 .第第16页页（4 4）状态转移函数）状态转移函数： 动态规划中本阶段的状态往往是由上动态规划中本阶段的状态往往是由上一阶段状态和上一阶段的决策决定的。如一阶段状态和上一阶段的决策决定的。如果给定了第果给定了第k阶段的状态阶段的状态sk，本阶段的决策，本阶段的决策xk(sk)，则第，则第k+1阶段的状态阶段的状态sk+1也就完全确也就完全确定了，它们关系可用方程表示为：定了，它们关系可用方程表示为： sk+1=Tk(sk xk) 由于它表示了由由于它表示了由k段到段到k+1段的状态转段的状态转移规律，所以称为

13、移规律，所以称为状态转移方程状态转移方程。第一节第一节 动态规划基本概念动态规划基本概念第第17页页2511214106104131112396581052C1C3D1AB1B3B2D2EC2k=1k=2k=3k=4s1=A x1(A) = B1或或B2或或B3s2=B1或或B2或或B3 x2(B1) = C1或或C2或或C3 x2(B2) = C1或或C2或或C3 x2(B3) = C1或或C2或或C3所以状态转移方程为：所以状态转移方程为： sk+1=xk(sk) 第第18页页（5 5）策略）策略： 每个阶段的决策确定以后，就得到一个决每个阶段的决策确定以后，就得到一个决策序列，称为策略。

14、策序列，称为策略。由所有各阶段的决策由所有各阶段的决策组成的决策函数序列称为组成的决策函数序列称为全过程策略全过程策略，简，简称称策略策略，记为，记为p1,n(s1)；对每个实际问题，；对每个实际问题，可供选择的策略有一定的范围，称为可供选择的策略有一定的范围，称为允许允许策略集合策略集合，记作，记作P1,n，使整个问题能够达到，使整个问题能够达到最优效果的策略就是最优效果的策略就是最优策略最优策略； 从第从第k阶段开始到最后阶段的决策组成的决阶段开始到最后阶段的决策组成的决策函数序列称为策函数序列称为k k子过程策略子过程策略，简称，简称k k子策子策略略，记为，记为pk,n(sk) 。第一

15、节第一节 动态规划基本概念动态规划基本概念第第19页页2511214106104131112396581052C1C3D1AB1B3B2D2EC2k=1k=2k=3k=4p1.4(A)=A,B1,C1,D1,E ,是一条全过程策略p2.4(B1 )=B1,C1,D1,E ,是一条2子策略第第20页页 （6 6）指标函数）指标函数： 衡量全过程策略或衡量全过程策略或k子过程策略优劣的数量指标称为子过程策略优劣的数量指标称为指标指标函数函数。 它分为阶段指标函数和过程指标函数两种。它分为阶段指标函数和过程指标函数两种。 阶段指标函数阶段指标函数是指第是指第k段，从段，从sk状态出发，采取决策状态出

16、发，采取决策xk时时的效益，用的效益，用dk (sk,xk)表示。表示。 对于一个对于一个n段的过程，从段的过程，从1到到n叫做问题的叫做问题的原过程原过程，对于，对于任意一个给定的任意一个给定的k(1kn)，从第，从第k段到第段到第n段的过程称为原过段的过程称为原过程的一个程的一个后部子过程后部子过程。 V1,n(s1,p1,n)表示初始状态为表示初始状态为s1采用策略采用策略p1,n时时原过程的指原过程的指标函数值标函数值； Vk,n(sk,pk,n)表示在第表示在第k阶段，初始状态为阶段，初始状态为sk采用策略采用策略pk,n时，时，后部子过程的指标函数值后部子过程的指标函数值；第第21

17、页页 （7 7）最优指标函数）最优指标函数：最优指标函数最优指标函数记为记为fk(sk) ，它表示从第，它表示从第k阶段初始状阶段初始状态态sk采用采用最优策略最优策略p*k,n到过程终止时的最佳效益值。到过程终止时的最佳效益值。 fk(sk) 与与Vk,n(sk,pk,n)间的关系为：间的关系为： fk(sk) =Vk,n(sk,p*k,n)= opt Vk,n(sk,pk,n) pk,n Pk,n当当k=1k=1时，时， f f1(s(s1) )就是从初始状态就是从初始状态s s1到全过程结束到全过程结束的整体最优函数。的整体最优函数。第第22页页 动态规划的研究对象是多阶段决策问题，动态

18、规划的研究对象是多阶段决策问题，而多阶段决策问题就是求一个策略，使各而多阶段决策问题就是求一个策略，使各阶段的效益的总和达到最优。阶段的效益的总和达到最优。p*k,nf1(s1) 温馨提示第第23页页 动态规划方法基于贝尔曼动态规划方法基于贝尔曼(R Bellman)等人提出的最优化原理：等人提出的最优化原理： “一个过程的最优策略具有这样的性一个过程的最优策略具有这样的性质：即无论其初始状态及其初始决策如质：即无论其初始状态及其初始决策如何，对于先前决策所形成的状态而言，何，对于先前决策所形成的状态而言，其以后的所有决策应构成最优策略其以后的所有决策应构成最优策略。”第二节第二节 动态规划基

19、本原理动态规划基本原理最优化原理最优化原理第第24页页最优化原理的理解最优化原理的理解 对于多阶段决策问题的最优策略，任一子对于多阶段决策问题的最优策略，任一子策略都是最优的。策略都是最优的。 如：最短路径上，从路径上任一点到终点如：最短路径上，从路径上任一点到终点的部分路径（最短路上的子路）也一定是从的部分路径（最短路上的子路）也一定是从该点到终点的最短路径（最短子路）该点到终点的最短路径（最短子路） 2511214106104131112396581052C1C3D1AB1B3B2D2EC2第第25页页n利用这个原理，可以把多阶段决策问题求解利用这个原理，可以把多阶段决策问题求解过程表示成

20、一个连续的递推过程，由后向前过程表示成一个连续的递推过程，由后向前逐步计算。在求解时，前面的各状态与决策，逐步计算。在求解时，前面的各状态与决策，对后面的子过程来说，只相当于初始条件，对后面的子过程来说，只相当于初始条件，并不影响后面子过程的最优决策。并不影响后面子过程的最优决策。n一般动态规划基本方程可以表示为：一般动态规划基本方程可以表示为：动态规划基本方程动态规划基本方程边界边界条件条件 fk(sk) =opt dk(sk,xk)+ fk+1(sk+1) k=n,n-1,1 xk Dk (sk) fn+1(sn+1)=0第第26页页1. 将多阶段决策过程划分阶段，恰当地选取将多阶段决策过

21、程划分阶段，恰当地选取状态变量、决策变量及定义最优指标函数，状态变量、决策变量及定义最优指标函数，从而把问题化成一族同类型的子问题，然从而把问题化成一族同类型的子问题，然后逐个求解。后逐个求解。2. 求解时从边界条件开始，逆过程行进方向，求解时从边界条件开始，逆过程行进方向，逐段递推寻优。在每一个子问题求解时，逐段递推寻优。在每一个子问题求解时，都要使用它前面已经求出的子问题的最优都要使用它前面已经求出的子问题的最优结果，最后一个子问题的最优解，就是整结果，最后一个子问题的最优解，就是整个问题的最优解。个问题的最优解。动态规划基本思想动态规划基本思想第第27页页第三节第三节 动态规划模型的建立

22、与求解动态规划模型的建立与求解建立动态规划的模型，就是分析问题并建建立动态规划的模型，就是分析问题并建立问题的立问题的动态规划基本方程动态规划基本方程。成功地应用。成功地应用动态规划方法的关键，在于识别问题的动态规划方法的关键，在于识别问题的多多阶段特征阶段特征，将问题分解成为可用递推关系，将问题分解成为可用递推关系式联系起来的若干子问题，而正确建立基式联系起来的若干子问题，而正确建立基本递推关系方程的关键又在于正确本递推关系方程的关键又在于正确选择状选择状态变量态变量，保证各阶段的状态变量具有递推，保证各阶段的状态变量具有递推的的状态转移关系状态转移关系sk+1=Tk(sk,xk)第第28页

23、页第三节第三节 动态规划模型的建立与求解动态规划模型的建立与求解求解动态规划的基本步骤：求解动态规划的基本步骤：（一）建立动态规划逆序递推基本方程（一）建立动态规划逆序递推基本方程1、划分阶段：、划分阶段：n k2、定义状态变量及其状态集合：、定义状态变量及其状态集合： sk Sk3、定义决策变量及其允许决策集合：、定义决策变量及其允许决策集合： xk*(sk) Dk*(sk) 4、确定状态转移关系：、确定状态转移关系： sk+1=Tk(sk,xk)5、定义最优指标函数：阶段指标、定义最优指标函数：阶段指标dk(sk,xk) 、最优指标函数、最优指标函数fk(sk)及其及其f1(s1)6、建立

24、动态规划逆序递推基本方程、建立动态规划逆序递推基本方程 fk(sk) =opt dk(sk,xk)+ fk+1(sk+1) k=n,n-1,1 xk Dk (sk) fn+1(sn+1)=0（二）求解（二）求解f1(s1)：k=n,n-1,1，注意标出最优决策，注意标出最优决策xk*(sk) （三）确定最优策略（三）确定最优策略:结合状态转移方程顺推最优决策结合状态转移方程顺推最优决策第第29页页2511214106104131112396581052C1C3D1AB1B3B2D2EC2例例1：最短路径问题：最短路径问题求从求从A到到E的最短路径和最短距离的最短路径和最短距离第三节第三节 动态

25、规划模型的建立与求解动态规划模型的建立与求解第第30页页2511214106104131112396581052C1C3D1AB1B3B2D2EC2k=1k=2k=3k=4解解（一）建立动态规划逆序递推基本方程（一）建立动态规划逆序递推基本方程1、划分阶段：将原问题按照空间划分为四个、划分阶段：将原问题按照空间划分为四个阶段，即阶段，即n=4，阶段变量，阶段变量 k=1,2,3,4第第31页页2511214106104131112396581052C1C3D1AB1B3B2D2EC2k=1k=2k=3k=4当当k=1时，时，s1=A S1=A当当k=2时，时，s2= B1或或B2或或B3 S2

26、=B1, B2, B3 当当k=3时，时，s3= C1或或C2或或C3 S3=C1, C2, C3 当当k=4时，时，s4= D1或或D2 S4=D1, D22、定义状态变量、定义状态变量sk： 令令sk表示各阶段的起始位表示各阶段的起始位置，则各阶段的状态变量置，则各阶段的状态变量sk及其状态集合及其状态集合Sk为为:第第32页页2511214106104131112396581052C1C3D1AB1B3B2D2EC2k=1k=2k=3k=43、定义决策变量、定义决策变量xk (sk ) ： 令令xk (sk )表示从阶段表示从阶段k的的sk出发所做的选择。出发所做的选择。第第33页页x1

27、(s1) ： x1(A) = B1或或B2或或B3 D1(A)=B1,B2,B3 x2(s2) ： x2(B1) = C1或或C2或或C3 D2(B1)=C1,C2,C3 x2(B2) = C1或或C2或或C3 D2(B2)=C1,C2,C3 x2(B3) = C1或或C2或或C3 D2(B3)=C1,C2,C3 x3(s3) ： x3(C1) = D1或或D2 D3(C1)=D1,D2 x3(C2) = D1或或D2 D3(C2)=D1,D2 x3(C3) = D1或或D2 D3(C3)=D1,D2x4(s4) ： x4(D1) = E D4(D1)=E x4(D2) = E D4(D2)=

28、E 各阶段的决策变量各阶段的决策变量xk (sk )及其允许决策集合及其允许决策集合Dk (sk )为为:第第34页页4、确定状态转移方程：、确定状态转移方程：2511214106104131112396581052C1C3D1AB1B3B2D2EC2k=1k=2k=3k=4 状态转移方程：状态转移方程： sk+1= xk第第35页页5、定义指标函数：、定义指标函数：2511214106104131112396581052C1C3D1AB1B3B2D2EC2 阶段指标：令阶段指标：令 dk (sk, xk)-表示相邻两个城市之间的距离表示相邻两个城市之间的距离最优指标函数：最优指标函数： fk

29、 (sk)-表示从第表示从第k阶段的阶段的sk到终点到终点E的最短距离的最短距离; f1 (s1)即即f1 (A) -表示从表示从A到终点到终点E的最短距离的最短距离;第第36页页2511214106104131112396581052C1C3D1AB1B3B2D2EC2k=1k=2k=3k=4F4(s4)F3(s3)F2(s2)F1(s1)第第37页页6、 建立逆序递推基本方程：建立逆序递推基本方程：动态规划的逆序递推算法的基本方程为：动态规划的逆序递推算法的基本方程为：fk(sk) = min dk(sk,xk)+ fk+1(sk+1) k=4,3,2,1 xk Dk (sk)f5(s5)

30、=0下面从边界条件出发逐段求得原问题的最短距离下面从边界条件出发逐段求得原问题的最短距离第第38页页2511214106104131112396581052C1C3D1AB1B3B2D2EC2f5(E)=0边界条件：边界条件：f5(E)=0（二）计算（二）计算f1(A)第第39页页D12511214106104131112396581052C1C3D1AB1B3B2C2f4(D1)=5f5(E)=0s4= D1或或D2 f4 (D1)= mind4 (D1,E)+ f5 (E)=min5+0=5 x4* (D1)=Ef4 (D2)= mind4 (D2,E)+ f5 (E)=min2+0=2

31、x4* (D2)=Ef4(D2)=2D1ED2E当当k=4时时 f4(s4) = min d4(s4,x4)+ f5(s5) x4 D4(s4)第第40页页f3(C1)=8112421141113DC8118min2953min)D(f)D,C()D(f)D,C(min)C(f最优决策s3= C1或或C2或或C3 最优决策最优决策x3* (C1)=D1D12511214106104131112396581052C1C3D1AB1B3B2C2f4(D1)=5f5(E)=0f4(D2)=2D1ED2EC1当当k=3时时 f3(s3) = min d3(s3,x3)+ f4(s4) =min d3(

32、s3,x3)+ f4(x3) x3 D3(s3) x3 D3(s3)第第41页页f3(C2)=7222422141223DC7711min2556min)D(f)D,C()D(f)D,C(min)C(f最优决策最优决策最优决策x3* (C2)=D2f3(C1)=8D12511214106104131112396581052C1C3D1AB1B3B2C2f4(D1)=5f5(E)=0f4(D2)=2D1ED2EC1C2当当k=3时时 f3(s3) = min d3(s3,x3)+ f4(s4) =min d3(s3,x3)+ f4(x3) x3 D3(s3) x3 D3(s3)第第42页页f3(

33、C3)=12232423141333DC121213min21058min)D(f)D,C()D(f)D,C(min)C(f最优决策f3(C2)=7f3(C1)=8D12511214106104131112396581052C1C3D1AB1B3B2C2f4(D1)=5f5(E)=0f4(D2)=2D1ED2EC1C2C3最优决策最优决策x3* (C3)=D2当当k=3时时 f3(s3) = min d3(s3,x3)+ f4(s4) =min d3(s3,x3)+ f4(x3) x3 D3(s3) x3 D3(s3)第第43页页f2(B1)=201133312321131112CB20222

34、120min1210714812min)C(f)C,B()C(f)C,B()C(f)C,B(min)B(f最优决策f3(C3)=12f3(C2)=7f3(C1)=8D12511214106104131112396581052C1C3D1AB1B3B2C2f4(D1)=5f5(E)=0f4(D2)=2D1ED2EC1C2C3B1最优决策最优决策x2* (B1)=C1s2= B1或或B2或或B3 当当k=2时时 f2(s2) = min d2(s2,x2)+ f3(s3) =min d2(s2,x2)+ f3(x2) x2 D2(s2) x2 D2(s2)第第44页页f2(B2)=14123332

35、2322131222CB14161714min12471086min)C(f)C,B()C(f)C,B()C(f)C,B(min)B(f最优决策最优决策最优决策x2* (B2)=C1f2(B1)=20f3(C3)=12f3(C2)=7f3(C1)=8D12511214106104131112396581052C1C3D1AB1B3B2C2f4(D1)=5f5(E)=0f4(D2)=2D1ED2EC1C2C3B1B2当当k=2时时 f2(s2) = min d2(s2,x2)+ f3(s3) =min d2(s2,x2)+ f3(x2) x2 D2(s2) x2 D2(s2)第第45页页f2(B

36、3)=192333332323131332CB19231921min1211712813min)C(f)C,B()C(f)C,B()C(f)C,B(min)B(f最优决策f2(B2)=14f2(B1)=20f3(C3)=12f3(C2)=7f3(C1)=8D12511214106104131112396581052C1C3D1AB1B3B2C2f4(D1)=5f5(E)=0f4(D2)=2D1ED2EC1C2C3B1B2最优决策最优决策x2* (B3)=C2B3当当k=2时时 f2(s2) = min d2(s2,x2)+ f3(s3) =min d2(s2,x2)+ f3(x2) x2 D2

37、(s2) x2 D2(s2)第第46页页f1(A)=1923232221211BA19201923min191145212min)B(f)B,A()B(f)B,A()B(f)B,A(min)A(f最优决策f2(B3)=19f2(B2)=14f2(B1)=20f3(C3)=12f3(C2)=7f3(C1)=8D12511214106104131112396581052C1C3D1AB1B3B2C2f4(D1)=5f5(E)=0f4(D2)=2D1ED2EC1C2C3B1B2B3最优决策最优决策x1* (A)=B2As3= A当当k=1时时 f1(s1) = min d1(s1,x1)+ f2(s

38、2) =min d1(s1,x1)+ f2(x1) x1 D1(s1) x1 D1(s1)第第47页页顺推最优决策：顺推最优决策：状态状态 最优决策最优决策 状态状态 最优决策最优决策 状态状态 最优决策最优决策 状态状态 最优决策最优决策 状态状态f1(A)=19f2(B3)=19f2(B2)=14f2(B1)=20f3(C3)=12f3(C2)=7f3(C1)=8D151061012351052C1C3D1AB1B3B2C2f4(D1)=5f5(E)=0f4(D2)=2D1ED2EC1C2C3B1B2B3A12A x1* (A)=B2 B2 x2* (B2)=C1 C1 x3* (C1)=

39、D1 D1 x4* (D1)=E E从从A到到E的最短路径为的最短路径为19，路径为，路径为AB 2C1 D1 E （三）推导最优策略（三）推导最优策略 第第48页页第三节第三节 动态规划模型的建立与求解动态规划模型的建立与求解求解动态规划的基本步骤：求解动态规划的基本步骤：（一）建立动态规划逆序递推基本方程（一）建立动态规划逆序递推基本方程1、划分阶段：、划分阶段：n k2、定义状态变量及其状态集合：、定义状态变量及其状态集合： sk Sk3、定义决策变量及其允许决策集合：、定义决策变量及其允许决策集合： xk(sk) Dk(sk) 4、确定状态转移关系：、确定状态转移关系： sk+1=Tk

40、(sk,xk)5、定义最优指标函数：阶段指标、定义最优指标函数：阶段指标dk(sk,xk) 、最优指标函数、最优指标函数fk(sk)及其及其f1(s1)6、建立动态规划逆序递推基本方程、建立动态规划逆序递推基本方程 fk(sk) =opt dk(sk,xk)+ fk+1(sk+1) k=n,n-1,1 xk Dk (sk) fn+1(sn+1)=0（二）求解（二）求解f1(s1)：k=n,n-1,1，注意标出最优决策，注意标出最优决策xk*(sk) （三）确定最优策略（三）确定最优策略:结合状态转移方程顺推最优决策结合状态转移方程顺推最优决策第第49页页最短路径问题最短路径问题资源分配问题资源

41、分配问题背包问题背包问题生产计划与库存问题生产计划与库存问题第四节第四节 动态规划在经济管理中的应用动态规划在经济管理中的应用生产过程的最优控制问题生产过程的最优控制问题机器负荷分配问题机器负荷分配问题装载问题装载问题系统可靠性问题系统可靠性问题第第50页页例例2、资源分配问题、资源分配问题n某公司拟将某种设备某公司拟将某种设备5台，分配给所属的甲、乙、丙三台，分配给所属的甲、乙、丙三个工厂，各工厂获得此设备后，预测可创造的利润如表个工厂，各工厂获得此设备后，预测可创造的利润如表所示，问这所示，问这5台设备应如何分配给这台设备应如何分配给这3个工厂，使得所创个工厂，使得所创造的总利润为最大？造

42、的总利润为最大？设备台数设备台数甲厂甲厂乙厂乙厂丙厂丙厂000013542710639111141211125131112第第51页页资源分配问题资源分配问题解：解：（一）建立动态规划逆序递推基本方程（一）建立动态规划逆序递推基本方程（1）划分阶段：）划分阶段： 将问题按甲、乙、丙三个工厂划分为三个阶段：将问题按甲、乙、丙三个工厂划分为三个阶段：k=1k=2k=3甲甲乙乙丙丙n=3,k=1,2,3第第52页页资源分配问题资源分配问题（2）定义状态变量）定义状态变量sk ： 令令sk表示可分配给第表示可分配给第k至第至第3个工厂的设备总台数个工厂的设备总台数 (k=1,2,3)k=1k=2k=3

43、甲甲乙乙丙丙s1s2s3s1=5 S1=5s2=0,1,2,3,4,5 S2=0,1,2,3,4,5s3=0,1,2,3,4,5 S3=0,1,2,3,4,5第第53页页资源分配问题资源分配问题（3）定义决策变量）定义决策变量xk ： 令令xk表示分配给第表示分配给第k个工厂的设备台数个工厂的设备台数 (k=1,2,3)k=1k=2k=3甲甲乙乙丙丙s1s2s3x3x2x1则0 xk sk x1 (s1): x1 (5)=0,1,2,3,4,5x2 (s2): x2 (0)=0 x2 (1)=0,1 x2 (2)=0,1,2 x2 (3)=0,1,2,3 x2 (4)=0,1,2,3,4 x2

44、 (5)=0,1,2,3,4,5x3 (s3): x3 (0)=0 x3 (1)=1 x3 (2)=2 x3 (3)=3 x3 (4)=4 x3 (5)=5第第54页页资源分配问题资源分配问题（4）确定状态转移方程）确定状态转移方程 ： sk+1= Tk(sk xk)k=1k=2k=3甲甲乙乙丙丙s1s2s3x3x2x1sk表示分配给第表示分配给第k个工厂至第个工厂至第3个工厂的设备台数个工厂的设备台数 (k=1,2,3)xk表示分配给第表示分配给第k个工厂的设备台数个工厂的设备台数 (k=1,2,3)s2= s1 x1s3= s2 x2s4= 0所以所以 sk+1= sk xk (k=1,2

45、,3)第第55页页资源分配问题资源分配问题（5）确定最优指标函数）确定最优指标函数 ：k=1k=2k=3甲甲乙乙丙丙s1s2s3x3x2x1令令dk (xk )表示给第表示给第k个工厂分配个工厂分配xk台设备能够获得的利润台设备能够获得的利润;令令fk(sk)表示将表示将sk台设备分配给第台设备分配给第k到第到第3个工厂采用最优分配策略时个工厂采用最优分配策略时所创造的最大利润所创造的最大利润 (k=1,2,3);设设f1(s1)即即f1(5)表示将表示将5台设备分配给台设备分配给3个工厂采用最优分配策略时所个工厂采用最优分配策略时所创造的最大利润创造的最大利润; 则动态规划的逆序递推算法的基

46、本方程为则动态规划的逆序递推算法的基本方程为:f3(s3) f2(s2) f1(s1) 第第56页页（二）计算（二）计算f1(s1)从边界条件出发逐段求得原问题的最大利润：从边界条件出发逐段求得原问题的最大利润：（6） 建立逆序递推基本方程：建立逆序递推基本方程：fk(sk)= maxd k (xk )+fk+1(sk+1) (k=3,2,1) 0 xksk f4(s4)=0第第57页页当当k=3时时 f3(s3)= maxd 3 (x3 )+f4(s4) = maxd 3 (x3 ) 0 x3 s3 x3= s3 s3=0,1,2,3,4,5x3 (s3): x3 (0)=0 x3 (1)=

47、1 x3 (2)=2 x3 (3)=3 x3 (4)=4 x3 (5)=5f3(0)= maxd 3 (x3 )= maxd 3 (0 )=0 x3 = 0d 3 (1 ) =maxf3(1)= maxd 3 (x3 )= max x3 = 14 =4=maxf3(2)= maxd 3 (x3 )= max x3 = 26 =6d 3 (2 ) x3 *(2)=2 x3 *(1)=1 x3 *(0)=0第第58页页=maxf3(3)= maxd 3 (x3 )= max x3= 311 =11=maxf3(4)= maxd 3 (x3 )= max x3 = 4=12d 3 (4 ) =max

48、f3(5)= maxd 3 (x3 )= max x3 = 5=12d 3 (3 )12 12 d 3 (5 ) x3 *(5)=5 x3 *(4)=4 x3 *(3)=3当当k=3时时 f3(s3)= maxd 3 (x3 )+f4(s4) = maxd 3 (x3 ) 0 x3 s3 x3= s3 第第59页页当当k=2时时 f2(s2)= maxd 2 (x2 )+f3(s3) 0 x2 s2s2=0,1,2,3,4,5x2 (s2): x2 (0)=0 x2 (1)=0,1 x2 (2)=0,1,2 x2(3)=0,1,2,3 x2 (4)=0,1,2,3,4 x2 (5)=0,1,2

49、,3,4,5f2(0)= maxd 2 (x2 )+f3(0-x2)= maxd2 (0 )+f3(0-0)=0 0 x2 0d 2(0 ) +f3(1-0)d 2(1 ) +f3(1-1)=maxf2(1)= maxd 2 (x2 )+f3(1-x2)=max 0 x2 10+45+0 =5d 2 (0 ) +f3(2-0)d 2 (1 ) +f3(2-1)=maxf2(2)= maxd 2 (x2 )+f3(2-x2)= max 0 x2 20+610+0 =10d 2 (2 ) +f3(2-2)5 +4 x2 *(2)=2 x2 *(1)=1 x2 *(0)=0= maxd 2 (x2

50、)+f3(s2-x2) 0 x2 s2第第60页页d 2 (0 ) +f3(3-0)d 2 (1 ) +f3(3-1)=maxf2(3)= maxd 2 (x2 )+f3(3 -x2)= max 0 x2 30+1111 +0=14=maxf2(4)= maxd 2 (x2 )+f3(4 -x2)= max 0 x2 40+1210+6=16d 2 (4 ) +f3(4-4)5+11 d 2 (0 ) +f3(5-0)d 2 (1 ) +f3(5-1)=maxf2(5)= maxd 2 (x2 )+f3(5 -x2)= max 0 x2 5=21 x2 *(5)=2d 2 (2 ) +f3(5