第5章 动态规划 5.1, 5.2 多阶段决策和最优化原理 2019/5/1

动态规划研究的问题 动态规划起源于1950年代，创始人为R. Bellman。 动态规划所研究的对象是多阶段决策问题。 这样的问题可以转化为一系列相互联系的单阶段优化问题。 在每个阶段都需要作出决策。 每个阶段的决策确定以后，就得到一个决策序列，称为策略。多阶段决策问题就是求一个策略，使各阶段的总体目标达到最优（如最小化费用，或最大化收益）。 相对于线性规划一次性地对一个问题求出整体最优解，多阶段决策问题的这种解决办法称为动态规划（Dynamic Programming）。而原来的线性规划方法被称为静态规划。 2019/5/1 山东大学 软件学院

内容 多阶段决策问题和最优化原理 定期多阶段决策问题 不定期多阶段决策问题 2019/5/1 山东大学 软件学院

问题举例一：最短路问题 如图，求从a到g的最短路。 由于这是一个多阶段图（分层图），该图上的最短路问题是一个多阶段决策（优化）问题。 2019/5/1 山东大学 软件学院

如何求解？（后向优化） 2019/5/1 山东大学 软件学院

逆向求解递推方程（标号法） 13 7 7 13 4 10 6 5 18 9 16 3 8 4 12 2019/5/1 山东大学 软件学院

动态规划表格 2019/5/1 山东大学 软件学院

递归如何？循环如何？ 递归程序 f(i, u, g) 1 if i = 1 then return d(u, g)， 2 else return min v  N(u) {d(u, v) + f(i  1, v, g)}。 循环程序 f(u, g) 1 p  (a, b1, c1, d1, e1, d1, f1, g)。 2 for b  b1 到 b2 do 3 for c  c1 到 c4 do 4 for d  d1 到 d3 do 5 for e  e1 到 e3 do 2019/5/1 山东大学 软件学院

循环？ 6 for f  f1 到 f2 do 7 q  (a, b, c, d, e, f, g)。 8 if q的长度 < p的长度 then p  q。 9 endfor /* f */ 10 endfor /* e */ 11 endfor /* d */ 12 endfor /* c */ 13 endfor /* b */ 14 return p。 2019/5/1 山东大学 软件学院

问题举例二：资源分配问题 设有数量为x的某种资源，将它投入两种生产方式A和B中（或称为投给部门A和部门B）。 若投给部门A的数量为z，则可获收益g(z)，回收az，其中a（0 a  1）为部门A的回收率。类似地，若投给部门B的数量为z，则可获收益h(z)，回收bz，其中b（0 b  1）为部门B的回收率。 连续投放n个阶段，问每个阶段如何分配资源才能使总收入最大？ 2019/5/1 山东大学 软件学院

再描述一遍 设第k个阶段的资源总数为xk，投给部门A的资源数量为yk。则投给部门B的数量为xk yk。于是可得到收入g(yk) + h(xk  yk)，回收axk + b (xk  yk)。 因此，问题就成为：求y1, y2, , yn， 最大化1  k  n g(yk) + h(xk  yk) ，且满足条件 x1 = x x2 = ay1 + b(x1  y1) …… xn = ayn  1 + b(xn  1  yn  1) yk  0，xk  0， k = 1..n  1 2019/5/1 山东大学 软件学院

如何求解？（后向优化） 2019/5/1 山东大学 软件学院

例5.1.2 例5.1.2：离散变量的资源分配问题。 今有 1000 台机床（x = 1000），投放到 A、B 两个部门。 若给部门 A 投放 z 台机床，则产生效益 g(z) = z2，回收 0.8z台机床（a = 0.8）。 若给部门 B 投放 z 台机床，则产生效益 h(z) = 2z2，回收 0.4z台机床（b = 0.4）。 问连续投放 5 年（n = 5），每年如何投放，可使 5 年的总收益最大？ 2019/5/1 山东大学 软件学院

如何求解？ 2019/5/1 山东大学 软件学院

计算一个单元格 f(k, x) 1 v   。 2 for y  0 到 x do 3 t  g(y) + h(x  y) + table(k  1,ay + b(x  y))。 /* 令 table(0, x) = 0 。*/ 4 if t > v then v  t。 5 endfor 6 return v。 2019/5/1 山东大学 软件学院

