运筹学动态规划
第7章 动态规划
动态规划是Bellman 在1957年提出的解多阶决策问题的方法，在那个时期，线性规划很流行，它是研究静态问题的，而Bellman 提出的解多阶决策问题的方法适用于动态问题，相对于线性规划研究静态问题，取名动态规划。动态规划方法应用范围非常广泛，方法也比较简单。动态规划是将一个多阶决策问题分解为一系列的互相嵌套的一步决策问题，序贯求解使问题得到简化。 动态规划问题按照问题的性质可以分为确定性的和随机性的，按决策变量的和状态变量的取值可以分为离散型的和连续型的。此外还有依据时间变量连续取值还是离散取值又分为连续时间动态规划问题和离散时间动态规划问题。本章重点讨论离散时间确定性动态规划问题，包括状态变量和决策变量连续取值和离散取值两种情况。
7.1解多阶决策问题的动态规划法
1.多阶决策问题的例
(1)最优路径问题—多阶决策问题的例
为了直观，先从最优路径问题谈起，它可以看作一个多阶决策过程。通过最优路径问题的解可以看到用动态规划法解多阶决策问题的基本思想。
考虑图7-1所示的最优路径问题。一汽车由S 点出发到终点F ，P
和Q 是一些可以通过的点。图中两点间标出的数字是汽车走这一段路所需的时间(单位为小时)。最优路径问题是确定一个路径，使汽车沿这条路径由S 点出发达到F 点所用时间最短。最优路径问题可以看作一个多阶决策问题，由S 到城市甲是第1个阶段，第1个结点P 1或第2个结点Q 1做为第1阶段可以通过的两个站点，由城市甲到城市乙是第2阶段，这个阶段是从P 1或Q 1到P 2或
Q 2，由城市乙到城市丙是第3阶段，这个阶段是从P 2或Q 2到P 3或Q 3，由城市丙的P 3或Q 3到F 做为第四阶段。
（2）最优路径问题的解 对最优路径问题，存在一个非常明显的原理，即最优路径的一部分还是最优路径。换句话说，如果SQ P Q F 123是所求的最优路径，那么，汽车从这一路径上的任何一点，例如P 2，出发到F 的最优路径必为P Q F 23。这一原理称为最优性原理。根据这一原理可以由后向前递推求出最优路径。
运筹学教案动态规划
一、教学目标
1. 了解动态规划的基本概念及其在运筹学中的应用。
2. 掌握动态规划的基本原理和方法，能够解决实际问题。
3. 学会使用动态规划解决最优化问题，提高解决问题的效率。
二、教学内容
1. 动态规划的基本概念
动态规划的定义
动态规划与分治法的区别
2. 动态规划的基本原理
最优解的性质
状态转移方程
边界条件
3. 动态规划的方法
递推法
迭代法
表格法
4. 动态规划的应用
背包问题
最长公共子序列
最短路径问题
三、教学方法 1. 讲授法：讲解动态规划的基本概念、原理和方法。
2. 案例分析法：分析实际问题，引导学生运用动态规划解决问题。
3. 编程实践法：让学生动手编写代码，加深对动态规划方法的理解。
四、教学准备
1. 教材：《运筹学导论》或相关教材。
2. 课件：动态规划的基本概念、原理、方法及应用案例。
3. 编程环境：为学生提供编程实践的平台，如Python、C++等。
五、教学过程
1. 引入：通过一个实际问题，引出动态规划的概念。
2. 讲解：讲解动态规划的基本原理和方法。
3. 案例分析：分析实际问题，展示动态规划的应用。
4. 编程实践：让学生动手解决实际问题，巩固动态规划方法。
5. 总结：对本节课的内容进行总结，强调动态规划的关键要点。
6. 作业布置：布置相关练习题，巩固所学知识。
六、教学评估
1. 课堂讲解：评估学生对动态规划基本概念、原理和方法的理解程度。
2. 案例分析：评估学生运用动态规划解决实际问题的能力。
3. 编程实践：评估学生动手实现动态规划算法的能力。
4. 课后作业：评估学生对课堂所学知识的掌握情况。
七、教学拓展
1. 研究动态规划与其他优化方法的联系与区别。
2. 探讨动态规划在运筹学其他领域的应用，如库存管理、生产计划等。 3. 了解动态规划在、数据挖掘等领域的应用。
八、教学反思
1. 反思本节课的教学内容、方法和过程，确保符合教学目标。
运筹学教案动态规划
教案章节一：引言
1.1 课程目标：
让学生了解动态规划的基本概念和应用领域。
让学生掌握动态规划的基本思想和解决问题的步骤。
1.2 教学内容：
动态规划的定义和特点
动态规划的应用领域
动态规划的基本思想和步骤
1.3 教学方法：
讲授法：介绍动态规划的基本概念和特点。
案例分析法：分析动态规划在实际问题中的应用。
教案章节二：动态规划的基本思想
2.1 课程目标：
让学生理解动态规划的基本思想。
让学生学会将问题转化为动态规划问题。
2.2 教学内容：
动态规划的基本思想
状态和决策的概念
状态转移方程和边界条件
2.3 教学方法：
讲授法：介绍动态规划的基本思想。 练习法：通过练习题让学生学会将问题转化为动态规划问题。
教案章节三：动态规划的求解方法
3.1 课程目标：
让学生掌握动态规划的求解方法。
让学生学会使用动态规划算法解决问题。
3.2 教学内容：
动态规划的求解方法：自顶向下和自底向上的方法
动态规划算法的实现：表格化和递归化的方法
3.3 教学方法：
讲授法：介绍动态规划的求解方法。
练习法：通过练习题让学生学会使用动态规划算法解决问题。
教案章节四：动态规划的应用实例
4.1 课程目标：
让学生了解动态规划在实际问题中的应用。
让学生学会使用动态规划解决实际问题。
4.2 教学内容：
动态规划在优化问题中的应用：如最短路径问题、背包问题等
动态规划在控制问题中的应用：如控制库存、制定计划等
4.3 教学方法：
讲授法：介绍动态规划在实际问题中的应用。
案例分析法：分析实际问题，让学生学会使用动态规划解决实际问题。
教案章节五：总结与展望 5.1 课程目标：
让学生总结动态规划的基本概念、思想和应用。
让学生展望动态规划在未来的发展。
5.2 教学内容：
动态规划的基本概念、思想和应用的总结。
动态规划在未来的发展趋势和挑战。
5.3 教学方法：
讲授法：总结动态规划的基本概念、思想和应用。
运筹学清华大学第四版答案
【篇一：运筹学作业2(清华版第二章部分习题)答案】
s=txt>2．1 题 （p. 77） 写出下列线性规划问题的对偶问题：
?
?
??（1）?
?
?
??maxz?2x1?2x2?4x3s.t.x1?3x2?4x3?22x1?x2?3x3?3x1?4x2?3x3?5x1?0，x2?0,x3无约束；
解：根据原—对偶关系表，可得原问题的对偶规划问题为：
?maxw?2y1?3y2?5y3?s.t.y1?2y2?y3?2??3y1?y2?4y3?2 ?
?4y1?3y2?3y3?4?
y1?0,y2?0,y3?0??
mn?minz???cijxij?
i?1j?1?
n?
??cijxij?ai,i?1,?,m（2）? j?1
?n
??cijxij?bj,j?1,?,n
?j?1
???xij?0,i?1,?,m;j?1,?,n
解：根据原—对偶关系表，可得原问题的对偶规划问题为：
mn?
?maxw??aiui??bjvj
i?1j?1??ui?vj?cij ?
?i?1,?,m;j?1,?,n?
??ui无约束，vj无约束
2．2判断下列说法是否正确，为什么？
（1） 如果线性规划的原问题存在可行解，则其对偶问题也一定存在可行解； 答：错。
因为：若线性规划的原问题存在可行解，且其对偶问题有可行解，则原问题和可行问题都将有最优解。但，现实中肯定有一些问题是无最优解的，故本题说法不对。
maxz?3x1?x2
例如原问题 s.t.?x1?x2?1?x2?3?
?x?0,x?02?1有可行解，但其对偶问题
minw?y1?3y2
s.t.?3?y1?y2?1?y1?
?y?0,y?02?1无可行解。
（2） 如果线性规划的对偶问题无可行解，则原问题也一定无可行解；
答：错，如（1）中的例子。
