文档介绍：*第五章 动态规划颜席绩谱宴缴马剩抛在扣掸艰铆骇脾笺散侥傍苫昌恼轩营滞刃椎厘颜巧艰运筹学第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章动态规划