运筹学教案动态规划.ppt

《运筹学教案动态规划.ppt》由会员分享，可在线阅读，更多相关《运筹学教案动态规划.ppt（38页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、运筹学教案运筹学教案动态规划动态规划陈安明陈安明概述概述 动态规划为运筹学的一个分支，是用于求解动态规划为运筹学的一个分支，是用于求解多个阶段决策过程的最优化数学方法。多个阶段决策过程的最优化数学方法。理论基础：理论基础：美国数学家贝尔曼（美国数学家贝尔曼（Richard Bellman)Richard Bellman)研研究提出的最优化原理（究提出的最优化原理（Principle of Principle of Decision)Decision)把多把多阶段过程转化为一系列单阶段问阶段过程转化为一系列单阶段问题，逐个求解，创立一类求解多阶段过程优化题，逐个求解，创立一类求解多阶段过程优化问

2、题的方法问题的方法动态规划（动态规划（Dynamic Dynamic Programming)Programming)动态规划的应用领域动态规划的应用领域经济管理、工程技术、工农业生产及军经济管理、工程技术、工农业生产及军事部门。事部门。具体讲：如最短路线，资源分配，库存具体讲：如最短路线，资源分配，库存管理，生产调度，排序，装载，市场营销，管理，生产调度，排序，装载，市场营销，设备维修与更新等方面。设备维修与更新等方面。主要解决时序或空间序阶段划分的多阶段主要解决时序或空间序阶段划分的多阶段问题。但对一些与时间甚至与空间都无关的问题。但对一些与时间甚至与空间都无关的静态问题，在引入特殊序之后

3、用动态规划方静态问题，在引入特殊序之后用动态规划方法处理。法处理。多阶段决策过程及实例多阶段决策过程及实例多多阶段决策问题举例阶段决策问题举例从从A地经地经B、C、D、E到到F地铺设管线，地铺设管线，问，怎样铺设，可使管线最短？问，怎样铺设，可使管线最短？AB1B2B3C1C2C3D1D2D3E1E2F35495435171584644222697514若用穷举法求若用穷举法求解，计算量大，且容易遗漏某一解，计算量大，且容易遗漏某一路径。路径。本例可将其划分为五个阶段，用动态规划原理本例可将其划分为五个阶段，用动态规划原理求其最短路径。求其最短路径。思路：思路：从从A站出发应经过哪些站点到站出

4、发应经过哪些站点到F站的总长度最站的总长度最短？若已作出从短？若已作出从ABi中之一决策，之后的问题变中之一决策，之后的问题变为，从各为，从各Bi站点经哪些站点到站点经哪些站点到F点的总长度最短，点的总长度最短，仍为一多阶段决策问题，与前一问题相似，解决方仍为一多阶段决策问题，与前一问题相似，解决方法也相似，只是少了一个阶段，问题变小了，若后法也相似，只是少了一个阶段，问题变小了，若后一问题解决了，则前一问题也解决了。一问题解决了，则前一问题也解决了。类似地，到了类似地，到了C站、站、D站、站、E站，都面临同一站，都面临同一问题，只是问题越来越小并易于解决。问题，只是问题越来越小并易于解决。到

5、了到了E站，从其各点到站，从其各点到F的最短距离已易得，的最短距离已易得，再逆推，可求出再逆推，可求出D站各点到站各点到F点的最短距离，逐次点的最短距离，逐次逆推，到最后可以求出逆推，到最后可以求出A点到点到F点的最短距离。点的最短距离。这就是动态规划问题逆推算法。这就是动态规划问题逆推算法。动态规划问题其它例子，见动态规划问题其它例子，见P193机器负荷问机器负荷问题。题。动态规划问题的基本概念动态规划问题的基本概念以前述求最短路为例说明动态规划问题中概念。以前述求最短路为例说明动态规划问题中概念。阶段与阶段变量阶段与阶段变量决策：处理问题时，从多个方案中作出的一某决策：处理问题时，从多个方

6、案中作出的一某种选择种选择。阶段：为解决复杂问题而把一个过程划分为若阶段：为解决复杂问题而把一个过程划分为若干个相互区别又相互联系的部分。干个相互区别又相互联系的部分。一般地，一个决策可从一个阶段变到另一阶段。一般地，一个决策可从一个阶段变到另一阶段。阶段的划分依据：阶段的划分依据：阶段一般是根据，（阶段一般是根据，（1 1）时间（）时间（2 2）空间等自然）空间等自然特征来划分。（特征来划分。（3 3）也可以是其他人为方式。）也可以是其他人为方式。阶段变量：阶段变量：描述阶段的变量，一般用描述阶段的变量，一般用k k表示。为离散变量，表示。为离散变量，取值取值1 1，2.n2.n分别表示分别

