运筹学教案动态规划.ppt

运筹学教案,动态规划,陈安明,概述,动态规划为运筹学的一个分支，是用于求解多个阶段决策过程的最优化数学方法。理论基础：美国数学家贝尔曼（Richard Bellman)研究提出的最优化原理（Principle of Decision)把多阶段过程转化为一系列单阶段问题，逐个求解，创立一类求解多阶段过程优化问题的方法动态规划（Dynamic Programming),动态规划的应用领域 经济管理、工程技术、工农业生产及军事部门。具体讲：如最短路线，资源分配，库存管理，生产调度，排序，装载，市场营销，设备维修与更新等方面。主要解决时序或空间序阶段划分的多阶段问题。但对一些与时间甚至与空间都无关的静态问题，在引入特殊序之后用动态规划方法处理。,多阶段决策过程及实例,多阶段决策问题举例 从A地经B、C、D、E到F地铺设管线，问，怎样铺设，可使管线最短？,若用穷举法求解，计算量大，且容易遗漏某一路径。本例可将其划分为五个阶段，用动态规划原理求其最短路径。思路：从A站出发应经过哪些站点到F站的总长度最短？若已作出从ABi中之一决策，之后的问题变为，从各Bi站点经哪些站点到F点的总长度最短，仍为一多阶段决策问题，与前一问题相似，解决方法也相似，只是少了一个阶段，问题变小了，若后一问题解决了，则前一问题也解决了。,类似地，到了C站、D站、E站，都面临同一问题，只是问题越来越小并易于解决。到了E站，从其各点到F的最短距离已易得，再逆推，可求出D站各点到F点的最短距离，逐次逆推，到最后可以求出A点到F点的最短距离。这就是动态规划问题逆推算法。动态规划问题其它例子，见P193 机器负荷问题。,动态规划问题的基本概念,以前述求最短路为例说明动态规划问题中概念。,阶段与阶段变量 决策：处理问题时，从多个方案中作出的一某种选择。阶段：为解决复杂问题而把一个过程划分为若干个相互区别又相互联系的部分。一般地，一个决策可从一个阶段变到另一阶段。,阶段的划分依据：阶段一般是根据，（1）时间（2）空间等自然特征来划分。（3）也可以是其他人为方式。阶段变量：描述阶段的变量，一般用k表示。为离散变量，取值1，2.n分别表示1，2 n阶段。,1 阶段,2 阶段,3 阶段,4 阶段,5 阶段,状态与状态变量状态：表示每个阶段开始时所处的自然状况或客观条件，又称为不可控因素，是阶段的特征，通常一个阶段有若干个状态。如：前例，第一阶段状态为点A，第二阶段的状态有B1，B2，B3三个状态。状态变量：描述过程状态的变量称为，一般用xk表示第k个阶段的状态变量。状态集：k阶段所有可能状态构成的集合。记为Sk，如S2=B1,B2,B3,状态的无后效性：即当某阶段的状态一旦确定,则此后过程的演变不再受此前各状态和决策的影响,或者说“未来与过去无关”。即由状态xk出发的后部子过程可以看成一个以xk为初始状态的独立过程。注：阶段的划分与状态的选择要具有此性质，是动态规划问题的特点。决策与决策变量决策：使在k阶段，使状态从xk 到xk+1 发生转移的选择。决策变量：描述决策的变量称为决策变量，一般用uk表示第k个阶段的决策变量。,决策空间：即决策变量可能取值的集合，用Dk(xk)表示第k个阶段xk状态下的所有允许决策的集合。状态转移方程状态转移：系统由某一阶段的一个状态因相关决策而转变到下一个阶段的另一个状态。与阶段、状态和决策有关，用下图示意：,阶段,决策,输入状态,输出状态,称,为状态转移方程,全过程与后部k子过程从k阶段开始到终止状态为止的过程称为动态规划问题的后部 k 子过程。如下图所示：全过程：k=1时的子过程。,n,k,k+1,k=n,n-1,n-23,2,1,策略与k子策略策略：设 为k阶段作出的决策，则称其组成的决策序列 为整个过程的一个全过程策略，简称为策略，记为p1,n(x1)。可供选择的所有全过程策略的集合构成允许策略集合，记为P1,n(x1)。最优策略：使总体效果达到最优的策略。记为 k子策略:k部子过程对应决策形成的决策序列。记为pk,n(xk)=,指标函数与最优指标数阶段指标函数：指对某一个阶段的决策效果进行衡量其优劣的一种数量指标。一般记为：vk(xk;uk)K指过程的指标函数：描述k子过程策略效果优劣的数量函数，记为：Vk,n(xk;pk,n)或Vk,n。由阶段划分与状态选择的无后效性知，k阶段指标函数具有可分性，即可写为：K=1时称为全过程的指标函数。,一般地，其可分性写为最优指标函数：指标函数的最优值称为最优指标函数，记为即有：,注:指标函数的含义是多样的,如:距离、利润、成本、产品产量、资源消耗等。,最优化原理“作为全过程的最优策略具有这样的性质：无论过去的状态和决策如何，对于前面决策所形成的状态（即该最优策略上某一状态）而言，余下的诸决策必须构成以此状态为初始状态的最优策略。即：最优策略的任一后部子策略都是最优的。,最优化原理与动态规划问题基本方程,即，为最优策略,对任意阶段k(1kn),他的子策略 对于 为 始点的后部k子过程而言，也必须是最优的。,注：最优化原理只是最优性定理的一个推论，即最优策略的必要条件。即最优性原理不是对任何决策过程普遍成立，它与基本方程不是无条件等价。,动态规划问题的基本方程利用动态规划最优性原理，可以把多阶段决策问题求解看成是对若干个相互联系的子问题逐个求解的反向递推过程。求解的过程可用如下基本方程描述：,fk(xk)表示第k阶段初始状态为xk时，k后部子过程的最优准则函数,故逆序递推法的基本方程为：,顺序递推算法的基本方程：,此两个基本方程描述多阶段决策问题的求解方法，可以处理广泛的实际优化问题，而且可以得到各阶段的一系列最优解。但是要受到维数限制。,顺序递推算法的基本方程：,求解动态规划问题的过程：（1）将问题过程划分恰当阶段，选择阶段变量k.。（2）正确选择状态变量xk.应注意：既能够正确描过程的演变，又要满足无后效性。（3）正确选择决策变量uk，确定允许集合。（4）正确写出状态转移方程 xk+1=Tk(xk,uk)。（5）列出按阶段可分的准则函数V1,n，要满足几个性质。（6）根据求解方向，给出边界条件。（7）利用基本方程逆推求解。,动态规划的最优性定理最优性原理仅为策略最优的必要条件，是最优性定理的推论，为此下面介绍最优性定理。,设阶段为n的多阶段决策过程，决策变量k=1,2,n,允许策略 是最优策略的充要条件是:对任意1kn,当初始状态为x1时,有：(4.3)式中,即 是由给定的初始状态x1和子策略p1，k-1所确定的第k阶段的状态.。,例一：前述最短距离问题逆向标注法,动态规划应用举例,首先求第五阶段各点到F点的最短距离,1,2,1,2,逆推一个阶段，用基本方程求第4阶段和状态点到F点的最短距离。,如：f4(D1)=min4+1,2+2=4,即D1经E2到F为最短路径。同理可标注出其它各点到F点的最短距离与路径。,4,7,7,5,11,8,14,9,12,14,最后得最优解，最短距离为14，路径为A-B2-C1-D1-E2-F,动态规划应用资源分配问题,设有某种资源，数量为a，用于生产n种产品，若分配数量为uk用于生产第k种产品时，其收益为gk(uk)。问应当如何分配资源，才使生产n种产品总收益最大？,此问题当gk(uk)为非线性函数时，为非线性规划问题。此问题虽为静态问题，但人为引进阶段与状态变量后，可用动态规划模型求解。,模型,将把资料分配给一个或多个使用者的过程作为一个阶段，此静态规划问题的决策变量为多阶段决策变量，将累计的量或递推过程中变化的量选择为状态变量。决变量策变量 uk 表示分配给第k种产品的原料数，状态 xk 表示分配用于生产第k种产品至第n种产品的原料数，则有状态转移方程：而且 阶段指标函数为 边界条件为,于是此静态规划问题转变的动态规划问题的基本方程为：,其中fk(xk)表示将手中资源xk分配生产第k种到第n种产品时的最大利润。下边以具体例子说明计算过程。,例：某公司现有4台设备准备分配给该公司所属的3家工厂.当分配台uk设备给工厂k时，工厂k利用这些设备为公司创造的利润（假设非负）为gk(uk).应当如何分配设备资源，使得公司总利润最大？其利润见下表：,将此问题划分为三个阶段，1，2，3个工厂，其模型为前述模型中n=3,a=4基本方程为：从最后一个阶段，即3阶段计算，并逐次逆推，直到求出最优解。,K=3时,k=2时：,k=1时：,得最优解,最大利润为。,U1=1,x2=4-1=3,u2=2,x3=1,u3=1即给第一个工厂分配1台,第二个工厂分配2台,第三工厂分配1台设备,可使总利润最大,其值为12。,用动态规划原理求解静态规划问题,某些静态规划问题，在适当引入阶段变量及状态变量之后，可转化为动态规划问题求解。并且可以用逆推算法或顺推算法求解。以具体例子加以说明。P206211,动态规划的计算框图,详见P211213,