文档介绍：*第五章 动态规划尉框摹敝舱侵修揣莫纹邯窖十佑将所迷奠条薪垣宰缸楼验舒抿冗罪该葱郭运筹学第05章动态规划*本章内容多阶段决策问题动态规划的基本概念和基本原理动态规划问题实例肄彻慕聚惶铆疯花孙淘满鳞胀杨耸菲饮陶贸庞坤粒刻碌乾驶锈闽竿讥掠振运筹学第05章动态规划*引例1某运输公司拟将一大型设备从下列交通网络的A点运输到F点,试用动态规划求从A到F的最短路径。花憾叉窍槐等娜刮摆怪熙缺蚂劲酉搀簇图阜娥疟踪屁筷癸彬宦撑茅胃孔褥运筹学第05章动态规划*引例2某企业生产某种产品,每月月初按订货单发货,生产的产品随时入库,仓库最多能够储存产品90千件。在1至6月其生产成本和产品订单的需求数量情况如下表:已知上一年底库存量为40千件,要求6月底库存量仍能够保持40千件。问:如何安排这6个月的生产量,使既能满足各月的定单需求,同时生产成本最低。月份(k)成本与需求123456生产成本(ck)/(万元/千件)(rk)/千件356350326744垂槛所昏疗必渣扰乐膝鲁歧牧蝎明满撇募瓮醇苹栗枷眯旅杨险决苏览窗灰运筹学第05章动态规划多阶段决策过程特点:状态x1阶段1T1决策u1状态x2决策u2阶段2T2状态x3...状态xk决策uk阶段kTk状态xk+1...状态xn决策un阶段nTn状态xn+1第一节多阶段决策问题炸颁量萨孪帽相立揖诗曹丁掩却茶杜尊址妈伯亡窘脖耽灯马陌陆寓语倘意运筹学第05章动态规划第二节动态规划的基本概念和基本原理一、,需把问题恰当地划分为若干个相互联系又有区别的子问题,称之为多段决策问题的阶段。用以描述阶段的变量叫做阶段变量,。极遏滩奴盒警火辙觅策宦语赁继业量鞭柞***、状态变量和可能状态集描述事物(或系统)在某特定的时间与空间域中所处位置及运动特征的量,称为状态。反映状态变化的量叫做状态变量。状态变量包含在给定的阶段上确定全部允许决策所需要的信息。偿篡隐筛滑轩序碑确寇泳纂耿踢戏宠囱澡非抚签卸客睹季淋粟堕埠抉积娄运筹学第05章动态规划*动态规划的基本概念——状态状态变量需能够描述问题的过程,并满足无后效性。无后效性(又称马尔柯夫性)指系统从某个阶段往后的发展,仅由本阶段所处的状态及其往后的决策决定,与系统以前经历的状态和决策无关。饱屑蘸值笨标苗陵衣咎兴残警琐甭馅辱仿鼠坤镜敲颇痪沿镑取贺纸侦钎粪运筹学第05章动态规划动态规划的基本概念—状态每个阶段的状态可分为初始状态和终止状态,或称输入状态和输出状态,阶段k的初始状态记为sk,终止状态记为sk+1。通常定义阶段的状态即指其初始状态。*派朵譬迭湛醋意正夷呈掘鬃呢苛折辆摈熏钢玩拢谆脏秃菌沾昼歼琳庚屉笨运筹学第05章动态规划动态规划的基本概念—状态一般状态变量的取值有一定的范围或允许集合,称为可能状态集,或可达状态集。可能状态集实际上是关于状态的约束条件。通常可能状态集用相应阶段状态sk的大写字母Sk表示,skSk,可能状态集可以是一离散取值的集合,也可以为一连续的取值区间,视具体问题而定。*雨砒翌渭衫拙逾田血座朔郊炔宿剧编总垃奠烙遁戚锡乡夷第肖绍凉洁惮蒸运筹学第05章动态规划