运筹学动态规划

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

1、第四章动态规划（DynamicProgramming）重点：理解动态规划基本概念、最优化原理和基本方程；通过资源分配、生产与存储和设备更新等问题，学习应用动态规划解决多阶段决策问题；重点掌握动态规划模型结构、逆序算法原理、资源分配问题、生产与存储问题。难点为动态规划中状态变量、基本方程等的确定。动态规划是用来解决多阶段决策过程最优化的一种数量方法。其特点在于，它可以把一个多阶段决策问题变换为几个相互联系的单阶段最优化问题，从而一个一个地去解决。需指出：动态规划是求解某类问题的一种方法，是考察问题的一种途径，而不是一种算法。必须对具体问题进行具体分析，运用动态规划

2、的原理和方法，划分阶段，建立相应的模型，然后再去求解。AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G531368766835338422123335526643123456引例：图中所示为从A到G的路线网络，图中数字表示相应线路的长度，如何求出从A到G的最短路线？（穷举法48条路线）AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G53136876683533842212333552663123456375976813109121316184AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G5313687668353384221

3、233355266312345615131315111313681095318174AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G453136876683533822123335526643123456最短路的特性：如果已有从起点到终点的一条最短路，那么从最短路线上中间任何一点出发到终点的路线仍然是最短路。（证明用反证法）§1动态规划的研究对象和引例动态系统：包含随时间变化的因素和变量的系统。动态决策问题：系统所处的状态和时刻是进行决策的重要因素。找到不同时刻的最优决策以及整个过程的最优策略。12n状态决策状态决策状态状态决策全过程的最优阶段1、

4、生产决策问题企业在生产过程中，由于需求是随时间变化的，因此企业为了获得全年的最佳生产效益，就要在整个生产过程中逐月或逐季度地根据库存和需求决定生产计划。多阶段决策问题的典型例子2、机器负荷分配问题某种机器高负荷低负荷g=g(u1)产品的年产量投入生产的机器数量机器的年完好率为a，0

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

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

7、3136876683533822123335526643123456决策变量，描述决策的变量。uk(sk)，表示第k阶段当状态为sk时的决策变量。允许决策集合，常用Dk(sk)表示第k阶段从状态sk出发的允许决策集合。uk(sk)Dk(sk)D2(B1)?AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G453136876683533822123335526643123456系统当前的状态和决策4、多阶段决策过程在每个阶段进行决策控制过程的发展；其发展是通过一系列的状态转移来实现的；系统过去的历史状态和决策B1C1s2=T1(s1,u1)s3=T2

8、(s1,u1,s2,u2