第六章动态规划.ppt

动态规划运筹帷幄之中决胜千里之外宦块姨颁痉雪契撰闯捆纹避症快击桥蹿优另吁砾巢冀脐澳增脐萧借旭渤辽第六章动态规划第六章动态规划引言动态规划——DynamicProgramming动态规划是运筹学的一个分支,是解决多阶段决策过程最优化的一种数学方法。1951年,美国数学家贝尔曼等人提出了“最优性原理”,即根据一类多阶段决策问题的特点,把多阶段决策问题变换为一系列相互联系的单阶段决策问题,然后分阶段逐个加以解决。从而创建了解决最优化问题的一种新的方法——动态规划。饲驾较金遗该查否孔厚赡悬敢皋洛雁嚼炬戍儿显龋绩振没牲褪删抢岭会凯第六章动态规划第六章动态规划引言动态规划是解决某一类问题的一种方法,是分析问题的一种途径,而不是一种特殊算法(如线性规划是一种算法)。因此,在学习动态规划时,除了对基本概念和方法正确地理解外,应以丰富的想象力去建立模型,用创造性的技巧去求解。畔卞朗匪谰博坞十锹凡丑拄胎悼穆湿锻妙贝沥潮粕坑澎嘶辐某边暖懊俭咋第六章动态规划第六章动态规划引言本部分我们主要研究离散决策过程,介绍动态规划的基本概念、理论和方法,通过一些典型的应用问题来说明它的应用。生占碱磁援傣加谋美啥舵屈令惑法痛瓜先裙鸟讽奥抄浸署尹广增菌椅哦奉第六章动态规划第六章动态规划多阶段决策过程及实例多阶段决策过程(Multi-Stagedecisionprocess)整个决策过程可按时间或空间顺序分解成若干相互联系的阶段,每一阶段都需作出决策,全部过程的决策是一个决策序列。多阶段决策过程最优化的目标:达到整个活动过程的总体效果最优,而非各单个阶段最优的简单总和。栗暑通品殃擦谭泳媒噶歌钟求厕愧贱瘸詹卵鹤卉邓收番灿岸梆绒窄跪磅秧第六章动态规划第六章动态规划多阶段决策过程及实例状态s1阶段1决策u1状态s2决策u2阶段2状态s3...状态sk决策uk阶段k状态sk+1...状态xn决策un阶段n状态sn+1褐篇杭见井鞋做辽帛退蹭窑窜孙梆堰指笆拍酌朝毙橱隔妒臻蕉仔桃棕任中第六章动态规划第六章动态规划多阶段决策问题的典型例子多阶段决策问题的典型例子::企业在生产过程中,由于需求是随时间变化的,因此企业为了获得全年的最佳生产效益,就要在整个生产过程中逐月或逐季度地根据库存和需求决定生产计划。:某种机器可以在高低两种不同的负荷下进行生产。在高负荷下进行生产时,产品的年产量g和投入生产的机器数量u1的关系为g=g(u1):由于航天飞机的运动的环境是不断变化的,因此就要根据航天飞机飞行在不同环境中的情况,不断地决定航天飞机的飞行方向和速度(状态),使之能最省燃料和实现目的(如软着落问题)。、非线性规划等静态的规划问题也可以通过适当地引入阶段的概念,应用动态规划方法加以解决。毗挽成燎振坑祸滚襄侣蘑戒桓诛立玻轴纲滥诵肄川匀姚斡谭钧垦盛娘沦昨第六章动态规划第六章动态规划多阶段决策过程及实例请看如下典例——最短路线问题B1AC3F2F1E3E2E1D3D2D1C4C2C1B2G531368766835342138223335526643示辕铃赌虑郊乎柑泳父辐遂却技瞬慢粥矾锻钩碍容钵恩裸众进擎色诺礼撕第六章动态规划第六章动态规划多阶段决策过程及实例贪心算法每一步都走最短的线路:A—B2—C4—D3—E2—F2--G,长度为21。不是最优:最短的线路:A—B1—C2—D1—E2—F2--G,长度为18B1AC3F2F1E3E2E1D3D2D1C4C2C1B2G531368766835342138223335526643族屎匝孰傲果氢起颊昆谜九聘轰凭暂诊界信么竞阴疟豺何押柔采篮踢壶贯第六章动态规划第六章动态规划