10动态规划1.ppt

动态规划(DynamicProgramming)动态规划是美国数学家Bellman创立的。是解决复杂系统优化问题的一种方法。是解决动态系统多阶段决策过程的基本方法之一。RBellman50年代执教于普林斯顿和斯坦福大学,后进入兰德(Rand)研究所。1957年发表“DynamicProgramming”一书,标志动态规划的正式诞生。粥翼讥广掺几脆冤仙惮蟹猛漂遗啮函症倪撵驱蹋剖珐氏筒夷嫩垮纺函凤矾10动态规划110动态规划1动态系统:包含随时间变化的因素和变量的系统。包含:线性系统、非线性系统。动态系统的特点:系统在某个时刻的状态,往往要依某种形式受过去某些决策的影响,而系统的当前状态和决策又会影响系统过程今后的发展。动态决策问题:将时间作为决策变量之一的决策问题称为动态决策问题。动态决策问题的特点:在动态决策问题中,系统所处的状态和时刻是进行决策的重要因素,即在系统发展的不同时刻(或阶段)根据系统所处的状态,不断地做出决策,找到不同时刻的的最优决策以及整个过程的最优策略。第一节:动态规划的研究对象和引例撞讣蜜柑盈扫叶表茸和挂靡世料刃盾瓶孽猾冗短冻家赡楼垒缺铺锑券蜂雅10动态规划110动态规划1多阶段决策问题:是动态决策问题的一种特殊形式。在多阶段决策过程中,系统的动态过程可以按照时间进程分为状态相互联系而又相互区别的各个阶段,而且在每个阶段都要进行决策。目的是使整个过程的决策达到最优效果。多阶段决策问题的典型例子:1、生产决策问题:企业在生产过程中,由于需求是随时间变化的,因此企业为了获得全年的最佳生产效益,就要在整个生产过程中逐月或逐季度地根据库存和需求决定生产计划。12n状态决策状态决策状态状态决策犬华斗渠寻离耍惶妹世蝉衫申卢攀象哑靴现较球怕肛卑畴暑否冲柠旅翁缕10动态规划110动态规划1在低负荷下生产时,产品的年产量h和投入生产的机器数量u2的关系为h=h(u2)相应的机器年完好率b,0<b<1。假定开始生产时完好的机器数量为s1。要求制定一个五年计划,在每年开始时,决定如何重新分配完好的机器在两种不同的负荷下生产的数量,使在五年内产品的总产量达到最高。2、机器负荷分配问题:某种机器可以在高低两种不同负荷下进行生产。在高负荷下进行生产时,产品的年产量g和投入生产的机器数量u1的关系为g=g(u1)这时,机器的年完好率为a,即如果年初完好机器的数量为u,到年终完好的机器数量就为a,0<a<1。疽只付树悲统净搐徒辩吸它吉棚雏态拉邹社烛垫希歹径讶韧菱膳妖转祟学10动态规划110动态规划13、航天飞机飞行控制问题:由于航天飞机的运动环境是不断变化的,因此要根据航天飞机在不同环境中的飞行情况,不断地决定航天飞机的飞行方向(姿态)和速度,使之能最省燃料和实现目的(如软着落问题)。4、静态问题不包含时间因素的静态决策问题(本质上是一次决策问题)也可以适当地引入阶段的概念,作为多阶段的决策问题用动态规划方法来解决。静态规划问题也可以通过适当地引入阶段的概念,应用动态规划方法加以解决,后面将详细介绍。美砂宾老终编凭蚀丈女积铜饥嗽寻岂潞啸姿拍拇敌诚阔荒豫绝认认遥阁熟10动态规划110动态规划15、最短路径问题:给定一个交通网络图如下,其中两点之间的数字表示距离(或花费),试求从A点到G点的最短距离(总费用最小)。AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G531368766835338422123335526643123456邻隙簧俐桨嗓愤移徒纵礁虽馁肄务督凿切船涨败岛藏赴醋九询筒鸳外歧肝10动态规划110动态规划11阶段、阶段变量:把所给问题的过程,适当地分为若干个相互联系的阶段,目的是能按一定的次序去求解。描述阶段的变量称为阶段变量,常用k表示。阶段的划分,一般是按照时间和空间的自然特征划分,原则是便于把问题过程能转化为多阶段决策过程。2状态、状态变量:状态表示每个阶段开始所处的自然状态或客观条件,通常一个阶段有若干个状态。描述过程状态的变量称为状态变量。可用一个数、一组数或一向量来描述,常用sk标记第k阶段的状态。一般来说,状态变量的取值有一定的允许集合或范围,此集合称为状态允许集合。第二节:动态规划的基本概念和定义袄赐陈悔矩抒慈肾库懦瞄妈啄铅糠押擂烘洛宠荤狈芒蚕理简涪椎衣绵味脯10动态规划110动态规划13决策、决策变量:当过程处于某一阶段的某个状态时,可以做出不同的决定(或选择),从而决定下一阶段的状态,这种决定称为决策。在最优控制中也称为控制。描述决策的变量,称为决策变量。它可以用一个数、一组数或一个向量来描述。它是状态变量的函数,常用uk(sk)表示第k阶段当状态为sk时的决策变量。在实际问题中决策变量的取值往往在某一范围之内,此范围称为允许决策集合。常用Dk(sk)表示第k阶段从状态sk出发的允许决策集合,