运筹学课件--6--动态规划

《运筹学课件--6--动态规划》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、运筹学工业工程研究所蒋美仙浙江工业大学工业工程蒋美仙jmx@zjut.edu.cn2006年7月第1页目录•第一章线性规划及单纯形法•第二章对偶理论与灵敏度分析•第三章运输问题•第四章目标规划•第五章整数规划•第六章动态规划•第七章图与网络分析浙江工业大学工业工程蒋美仙jmx@zjut.edu.cn2006年7月第2页第六章DynamicProgramming（DP）运决筹胜帷千幄动态规划里之之中外浙江工业大学工业工程蒋美仙jmx@zjut.edu.cn2006年7月第3页第六章动态规划•第1节动态规划的概述•第2节多阶段决策过程的最优化问题•第3节基本概念和基本原理•第4节动态规划的建模

2、与求解•第5节最优性原理和最优性定理•第6节生产与存贮问题•第7节资源配置问题•第8节不定期最短路径问题•第9节货郎担问题浙江工业大学工业工程蒋美仙jmx@zjut.edu.cn2006年7月第4页第1节动态规划的概述•动态规划的产生•动态规划的应用•动态规划与线性规划的区别•动态规划模型的分类浙江工业大学工业工程蒋美仙jmx@zjut.edu.cn2006年7月第5页一.动态规划的产生运筹学的分支，解决多阶段决策过程最优化的一种数学方法。产生于50年代。1951年美国数学家贝尔曼（R.Bellman）等人，根据一类多阶段决策问题的特点，把多阶段决策问题变换为一系列互相联系单阶段问题，然后

3、逐个加以解决。同时提出解决此类问题的“最优性原理”，研究了许多实际问题，从而创建了一种解决最优化问题的新方法－－动态规划。1957出版了其名著“动态规划”，是动态规划的第一本著作。浙江工业大学工业工程蒋美仙jmx@zjut.edu.cn2006年7月第6页二.动态规划的应用©1、在工程技术、企业管理、工农业生产及军事等部门中应用广泛，效果显著。©2、企业管理方面：最优路径问题、资源配置问题、产生调度问题、库存问题、装载问题、排序问题、设备更新问题生产过程最优控制问题。©3、离散性的问题：解析数学无法施展其术，动态规划非常有用。浙江工业大学工业工程蒋美仙jmx@zjut.edu.cn2006

4、年7月第7页三.动态规划与线性规划的区别©1、动态规划：是求解某类问题的一种方法，是考察问题的一类途径，而不是一种特殊算法线性规划：是一种算法©2、动态规划：无标准的数学表达式和明确定义的一组规则，必须具体问题具体分析处理线性规划：有标准的数学表达式和明确定义的一组规则浙江工业大学工业工程蒋美仙jmx@zjut.edu.cn2006年7月第8页学动态规划时，要对基本概念和方法正确理解，同时应以丰富的想象力去建立模型，用创造性的技巧去求解。浙江工业大学工业工程蒋美仙jmx@zjut.edu.cn2006年7月第9页四.动态规划模型的分类©1、根据多阶段决策过程的时间参量分类离散决策过程连续决

5、策过程©2、根据决策过程的演变是确定性的还是随机性的即演变性质确定性决策过程随机性决策过程浙江工业大学工业工程蒋美仙jmx@zjut.edu.cn2006年7月第10页©3、组合起来模型共有四类为最基本的类型离散确定性决策过程离散随机性决策过程连续确定性决策过程连续随机性决策过程本部分主要研究离散确定性，介绍动态规划的基本概念、理论和方法，并通过几个典型的问题来说明它的应用，这些都是整个动态规划的基本内容。浙江工业大学工业工程蒋美仙jmx@zjut.edu.cn2006年7月第11页第六章动态规划•第1节动态规划的概述•第2节多阶段决策过程的最优化问题•第3节基本概念和基本原理•第4节动态

6、规划的建模与求解•第5节最优性原理和最优性定理•第6节生产与存贮问题•第7节资源配置问题•第8节不定期最短路径问题•第9节货郎担问题浙江工业大学工业工程蒋美仙jmx@zjut.edu.cn2006年7月第12页第2节多阶段决策过程的最优化问题•多阶段决策问题•动态规划方法•动态规划方法的特点•静态规划的动态处理•举例说明多阶段决策问题的最优化问题浙江工业大学工业工程蒋美仙jmx@zjut.edu.cn2006年7月第13页一.多阶段决策问题指系统的动态过程可以按照时间或空间关系分为相互联系而又相互区别的部分称之为阶段，在每个阶段都要进行决策。当所有阶段的决策确定以后，就完全确定了该过程的活

7、动路线。浙江工业大学工业工程蒋美仙jmx@zjut.edu.cn2006年7月第14页即把一个问题看作是一个前后关联具有链状结构的多阶段过程，称之为多阶段决策过程，也称序贯决策过程，这种问题称为多阶段决策问题。决策决策⋅⋅⋅⋅⋅⋅决策状态状态状态状态状态12n第一阶段浙江工业大学工业工程蒋美仙jmx@zjut.edu.cn2006年7月第15页二.动态规划方法©1.动态:多阶段决策问题中，各个阶段采取的决策，一般来说是与