动态规划培训

一、什么是动态规划（DynamicProgramming）过程最优化：为了实现某项预定任务，需要对任务之前的过程施加控制，任务实现的好坏可以用某个数值指标衡量。在此情况下，需要选择一个措施去控制过程的发展，以期最好的完成任务，称这样的问题为过程最优化。多阶段决策问题：若过程可分为互相联系的若干阶段,每阶段都需做决策,且决策之间不是孤立的,有一定的联系.当前的决策影响当前的收益,也同时影响过程的总收益,为了达到一定的目标,下一个决策要根据上一课决策的效果做适当的调整,以实现总过程的最优化.则称该决策问题为一个多阶段决策问题（Multi-StageDecisionProblem）各阶段的决策结果构成一个决策序列,称为一个策略(Policy).每个阶段可选决策可能有很多,因此策略可能也很多.多阶段决策问题就是在众多的容许策略中,根据给定的标准选择一个最优.决策的关键：每次决策,不能仅仅从局部利益出发,也必须考虑整体的利益.动态规划是解决多阶段决策过程最优化的一种方法，主要思想是根据最优化原理，将一个多变量最优化问题转变为一系列单变量最优问题。二、动态规划基本数学描述和求解思想2.1动态规划基本构成动态规划基本元素：{决策时刻集,系统状态集,系统行动集,状态转移，转移概率,收益}系统：所针对研究的对象，称之为系统。后面具体的举例子。1）决策时刻集即做出决策的时间点集合,以T表示,其可以是连续的,也可以是离散的,可以有限、也可以无限.分类两类：当T离散时,如{1,2,,}TN,一般称周期或多阶段决策问题.1a2aNa1s2sNs结束1Ns当决策时刻是固定的，且当N有限时,称为有限周期决策问题（Finite-Period（Stage）DecisionProblem）.如果无限，则称为一个无限周期（InfinitePeriod）决策问题.我们将主要关注，离散情况。决策时刻是离散点,但是可能不是固定的,可能出现在任意的时刻点上(不是每个点必须做),如排队顾客的到来,电话的到来.这样的问题也称为离散事件动态系统（DiscreteEventDynamicSystem,DEDS）.虽然也是在离散点上决策,但是没有固定决策点.在通讯、电子、交通灯领域用的很多,主要处理难以用微分和差分方程描述的问题.当T为连续时,随机最优控制问题.2）状态和行动集通过状态，来了解系统部分信息，为把握其运行规律奠定基础。状态实际上就是我们观测理解系统的一个中介。对于一个动态系统，由于其演化是动态变化的，每个决策时刻t,系统有可能表现为不同的状态值，从而构成一个状态集,表示为tS,状态可以是向量.当决策观测到一个具体的状态ttxS时,可以从tx所允许的行动集合txA选择一个行动,如txaA.行动集是依赖于状态，不同的状态的行动集可能是不同的.,ttxSA都可以是有限集或无限集.这里的状态可能仅指当前时刻t的状态,也可能包含以往的所有时刻的状态.3）收益与状态转移及转移概率时刻t选择一个行动at,后果有两个：得到一个当前的收益（或成本）(,)tttrxa；状态发生转移.可以用1(,)ttxTxa，也可以用概率分布(|,)tttpjxa刻画,(|,)tttpjxa表示系统状态为tx,行动选择ta时,到状态j的转移概率.以概率1转移到某个状态，即(|,)tttpjxa，则为确定动态规划，否则，如果不存在任何概率等于1的状态，则表示为随机动态规划。对于随机动态规划而言，必须描述(|,)tttpjxa，对于确定动态规划，则不需要写该项。最优系统还有一个终端收益11()NNrx4）决策目标和最优化问题决策目标：对确定问题，一般就是总费用最小或总收益最大等；1111(,)(,)()NtttNNtVxrxarx对随机问题，一般是总费用的期望最小或总收益的期望最大.1111(,)[(,)()]NtttNNtVxErxarx最优化问题：在所有的可能的策略集合中，找一个策略***12{,,,}Naaa，使得*111()(,){(,)}WxVxOptVx5）动态规划方程（数学模型，也是算法步骤）基于动态规划原理，将上面的最优化问题用动态规划方程等价表示，实现多变量复杂问题联合最优后到单变量简单问题独立最优化的效果。具体表示为如下方程：令1{,,,}kkkNaaa，11(,)(,)()NkkktttNNtkVxrxarx或11(,)[(,)()]NkkktttNNtkVxErxarx111{,,,}(){(,)}{(,)()kkkNNkkkkktttNNaaatkWxOptVxOptrxarx则有111(){(,)()}{(,)((,))}kkkkkktkkakkkkkkkaWxOptrxaWxOptrxaWTxa如果有限阶段问题，必须说明1111()()NNNNWxrx.表示含义是：从第k周期之后的最优等于对两部分和的最优，一部分为第k周期的收益，另外一部分为第k+1以后以1((,))kkkkxTxa为初始的最优收益。实现该过程依赖的思想——最优化原理：直观的，一个最优策略（各阶段决策顺序排列的决策集合）应该满足这样的性质,无论过去的状态和决策如何,对初始状态和前面决策所形成的当前状态而言,余下的各阶段决策仍是是最优的.简单描述为：一个最优策略的子策略仍是最优的.针对初始状态1s,如果****12{,,,}Naaa是最优的,不管以前的状态和决策如何,对于以前决策导致的当前状态ks而言,****1{,,,}kkkNaaa仍然是后面子系统的最优决策,即*(,){(,)}kkkkkkkVxOptVx最优化原理直观解释例子----最短路问题（Djstra算法）最短路为：0123456AABABBA.任意截取最优策略，则3456ABBA一定为从3A开始最优的.对于这样的问题，能够想到的方法：穷举法（小规模可以）动态规划模型，DJStra算法（对于有限状态有限阶段问题，非常有效）线性规划模型，（也相对有效）启发算法：找一个规则，尽量向优的方向靠近，每次都找一个最好的。每次都找最短的，但是结果不是最短。三、确定型动态规划对确定性问题，由于一开始就能够知道事态以后的全部信息，中间过程没有必要做一些重新调整，因此，此时有可能没有必要将一个多变量最优问题转变为单变量最优问题，直接建立一个规划模型（线性规划或非线性规划或整数规划），用相应的算法（如最速下降法、共轭梯度法、牛顿法，单纯性法等）进行求解，可能比动态规划算法更有效。对于确定问题，如果可以用别的算法，就别用动态规划算法。但是如果遇到离散的状态集规模较大时，可以用动态规划。而且动态规划获得是全局最优解，前面的方法很困难，包括单纯形法也不是最优算法。确定型动态规划模型逆序算法动态规划模型：1(){(,)((,))}kkkkkkkkkkaWxOptrxaWTxa1111()()NNNNWxrx.最优决策的动态规划逆序算法:步骤1:令1kN且1111()()NNNNWxrx对任意的1Nx;步骤2:让1kk,对每一个kx计算*ka,满足公式**11()(,)((,)){(,)((,))}kkkkkkkkkkkkkkkkkaWxrxaWTxaOptrxaWTxa令*,1argmax{(,)((,))}kkskxkkkkkkkkaAArsaWTxa步骤3:如果1k,停止,否则转步骤2；还可以用动态规划前序算法：想一想模型该是什么样子？算法该如何执行************************************************例题1.库存问题一．问题描述和模型建立1）问题描述设某工厂调查研究了解市场情况，估计在今后四个时期市场对产品的需求量，如表所示：时期1234需求量2324假定不论在任何时期，生产每批产品的固定成本费为3（千元），若不生产，则为0，每单位生产成本费为1（千元）.同时任何一个时期生产能力所允许的最大生产批量不超过6个单位.又设每时期的每个单位产品库存费为0.5（千元），同时规定在第一期期初及第四期期末均无产品库存.试问：该工厂如何安排各个时期的生产与库存，使所花的总成本费用最低？问题假设：本周期消耗不完的产品要过渡到下一周期，产生库存费用不允许缺货，否则不进行任何生成是费用最小的2）模型建立N=表示系统运行周期总数；k=生产过程的阶段变量；kd=第k阶段的需求量；C=每批产品的固定成本；kc=第k阶段的单位生产成本；kX=第k阶段的最大生产能力；kh=第k阶段的单位存储成本；kx=第k阶段末的库存量，作为状态变量；ka=第k阶段的生产量，作为决策变量状态转移方程：1kkkkxxad第k周期的费用函数：库存费用：()kkkkHxhx;生产费用：,0()0,0kkkkkkCcaaPaa或者()sgn()()kkkkkPaaCca于是第k周期的费用函数(,)()()kkkkkkkrxaHxPa；令12{,,,}Naaa表示一个策略，则当初始状态为1x和策略为，系统的总费用为1111(,)(,)()NtttNNtVxrxarx系统的最优化问题是：对于给定的初始状态为1x，找一个策略为*，使得12*11{,,,}(,)min{(,)}NaaaVxVx称*为初始状态为1x时系统的最优决策。动态规划方程为：11111()min{(,)((,))}()()kkkkkkkkkkaNNNNWxrxaWTxaWxrx其中()kkWx表示第k周期之后相对于状态kx的最优费用，且*1111()(,)WxVx。二、问题求解在上面参数假设下，150xx，费用函数为0.53,0(,)0.5,0kkkkkkkkxaarxaxa，1,2,3,4k55()0rx动态规划方程为：1{0,1,,6}55()min{(,)()}()0kkkkkkkkkkaWxrxaWxadWx具体的手算步骤就是DJStra算法过程。注明：如果有能力上限M，则系统状态为1min{,}kkkkxMxad可用计算机代替手工过程：具体求解用Lingo，Matlab，Mathematica等都可以。三、线性规划模型当没有启动费用时，实际上是一个平衡问题，不发生缺货，又尽量的费用最少。用习惯的形式表示为：4112223334440.5..23240,0kktkkkMinZxastaxxaxxaxxaaXx有启动费用时，得加入示性函数。同样可用软件求解。============================================例2：机器负荷分配问题一．问题描述和模型建立1）问题描述某种机器可以在高低两种负荷下生产，年产量与年初投入生产的机器数有关。在高负荷下生产时，年产量118su，式中1u为投入生产的机器数，年终的完好机器数为10.7u，称系数0.7为机器完好率。在低负荷下生产时，年产量225su，式中2u为投入生产的机器数，机器完好率为0.9，设开始时，完好的机器数为11000x台，要求制定一个五年计划，在每年开始时决定如何重新分配完好机器在两种不同负荷下工作的数量，使五年的总产量最高。2)模型建立N=表示系统运行周期总数k=生产过程的阶段变量hc=高负荷下生产时，单位机器的年产量lc=低负荷下生产时，单位机器的年产量hr=高负荷下生产时，机器的完好率lr=低负荷下生产时，机器的完好率kx=第k年初拥有的完好机器数（或第k-1年度末完好机器数）ku=第k年度中分配在高负荷下生产的机器数，则分配低负荷生产的机器数为kkxu；系统的状态为第k年初拥有的完好机器数kx，其状态方程为1()khklkkxrur