7、表示1 1，2 n2 n阶段。阶段。AB1B2B3C1C2C3D1D2D3E1E2F354954351715846442226975141阶段阶段2阶段阶段3阶段阶段4阶段阶段5阶段阶段状态与状态变量状态与状态变量状状态态：表表示示每每个个阶阶段段开开始始时时所所处处的的自自然然状状况况或或客客观观条条件件，又又称称为为不不可可控控因因素素，是是阶阶段段的的特特征，通常一个阶段有若干个状态。征，通常一个阶段有若干个状态。如如：前前例例，第第一一阶阶段段状状态态为为点点A A，第第二二阶阶段段的状态有的状态有B1B1，B2B2，B3B3三个状态。三个状态。状状态态变变量量：描描述述过过程程状状态

8、态的的变变量量称称为为，一一般般用用xk表示第表示第k k个阶段的状态变量。个阶段的状态变量。状状态态集集：k k阶阶段段所所有有可可能能状状态态构构成成的的集集合合。记为记为SkSk，如，如S2=B1,B2,B3S2=B1,B2,B3状态的无后效性：状态的无后效性：即当某阶段的状态一旦确定即当某阶段的状态一旦确定,则此后过程的则此后过程的演变不再受此前各状态和决策的影响演变不再受此前各状态和决策的影响,或者说或者说“未来与过去无关未来与过去无关”。即由状态即由状态xk出发的后部子过出发的后部子过程可以看成一个以程可以看成一个以xk为初始状态的独立过程。为初始状态的独立过程。注：注：阶段的划分

9、与状态的选择要具有此性质，阶段的划分与状态的选择要具有此性质，是动态规划问题的特点。是动态规划问题的特点。决策与决策变量决策与决策变量决策：决策：使在使在k k阶段，使状态从阶段，使状态从xk 到到xk+1 发生发生转移的选择。转移的选择。决策变量决策变量：描述决策的变量称为决策变描述决策的变量称为决策变量，一般用量，一般用u uk k表示第表示第k k个阶段的决策变量。个阶段的决策变量。决策空间：决策空间：即决策变量可能取值的集合，用即决策变量可能取值的集合，用D Dk k(x(xk k)表示第表示第k k个阶段个阶段x xk k状态下的所有允许决策的状态下的所有允许决策的集合。集合。状态转

10、移方程状态转移方程状态转移：系统由某一阶段的一个状态因相状态转移：系统由某一阶段的一个状态因相关决策而转变到下一个阶段的另一个状态。与阶关决策而转变到下一个阶段的另一个状态。与阶段、状态和决策有关，用下图示意：段、状态和决策有关，用下图示意：k阶段阶段决策决策输入状态输入状态输出状态输出状态称称为为状态转移方程状态转移方程全过程与后部全过程与后部k k子过程子过程从从k k阶段开始到终止状态为止的过程称为动阶段开始到终止状态为止的过程称为动态规划问题的态规划问题的后部后部 k k 子过程子过程。如下图所示：。如下图所示：全过程：全过程：k=1k=1时的子过程。时的子过程。k=1k=n kk=2

11、n kk+1k=n,n-1,n-23,2,1k=n,n-1,n-23,2,1策略与策略与k k子策略子策略策略：策略：设设 为为k k阶段作出的决阶段作出的决策，则称其组成的决策序列策，则称其组成的决策序列 为整个过程的一个全过程策略，简称为策略，记为整个过程的一个全过程策略，简称为策略，记为为p1,n(x1)。可供选择的所有全过程策略的集合构可供选择的所有全过程策略的集合构成允许策略集合，记为成允许策略集合，记为P1,n(x1)。最优策略：最优策略：使总体效果达到最优的策略。记使总体效果达到最优的策略。记为为 k子策略子策略:k部子过程对应决策形成的决策序部子过程对应决策形成的决策序列。记为

12、列。记为pk,n(xk)=)=指标函数与最优指标数指标函数与最优指标数阶段指标函数：阶段指标函数：指对某一个阶段的决策效果指对某一个阶段的决策效果进行衡量其优劣的一种数量指标。进行衡量其优劣的一种数量指标。一般记为：一般记为：vk(xk;uk)K K指过程的指标函数：指过程的指标函数：描述描述k k子过程策略效子过程策略效果优劣的数量函数，记为：果优劣的数量函数，记为：Vk,n(xk;pk,n)或或Vk,n 。由由阶段划分与状态选择的无后效性知，阶段划分与状态选择的无后效性知，k k阶阶段指标函数具有可分性，即可写为：段指标函数具有可分性，即可写为：K=1K=1时称为时称为全过程的指标函数。全

