运筹学动态规划ppt课件.ppt

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

1、运筹学运筹帷幄之中决胜千里之外动态规划DynamicProgramming第五章2第五章动态规划重点：理解动态规划基本概念、最优化原理和基本方程；通过资源分配、生产与存储和设备更新等问题，学习应用动态规划解决多阶段决策问题；重点掌握动态规划模型结构、逆序算法原理、资源分配问题、生产与存储问题。难点为动态规划中状态变量、基本方程等的确定。3概述1951年Bellman提出，1957《动态规划》动态规划是解决多阶段决策问题的一种数学方法。动态规划思想：把多阶段决策问题变换为一系列互相联系的单阶段问题，然后逐个加以解决。即：把一个n维决策问题变换

2、为几个一维最优化问题，从而一个一个地去解决。需指出：动态规划是求解某类问题的一种方法，是考察问题的一种途径，而不是一种算法。必须对具体问题进行具体分析，运用动态规划的原理和方法，建立相应的模型，然后再用动态规划求解方法去求解。应用：最短路线、资源分配、生产调度问题4主要内容一、多阶段决策问题二、动态规划的基本概念三、动态规划的基本思想四、动态规划递推求解方法五、动态规划的最优性原理六、动态规划的优缺点七、动态规划问题应用举例5AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G5313687668353384221233355266

3、43123456引例：图中所示为从A到G的路线网络，图中数字表示相应线路的长度，如何求出从A到G的最短路线？（穷举法48条路线）6AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G5313687668353384221233355266312345637597681310912131618447AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G53136876683533842212333552663123456151313151113136810953181648AB1B2C1C2C3C4D1D2D3E1E2E3F1F

4、2G453136876683533822123335526643123456最短路的特性：如果已有从起点到终点的一条最短路，那么从最短路线上中间任何一点出发到终点的路线仍然是最短路。（证明用反证法）9§1动态规划的研究对象和引例动态系统：包含随时间变化的因素和变量的系统。动态决策问题：系统所处的状态和时刻是进行决策的重要因素。找到不同时刻的最优决策以及整个过程的最优策略。12n状态决策状态决策状态状态决策全过程的最优阶段101、生产决策问题企业在生产过程中，由于需求是随时间变化的，因此企业为了获得全年的最佳生产效益，就要在整个生产过程中逐

5、月或逐季度地根据库存和需求决定生产计划。多阶段决策问题的典型例子112、机器负荷分配问题某种机器高负荷低负荷g=g(u1)产品的年产量投入生产的机器数量机器的年完好率为a，0

6、）也可以适当地引入阶段的概念，作为多阶段的决策问题用动态规划方法来解决。4、最短路问题（引例）：给定一个交通网络图如前，其中两点之间的数字表示距离（或花费），试求从A点到G点的最短距离（总费用最小）。13AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G531368766835338422123335526643123456§2动态规划的基本概念和定义1、阶段、阶段变量把所给问题的过程，适当（按时间和空间）地分为若干个相互联系的阶段；描述阶段的变量称为阶段变量，常用k表示。142、状态、状态变量每个阶段开始所处的自然状态或客观条件

7、，描述过程的状况，通常一个阶段有若干个状态。AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G453136876683533822123335526643123456描述过程状态的变量称为状态变量，它可用一个数、一组数或一向量来描述，常用sk表示第k阶段的状态。s2=?状态允许集合，状态变量的取值允许集合或范围。15在最优控制中也称为控制。3、决策、决策变量某一阶段、某个状态，可以做出不同的决定（选择），决定下一阶段的状态，这种决定称为决策。453136876683533822123335526643AB1B2C1C2C3C4D1

8、D2D3E1E2E3F1F2G123456决策变量，描述决策的变量。uk(sk)，表示第k阶段当状态为sk时的决策变量。允许决策集合，常用Dk(sk)表示第k阶段从状态sk出发的