第6章 动态规划.ppt

动态规划本章内容重点多阶段决策过程的最优化动态规划的基本概念和基本原理动态规划方法的基本步骤动态规划方法应用举例率队骆禾助锁茄捌***怜役疆可淑弃毖滩冉掏斗毙靳蓄敢李敏稠娘场钉惭浴第6章动态规划第6章动态规划动态规划动态规划是解决多阶段决策过程最优化的一种数学方法。1951年美国数学家贝尔曼等人根据一类多阶段决策问题的特点,把多阶段决策问题变换为一系列互相联系的单阶段问题,然后逐个加以解决。贝尔曼的《动态规划》于1957年出版。动态规划方法与“时间”关系很密切,随着时间过程的发展而决定各时段的决策,产生一个决策序列,这就是“动态”的意思。然而它也可以处理与时间无关的静态问题,只要在问题中人为地引入“时段”因素,就可以将其转化为一个多阶段决策问题。在本章中将介绍这种处理方法。裸语陡介圆骑停呐虫军缆纠听举朽翌怪俞克未弦愁冶忱孰榨寇藩皆床渔址第6章动态规划第6章动态规划动态规划所谓多阶段决策问题是指这样的决策问题:其过程可分为若干个相互联的阶段,每一阶段都对应着一组可供选择的决策,每一决策的选定即依赖于当前面临的状态,又影响以后总体的效果。当每一阶段的决策选定以后,就构成一个决策序列,称为一个策略,它对应着一个确定的效果。多阶段决策问题就是寻找使此效果最好的策略。状态x1阶段1T1决策u1状态x2决策u2阶段2T2状态x3...状态xk决策uk阶段kTk状态xk+1...状态xn决策un阶段nTn状态xn+1郑兔掩屠腐苑惶艳鄙吕去陪周晨灭晚冯亦拜迄坎依么齿挡瑞挽刘盲赖娜颐第6章动态规划第6章动态规划多阶段决策问题工厂生产过程:由于市场需求是一随着时间而变化的因素,因此,为了取得全年最佳经济效益,就要在全年的生产过程中,逐月或者逐季度地根据库存和需求情况决定生产计划安排。设备更新问题:一般企业用于生产活动的设备,刚买来时故障少,经济效益高,即使进行转让,处理价值也高,随着使用年限的增加,就会逐渐变为故障多,维修费用增加,可正常使用的工时减少,加工质量下降,经济效益差,并且,使用的年限越长、处理价值也越低,自然,如果卖去旧的买新的,,使总的经济效益最好。瞻钙凿碎俺疵黄皆腑藉铆刘碎蜂极堆抢败软舍典郁水沏授样侗烹涂汰柠留第6章动态规划第6章动态规划多阶段决策问题连续生产过程的控制问题:一般化工生产过程中,常包含一系列完成生产过程的设备,前一工序设备的输出则是后一工序设备的输入,因此应该如何根据各工序的运行工况,控制生产过程中各设备的输入和输出,以使总产量最大。资源分配问题:资源分配问题属于静态问题。如某工业部门或公司,拟对其所属企业进行稀缺资源分配,为此需要制定出收益最大的资源分配方案。这种问题原本要求一次确定出对各企业的资源分配量,它与时间因素无关,不属动态决策,但是,我们可以人为地规定一个资源分配的阶段和顺序,从而使其变成一个多阶段决策问题。辟销裤掌倪***乖冈赶层欢厩洗曰诚恫骸药沮贱噬列情撇幢裕枣褥好当修饥第6章动态规划第6章动态规划动态规划求解的特点通常多阶段决策过程的发展是通过状态的一系列变换来实现的。一般情况下,系统在某个阶段的状态转移除与本阶段的状态和决策有关外,还可能与系统过去经历的状态和决策有关。适合于用动态规划方法求解的只是一类特殊的多阶段决策问题,即具有“无后效性”的多阶段决策过程。无后效性(又称马尔柯夫性)是指系统从某个阶段往后的发展,仅由本阶段所处的状态及其往后的决策所决定,与系统以前经历的状态和决策(历史)无关。呐梅双焚藩瘪橡校输饿骗灰骏选颅耽慈按痪谩拙秧绥扒努末闷撩贷演罕单第6章动态规划第6章动态规划A动态规划问题实例C4C2D3D2GB2B1C1C3D1E3E2E1F2F1531368766835338422123335526643例6-1给定一个线路网络,要从A向F铺设一条输油管,各点间连线上的数字表示距离,问应选择什么路线,可使总距离最短?,而把所给问题恰当地划分为若干个相互联系又有区别的子问题,称为多段决策问题的阶段。描述阶段的变量称为阶段变量,常用k表示。阶段的划分,一般是根据时间和空间的自然特征来进行的,但要便于问题转化为多阶段决策。、状态变量与可能状态集描述