第三节动态规划

§4.3动态规划模型一、多阶段决策过程及实例二、动态规划的基本概念三、动态规划模型举例一、多阶段决策过程及实例动态规划是解决多阶段决策过程最优化问题的一种数学方法。1951年美国数学家Bellman(贝尔曼）等人，根据一类多阶段决策问题的特性，提出了解决这类问题的“最优化原理”，并研究了许多实际问题，从而创建了最优化问题的一种新方法——动态规划。多阶段决策问题是指这样一类活动的过程，由于他的特殊性，可将其分为若干个互相联系的阶段，在它的每一个阶段都需作出决策，并且一个阶段的决策决定后，常常影响下一个阶段的决策，从而使整个过程达到最好的活动效果。这样一个前后关联具有链状结构的多阶段过程就称为多阶段决策过程，也称为序贯决策过程。例1（最短路线问题）如图，给出一个线路网络，A为始点，G为终点，两点之间的连线可以表示道路、管道等，连线上的数字表示两点间的距离（或费用），试选择一条由A到G的线路，使总距离（或费用）为最小。GE3F2F1E1E2D3D2D1C4B2C3C2C1B1A157333836668353834221233552646第一阶段第二第三阶段第六第四第五例2（生产存贮问题）某工厂根据市场调研情况，需制定今后四个月的生产计划，据估计，在这四个月内，市场对该产品的需求量如下表所示：假定市场每批产品的固定成本费用为3千元，每单位产品成本费用为1千元，库存费用每月为0.5千元.并且规定1月月初和4月月底均无产品库存.试问该厂如何安排各个月的生产与库存，使总费用最小.月份1234需求量（Dk)2324二、动态规划的基本概念和基本方程动态规划的基本概念1、阶段(stage)k：把所给问题的过程，恰当地分成若干个相互联系的阶段（步骤）.描述阶段的变量称为阶段变量，常用k表示.k=1、2、3、……2、状态(state)sk：状态表示每个阶段开始所处的状况，即是每一阶段的出发位置（阶段的起点）.通常一个阶段有多个状态.描述状态的变量称为状态变量.第k阶段的状态变量记为sk,该阶段所有可能的状态的全体称为状态集合，记为Sk.如例1：S1={A}，S2={B1,B2}，S3={C1,C2,C3，C4}，……3、决策(decision)uk(sk)：从一个阶段某状态演变到下一个阶段某状态的选择或决定称为决策。描述决策的变量称为决策变量，用uk(sk)表示第k阶段当状态为sk时的决策变量，它是状态sk的函数。决策变量的取值范围称为决策集合，允许决策集用Dk(sk)表示。如例1：D1(s1)={u1(A)}={B1,B2}，s1=AD2(s2)={u2(B1)}={C1,C2,C3},s2=B1D3(s3)={u3(B2)}={C2,C3,C4}，……4、状态转移方程：状态转移方程描述由一个状态到另一个状态的演变过程.因为某一阶段的状态变量及决策变量取定后，下一阶段的状态就随之而定.用sk+1=T(sk,uk)表示k阶段与k+1阶段的变化规律.5、策略由过程的第k阶段开始到终点为止的过程，称为问题的后部子过程，由每阶段的决策组成的决策函数序列{uk(sk),uk+1(sk+1),…,un(sn)}称为子过程策略，简称子策略，记为Pk(sk),即：Pk(sk)={uk(sk),uk+1(sk+1),…,un(sn)}.当k=1时，则此决策函数序列称为全过程的一个策略，简称为策略，记为P(s1).或者说全过程中各个阶段的决策uk组成的有序总体就称为策略.允许策略集合——可供选择的策略范围，用P表示.最优策略——从允许策略集合中找出的使问题达到最有效果的策略称为最优策略.6、指标函数和最优指标函数值阶段效益（指标）——是衡量该阶段决策效果的数量指标，它是阶段状态和阶段决策的函数.用dk(sk,uk)表示在第k阶段由状态sk和执行决策uk(sk)所得的效益.指标函数（目标函数）——是用来衡量所实现过程优劣的一种数量指标，它表示系统执行某一策略所产生的效益，它是定义在过程（可以是全过程，也可以是后部子过程）上的数量函数.用fk,n表示：当初始状态确定后，过程的策略就确定了，因而指标函数也就确定了，故指标函数是初始状态和策略的函数，即：最优指标函数值——指标函数的最优值称为最优指标函数值，记为fk(sk).nksususffnkkkknknk,...,2,1),,...,,,,(111,,)](,[,,kkknknksPsff动态规划的基本思想和基本方程最短路线的特性——如果从起点到终点的最短路线在第k阶段通过点Pk，则最短路线上由点Pk出发到达终点的这一段子路线，对于从Pk到达终点的所有可能选择的不同路线来说，必定是最短的。动态规划的基本思想——由后向前逐步推移计算.即从最后一段开始，由后向前逐步递推，求出各点到终点的最短路线.下面我们利用动态规划基本思想来解决如下问题：例3、求由A到D的最短路线.4)(,3)(,1)(3332313CfCfCfk时，有：解：当AB1B2C1C2C3D243333211143221212CCCBBBB1，，都有三个选择：出发，或两个，不论从，时，出发点有当k11233312232121311212)(4413313)(),()(),()(),(min)(CBuCfCBdCfCBdCfCBdBf，12233322232221312222)(3413312)(),()(),()(),(min)(CBuCfCBdCfCBdCfCBdBf，11222112111)(,63442)(),()(),(min)(BAufdfdfBBABBAAA时，出发点只有一个点当1k6.DCBA相应的最短距离为：由此得图的最短路线为11再按计算顺序反推之，可得最优决策函数序列{uk},即：u1(A)=B1,u2(B1)=C1,u3(C1)=D.从最短路线问题的例子的计算过程，可以看到，用动态规划方法解决问题的关键是正确写出k阶段与k+1阶段之间的递推关系式（基本方程）：由此得动态规划的一般模型为：1,2,3))}(())(,({min)(1)(ksufsusdsfkkkkkkksDukkkk，.0)(4Df和边界条件1,,1,,0)())},(())(,({)(111)(nnksfsufsusdoptsfnnkkkkkkksDukkkkkmaxmin)(或，出发到终点的最优效益为从状态其中optssfkkk按照上述方法我们来求例1图中的最短路线解：GE3F2F1E1E2D3D2D1C4B2C3C2C1B1A157333836668353834221233552646三、动态规划模型举例动态规划建模的一般步骤（1）划分阶段划分阶段是运用动态规划求解多阶段决策问题的第一步，在确定多阶段特性后，按时间或空间先后顺序，将过程划分为若干相互联系的阶段。对于静态问题要人为地赋予“时间”概念，以便划分阶段。（2）正确选择状态变量选择变量既要能确切描述过程演变又要满足无后效性，而且各阶段状态变量的取值能够确定。一般地，状态变量的选择是从过程演变的特点中寻找。（3）确定决策变量及允许决策集合通常选择所求解问题的关键变量作为决策变量，同时要给出决策变量的取值范围，即确定允许决策集合。（4）确定状态转移方程根据k阶段状态变量和决策变量，写出k+1阶段状态变量，状态转移方程应当具有递推关系。（5）确定阶段效益（指标）函数和最优指标函数，建立动态规划基本方程阶段（效益）指标函数是指第k阶段的收益，最优指标函数是指从第k阶段状态出发到第n阶段末所获得收益的最优值，最后写出动态规划基本方程。以上五步是建立动态规划数学模型的一般步骤。由于动态规划模型与线性规划模型不同，动态规划模型没有统一的模式，建模时必须根据具体问题具体分析，只有通过不断实践总结，才能较好掌握建模方法与技巧。例4（生产库存管理系统）设某公司全年计划生产某种产品A，其四个季度的订货量分别为600件，700件，500件，1200件.已知生产产品A的生产费用与产品数量的平方成正比，其比例系数为0.005，厂内有仓库可以存放未销售出的产品，其存贮费为每件每季度1元，问如何安排各季度的产量，可以满足各季度的订货量需求，又使全年的总费用最小？模型建立：1、划分阶段：每一季度为一个阶段；2、设出状态变量：令sk（k=1,2,3,4)表示第k个季度初的产品数量（库存数量）,s1=0,s5表示年终剩余的产品数量；3、设出决策变量：令uk(k=1,2,3,4)表示第k季度的产量,uk≥Ak-sk，Ak表示第k季度的订货量；4、状态转移方程：sk+1=sk+uk-Ak,5、阶段效益：表示该季度的生产费用与库存费用之和——dk(sk,uk)=1*sk+0.005uk2;6、基本方程：模型求解：1,2,3,4,0)()}(005.0{min)(),(min)(5511211ksfsfussfusdsfkkkksAukkkkkukkkkkkskAk例5（生产管理问题）设某生产企业有数量为A的某种机器，可在高低两种负荷下生产某种产品.假设在高负荷下生产时，产品的年产量s1和投入生产的机器数量y的关系为s1=g(y)，到年终的机器完好率为a(0a1);在低负荷下生产时，产品的产量s2和投入生产的机器数z的关系为s2=h(z),其机器的完好率为b(0b1).现在要制定一个n年的生产计划，在每年的年初，问如何重新分配完好的机器在两种负荷下工作的数量，可使得n年内的总产量最高？如果要求在第n年必须保证仍有一定数量B的完好机器，又如何制定生产计划？模型建立（1）设出状态变量：令sk表示第k年年初具有完好的机器数量，s1=A,sn+1表示第n年末的完好机器数量；（2）设出决策变量：令uk表示第k年初分配给高负荷生产的机器数量，则分配给低负荷的机器数量为sk-uk；（3）状态转移方程：Sk+1=auk+b(sk-uk)=(a-b)uk+bsk；（4）阶段效益：表示第k年底产品的产量，即：dk(sk,uk)=g(uk)+h(sk-uk)(5)基本方程：fk(sk)表示从状态sk出发，采用后部最优子策略，到第n年底年终的最高产量，则的动态规划模型为：1,,1,,0)()})(()()({max)}(),({max)(1110110nnksfbsubafushugsfusdsfnnkkkkkksukkkkksukkkkkk.)(),(,,,,1规划模型态都给的后，即可解此动在zhygbanAs模型求解:设s1=1000台，n=5年，a=0.7,b=0.9,g(y)=8y,h(z)=5z.则状态转移方程为:sk+1=0.7uk+0.9(sk-uk)=0.9sk-0.2uk阶段效益为dk=8uk+5(sk-uk)=3uk+5sk；动态规划模型为：求解如下：1,2,3,4,5,0)()}9.02.0(53{max)(6610ksfsufsusfkkkkksukkkk如果要求终端s6=500,这时如何安排生产，才能在满足这一要求的条件下产量最高？解：由状态转移方程得：s6=-0.2u5+0.9s5=500∴u5=4.5s5-2500,即u5*=4.5s5-250075005.185)25005.4(*3)53max{)(5555555ssssusf0,750065.21}750065.217.0{max}7500)9.02.0(5.1853{max)(*4444044440444444