7动态规划1讲解.ppt

即由 B2到F 的最短距离为15，相应的决策为 A B1 B2 C1 C2 C3 C4 D1 D2 D3 E1 E2 F 4 5 2 3 6 8 7 7 5 8 4 5 3 4 8 4 3 5 6 2 3 1 4 3 （1）k=1 时，只有一个状态点A, 则 即由 A到F 的最短距离为17，相应的决策为 A B1 B2 C1 C2 C3 C4 D1 D2 D3 E1 E2 F 4 5 2 3 6 8 7 7 5 8 4 5 3 4 8 4 3 5 6 2 3 1 4 3 所以最优路线为： 再按计算顺序反推可得最优决策序列： A B1 B2 C1 C2 C3 C4 D1 D2 D3 E1 E2 F 4 5 2 3 6 8 7 7 5 8 4 5 3 4 8 4 3 5 6 2 3 1 4 3 逆序递推方程（第k段与k+1段之间的关系）： A B1 B2 C1 C2 C3 C4 D1 D2 D3 E1 E2 F 4 5 2 3 6 8 7 7 5 8 4 5 3 4 8 4 3 5 6 2 3 1 4 3 二、动态规划的基本思想与原理 这种递推关系称为动态规划的基本方程，f6(s6)=0称为边界条件 A B1 B2 C1 C2 C3 C4 D1 D2 D3 E1 E2 F 4 5 2 3 6 8 7 7 5 8 4 5 3 4 8 4 3 5 6 2 3 1 4 3 二、动态规划的基本思想与原理 上述最短路线的计算过程也可用图直观表示出来,每个结点上方的括号内的数,表示该点到终点F的最短距离。连结各点到F点的粗线表示最短路径。这种在图上直接计算的方法叫标号法。 [4] [3] [7] [5] [5] [12] [10] [8] [9] [13] [15] [17] 逆序法 A B1 B2 C1 C2 C3 C4 D1 D2 D3 E1 E2 F 4 5 2 3 6 8 7 7 5 8 4 5 3 4 8 4 3 5 6 2 3 1 4 3 二、动态规划的基本思想与原理 [14] [14] [11] [12] [14] [6] [7] [10] [12] [4] [5] [17] 顺序法 d a e b h t g f c s 3 4 11 3 4 6 9 7 12 5 5 3 4 4 6 1 8 1 2 3 4 0 5 3 11 12 8 12 14 12 16 动态规划方法的基本思想： DP的关键在于正确地写出基本的递推关系式和恰当的边界条件。首先将多阶段决策过程划分阶段,恰当地选取状态变量、决策变量及定义最优指标函数。从而把问题化成一族同类型的子问题,然后逐个求解。 (2) DP方法既把当前一段和未来各段分开，又把当前效益和未来效益结合起来考虑。每阶段的决策均从全局最优来考虑。 (3) 求解时从边界条件开始,逆过程行进,逐段递推寻优.在每个子问题求解时,都要使用它前面已求出的子问题的最优结果,最后—个子问题的最优解,就是整个问题的最优解. 动态规划是解决多阶段决策过程最优化的一种方法。 该方法是由美国数学家贝尔曼（R. E. Bellman)等人在20世纪50年代初提出的。他们针对多阶段决策问题的特点，提出了解决这类问题的“最优化原理”，并成功地解决了生产管理、工程技术等方面的许多问题，从而建立了运筹学的一个新的分支，即动态规划。 Bellman在1957年出版了《Dynamic Programming》一书，是动态规划领域中的第一本著作。 给定一个线路网络，要从A向F铺设一条输油管道，各点间连线上的数字表示距离，问应选择什么路线，可使总距离最短？ 例1：最短路线问题 多阶段决策过程：是一类特殊的活动过程，这类活动可以按时间顺序分解成若干个相互联系的阶段，每个阶段都有若干个方案可供选择。 多阶段决策过程最优化的目标是要达到整个活动过程的总体效果最优。由于各段决策间有机地联系着，本段决策的执行将影响到下一段的决策，以至于影响总体效果．所以决策者在每段决策时不应仅考虑本阶段最优，还应考虑对最终目标的影响，从而做出对全局来讲是最优的决策。动态规划就是符合这种要求的一种决策方法。 因此动态规划方法与“时间”关系很密切，随着时间过程的发展而决定各时段的决策，产生一个决策序列。但它也可以处理与时间无关的静态问题，只要在问题中人为地引入“时段”因素，将问题看成多阶段的决策过程即可。 可用于最优路径问题、资源分配问题、生产计划和库存问题、投资问题、装载问题、排序问题及生产过程的最优控制等。 动态规划模型的分类： 以“时间”角度可分成：离散型和连续型。 从信息确定与否可分成：确定型和随机型。 从目标函数的个数可分成：单目标型和多目标型。 其中离散确定型是最基本的，本章主要针对这种类型的问题，介绍动态规划的基本思想、原理和方法，这些对其它