资源描述：
《《运筹》教学课件动态规划 8.1动态规划的基本概念和方法.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、美国数学家贝尔曼（Richard.Bellman)创始时间上个世纪50年代创始人第八章动态规划(DynamicProgramming)是运筹学的一个主要分支是解决多阶段决策过程的最优化的一种方法多阶段决策过程：资源分配问题，生产计划与库存问题，,投资问题，装载问题排序问题生产过程的最优控制等是一类特殊的活动过程，这类活动可以按时间顺序分解成若干个相互联系的阶段，每个阶段都有若干个方案可供选择。多阶段决策过程的最优化的目标：达到整个活动过程的总体效果最优主要用于解决：最优路径问题，动态规划离散确定型离散随机型连续确定型连续随机型8.1动态规划的基本概念8.2动态规划的基本原理8.3连续问题建模与
2、求解8.4离散问题建模与求解8.5应用举例内容8.1动态规划的基本概念例1设从甘肃要铺一条煤气管道到北京，途中须经过三个省：陕西、山西、河北，每省设一个中间站。各省建站可供选择的地点及各段距离如下图，现要求选择一条甘肃到北京的铺管线路，使总距离最短。○1○2○3○4○5○6○7○8○9○10北京河北山西陕西甘肃8458961610967738423问题分析:从甘肃到北京的管道,由四部分组成:a.甘肃→陕西段b.陕西→山西段c.山西→河北段d.河北→北京段每一段管道的铺设都有多种选择，将有多种方案○1○2○3○4○5○6○7○8○9○10北京河北山西陕西甘肃8458961610967738423
3、○1○3○5○8○10铺设方案1：○1○4○7○8○10铺设方案2：○1○3○5○8○10铺设方案1：在这个方案中,事实上作了四次决策:a.甘肃—陕西段：路线1—3，始点为1，终点为3b.陕西—山西段：路线3—5，始点为3，终点为5c.山西—河北段：路线5—8，始点为5，终点为8d.河北—北京段：路线8—10，始点为8，终点为103.每一段管道都有一个始点和一个终点,下一段的始点必须是上一段的终点。.○1○3○5○8○10铺设方案1：4.对于不同的方案，每一段始点和终点都不是确定的。○1○4○7○8○10铺设方案2：如在方案1中，陕西—山西段始点为3，终点为5，而在方案2中，陕西—山西段始点为
4、3，终点为5总结:一个问题有多种解决方案一个方案要经过多个阶段的决策才能形成下一阶段的决策必须以上一阶段的决策后果为基础每个阶段都有多种决策，不同决策产生不同的终态○1○2○3○4○5○6○7○8○9○10北京河北山西陕西甘肃8458961610967738423基本概念1、阶段2、状态：描述一个阶段的始态和终态3、决策：每一阶段作出的决策4、策略：一个解决方案5、状态转移方程：上一阶段向下一阶段的演变6、指标函数：全部和部分决策产生的后果或效用k=1s1s2s3…snsn+1k=2k=nu1(s1)u2(s2)un(sn)V1(u1,s1)V2(u2,s2)Vn(un,sn)决策效用状态转移
5、方程k=1s1s2s3…snsn+1k=2k=nu1(s1)u2(s2)un(sn)决策所有决策→策略后半部分决策→后部k阶段子策略前半部分决策→前部k阶段子策略○1○2○3○4○5○6○7○8○9○10北京河北山西陕西甘肃8458961610967738423○1○3○5○8○10铺设方案1：策略1：{1→3,3→5,5→8,8→10}后部2阶段子策略：{3→5,5→8,8→10}前部2阶段子策略：{1→3,3→5}k=1s1s2s3…snsn+1k=2k=nV1(u1,s1)V2(u2,s2)Vn(un,sn)效用全部效用→总指标函数(和形式）后半部分效用→后部k阶段子指标函数前半部分效用
6、→前部k阶段子指标函数k=1s1s2s3…snsn+1k=2k=nV1(u1,s1)V2(u2,s2)Vn(un,sn)效用全部效用→总指标函数(积形式）后半部分效用→后部k阶段子指标函数前半部分效用→前部k阶段子指标函数○1○2○3○4○5○6○7○8○9○10北京河北山西陕西甘肃8458961610967738423○1○3○5○8○10铺设方案1：每一个方案的总指标函数值是不同的○1○4○7○8○10铺设方案2：k=1s1s2s3…snsn+1k=2k=nV1(u1,s1)V2(u2,s2)Vn(un,sn)前部k阶段子指标函数形成的递推公式后部k阶段子指标函数形成的递推公式效用例2（多
7、阶段资源分配问题）设有数量为y的某种资源，将它分别投入两种生产方式A和B，已知收益函数分别是g(x)和h(x)，x为资源投入量。设这种资源用于生产后还可以回收一部分用于生产，A、B的回收率分别为a和b（0≤a≤1，0≤b≤1），问：对总数量为y的资源进行n个阶段的生产，应如何分配每个阶段投入A、B的资源数量，才能使总收益最大？n个阶段的决策问题例3（投资决策问题）某公司现有资金Q万元，在今后5年内
