系统工程---第六章 动态规划.pptVIP

第六章 动态规划 6.1 动态规划的基本原理和基本方程 6.2 机器负荷分配问题 6.3 资源分配问题 6.4 背包问题 6.5 连续型动态规划问题 6.1 动态规划的基本原理和基本方程 6.1.1 动态规划的最优性原理 6.1.2 动态规划的基本概念 6.1.3 动态规划的基本方程 6.1.4 建立动态规划的数学模型 6.1.5 动态规划的求解 6.1 动态规划的基本原理和基本方程 6.1 动态规划的基本原理和基本方程 6.1 动态规划的基本原理和基本方程 6.1 动态规划的基本原理和基本方程 6.1 动态规划的基本原理和基本方程 6.1 动态规划的基本原理和基本方程 6.1 动态规划的基本原理和基本方程 6.1 动态规划的基本原理和基本方程 6.1 动态规划的基本原理和基本方程 6.1 动态规划的基本原理和基本方程 6.1 动态规划的基本原理和基本方程 6.1 动态规划的基本原理和基本方程 6.1 动态规划的基本原理和基本方程 6.2 机器负荷分配问题 6.2.1 问题描述 6.2.2 静态规划模型 6.2.3 动态规划模型及其求解 6.2 机器负荷分配问题 6.2 机器负荷分配问题 6.2 机器负荷分配问题 6.3 资源分配问题 6.3.1 问题描述 6.3.2 静态规划模型 6.3.3 动态规划模型及其求解 6.3 资源分配问题 6.3 资源分配问题 6.3 资源分配问题 6.4 背包问题 6.4.1 问题描述 6.4.2 静态规划模型 6.4.3 动态规划模型及其求解 6.4 背包问题 6.4 背包问题 6.4 背包问题 6.5 连续型动态规划问题 6.5.1 问题描述 6.5.2 连续型动态规划模型及其求解 作业 6.5 连续型动态规划问题 6.5 连续型动态规划问题 6.3 资源分配问题 6.3 资源分配问题 6.3 资源分配问题 6.3 资源分配问题 6.3 资源分配问题 6.3 资源分配问题 6.4.1 问题描述 背包问题的原始意义：一个旅行者要从n种物品的每一种中挑选若干件装入他的背包中，已知第i种物品的重量及价值分别为ai和ci (i=1, 2,…, n)，又知这位旅行者所能承受的最大重量为a。问他应如何选择这n种物品的件数，才能使得价值为最大？ 6.4.2 静态规划模型 6.4.3 动态规划模型及其求解 例： 用动态规划方法求解下列的背包问题 6.4 背包问题 ，且为整数 ?求解过程 把该问题分为三个阶段来考虑： 6.4 背包问题 分析：这个问题属于背包问题，其中n=3，a=5，我们的问题是求 第三阶段： 第二阶段： 6.4 背包问题 第一阶段： 现在回过头来求 和 6.4 背包问题 最后，再计算 故该背包问题的最优解为 相应的目标函数最大值为13。 6.5.1 问题描述 动态规划按其状态变量的取值情况可以分为离散型和连续型。 如果状态变量取值为离散数据，则称为离散型动态规划； 如果状态变量取值为连续数据，则称为连续型动态规划。 ， ， (1) 连续型动态规划的基本方程(逆序递推公式) (2) 连续型动态规划的基本方程(正序递推公式) 6.5.2 连续型动态规划模型及其求解 * 山东理工大学管理学院 * 电子制作 齐向阳 6.1.1 动态规划的最优性原理 ◆ 动态规划是解决多阶段决策问题的一种数学方法。 ◆ 所谓多阶段决策问题，是指对系统运行过程中若干相继阶段的每一段都要作出决策，并使整个过程达到最优的一类问题。 50年代，美国数学家贝尔曼(Richard Bellman)等人，根据多阶段决策问题的性质，提出了解决这类问题的“最优性原理”，并研究了许多实际问题，从而建立了一种新的最优化方法——动态规划（Dynamic Programming)。 表述一：一个最优策略具有这样的性质，不论初始状态及初始决策如何，对于该决策所造成的某一状态而言，下余的所有决策必构成一个最优策略。 表述二：假设对任意的时刻t，不论过程在时刻t以前的历史状态如何，若按时刻t的状态而言，过程今后的行为是最优的。则整个过程的行为亦必是最优的。(无后效性) 表述三：如图，假设采取了最优策略，得到了某个系统运动的最优轨线，该最优轨线