说明 每计算一个单元格的 fk(x)，都需要计算一个max 0  y  x {…}函数。因此，尽管使用表格暂存了计算结果，为计算出最后的 fn(x) 仍需要大量的计算。 小技巧：不用每行都从 0 计算到 1000。每年无论如何投放，回收的机床最多是 0.8x 台（max{a, b} = 0.8）。例如表格第 5 行表示最后一个阶段，其前面有 4 个阶段。因此对于第5行，只需要从 0 计算到 0.84  1000 4096。 但动态规划法已经比直接用递归的方法解递推方程减少了大量的计算。 2019/5/1 山东大学 软件学院

计算结果 2019/5/1 山东大学 软件学院

递归的方法 f(k, x) 1 v  0。 2 if k = 1 then 3 for y  0 到 x do 4 t  g(y) + h(x  y)。 5 if t > v then v  t。 6 endfor 7 else 8 for y  0 到 x do 9 t  g(y) + h(x  y) + f(k  1, ay + b(x  y))。 10 if t > v then v  t。 2019/5/1 山东大学 软件学院

递归的方法 11 endfor 12 endif 13 return v。 2019/5/1 山东大学 软件学院

多阶段决策问题 有一个系统，可以分成若干个阶段。 任意一个阶段 k，系统的状态可以用 xk 表示（可以是数量、向量、集合等）。 每一状态 xk 都有一个决策集合 Qk(xk)，在 Qk(xk) 中选定一个决策 qk  Qk(xk)，状态 xk 就转移到新的状态x k + 1 = Tk(xk, qk)，并且得到效益（或费用）Rk(xk, qk)。 系统的目标就是在每一个阶段都在它的决策集合中选择一个决策，使所有阶段的总效益达到最大（或总费用达到最小）。 这样的多阶段决策问题通常使用动态规划方法来求解。 2019/5/1 山东大学 软件学院

动态规划的最优子结构性质 动态规划的最优化原理：需要问题的最优解具有如下所述的最优子结构性质： 一个多阶段决策问题，假设其最优策略的第一阶段的决策为 q1，系统转移到的新状态为 x2。则该最优策略以后诸决策对以 x2 为初始状态的子问题而言，必须构成其最优策略。 该子问题与原问题是同一类问题，只是问题规模下降了。 当观察到问题解的最优子结构性质时，就意味着问题可能用动态规划法求解。 2019/5/1 山东大学 软件学院

动态规划的子问题重叠性质 从算法角度而言，（离散变量的）动态规划所依赖的另一个要素是子问题重叠性质：一个问题的求解可以划分成若干子问题的求解，而处理这些子问题的计算是部分重叠的。 动态规划法利用问题的子问题重叠性质设计算法，能够节省大量的计算。对一些看起来不太可能快速求解的问题，往往能设计出多项式时间算法。 在算法理论中，多项式时间算法通常被认为是“有效的算法”（efficient algorithm）。 2019/5/1 山东大学 软件学院

前向优化 写动态规划递推方程时，一般有两种写法：前向优化和后向优化。假设问题有n个阶段。 定义fk() 为问题的前k个阶段（从第1阶段到第k阶段）的最优解值，然后将fk()递推至fk  1()。 最后写出递推的终止条件f1()的表达式。 原问题就是计算fn()。这称为前向优化。 1 2 n n – 1 … fn – 1() fn() 2019/5/1 山东大学 软件学院

后向优化 假设问题有n个阶段。 定义fk() 为问题的后k个阶段（从第n – k + 1阶段到第n阶段）的最优解值，然后将fk()递推至fk – 1()。 最后写出递推的终止条件f1()的表达式。 原问题就是计算fn()。这称为后向优化。 1 2 n n – 1 … fn – 1() fn() 2019/5/1 山东大学 软件学院

说明 前面给出的两个例子，最短路问题和资源分配问题，都是采用后向优化技术解决的。 原则上，多阶段决策问题既可以使用前向优化技术解决，也可以使用后向优化技术解决。 依据问题不同，前向优化和后向优化其中的一种或二者是“自然”的解法。 2019/5/1 山东大学 软件学院

最短路问题，前向优化 2019/5/1 山东大学 软件学院

资源分配问题，前向优化 2019/5/1 山东大学 软件学院

资源分配问题，前向优化 2019/5/1 山东大学 软件学院

动态规划所研究的问题 阶段数固定还是不固定？ 离散变量还是连续变量？ 很多阶段数不明显的优化问题，也可以使用动态规划方法求解。 阶段数固定（也称为“定期”），指阶段数有限且固定。 阶段数不固定（也称为“不定期”）：指阶段数有限但不固定，以及阶段数无限大两种情况。 离散变量还是连续变量？ 很多阶段数不明显的优化问题，也可以使用动态规划方法求解。 2019/5/1 山东大学 软件学院

2019/5/1 山东大学 软件学院