13、过程的指标函数。一般地，其可分性写为一般地，其可分性写为最最优优指标函数：指标函数的最优值称为指标函数：指标函数的最优值称为最优指标函数，记为最优指标函数，记为即有：即有：注注:指标函数的含义是多样的指标函数的含义是多样的,如如:距离、距离、利润、成本、产品产量、资源消耗等。利润、成本、产品产量、资源消耗等。最优化原理最优化原理“作为全过程的最优策略具有这样的性质：作为全过程的最优策略具有这样的性质：无论过去的状态和决策如何，对于前面决策所形无论过去的状态和决策如何，对于前面决策所形成的状态（即该最优策略上某一状态）而言，余成的状态（即该最优策略上某一状态）而言，余下的诸决策必须构成以此状态为

14、初始状态的最优下的诸决策必须构成以此状态为初始状态的最优策略。策略。即：最优策略的任一后部子策略都是最优的。即：最优策略的任一后部子策略都是最优的。最优化原理与动态规划问题基本方程最优化原理与动态规划问题基本方程即，即，为最优策略为最优策略,对任意阶段对任意阶段k(1kn),k(1kn),他他的子策略的子策略 对于对于 为为 始点始点的后部的后部k k子过程而言，也必须是最优的。子过程而言，也必须是最优的。注：最优化原理只是最优性定理的一个推论，注：最优化原理只是最优性定理的一个推论，即最优策略的必要条件。即最优性原理不是对任即最优策略的必要条件。即最优性原理不是对任何决策过程普遍成立，它与基

15、本方程不是无条件何决策过程普遍成立，它与基本方程不是无条件等价。等价。动态规划问题的基本方程动态规划问题的基本方程利用动态规划最优性原理，可以把多阶段决利用动态规划最优性原理，可以把多阶段决策问题求解看成是对若干个相互联系的子问题逐策问题求解看成是对若干个相互联系的子问题逐个求解的反向递推过程。个求解的反向递推过程。求解的过程可用如下基本方程描述：求解的过程可用如下基本方程描述：k=1k=n kk=2逆逆序计算序计算fk(xk)表示第k阶段初始状态为xk时，k后部子过程的最优准则函数 故逆序递推法的基本方程为：故逆序递推法的基本方程为：顺序递推算法的基本方程：顺序递推算法的基本方程：k=1k=

16、n kk=2顺序计算顺序计算此两个此两个基本方程描述多阶段决策问题的求解基本方程描述多阶段决策问题的求解方法，可以处理广泛的实际优化问题，而且可以方法，可以处理广泛的实际优化问题，而且可以得到各阶段的一系列最优解。得到各阶段的一系列最优解。但是要受到维数限制。但是要受到维数限制。顺序递推算法的基本方程：顺序递推算法的基本方程：求解求解动态规划问题的过程：动态规划问题的过程：（1）将将问问题题过过程程划划分分恰恰当当阶阶段段，选选择择阶阶段段变量变量k.。（2）正正确确选选择择状状态态变变量量xk.应应注注意意：既既能能够够正确描过程的演变，又要满足无后效性。正确描过程的演变，又要满足无后效性。

17、（3）正正确确选选择择决决策策变变量量uk，确确定定允允许许集集合合。（4）正正确确写写出出状状态态转转移移方方程程xk+1=Tk(xk,uk)。（5 5）列列出出按按阶阶段段可可分分的的准准则则函函数数V1,n，要要满足几个性质。满足几个性质。（6）根据求解方向，给出边界条件。）根据求解方向，给出边界条件。（7）利用基本方程逆推求解。）利用基本方程逆推求解。动态规划的最优性定理动态规划的最优性定理最优性原理仅为策略最优的必要条件，是最最优性原理仅为策略最优的必要条件，是最优性定理的推论，为此下面介绍最优性定理。优性定理的推论，为此下面介绍最优性定理。设设阶阶段段为为n的的多多阶阶段段决决策策

18、过过程程，决决策策变变量量k=1,2,n,允允许许策策略略是是最最优优策策略略的的充充要要条条件件是是:对对任任意意1kn,当初始状态为当初始状态为x1时时,有：有：(4.3)式中式中 ,即即 是由给定的初始状态是由给定的初始状态x1和和子策略子策略p1，k-1所确定的第所确定的第k阶段的状态阶段的状态.。例例一：前述最短距离问题逆向标注法一：前述最短距离问题逆向标注法动态规划应用举例动态规划应用举例AB1B2B3C1C2C3D1D2D3E1E2F354954351715846442226975141阶段阶段2阶段阶段3阶段阶段4阶段阶段5阶段阶段首先求第五阶段各点到首先求第五阶段各点到F点的

