运筹学动态规划
该方法是由美国数学家贝尔曼(R. Bellman)等人在20世纪50年代初提出的。
并成功地解决了生产管理、工程技术等方面的许多问题，从而建立了运筹学的一个新的分支，即动态规划。
Bellman在1957年出版了《Dynamic Programming》一书，是动态规划领域中的第一本著作。
动态规划与其他规划方法的不同之处在于:动态规划是求解某类问题(多阶段决策问题)的一种方法， 是考察问题的一种途径，而不是一种特定算法。
因此，它不像线性规划那样有一个标准的数学表达式和明确定义的一组(算法)规则，而必须对具体问题进行具体分析处理。
因此，学习动态规划时，除对基本概念和基本方法正确理解 外，还应在一定经验积累基础上，以丰富的想像力去建立模型， 用创造性的技巧去求解。
明确什么是多阶段的决策问题，特别要注意没有明显的时段背景的问题如何化归为多阶段的决策问题。
机器负荷分配问题(时间阶段问题)设有某种机器设备，用于完成两类工作A和B。
相应的问题称为多阶段决策问题。
这是一个多阶段决策过程。
该过程可以分为相互联系的若干阶段，每一阶段都需作出决策，从而形成全过程的决策。
从以上两个例子，可以知道所谓多阶段决策问题是指这样的决策问题:其过程可分为若干个相互联系的阶段，每一阶段都对应着一组可供选择的决策， 每一决策的选定既依赖于当前面临的状态，又影响以后总体的效 当每一阶段的决策选定以后，就构成一个决策序列，称为一个策略，它对应着一个确定的效果。
多阶段决策问题就是寻找使 此效果最好的策略。
10 多阶段决策过程的特点多阶段决策过程的特点 1.各阶段的决策相互关联 多阶段决策过程最优化的目的，是要达到整个活动过程的总体 效果最优，而不是某个阶段"局部"的效果最优。
因此，各个阶 决策的选取不是任意确定的。
前一个决策的选取决定了当前状态，当前状态进行决策后又影响到下一阶段的状态和决策，以至于影响总体效果。
所以决策者在每个阶段决策时，不应仅考虑本阶段最优，还应考虑对最终目标的影响，从而做出对全局而言是最优的决策。
动态规划就是符合这一要求的一种最优化方法。
11 2.各个阶段的决策一般与"时间"有关 动态规划方法与"时间"关系很密切，随着时间过程的发展而 但是，一些与时间无关的静态问题，只要在问题中人为引入"时间"因素，也可将其看成是多阶段的决策问题，用动态规 方法去处理。
12 学习目标: 准确、熟练地掌握动态规划的基本概念、特别是状态变量、决策变量、状态转移律、指标函数、基本方程 为了便于求解和表示决策及过程的发展顺序，而把所给问题恰当地划分为若干个相互联系又有区别的子问题，称之为多段决策 问题的阶段。
一个阶段，就是需要作出一个决策的子问题。
通常，阶段是按决策进行的时间或空间上先后顺序划分的。
描述各阶段状态的变量称为状态 变量，常用x 表示第k阶段的状态。
(2)状态(state) (2)状态(state) 例1中，状态就是某 阶段的出发位臵。
按状态变量的取值是连续还是离散，可将动态规划问题分为离散型和连续型。
15 动态规划中的状态应满足无后效性(马尔科夫性): 所谓无后效性指系统到达某个状态前的过程的决策将不影响 到该状态以后的决策。
[指系统从某个阶段往后的发展，仅由本 阶段所处的状态及其往后的决策所决定，与系统以前经历的状态 和决策(历史)无关。
过程的过去历史只能通过当前的状态去影响它未来的发展] 例1中，当某阶段的状态已选定某个点时，从这个点以后的路线只与该点有关，不受该点以前的路线的影响，所以满足状态的无后效性。
16 状态集合:状态变量的取值集合称为状态集合，状态集合实际上是关于状态的约束条件。
(3)决策(decision)(3)决策(decision) 当过程处于某一阶段的某状态时，可以做出不同的决定，从而 确定下一阶段的状态，这种决定称为决策。
从第2阶段的状态 B1出发，如我们决定选择C2(也即确定了下一阶段的状 C2状态转移律为: 一般来说，下一阶段状态变量xk+1 的取值是上阶段的某一状 n+1(5)策略(policy)和子策略(subpolicy) (5)策略(policy)和子策略(subpolicy) 策略:由依次进行的n个阶段决策构成的决策序列就构成一个 策略，用 本例中，如p14 表示其中一个策略，其总距离为2+5+6+3=16。
23 策略集合:在实际问题中，由于在各个阶段可供选择的决策有许多个，因此，它们的不同组合就构成了许多可供选择的决策序列(策略)，由它们组成的集合，称为策略集合，记作 从策略集合中，找出具有最优效果的策略称为最优策略。
阶段 指标函数 过程 指标函数 26 阶段指标函数:是指第 表示。
例1中，指标函数是 距离。
29 多阶段决策问题中，常见的目标函数形式之一是取各阶段效应 之和的形式，即: 有些问题，如系统可靠性问题，其目标函数是取各阶段效应的连乘积形式，如: 总之，具体问题的目标函数表达形式需要视具体问题而定。
动态规划的目标
,n 阶段变量 st. 上述数学模型说明了对于给定的多阶段决策过程，求取一个(或多个)最优策略或最优决策 序列{ 足左式给出的全部约束条件，又使左式所示的目标函数取得 极值，并且同时指出执行该最优策略时，过程状态演变序列 即是最优路线。
建立动态规划模型的步骤 选择状态变量既要能确切描述过程演变又要满足无后 效性，而且各阶段状态变量的取值能够确定。
通常选择所求解问题的关键变量作为决策变量，同时要给出决策变量的取值范围，即确定允许决策集合。
阶段指标函数是指第k 阶段的收益，最优指标函数是 阶段状态出发到第n阶段末所获得收益的最优值，最后写出动态规划基本方程。
36 以上五步是建立动态规划数学模型的一般步骤。
下面我们看一个具体的例子 P156 机器负荷分配问题(时间阶段问题)37 P156 机器负荷分配问题(时间阶段问题)设有某种机器设备，用于完成两类工作A和B。
因而有: 40学习目标: 多阶段决策过程的最优化一般有三种思路求解1.全枚举法或穷举法:它的基本思想是列举出所有可能发生的方案和结果，再对它们一一进行比较，求出最优方案。
用穷举法求最优路线的计算 工作量将会十分庞大，而且 其中包含着许多重复计算。
43 小结: 全枚举法虽可找出最优方案，但不是个好算法， 局部最优法则完全是个错误方法， 只有动态规划方法属较科学有效的算法 作为一个全过程的最优策略具有这样的性质:对于最优策略 过程中的任意状态而言，无论其过去的状态和决策如何，余下的诸决策必构成一个最优子策略。
(一个最优策略的子策略总是最优的) 46 4.函数基本方程 基于这个原理，提出了一种逆序递推法;该法的关键在于给出一种递推关系。
对于求最小的加法的基本方程为(如例1): 47用函数基本方程逆推求解是常用的方法: 首先要有效地建立动态规划模型， 然后再递推求解， 最后得出结论。
正确地建立一个动态规划模型，是解决问题的关键。
48 5.标号法(只适用于一类最优路线问题的特殊解法) 标号法是借助网络图通过分段标号来求出最优路线的一种 简便、直观的方法。
通常标号法采取"逆序求解"的方法来寻找 题的最优解，即从最后阶段开始，逐次向阶段数小的方向推算，最终求得全局最优解。
行进方向 动态规划寻优途径 标号法的一般步骤:(1)给最后一段标号，该段各状态(即各始点)到终点的距离用数字分别标在各点上方的方格内，并用粗箭线连接各点和终 (2)向前递推，给前一阶段的各个状态标号。
每个状态上方方格内的数字表示该状态到终点的最短距离。
将刚标号的点沿着 最短距离用粗箭线连接起来，表示出各刚标号的点到终点的最短路线。
(3)逐次向前递推，直到将第一阶段的状态(即起点)标 号，起点方格内的数字就是起点到终点的最短距离，从起点开始 连接终点的粗箭线就是最短路线。
因此，由A到终点E的最优解为: AB3C2D2E 由点A到终点E的最优值为11。
其中(2)式称为边界条件。
61 动态规划方法的优点 动态规划方法的优点 1.减少计算量 动态规划方法减少了计算量，而且随着阶段数的增加，计算量将大大减少。
这对于许多实际问题来说是很有用的，有利于帮助分析所得的结果。
62 动态规划方法的基本思想 动态规划方法的基本思想 将多阶段决策过程划分阶段，恰当地选择状态变量、决策变量，定义最优指标函数，从而把问题化成一簇同类型的子问题，然后逐个求解。
顺序解法(前向动态规划方法) 与逆序解法相反，顺序解法的寻优的方向与过程的行进方向 相同，计算时从第一段开始逐段向后递推，计算后一段要用到 前一段的求优结果，最后一段计算的结果就是全过程的最优结 65我们再次用例1来说明顺序解法。