第十章动态规划ppt课件

第第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复习指派问题的匈牙利解法复习指派问题的匈牙利解法:4 10 7 5-40 6 第第2页页运运 筹筹 帷帷 幄幄 之之 中中决决 胜胜 千千 里里 之之 外外第十章动动 态态 规规 划划Dynamic Programming运 筹 帷 幄 之 中决 胜 千 里 之 第第3页页概概 述述 动态规划是解决多阶段决策过程最优化动态规划是解决多阶段决策过程最优化问题的一种方法，该方法是由美国数学家贝问题的一种方法，该方法是由美国数学家贝尔曼（尔曼（R Bellman)等人等人20世纪世纪50年代初提出年代初提出的。他们针对多阶段决策问题的特点，提出的。他们针对多阶段决策问题的特点，提出了解决这类问题的最优化原理，并成功地解了解决这类问题的最优化原理，并成功地解决了生产管理、工程技术等方面的许多实际决了生产管理、工程技术等方面的许多实际问题，从而建立了运筹学的一个新分支，即问题，从而建立了运筹学的一个新分支，即动态规划。动态规划。概 述 动态规划是解决多阶段决策过程最优化问第第4页页2511214106104131112396581052C1C3D1AB1B3B2D2EC2例例1 1、最短路径问题、最短路径问题求从求从A到到E的最短距离和最短路径的最短距离和最短路径2511214106104131112396581052C1第第5页页例例2 2 多阶段资源分配问题多阶段资源分配问题 设有数量为设有数量为x的某种资源，将它投入两种生产方的某种资源，将它投入两种生产方式式A和和B中：以数量中：以数量y投入生产方式投入生产方式A，剩下的量，剩下的量投入生产方式投入生产方式B，则可得到收入，则可得到收入g(y)+h(x-y)，其，其中中g(y)和和h(x-y)是已知函数，并且是已知函数，并且g(0)=h(0)=0；同时假设以同时假设以y与与x-y分别投入两种生产方式分别投入两种生产方式A，B后可以回收再生产，回收率分别为后可以回收再生产，回收率分别为a与与b。试求进。试求进行行n个阶段后的最大总收入？个阶段后的最大总收入？例2 多阶段资源分配问题 设有数量为x的某种资源，将它投第第6页页 若若以以y与与x-y分分别别投投入入生生产产方方式式A与与B，在在第第一一阶阶段段生生产产后后回回收收的的总总资资源源为为x1=ay+b(x-y)，再再将将x1投投入入生产方式生产方式A和和B，则可得到收入，则可得到收入:g(y1)+h(x1-y1)继续回收资源继续回收资源x2=ay1+b(x1-y1)，若若上上面面的的过过程程进进行行n个个阶阶段段，我我们们希希望望选选择择n个个变变量量y,y1,y2,yn-1，使使这这n个个阶阶段段的的总总收收入入最最大。大。分分 析析 若以y与x-y分别投入生产方式A与B，在第一阶段生产第第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)分分 析析 因此，我们的问题就变成：求y,y1,y2,yn第第8页页多阶段决策问题多阶段决策问题 所谓所谓多阶段决策问题是多阶段决策问题是指一类活动过程，它指一类活动过程，它可以分为若干个相互联系的阶段，在每个阶段都可以分为若干个相互联系的阶段，在每个阶段都需要作出决策。这个决策不仅决定这一阶段的效需要作出决策。这个决策不仅决定这一阶段的效益，而且决定下一阶段的初始状态。益，而且决定下一阶段的初始状态。动态规划的研究对象动态规划的研究对象多阶段决策问题 动态规划的研究对象第第9页页动态规划是现代企业管理中的一种重要决策方法：动态规划是现代企业管理中的一种重要决策方法：最优路径问题最优路径问题资源分配问题资源分配问题生产计划与库存问题生产计划与库存问题装载问题装载问题生产过程的最优控制问题生产过程的最优控制问题独特的解独特的解题思路题思路离散决策过程离散决策过程连续决策过程连续决策过程时间参量时间参量确定性决策过程确定性决策过程随机性决策过程随机性决策过程决策过程决策过程离散确定性决策过程离散确定性决策过程离散随机性决策过程离散随机性决策过程连续确定性决策过程连续确定性决策过程连续随机性决策过程连续随机性决策过程动态规划模型的分类：动态规划模型的分类：动态规划是现代企业管理中的一种重要决策方法：最优路径问题资源第第10页页第十章第十章 动态规划动态规划第一节第一节 动态规划基本概念动态规划基本概念第二节第二节 动态规划基本原理动态规划基本原理第三节第三节 动态规划模型的建立与求解动态规划模型的建立与求解第四节第四节 动态规划在经济管理中的应用动态规划在经济管理中的应用第十章 动态规划第一节 动态规划基本概念第第11页页（1 1）阶阶段段：将将所所给给问问题题的的全全过过程程按按照照时时间间或或空空间间特特征征分分解解成成若若干干相相互互联联系系的的部部分分，以以便便按按次次序序去去求求解解每每部部分分的的解解，称称为为阶阶段段，一一般般用用n表表示示阶阶段段总总数数，用用k表示表示阶段变量阶段变量，k=1,2,n。第一节第一节 动态规划基本概念动态规划基本概念2511214106104131112396581052C1C3D1AB1B3B2D2EC2k=1k=2k=3k=4（1）阶段：将所给问题的全过程按照时间或空间特征分解成若干相第第12页页（2 2）状态）状态：每个阶段开始时所处的自然状况：每个阶段开始时所处的自然状况或客观条件称为该阶段的状态。或客观条件称为该阶段的状态。描述各阶段状态的变量称为描述各阶段状态的变量称为状态变量状态变量，常，常用用sk表示；状态变量的取值集合称为表示；状态变量的取值集合称为状态状态集合集合，用，用Sk表示表示第一节第一节 动态规划基本概念动态规划基本概念（2）状态：每个阶段开始时所处的自然状况或客观条件称为该阶段第第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时，时，s4=D1或或D2 S4=D1,D2第一节第一节 动态规划基本概念动态规划基本概念2511214106104131112396581052C1第第14页页第一节第一节 动态规划基本概念动态规划基本概念（3）决策）决策：某一阶段内的选择。当各阶段的状：某一阶段内的选择。当各阶段的状态取定以后，就可以作出不同的决策（或选择）态取定以后，就可以作出不同的决策（或选择），从而确定下一阶段的状态，这种决定称为决，从而确定下一阶段的状态，这种决定称为决策。策。表示决策的变量称为表示决策的变量称为决策变量决策变量，常用，常用xk(sk)表示第表示第k阶段当状态为阶段当状态为sk时的决策变量；时的决策变量；在实际问题中在实际问题中,决策变量的取值往往限制在决策变量的取值往往限制在一定范围内一定范围内,称此范围为称此范围为允许决策集合允许决策集合，常用，常用Dk(sk)表示第表示第k阶段从状态阶段从状态sk出发的允许决策集合，出发的允许决策集合，显然有：显然有：xk(sk)Dk(sk)第一节 动态规划基本概念（3）决策：某一阶段内的选择。当各第第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,C2,C3 x2(B3)=C1或或C2或或C3 D2(B3)=C1,C2,C3.2511214106104131112396581052C1第第16页页（4 4）状态转移函数）状态转移函数：动态规划中本阶段的状态往往是由上动态规划中本阶段的状态往往是由上一阶段状态和上一阶段的决策决定的。如一阶段状态和上一阶段的决策决定的。如果给定了第果给定了第k阶段的状态阶段的状态sk，本阶段的决策，本阶段的决策xk(sk)，则第，则第k+1阶段的状态阶段的状态sk+1也就完全也就完全确定了，它们关系可用方程表示为：确定了，它们关系可用方程表示为：sk+1=Tk(sk xk)由于它表示了由由于它表示了由k段到段到k+1段的状态转段的状态转移规律，所以称为移规律，所以称为状态转移方程状态转移方程。第一节第一节 动态规划基本概念动态规划基本概念（4）状态转移函数：第一节 动态规划基本概念第第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)2511214106104131112396581052C1第第18页页（5 5）策略）策略：每个阶段的决策确定以后，就得到一个决每个阶段的决策确定以后，就得到一个决策序列，称为策略。策序列，称为策略。由所有各阶段的决策由所有各阶段的决策组成的决策函数序列称为组成的决策函数序列称为全过程策略全过程策略，简，简称称策略策略，记为，记为p1,n(s1)；对每个实际问题，；对每个实际问题，可供选择的策略有一定的范围，称为可供选择的策略有一定的范围，称为允许允许策略集合策略集合，记作，记作P1,n，使整个问题能够达到，使整个问题能够达到最优效果的策略就是最优效果的策略就是最优策略最优策略；从第从第k阶段开始到最后阶段的决策组成的决阶段开始到最后阶段的决策组成的决策函数序列称为策函数序列称为k k子过程策略子过程策略，简称，简称k k子策子策略略，记为，记为pk,n(sk)。第一节第一节 动态规划基本概念动态规划基本概念（5）策略：第一节 动态规划基本概念第第19页页2511214106104131112396581052C1C3D1AB1B3B2D2EC2k=1k=2k=3k=4p1.4(A)=A,B1,C1,D1,E,是一条全过程策略p2.4(B1)=B1,C1,D1,E,是一条2子策略2511214106104131112396581052C1第第20页页（6 6）指标函数）指标函数：衡量全过程策略或衡量全过程策略或k子过程策略优劣的数量指标称为子过程策略优劣的数量指标称为指标指标函数函数。它分为阶段指标函数和过程指标函数两种。它分为阶段指标函数和过程指标函数两种。阶段指标函数阶段指标函数是指第是指第k段，从段，从sk状态出发，采取决策状态出发，采取决策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时，时，后部子过程的指标函数值后部子过程的指标函数值；（6）指标函数：第第21页页（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到全过程结束到全过程结束的整体最优函数。的整体最优函数。（7）最优指标函数：第第22页页动态规划的研究对象是多阶段决策问题，动态规划的研究对象是多阶段决策问题，而多阶段决策问题就是求一个策略，使各而多阶段决策问题就是求一个策略，使各阶段的效益的总和达到最优。阶段的效益的总和达到最优。p*k,nf1(s1)温馨提示动态规划的研究对象是多阶段决策问题，而多阶段决策问题就是求一第第23页页 动态规划方法基于贝尔曼动态规划方法基于贝尔曼(R Bellman)等人提出的最优化原理：等人提出的最优化原理：“一个过程的最优策略具有这样的性质：一个过程的最优策略具有这样的性质：即无论其初始状态及其初始决策如何，即无论其初始状态及其初始决策如何，对于先前决策所形成的状态而言，其以对于先前决策所形成的状态而言，其以后的所有决策应构成最优策略后的所有决策应构成最优策略。”第二节第二节 动态规划基本原理动态规划基本原理最优化原理最优化原理 动态规划方法基于贝尔曼(R Bellman)等人提第第24页页最优化原理的理解最优化原理的理解 对对于于多多阶阶段段决决策策问问题题的的最最优优策策略略，任任一一子子策略都是最优的。策略都是最优的。如如：最最短短路路径径上上，从从路路径径上上任任一一点点到到终终点点的的部部分分路路径径（最最短短路路上上的的子子路路）也也一一定定是是从从该该点到终点的最短路径（最短子路）点到终点的最短路径（最短子路）2511214106104131112396581052C1C3D1AB1B3B2D2EC2最优化原理的理解 对于多阶段决策问题的第第25页页n利用这个原理，可以把多阶段决策问题求解利用这个原理，可以把多阶段决策问题求解过程表示成一个连续的递推过程，由后向前过程表示成一个连续的递推过程，由后向前逐步计算。在求解时，前面的各状态与决策，逐步计算。在求解时，前面的各状态与决策，对后面的子过程来说，只相当于初始条件，对后面的子过程来说，只相当于初始条件，并不影响后面子过程的最优决策。并不影响后面子过程的最优决策。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.将多阶段决策过程划分阶段，恰当地选取将多阶段决策过程划分阶段，恰当地选取状态变量、决策变量及定义最优指标函数，状态变量、决策变量及定义最优指标函数，从而把问题化成一族同类型的子问题，然从而把问题化成一族同类型的子问题，然后逐个求解。后逐个求解。2.求解时从边界条件开始，逆过程行进方向，求解时从边界条件开始，逆过程行进方向，逐段递推寻优。在每一个子问题求解时，逐段递推寻优。在每一个子问题求解时，都要使用它前面已经求出的子问题的最优都要使用它前面已经求出的子问题的最优结果，最后一个子问题的最优解，就是整结果，最后一个子问题的最优解，就是整个问题的最优解。个问题的最优解。动态规划基本思想动态规划基本思想将多阶段决策过程划分阶段，恰当地选取状态变量、决策变量及定义第第27页页第三节第三节 动态规划模型的建立与求解动态规划模型的建立与求解建立动态规划的模型，就是分析问题并建建立动态规划的模型，就是分析问题并建立问题的立问题的动态规划基本方程动态规划基本方程。成功地应用。成功地应用动态规划方法的关键，在于识别问题的动态规划方法的关键，在于识别问题的多多阶段特征阶段特征，将问题分解成为可用递推关系，将问题分解成为可用递推关系式联系起来的若干子问题，而正确建立基式联系起来的若干子问题，而正确建立基本递推关系方程的关键又在于正确本递推关系方程的关键又在于正确选择状选择状态变量态变量，保证各阶段的状态变量具有递推，保证各阶段的状态变量具有递推的的状态转移关系状态转移关系sk+1=Tk(sk,xk)第三节 动态规划模型的建立与求解建立动态规划的模型，就是分第第28页页第三节第三节 动态规划模型的建立与求解动态规划模型的建立与求解求解动态规划的基本步骤：求解动态规划的基本步骤：（一）建立动态规划逆序递推基本方程（一）建立动态规划逆序递推基本方程1、划分阶段：、划分阶段：n k2、定义状态变量及其状态集合：、定义状态变量及其状态集合：sk Sk3、定义决策变量及其允许决策集合：、定义决策变量及其允许决策集合：xk*(sk)Dk*(sk)4、确定状态转移关系：、确定状态转移关系：sk+1=Tk(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)（三）确定最优策略（三）确定最优策略:结合状态转移方程顺推最优决策结合状态转移方程顺推最优决策第三节 动态规划模型的建立与求解求解动态规划的基本步骤：第第29页页2511214106104131112396581052C1C3D1AB1B3B2D2EC2例例1：最短路径问题：最短路径问题求从求从A到到E的最短路径和最短距离的最短路径和最短距离第三节第三节 动态规划模型的建立与求解动态规划模型的建立与求解2511214106104131112396581052C1第第30页页2511214106104131112396581052C1C3D1AB1B3B2D2EC2k=1k=2k=3k=4解解（一）建立动态规划逆序递推基本方程（一）建立动态规划逆序递推基本方程1、划分阶段：将原问题按照空间划分为四个、划分阶段：将原问题按照空间划分为四个阶段，即阶段，即n=4，阶段变量，阶段变量 k=1,2,3,42511214106104131112396581052C1第第31页页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时，时，s4=D1或或D2 S4=D1,D22、定义状态变量、定义状态变量sk：令令sk表示各阶段的起始位表示各阶段的起始位置，则各阶段的状态变量置，则各阶段的状态变量sk及其状态集合及其状态集合Sk为为:2511214106104131112396581052C1第第32页页2511214106104131112396581052C1C3D1AB1B3B2D2EC2k=1k=2k=3k=43、定义决策变量、定义决策变量xk(sk)：令令xk(sk)表示从阶表示从阶段段k的的sk出发所做的选择。出发所做的选择。2511214106104131112396581052C1第第33页页x1(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)=E 各阶段的决策变量各阶段的决策变量xk(sk)及其允许决策集合及其允许决策集合Dk(sk)为为:x1(s1)：x1(A)=B1或B2或B3 第第34页页4、确定状态转移方程：、确定状态转移方程：2511214106104131112396581052C1C3D1AB1B3B2D2EC2k=1k=2k=3k=4 状态转移方程：状态转移方程：sk+1=xk4、确定状态转移方程：2511214106104131112第第35页页5、定义指标函数：、定义指标函数：2511214106104131112396581052C1C3D1AB1B3B2D2EC2 阶段指标：令阶段指标：令 dk(sk,xk)-表示相邻两个城市之间的距表示相邻两个城市之间的距离离最优指标函数：最优指标函数：fk(sk)-表示从第表示从第k阶段的阶段的sk到终点到终点E的最短距离的最短距离;f1(s1)即即f1(A)-表示从表示从A到终点到终点E的最短距离的最短距离;5、定义指标函数：251121410610413111239第第36页页2511214106104131112396581052C1C3D1AB1B3B2D2EC2k=1k=2k=3k=4F4(s4)F3(s3)F2(s2)F1(s1)2511214106104131112396581052C1第第37页页6、建立逆序递推基本方程：建立逆序递推基本方程：动态规划的逆序递推算法的基本方程为：动态规划的逆序递推算法的基本方程为：fk(sk)=min dk(sk,xk)+fk+1(sk+1)k=4,3,2,1 xk Dk(sk)f5(s5)=0下面从边界条件出发逐段求得原问题的最短距离下面从边界条件出发逐段求得原问题的最短距离6、建立逆序递推基本方程：动态规划的逆序递推算法的基本方程第第38页页2511214106104131112396581052C1C3D1AB1B3B2D2EC2f5(E)=0边界条件：边界条件：f5(E)=0（二）计算（二）计算f1(A)2511214106104131112396581052C1第第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 x4*(D2)=Ef4(D2)=2D1ED2E当当k=4时时 f4(s4)=min d4(s4,x4)+f5(s5)x4 D4(s4)D12511214106104131112396581052第第40页页f3(C1)=8s3=C1或或C2或或C3 最优决策最优决策x3*(C1)=D1D12511214106104131112396581052C1C3D1AB1B3B2C2f4(D1)=5f5(E)=0f4(D2)=2D1ED2EC1当当k=3时时 f3(s3)=min d3(s3,x3)+f4(s4)=min d3(s3,x3)+f4(x3)x3 D3(s3)x3 D3(s3)f3(C1)=8s3=C1或C2或C3 最优决策x3*(第第41页页f3(C2)=7最优决策最优决策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)f3(C2)=7最优决策x3*(C2)=D2f3(C1)=第第42页页f3(C3)=12f3(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)f3(C3)=12f3(C2)=7f3(C1)=8D1251第第43页页f2(B1)=20f3(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)f2(B1)=20f3(C3)=12f3(C2)=7f3(C第第44页页f2(B2)=14最优决策最优决策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)f2(B2)=14最优决策x2*(B2)=C1f2(B1)第第45页页f2(B3)=19f2(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(s2)x2 D2(s2)f2(B3)=19f2(B2)=14f2(B1)=20f3(第第46页页f1(A)=19f2(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(s2)=min d1(s1,x1)+f2(x1)x1 D1(s1)x1 D1(s1)f1(A)=19f2(B3)=19f2(B2)=14f2(B第第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)=D1 D1 x4*(D1)=E E从从A到到E的最短路径为的最短路径为19，路径为，路径为AB 2C1 D1 E（三）推导最优策略（三）推导最优策略 顺推最优决策：f1(A)=19f2(B3)=19f2(B2)第第48页页第三节第三节 动态规划模型的建立与求解动态规划模型的建立与求解求解动态规划的基本步骤：求解动态规划的基本步骤：（一）建立动态规划逆序递推基本方程（一）建立动态规划逆序递推基本方程1、划分阶段：、划分阶段：n k2、定义状态变量及其状态集合：、定义状态变量及其状态集合：sk Sk3、定义决策变量及其允许决策集合：、定义决策变量及其允许决策集合：xk(sk)Dk(sk)4、确定状态转移关系：、确定状态转移关系：sk+1=Tk(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页页最短路径问题最短路径问题资源分配问题资源分配问题背包问题背包问题生产计划与库存问题生产计划与库存问题第四节第四节 动态规划在经济管理中的应用动态规划在经济管理中的应用生产过程的最优控制问题生产过程的最优控制问题机器负荷分配问题机器负荷分配问题装载问题装载问题系统可靠性问题系统可靠性问题最短路径问题第四节 动态规划在经济管理中的应用生产过程的第第50页页例例2、资源分配问题、资源分配问题n某公司拟将某种设备某公司拟将某种设备5台，分配给所属的甲、乙、丙三台，分配给所属的甲、乙、丙三个工厂，各工厂获得此设备后，预测可创造的利润如表个工厂，各工厂获得此设备后，预测可创造的利润如表所示，问这所示，问这5台设备应如何分配给这台设备应如何分配给这3个工厂，使得所创个工厂，使得所创造的总利润为最大？造的总利润为最大？设备台数设备台数甲厂甲厂乙厂乙厂丙厂丙厂000013542710639111141211125131112例2、资源分配问题某公司拟将某种设备5台，分配给所属的甲、乙第第51页页资源分配问题资源分配问题解：解：（一）建立动态规划逆序递推基本方程（一）建立动态规划逆序递推基本方程（1）划分阶段：）划分阶段：将问题按甲、乙、丙三个工厂划分为三个阶段：将问题按甲、乙、丙三个工厂划分为三个阶段：k=1k=2k=3甲甲乙乙丙丙n=3,k=1,2,3资源分配问题解：（一）建立动态规划逆序递推基本方程k=1k=第第52页页资源分配问题资源分配问题（2）定义状态变量）定义状态变量sk：令令sk表示可分配给第表示可分配给第k至第至第3个工厂的设备总台数个工厂的设备总台数(k=1,2,3)k=1k=2k=3甲甲乙乙丙丙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资源分配问题（2）定义状态变量sk：k=1k=2k=3甲乙第第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(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资源分配问题（3）定义决策变量xk：k=1k=2k=3甲乙第第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,3)资源分配问题（4）确定状态转移方程：sk+1=Tk(s第第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个工厂采用最优分配策略时所个工厂采用最优分配策略时所创造的最大利润创造的最大利润;则动态规划的逆序递推算法的基本方程为则动态规划的逆序递推算法的基本方程为:f3(s3)f2(s2)f1(s1)资源分配问题（5）确定最优指标函数：k=1k=2k=3甲乙第第56页页（二）计算（二）计算f1(s1)从边界条件出发逐段求得原问题的最大利润：从边界条件出发逐段求得原问题的最大利润：（6）建立逆序递推基本方程：建立逆序递推基本方程：fk(sk)=maxd k(xk)+fk+1(sk+1)(k=3,2,1)0 xksk f4(s4)=0（二）计算f1(s1)（6）建立逆序递推基本方程：fk(s第第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)=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当k=3时 f3(s3)=maxd 3(x3)+f第第58页页=maxf3(3)=maxd 3(x3)=max x3=311=11=maxf3(4)=maxd 3(x3)=max x3=4=12d 3(4)=maxf3(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=maxf3(3)=maxd 3(x3)=max第第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,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)+f3(s2-x2)0 x2 s2当k=2时 f2(s2)=maxd 2(x2)+f第第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-2)d 2(2)+f3(3-2)d 2(3)+f3(3-3)5+610+4d 2(1)+f3(4-1)d 2(2)+f3(4-2)d 2(0)+f3(4-0)d 2(3)+f3(4-3)11+411+0 10+11 5+12 11+611+4 0+1211+0d 2(3)+f3(5-3)d 2(4)+f3(5-4)d 2(5)+f3(5-5)x2*(3)=2 x2*(4)=1或或2当当k=2时时 f2(s2)=maxd 2(x2)+f3(s3)0 x2 s2=maxd 2(x2)+f3(s2-x2)0 x2 s2d 2(0)+f3(3-0)d 2(1)+f3(第第61页页当当k=1时时 f1(s1)=maxd 1(x1)+f2(s1-x1)0 x1 s1s1=5d 1(0)+f2(5-0)d 1(1)+f2(5-1)=maxf1(5)=maxd 1(x1)+f2(5 x1)=max 0 x1 5=21d 1(2)+f2(5-2)7+143+16 9+10 12+5 0+2113+0d 1(3)+f2(5-3)d 1(4)+f2(5-4)d 1(5)+f2(5-5)所以所以 x1*(5)=0或或2x1(5)=0,1,2,3,4,5当k=1时 f1(s1)=maxd 1(x1)+f第第62页页（三）推导最优策略（三）推导最优策略(顺推确定最优策略顺推确定最优策略)由上可见最大利润为由上可见最大利润为f1(5)=21 此时此时s1=5 x1*(5)=0或或2当当x1*(5)=0时时,由状态转移方程由状态转移方程s2=s1-x1=5-0=5,查得查得x2*(5)=2;又又s3=s2-x2=5-2=3,查得查得x3*(3)=3;所以所以x1*=0，x2*=2，x3*=3是一组解是一组解当当x1*(5)=2时时,由状态转移方程由状态转移方程s2=s1-x1=5-2=3,查得查得x2*(3)=2;又又s3=s2-x2=3-2=1,查得查得x3*(1)=1;所以所以x1*=2，x2*=2，x3*=1也是一组解也是一组解可见原方程有两个最优分配方案：可见原方程有两个最优分配方案：x1*=0，x2*=2，x3*=3，或或 x1*=2，x2*=2，x3*=1这两种分配方案都能得到最高的总利润这两种分配方案都能得到最高的总利润21万元万元（三）推导最优策略(顺推确定最优策略)由上可见最大利润为f1第第63页页课堂练习n某公司有资金某公司有资金4万元，可向万元，可向A、B、C三个项目投资，三个项目投资，已知各项目不同投资额的相应效益值如表所示，已知各项目不同投资额的相应效益值如表所示，问如何分配资金可使总效益最大？问如何分配资金可使总效益最大？项目项目01234ABC000414264485068606078666676课堂练习某公司有资金4万元，可向A、B、C三个项目投资，已知第第64页页杭州网通公司正在计划如何安排在杭州网通公司正在计划如何安排在15天时间里对天时间里对3个小区进行网络个小区进行网络调试，要求每天只能安排一个小区的调试，每个小区至少需要调调试，要求每天只能安排一个小区的调试，每个小区至少需要调试试4天，已知花费在各个小区的时间与将来创造的利润（万元）的天，已知花费在各个小区的时间与将来创造的利润（万元）的关系如下表，问如何安排时间使得将来所获得的利润最高？关系如下表，问如何安排时间使得将来所获得的利润最高？小区小区天数天数1 12 23 34 45 56 67 73 36 68 811115 57 79 912122 25 58 81010资源分配问题例资源分配问题例 3杭州网通公司正在计划如何安排在15天时间里对3个小区进行网络第第65页页（1）划分阶段：按小区将原问题划分为三个阶段）划分阶段：按小区将原问题划分为三个阶段，则，则n=3,k=1,2,3k=2k=1k=3S1S2S3S4基准点f1(S1)f2(S2)f3(S3)（2）确定状态变量：）确定状态变量：sk k表示分配用于第表示分配用于第k个小区到第三个小区的总的网络调试天数，则：个小区到第三个小区的总的网络调试天数，则：s1 1=15;s2 2=8，9，10，11;s3 3=4，5，6，7;s4 4=0;（一）建立动态规划逆序递推基本方程（一）建立动态规划逆序递推基本方程（1）划分阶段：按小区将原问题划分为三个阶段，则n=3,第第66页页（3）确定决策变量：）确定决策变量：xk(sk)表示分配给第表示分配给第k个小区的调试天数，则：个小区的调试天数，则：x1(s1)：x1(15)=4，5，6，7；D1(15)=4，5，6，7x2(s2)：x2(8)=4；D2(8)=4 x2(9)=4，5；D2(9)=4，5 x2(10)=4，5，6；D2(10)=4，5，6 x2(11)=4，5，6，7；D2(11)=4，5，6，7x3(s3)：x3(4)=4；D3(4)=4 x3(5)=5；D3(5)=5 x3(6)=6；D3(6)=6 x3(7)=7；D3(7)=7（3）确定决策变量：x2(s2)：x2(8)=4；第第67页页阶段指标：阶段指标：dk(xk,)-表示第表示第k阶段调试天数为阶段调试天数为xk天时创造的利润；天时创造的利润；最优指标函数：最优指标函数：fk(sk)-表示第表示第k阶段用于第阶段用于第k到第到第3阶段调试总阶段调试总天数为天数为sk天时天时,采用最优策略时，创造的最大利润；采用最优策略时，创造的最大利润；最优指标函数：最优指标函数：f1(s1)-表示第表示第1阶段用于第阶段用于第1到第到第3阶段调试总阶段调试总天数为天数为s1天时天时,采用最优策略时，创造的最大利润；采用最优策略时，创造的最大利润；则动态规划逆序递推基本方程为：则动态规划逆序递推基本方程为：fk k(sk k)=max dk(xk k)+fk+1k+1(sk+1k+1)k=3,2,1 xk Dk(sk)f 4 4(s4 4)=0(4)确定状态转移方程：确定状态转移方程：由分析可知该问题的状态转移方程为：由分析可知该问题的状态转移方程为：sk+1=sk xk（5）确定最优指标函数：）确定最优指标函数：fk(sk)=max dk(xk)+fk+1(sk第第68页页当当k=3时：时：f3 3(s3 3)=maxd3(x3 3)+f4 4(s4 4)=maxd3(x3 3)x3 D3(s3)x3=s3f3 3(5)=maxd3(x3 3)=maxd3(5)=max5=5 x3=5 f3 3(6)=maxd3(x3 3)=maxd3(6)=max8=8 x3=6f3 3(7)=maxd3(x3 3)=maxd3(7)=max10=10 x3=7 （二）计算（二）计算f1(s1)f3 3(4)=maxd3(x3 3)=maxd3(4)=max2=2 x3=4当k=3时：f3(s3)=maxd3(x3)+f4(s第第69页页当当k=2时：时：f2 2(s2 2)=maxd2(x2 2)+f3 3(s3 3)x2 2 D2 2(s2 2)f2 2(9)=maxd2(x2 2)+f3 3(9-x2)x2 2 4,5 d2(4)+f3 3(9-4)=max d2(5)+f3 3(9-5)5+5=max =10 7+2f2 2(8)=maxd2(x2 2)+f3 3(8-x2)x2 2 4=maxd2(4)+f3(8-4)=max5+2=7=maxd2(x2 2)+f3 3(s2 2-x2)x2 2 D2 2(s2 2)f2 2(10)=maxd2(x2 2)+f3 3(10-x2)x2 2 4,5,6 d2(4)+f3 3(10-4)=max d2(5)+f3 3(10-5)d2(6)+f3 3(10-6)5+8=max 7+5 =13 9+2f2 2(11)=maxd2(x2 2)+f3 3(11-x2)x2 2 4,5,6,7 d2(4)+f3 3(11-4)=max d2(5)+f3 3(11-5)d2(6)+f3 3(11-6)d2(7)+f3 3(11-7)5+10=max 7+8 =15 9+5 12+2当k=2时：f2(s2)=maxd2(x2)+f3(s第第70页页当当k=1时：时：f1 1(s1 1)=maxd1(x1 1)+f2 2(s2 2)x1 1 D1 1(s1 1)=maxd1(x1 1)+f2 2(s1 1-x1)x1 1 D1 1(s1 1)f1 1(15)=maxd1(x1 1)+f2 2(15-x1)x1 1 4,5,6,7 d1(4)+f2 2(15-4)=max d1(5)+f2 2(15-5)d1(6)+f2 2(15-6)d1(7)+f2 2(15-7)3+15=max 6+13 =19 8+10 11+5注注:可以通过倒推减少计算量可以通过倒推减少计算量当k=1时：f1(s1)=maxd1(x1)+f2(s第第71页页（三）推导最优策略：（三）推导最优策略：因为因为s1 1=15，从上述最优结果中查得：，从上述最优结果中查得：根据状态转移方程：根据状态转移方程：s2 2=s1 1-x1=15-5=10,从上述最优结果中又查得：从上述最优结果中又查得：又根据状态转移方程：又根据状态转移方程：s3 3=s2 2-x2=10-4=6,从上述最优结果中又查得：从上述最优结果中又查得：综上所述，综上所述，即即杭州网通公司正在对第杭州网通公司正在对第1 1个小区进行网络调试个小区进行网络调试5 5天，第天，第2 2个小区个小区4 4天，第天，第3 3个小区个小区6 6天，使得将来所获得的利润最高，最高利润为天，使得将来所获得的利润最高，最高利润为1919万元。万元。（三）推导最优策略：根据状态转移方程：s2=s1-x1=1第第72页页背包问题背包问题n背包问题的一般提法是背包问题的一般提法是:一位旅行者携带背包去一位旅行者携带背包去登山，已知他所能承受的背包重量限度为登山，已知他所能承受的背包重量限度为a千克千克,现有现有n种物品可供他选择装入背包，第种物品可供他选择装入背包，第i种物品的种物品的单价重量为单价重量为ai千克千克,其价值其价值(可以是表明本物品对可以是表明本物品对登山的重要性的数量指标登山的重要性的数量指标)是携带数量是携带数量xi的函数的函数ci(xi)(i=1,2,n),问旅行者应如何选择携带各种问旅行者应如何选择携带各种物品的件数物品的件数,以使总价值最大？以使总价值最大？n背包问题等用于车、船、人造卫星等工具的最优背包问题等用于车、船、人造卫星等工具的最优装载等装载等,有广泛的实用意