19、最短距离点的最短距离12AB1B2B3C1C2C3D1D2D3E1E2F354954351715846442226975141阶段阶段2阶段阶段3阶段阶段4阶段阶段5阶段阶段12逆推逆推一个阶段，用基本方程求第一个阶段，用基本方程求第4阶段和状态点到阶段和状态点到F点的最短距离。点的最短距离。如：如：f4(D1)=min4+1,2+2=4,即即D1经经E2到到F为最短路径。为最短路径。同理可标注出其它各点到同理可标注出其它各点到F点的最短距离与路径。点的最短距离与路径。47751181491214最后得最优解，最短距离为最后得最优解，最短距离为14，路径为，路径为A-B2-C1-D1-E2-F

20、动态规划应用动态规划应用资源分配问题资源分配问题 设设有有某某种种资资源源，数数量量为为a a，用用于于生生产产n n种种产产品品，若若分分配配数数量量为为uk用用于于生生产产第第k种种产产品品时时，其其收收益益为为gk(uk)。问问应应当当如如何何分分配配资源，才使生产资源，才使生产n种产品总收益最大？种产品总收益最大？此问题当此问题当gk(uk)为非线性函数时，为非线性规划问题。此为非线性函数时，为非线性规划问题。此问题虽为静态问题，但人为引进阶段与状态变量后，可用动态问题虽为静态问题，但人为引进阶段与状态变量后，可用动态规划模型求解。规划模型求解。模型模型将把将把资料分配给一个或多个使用

21、者的过程作资料分配给一个或多个使用者的过程作为一个阶段，此静态规划问题的决策变量为多阶为一个阶段，此静态规划问题的决策变量为多阶段决策变量，将累计的量或递推过程中变化的量段决策变量，将累计的量或递推过程中变化的量选择为状态变量。选择为状态变量。决变量策变量决变量策变量 uk 表示分配给第表示分配给第k k种产品的原种产品的原料数，状态料数，状态 xk 表示分配用于生产第表示分配用于生产第k k种产品至第种产品至第n n种种产品的原料数，则有状态转移方程：产品的原料数，则有状态转移方程：而且而且 阶段指标函阶段指标函数为数为 边界条件为边界条件为 于是此静态规划问题转变的动态规划问题于是此静态规

22、划问题转变的动态规划问题的基本方程为：的基本方程为：其中其中fk(xk)表示将手中资源表示将手中资源xk分配分配生产第生产第k种种到第到第n种产品时的最大利润。种产品时的最大利润。下边以具体例子说明计算过程。下边以具体例子说明计算过程。例：例：某公司现有某公司现有4台设备准备分配给该公司台设备准备分配给该公司所属的所属的3家工厂家工厂.当分配台当分配台uk设备给工厂设备给工厂k时，工时，工厂厂k利用这些设备为公司创造的利润（假设非负）利用这些设备为公司创造的利润（假设非负）为为gk(uk).应当如何分配设备资源，使得公司总应当如何分配设备资源，使得公司总利润最大？其利润见下表：利润最大？其利润

23、见下表：工厂工厂k k设备数设备数12301234046770256803578将此将此问题划分为三个阶段，问题划分为三个阶段，1 1，2 2，3 3个工厂，个工厂，其模型为前述模型中其模型为前述模型中n=3,a=4n=3,a=4基本方程为：基本方程为：从最后一个阶段，即从最后一个阶段，即3 3阶段计算，并逐次逆阶段计算，并逐次逆推，直到求出最优解。推，直到求出最优解。K=3时时k k=2=2时：时：k k=1=1时：时：得最优解得最优解 ,最大利润为最大利润为 。U1=1,x2=4-1=3,u2=2,x3=1,u3=1即给第一个即给第一个工厂分配工厂分配1台台,第二个工厂分配第二个工厂分配2台台,第三工第三工厂分配厂分配1台设备台设备,可使总利润最大可使总利润最大,其值为其值为12。用动态规划原理求解静态规划问题用动态规划原理求解静态规划问题某些静态规划问题，在适当引入阶段变某些静态规划问题，在适当引入阶段变量及状态变量之后，可转化为动态规划问量及状态变量之后，可转化为动态规划问题求解。题求解。并且可以用逆推算法或顺推算法求解。并且可以用逆推算法或顺推算法求解。以具体例子加以说明。以具体例子加以说明。P206211动态规划的计算框图动态规划的计算框图详见详见P211213