运筹学教案动态规划ppt课件

运筹学教案运筹学教案动态规划动态规划陈安明陈安明概述概述 动态规划为运筹学的一个分支，是用于求解动态规划为运筹学的一个分支，是用于求解多个阶段决策过程的最优化数学方法。多个阶段决策过程的最优化数学方法。 理论基础：理论基础： 美国数学家贝尔曼（美国数学家贝尔曼（Richard Bellman)Richard Bellman)研研究提出的最优化原理（究提出的最优化原理（Principle of Decision)Principle of Decision)把多阶段过程转化为一系列单阶段问题，逐个把多阶段过程转化为一系列单阶段问题，逐个求解，创立一类求解多阶段过程优化问题的方求解，创立一类求解多阶段过程优化问题的方法法动态规划（动态规划（Dynamic Programming)Dynamic Programming) 动态规划的应用领域动态规划的应用领域 经济管理、工程技术、工农业生产及军经济管理、工程技术、工农业生产及军事部门。事部门。 具体讲：如最短路线，资源分配，库存具体讲：如最短路线，资源分配，库存管理，生产调度，排序，装载，市场营销，管理，生产调度，排序，装载，市场营销，设备维修与更新等方面。设备维修与更新等方面。 主要解决时序或空间序阶段划分的多阶段主要解决时序或空间序阶段划分的多阶段问题。但对一些与时间甚至与空间都无关的问题。但对一些与时间甚至与空间都无关的静态问题，在引入特殊序之后用动态规划方静态问题，在引入特殊序之后用动态规划方法处理。法处理。多阶段决策过程及实例多阶段决策过程及实例 多阶段决策问题举例多阶段决策问题举例 从从A地经地经B、C、D、E到到F地铺设管线，地铺设管线，问，怎样铺设，可使管线最短？问，怎样铺设，可使管线最短？AB1B2B3C1C2C3D1D2D3E1E2F35495435171584644222697514 若用穷举法求解，计算量大，且容易遗漏某一若用穷举法求解，计算量大，且容易遗漏某一路径。路径。 本例可将其划分为五个阶段，用动态规划原理本例可将其划分为五个阶段，用动态规划原理求其最短路径。求其最短路径。 思路：思路： 从从A站出发应经过哪些站点到站出发应经过哪些站点到F站的总长度最站的总长度最短？若已作出从短？若已作出从ABi中之一决策，之后的问题变中之一决策，之后的问题变为，从各为，从各Bi站点经哪些站点到站点经哪些站点到F点的总长度最短，点的总长度最短，仍为一多阶段决策问题，与前一问题相似，解决方仍为一多阶段决策问题，与前一问题相似，解决方法也相似，只是少了一个阶段，问题变小了，若后法也相似，只是少了一个阶段，问题变小了，若后一问题解决了，则前一问题也解决了。一问题解决了，则前一问题也解决了。 类似地，到了类似地，到了C站、站、D站、站、E站，都面临同一站，都面临同一问题，只是问题越来越小并易于解决。问题，只是问题越来越小并易于解决。 到了到了E站，从其各点到站，从其各点到F的最短距离已易得，的最短距离已易得，再逆推，可求出再逆推，可求出D站各点到站各点到F点的最短距离，逐次点的最短距离，逐次逆推，到最后可以求出逆推，到最后可以求出A点到点到F点的最短距离。点的最短距离。 这就是动态规划问题逆推算法。这就是动态规划问题逆推算法。 动态规划问题其它例子，见动态规划问题其它例子，见P193 机器负荷问机器负荷问题。题。动态规划问题的基本概念动态规划问题的基本概念以前述求最短路为例说明动态规划问题中概念。以前述求最短路为例说明动态规划问题中概念。 阶段与阶段变量阶段与阶段变量 决策：处理问题时，从多个方案中作出的一某决策：处理问题时，从多个方案中作出的一某种选择种选择。 阶段：为解决复杂问题而把一个过程划分为若阶段：为解决复杂问题而把一个过程划分为若干个相互区别又相互联系的部分。干个相互区别又相互联系的部分。 一般地，一个决策可从一个阶段变到另一阶段。一般地，一个决策可从一个阶段变到另一阶段。阶段的划分依据：阶段的划分依据： 阶段一般是根据，（阶段一般是根据，（1 1）时间（）时间（2 2）空间等自然）空间等自然特征来划分。（特征来划分。（3 3）也可以是其他人为方式。）也可以是其他人为方式。阶段变量：阶段变量： 描述阶段的变量，一般用描述阶段的变量，一般用k k表示。为离散变量，表示。为离散变量，取值取值1 1，2 2.n.n分别表示分别表示1 1，2 2 n n阶段。阶段。AB1B2B3C1C2C3D1D2D3E1E2F354954351715846442226975141 阶段阶段2 阶段阶段3 阶段阶段4 阶段阶段5 阶段阶段状态与状态变量状态与状态变量状态：状态： 表示每个阶段开始时所处的自然状表示每个阶段开始时所处的自然状况或客观条件，又称为不可控因素，是阶段的特况或客观条件，又称为不可控因素，是阶段的特征，通常一个阶段有若干个状态。征，通常一个阶段有若干个状态。如：前例，第一阶段状态为点如：前例，第一阶段状态为点A A，第二阶段，第二阶段的状态有的状态有B1B1，B2B2，B3B3三个状态。三个状态。状态变量：状态变量：描述过程状态的变量称为，一般描述过程状态的变量称为，一般用用xk表示第表示第k k个阶段的状态变量。个阶段的状态变量。状态集：状态集： k k阶段所有可能状态构成的集合。阶段所有可能状态构成的集合。记为记为SkSk，如，如S2=B1,B2,B3S2=B1,B2,B3状态的无后效性：状态的无后效性：即当某阶段的状态一旦确定即当某阶段的状态一旦确定, ,则此后过程的则此后过程的演变不再受此前各状态和决策的影响演变不再受此前各状态和决策的影响, , 或者说或者说“未来与过去无关未来与过去无关”。 即由状态即由状态xk出发的后部出发的后部子过程可以看成一个以子过程可以看成一个以xk为初始状态的独立过程。为初始状态的独立过程。注：注：阶段的划分与状态的选择要具有此性质，阶段的划分与状态的选择要具有此性质，是动态规划问题的特点。是动态规划问题的特点。决策与决策变量决策与决策变量决策：决策：使在使在k k阶段，使状态从阶段，使状态从xk 到到xk+1 发生发生转移的选择。转移的选择。决策变量决策变量：描述决策的变量称为决策变描述决策的变量称为决策变量，一般用量，一般用u uk k表示第表示第k k个阶段的决策变量。个阶段的决策变量。决策空间：决策空间：即决策变量可能取值的集合，用即决策变量可能取值的集合，用D Dk k(x(xk k) )表示第表示第k k个阶段个阶段x xk k状态下的所有允许决策的状态下的所有允许决策的集合。集合。状态转移方程状态转移方程状态转移：系统由某一阶段的一个状态因相状态转移：系统由某一阶段的一个状态因相关决策而转变到下一个阶段的另一个状态。与阶关决策而转变到下一个阶段的另一个状态。与阶段、状态和决策有关，用下图示意：段、状态和决策有关，用下图示意： k1kxkxku阶段阶段决策决策输入状态输入状态输出状态输出状态),(1kkkkuxTx称称为状态转移方程为状态转移方程全过程与后部全过程与后部k k子过程子过程从从k k阶段开始到终止状态为止的过程称为动阶段开始到终止状态为止的过程称为动态规划问题的态规划问题的后部后部 k k 子过程子过程。如下图所示：。如下图所示：全过程：全过程：k=1k=1时的子过程。时的子过程。k=1k=n kk=21x2x3x1kx1nxkxnx1u2ukunun kk+11kx1nxkxnxkunu1ku2kxk=n,n-1,n-2k=n,n-1,n-23,2,13,2,1策略与策略与k k子策略子策略策略：策略：设设 为为k k阶段作出的决阶段作出的决策，则称其组成的决策序列策，则称其组成的决策序列 为整个过程的一个全过程策略，简称为策略，记为整个过程的一个全过程策略，简称为策略，记为为p1,n(x1) )。可供选择的所有全过程策略的集合构。可供选择的所有全过程策略的集合构成允许策略集合，记为成允许策略集合，记为P1,n(x1) )。最优策略：最优策略：使总体效果达到最优的策略。记使总体效果达到最优的策略。记为为 k子策略子策略: k部子过程对应决策形成的决策序部子过程对应决策形成的决策序列。记为列。记为pk,n(xk)=)=),(*2*1*, 1nnuuupnkxukk, 2 , 1)()(),(),(2211nnxuxuxu)(),(),(11nnkkkkxuxuxu指标函数与最优指标数指标函数与最优指标数阶段指标函数：阶段指标函数：指对某一个阶段的决策效果指对某一个阶段的决策效果进行衡量其优劣的一种数量指标。进行衡量其优劣的一种数量指标。一般记为：一般记为： vk(xk; uk) )K K指过程的指标函数：指过程的指标函数：描述描述k k子过程策略效子过程策略效果优劣的数量函数，记为：果优劣的数量函数，记为： Vk,n(xk; pk,n ) ) 或或Vk,n 。由阶段划分与状态选择的无后效性知，由阶段划分与状态选择的无后效性知，k k阶阶段指标函数具有可分性，即可写为：段指标函数具有可分性，即可写为：K=1K=1时称为时称为全过程的指标函数。全过程的指标函数。198*),(),(),(111,PuxvuxvuxvVnnnkkkkkknk具体形式详见等运算符。或乘法算，如加法是满足单调性的某种运其中一般地，其可分性写为一般地，其可分性写为最优指标函数：指标函数的最优值称最优指标函数：指标函数的最优值称为最优指标函数，记为为最优指标函数，记为即有：即有：nkkkknjjjjnkVuxvuxvV,11,),(),()(kkxf),()(1,),(2nnnkknkuuukkxuxuxVxfoptnk注注: 指标函数的含义是多样的指标函数的含义是多样的,如如:距离、距离、利润、成本、产品产量、资源消耗等。利润、成本、产品产量、资源消耗等。最优化原理最优化原理“作为全过程的最优策略具有这样的性质：作为全过程的最优策略具有这样的性质：无论过去的状态和决策如何，对于前面决策所形无论过去的状态和决策如何，对于前面决策所形成的状态（即该最优策略上某一状态）而言，余成的状态（即该最优策略上某一状态）而言，余下的诸决策必须构成以此状态为初始状态的最优下的诸决策必须构成以此状态为初始状态的最优策略。策略。即：最优策略的任一后部子策略都是最优的。即：最优策略的任一后部子策略都是最优的。最优化原理与动态规划问题基本方程最优化原理与动态规划问题基本方程即，即， 为最优策略为最优策略, ,对任意阶段对任意阶段k(1kn),k(1kn),他的子策略他的子策略 对于对于 为为 始始点的后部点的后部k k子过程而言，也必须是最优的。子过程而言，也必须是最优的。)(1*, 1xpn)(*,knkxp),(111kkkkuxTx注：最优化原理只是最优性定理的一个推论，注：最优化原理只是最优性定理的一个推论，即最优策略的必要条件。即最优性原理不是对任即最优策略的必要条件。即最优性原理不是对任何决策过程普遍成立，它与基本方程不是无条件何决策过程普遍成立，它与基本方程不是无条件等价。等价。动态规划问题的基本方程动态规划问题的基本方程利用动态规划最优性原理，可以把多阶段决利用动态规划最优性原理，可以把多阶段决策问题求解看成是对若干个相互联系的子问题逐策问题求解看成是对若干个相互联系的子问题逐个求解的反向递推过程。个求解的反向递推过程。求解的过程可用如下基本方程描述：求解的过程可用如下基本方程描述：k=1k=n kk=21x2x3x1kx1nxkxnx),(111uxv1u2ukunu),(222uxv),(kkkuxv),(nnnuxv逆序计算逆序计算)(),();(),();(),();()(11, 11, 1)(, 11, 1)(,)(1,1,1,kkkkkUunkknkxPpkkkUunkknkkkkxPpnkknkxPpkkxfuxvoptpxVoptuxvoptpxVuxvoptpxVoptxfkkknknkkkknknkknknkfk(xk)表示第k阶段初始状态为xk时，k后部子过程的最优准则函数 故逆序递推法的基本方程为：故逆序递推法的基本方程为：1 , 2 , 3, 1,(0)(),()(),()(11111nnkxfuxTxxfuxvoptxfnnkkkkkkkkkUukkkk边界条件）顺序递推算法的基本方程：顺序递推算法的基本方程：k=1k=n kk=21x2x3x1kx1nxkxnx),(111uxv1u2ukunu),(222uxv),(kkkuxv),(nnnuxv顺序计算顺序计算此两个基本方程描述多阶段决策问题的求解此两个基本方程描述多阶段决策问题的求解方法，可以处理广泛的实际优化问题，而且可以方法，可以处理广泛的实际优化问题，而且可以得到各阶段的一系列最优解。得到各阶段的一系列最优解。但是要受到维数限制。但是要受到维数限制。 nnkxfuxTxxfuxvoptxfkkkkkkkkkUukkkk, 12 , 1(0)(),()(),()(101111边界条件）顺序递推算法的基本方程：顺序递推算法的基本方程：求解动态规划问题的过程：求解动态规划问题的过程：（1）将问题过程划分恰当阶段，选择阶段）将问题过程划分恰当阶段，选择阶段变量变量k.。（2）正确选择状态变量）正确选择状态变量xk. 应注意：既能够应注意：既能够正确描过程的演变，又要满足无后效性。正确描过程的演变，又要满足无后效性。 （3）正确选择决策变量）正确选择决策变量uk，确定允许集合，确定允许集合 。（4）正确写出状态转移方程）正确写出状态转移方程 xk+1= Tk(xk, uk)。（5 5） 列出按阶段可分的准则函数列出按阶段可分的准则函数V1,n ，要，要满足几个性质。满足几个性质。（6）根据求解方向，给出边界条件。）根据求解方向，给出边界条件。（7）利用基本方程逆推求解。）利用基本方程逆推求解。动态规划的最优性定理动态规划的最优性定理最优性原理仅为策略最优的必要条件，是最最优性原理仅为策略最优的必要条件，是最优性定理的推论，为此下面介绍最优性定理。优性定理的推论，为此下面介绍最优性定理。 设阶段为设阶段为n的多阶段决策过程，决策变量的多阶段决策过程，决策变量k=1,2,n,允许策允许策略略 是最优策略的充要条件是是最优策略的充要条件是: 对任意对任意1kn, 当当初始状态为初始状态为x1时时, 有：有：(4.3)式中式中 , ,即即 是由给定的初始状态是由给定的初始状态x1和和子策略子策略p1，k-1所确定的第所确定的第k阶段的状态阶段的状态.。),(*2*1*, 1nnuuup);();();(,)(1, 111, 1)(*, 11, 1,11, 11, 1nkknkxPpkkxPpnnpxVoptpxVoptpxVknknkkk);(,1, 1, 1nkknppp),(111kkkkuxTxkx例一：前述最短距离问题逆向标注法例一：前述最短距离问题逆向标注法动态规划应用举例动态规划应用举例AB1B2B3C1C2C3D1D2D3E1E2F354954351715846442226975141 阶段阶段2 阶段阶段3 阶段阶段4 阶段阶段5 阶段阶段首先求第五阶段各点到首先求第五阶段各点到F点的最短距离点的最短距离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动态规划应用动态规划应用资源分配问题资源分配问题 设有某种资源，数量为设有某种资源，数量为a a，用于生产，用于生产n n种产品，若种产品，若分配数量分配数量为为uk用于生产第用于生产第k种产品时，其收益为种产品时，其收益为gk(uk)。问应当如何分配。问应当如何分配资源，才使生产资源，才使生产n种产品总收益最大？种产品总收益最大？ Zuautsugzkknkknkk11.)(max 此问题当此问题当gk(uk)为非线性函数时，为非线性规划问题。此为非线性函数时，为非线性规划问题。此问题虽为静态问题，但人为引进阶段与状态变量后，可用动态问题虽为静态问题，但人为引进阶段与状态变量后，可用动态规划模型求解。规划模型求解。模型模型将把资料分配给一个或多个使用者的过程作将把资料分配给一个或多个使用者的过程作为一个阶段，此静态规划问题的决策变量为多阶为一个阶段，此静态规划问题的决策变量为多阶段决策变量，将累计的量或递推过程中变化的量段决策变量，将累计的量或递推过程中变化的量选择为状态变量。选择为状态变量。决变量策变量决变量策变量 uk 表示分配给第表示分配给第k k种产品的原种产品的原料数，状态料数，状态 xk 表示分配用于生产第表示分配用于生产第k k种产品至第种产品至第n n种产品的原料数，则有状态转移方程：种产品的原料数，则有状态转移方程： 而且而且 阶段指标函阶段指标函数为数为 边界条件为边界条件为 kkkuxx1kkxu 0)(),(kkkkkuguxvax 101nx 于是此静态规划问题转变的动态规划问题于是此静态规划问题转变的动态规划问题的基本方程为：的基本方程为：1 , 1,0)(0)()(max)(11111110nnkxfaxxuxxxfugxfnnnkkkkkkkxukkkk 其中其中fk(xk) 表示将手中资源表示将手中资源xk分配生产第分配生产第k种种到第到第n种产品时的最大利润。种产品时的最大利润。 下边以具体例子说明计算过程。下边以具体例子说明计算过程。 例：例：某公司现有某公司现有4台设备准备分配给该公司台设备准备分配给该公司所属的所属的3家工厂家工厂. 当分配台当分配台uk设备给工厂设备给工厂k时，工时，工厂厂k利用这些设备为公司创造的利润（假设非负）利用这些设备为公司创造的利润（假设非负）为为gk(uk). 应当如何分配设备资源，使得公司总利应当如何分配设备资源，使得公司总利润最大？其利润见下表：润最大？其利润见下表：)(kkugku 工厂工厂k k设备数设备数 1 2 301234046770256803578将此问题划分为三个阶段，将此问题划分为三个阶段，1 1，2 2，3 3个工厂，个工厂，其模型为前述模型中其模型为前述模型中n=3,a=4n=3,a=4基本方程为：基本方程为：从最后一个阶段，即从最后一个阶段，即3 3阶段计算，并逐次逆阶段计算，并逐次逆推，直到求出最优解。推，直到求出最优解。1 , 2 , 30)(40)()(max)(44141110kxfxxuxxxfugxfkkkkkkkxukkkk8) 4() 4(8) 4() 4(; 7) 3() 3(; 5) 2() 2(; 3) 1 () 1 (; 0) 0() 0()()0()(max)(3333333333333343303333gfgfgfgfgfgfxgfugxfxuK=3时时k k=2=2时：时： )()(max)()(max)(22322033220222222uxfugxfugxfxuxu; 000)0()0()0()(max)0(3223220022fgufugfu; 302 , 30max)0() 1 (),1 ()0(max)1 ()(max) 1 (323223221022fgfgufugfu; 505 , 32 , 50max)0 () 2 (),1 () 1 (),2 () 0 (max)2 ()(max) 2 (32323223222022fgfgfgufugfu; 806 , 35 , 52 , 70max)0 () 3 (),1 () 2 (),2 () 1 (),3 () 0 (max)3 ()(max) 3 (3232323223223022fgfgfgfgufugfu;1008 , 36 , 55 , 72 , 80max)0 () 4 (),1 () 3 (),2 () 2 (),3 () 1 (),4 () 0 (max)4 ()(max) 4 (323232323223224022fgfgfgfgfgufugfuk k=1=1时：时：.1207 , 37 , 56 , 84 ,100max)0()4(),1 ()3(),2()2(),3() 1 (),4()0(max)4()(max)4(212121212112114011fgfgfgfgfgufugfu)()(max)()(max)(11211022110111111uxfugxfugxfxuxu得最优解得最优解 , ,最大利润为最大利润为 。 1, 2, 1*3*2*1uuu12)4(1* fz0 01 12 23 34 40 00 00 00 01 13 33 31 12 25 55 52 23 37 77 73 34 48 88 84 4 u3x3g3(u3)f3(x3) u3*0 01 12 23 34 44 40+10 4+86+57+37+012121 1 u1x1g1(u1)+f2(4-u1)f1(4)u1*U1=1,x2=4-1=3,u2=2,x3=1,u3=1即给第一个即给第一个工厂分配工厂分配1台台,第二个工厂分配第二个工厂分配2台台,第三工厂第三工厂分配分配1台设备台设备,可使总利润最大可使总利润最大,其值为其值为12。用动态规划原理求解静态规划问题用动态规划原理求解静态规划问题某些静态规划问题，在适当引入阶段某些静态规划问题，在适当引入阶段变量及状态变量之后，可转化为动态规划变量及状态变量之后，可转化为动态规划问题求解。问题求解。并且可以用逆推算法或顺推算法求解。并且可以用逆推算法或顺推算法求解。以具体例子加以说明。以具体例子加以说明。P206211动态规划的计算框图动态规划的计算框图详见详见P211213