动态规划运筹学的一个主要分支解决多阶段决策过程的最优化的一种方法多阶段决策过程:一类特殊的活动过程,这类活动可以按时间顺序分解成若干个相互联系的阶段,每个阶段都有若干个方案可供选择。多阶段决策过程的最优化的目标:达到整个活动过程的总体效果最优资源分配问题,生产计划与库存问题,,投资问题,装载问题排序问题生产过程的最优控制等主要用于解决:最优路径问题,动态规划离散确定型离散随机型连续确定型连续随机型例1设从甘肃要铺一条煤气管道到北京,途中须经过三个省:陕西、山西、河北,每省设一个中间站。各省建站可供选择的地点及各段距离如下图,现要求选择一条甘肃到北京的铺管线路,使总距离最短。○1○2○3○4○5○6○7○8○9○10北京河北山西陕西甘肃84589616**********最短路问题多阶段决策问题○1○3○5○8○10路长=21○1○4○6○9○10路长=16每一个阶段的决策合在一起构成一个铺设方案铺设方案1:铺设方案2:一个策略每个策略对应一个路长寻找最优策略寻找路长最短的铺设方案策略例2(多阶段资源分配问题)设有数量为y的某种资源,将它分别投入两种生产方式A和B,已知收益函数分别是g(x)和h(x),x为资源投入量。设这种资源用于生产后还可以回收一部分用于生产,A、B的回收率分别为a和b(0≤a≤1,0≤b≤1),问:对总数量为y的资源进行n个阶段的生产,应如何分配每个阶段投入A、B的资源数量,才能使总收益最大?n个阶段的决策问题例3(生产与存储问题)某工厂生产并销售某种产品。已知今后四个月市场需求预测及每月生产j个单位产品的费用如下:每月库存i个单位产品的费用E(i)=(千元),该厂最大库存容量为3个单位,每月最大生产能力为6个单位,计划开始和计划期末库存量都是零,试制定四个月的生产计划,在满足用户需求条件下,使总费用最小。每个月视为一个阶段,每个阶段都须决定生产几个、库存几个上一个阶段的决策直接影响下一个阶段的决策四个阶段的决策问题例4(投资决策问题)某公司现有资金Q万元,在今后5年内决定给A、B、C、D四个项目投资,这些项目的投资期限、回报率均不相同,问应如何确定这些项目每年的投资额,使到第5年末拥有资金的本利总额最大。5个阶段的决策问题例5(设备更新问题)某企业要决定一台设备未来8年的更新计划,已预测了第j年的购买设备的价格为Kj,Gj为设备经过j年后的残值,Cj为设备连续使用j-1年后在第j年的维修费(j=1,2,…,8),问应在哪一年更新设备可使总费用最小每一年视为一个阶段,每个阶段都须做决策:继续使用旧设备还是购买新设备?上一个阶段的决策直接影响下一个阶段的决策8个阶段的决策问题二、基本概念1、阶段2、状态3、决策4、策略5、状态转移方程6、指标函数1、阶段:阶段是指对整个过程的自然划分○1○2○3○4○5○6○7○8○9○10北京河北山西陕西甘肃84589616**********如最短路问题:问题分成4个阶段:通常用k表示阶段k=1,2,3,412,13,1458,7968,59,69,78,划分阶段的规则:根据时间顺序或空间特征来划分阶段目的:以便按次序来解优化问题线路:第一阶段,甘肃陕西第三阶段:山西河北线路:k=1:k=3:
09 10动态规划 来自淘豆网m.daumloan.com转载请标明出处.
