07 第七章 动态规划.pptx

第1页：动态规划章节目录

本章内容：

• 1. 多阶段决策问题与动态规划
• 2. 动态规划的基本概念
• 3. 动态规划的步骤
• 4. 动态规划的应用：① 求解静态规划问题 ② 资源分配问题 ③ 不确定性采购问题 ④ 排序问题 ⑤ 离散确定型动态规划模型的求解

第2页：多阶段决策问题

以上两个问题都可以划分为先后多个决策阶段，这类问题就称为多阶段决策问题。多阶段决策问题的过程如下图所示：

决策1 → 决策2 → …… → 决策n，状态1 → 状态2 → 状态3 → …… → 状态n → 状态n+1

多阶段决策问题和前面遇到的决策问题不同，它是和时间有关的。与时间有关的活动过程称为动态过程，其优化方法称为动态规划；与时间无关的活动过程称为静态过程，相应的优化方法称为静态规划。

例1 最短路问题

图中 A 为起点、G 为终点，中间经 B、C、D、E、F 各层节点，求 A 到 G 的最短路线（各弧权值 5、3、1、3、6、8、7、6、6、8、3、5、3、8、4、2、2、1、2、3、3、3、4 等）

例2 机器负荷分配问题

某种机器可在高低两种不同负荷下生产：高负荷下年产量 g = g(u)，机器年完好率为 a（0 < a < 1）；低负荷下年产量 h = h(v)，年完好率为 b（a < b < 1）。开始生产时完好机器数为 s1，要求制定五年计划，在每年开始时决定两种负荷下生产的机器数量，使五年内产品总产量最高

源文件该页两例的图形数据（各弧权值与节点编号）为连排数字，节点之间的连接关系建议对照原图核对。

第3页：动态规划的基本概念（一）

7.2 动态规划的基本概念

（1）阶段（stage）

把所研究的决策问题按先后顺序划分为若干相互联系的决策步骤，以便按一定次序求解。描述阶段的变量称阶段变量，常用 k 表示

（2）状态（state）

状态表示每个阶段开始时所处的自然状况或客观条件，它既是前面阶段所作决策的结果，又是本阶段作出决策的出发点和依据。描述状态的变量称为状态变量，第 k 阶段的状态变量常用 xk 表示；第一阶段状态变量 x1 是确定的，称初始状态

（3）决策（decision）

决策表示在某一阶段处于某种状态时，决策者在若干种方案中作出的选择决定。描述决策的变量称决策变量，第 k 阶段的决策变量常用 uk 表示，其取值受状态变量制约

（4）策略（policy）

从第一阶段开始到最后阶段终止的整个决策过程称为问题的全过程；从第 k 阶段开始到最后阶段终止的决策过程称为 k 子过程。全过程上各阶段决策按顺序排列组成的决策序列 p1,n = {u1, u2, ……, un} 称全过程策略，简称策略；k 子过程上的决策序列 pk,n 称子策略

（5）状态转移方程

若第 k 阶段状态变量值为 xk，当决策变量 uk 取值决定后，下一阶段状态 xk+1 的值也随之确定，对应关系记为 xk+1 = Tk(xk, uk)，称为状态转移方程

第4页：指标函数与基本方程

7.2 动态规划的基本概念（二）

（6）指标函数和最优值函数

阶段指标函数 vk(xk, uk) 度量某一阶段的状态和决策产生的效益；过程指标函数 Vk,n 表示各阶段效益的总和，应具有可分离性，常见两种形式：① 各阶段指标函数的和 Vk,n = Σ vj(xj, uj)；② 各阶段指标函数的积 Vk,n = Π vj(xj, uj)。把 Vk,n 对 k 子过程策略 pk,n 求最优，得到关于状态 xk 的函数，称为最优值函数，记为 fk(xk) = opt Vk,n(xk, uk, ……, xn, un)，其中「opt」按题意取 min 或 max

（7）基本方程

设过程指标函数为各阶段指标之和，则有递推方程 fk(sk) = opt{ vk(xk, uk) + fk+1(xk+1) }，k = n, n-1, …, 1，uk ∈ Dk(sk)；边界条件 fn+1(xn+1) = 0。递推方程和边界条件一起称为动态规划的基本方程。由边界条件从 k = n 开始由后向前逆推，逐步求得各阶段的最优决策与最优值，最后求出 f1(x1) 即得整个问题的最优解

第5页：最短路的动态规划递推

例：最短路问题。此问题的基本方程为

fk(xk) = Min{ dk(uk) + fk+1(xk+1) }，uk ∈ Dk(sk)，k = 6, 5, 4, 3, 2, 1；f7(x7) = 0

按基本方程由后向前递推：

• k = 6 时：F1 → G 为 4 + 0 = 4*；F2 → G 为 3 + 0 = 3*
• k = 5 时：E1 经 F1 得 2 + 5 = 7*，E2 经 F2 得 2 + 3 = 5*，E3 经 F2 得 6 + 3 = 9*
• k = 4 时：C1 → D1 得 6 + 7 = 13*，C2 → D1 得 3 + 7 = 10*，C3 → D2 得 3 + 6 = 9*，C4 → D3 得 4 + 8 = 12*
• k = 3 时：D2 → E3 得 2 + 9 = 11，D3 → E2 得 3 + 5 = 8*
• k = 2 时：B1 → C2 得 3 + 10 = 13*，B2 → C3 得 7 + 9 = 16*
• k = 1 时：A → B1 得 5 + 13 = 18*，A → B2 得 3 + 16 = 19

由此可以看出，A 到 G 的最短路长为 18，路径为 A → B1 → C2 → D1 → E2 → F2 → G。

源文件该页各阶段的递推计算表为连排数字，部分数值与节点的对应关系按原文碎片整理，建议对照原图核对。

第6页：动态规划的步骤与机器负荷问题

现在把动态规划法的步骤归纳如下：

1. 将所研究问题的过程划分为 n 个恰当的阶段，k = 1, 2, …, n
2. 正确地选择状态变量 xk，并确定初始状态 s1 的值
3. 确定决策变量 uk 以及各阶段的允许决策集 Dk(xk)
4. 给出状态转移方程
5. 给出满足要求的过程指标函数 Vk,n 及相应的最优值函数
6. 写出递推方程和边界条件，建立基本方程
7. 按照基本方程递推求解

以上前六步是建立动态规划模型的步骤。

例：机器负荷问题。某机器可在高低两种负荷下生产，高负荷下年产量 g = 8u，机器年完好率 a = 0.7；低负荷下年产量 h = 5v，年完好率 b = 0.9。开始生产时完好机器数量为 s1，要求制定五年计划，在每年开始时决定机器在两种不同负荷下生产的数量，使五年内产品的总产量最高。

第7页：求解静态规划问题

某些静态规划问题可用动态规划法来求解。

例：用动态规划法求解 max F = 4x1 - x1² + 2x2 - x2² + x3²（或 max z = x1 · x2 · x3 型），满足 x1 + 2x2 + x3 ≤ 9，xi ≥ 0（i = 1, 2, 3）。此类问题把各变量的取值作为相互联系的阶段，以剩余资源量作为状态，按基本方程逆推求解。

源文件该页目标函数与约束被打散连排（如 x1 + x2 + x3 = c 与 xi ≥ 0），具体函数形式建议对照原图核对。

第8页：不确定性采购问题

某单位准备在以后的 n 个时期内采购一批物资。各时期的价格不是确定的，而是按照某种已知的概率分布取值。试制定采购策略，确定在哪一时期以什么价格采购，能使采购价的数学期望值最低。这类问题也适合用动态规划法处理。

例7：某厂生产上需要在近五周内采购一批原料，而估计在未来五周的价格有波动，其浮动价格和概率测得如下表。试确定该厂应在哪一周以什么价格购入，能使其采购价的数学期望值最小，并求出期望值。

建模思路：以周为阶段 k（k = 1,…,5），以该周的实际价格 xk 为状态，决策为「采购」或「等待」，按期望值递推求最优采购策略。

第9页：资源分配问题

例：某工业部门根据国家计划安排，拟将五台某种高效率的机器分配给所属的甲、乙、丙三个工厂，各工厂得到不同数量的机器可获得的收益如下表。问应如何分配机器，才能使各厂的总效益最大。

资源分配问题的一般描述：设有某种原料，总数量为 a，分配给 n 个使用者。已知第 i 个使用者得到数量 xi 的该资源，可创造的收益为 gi(xi)，问应如何分配才能使总收益最大。用动态规划法处理时，通常把给一个使用者分配资源的过程看成一个阶段，按 n 个使用者分成先后 n 个决策阶段：先给第 1 个使用者分配为第一阶段，再给第 2 个使用者分配为第二阶段，依此类推。

源文件该页收益表的数字被打散连排，表格按教材中本例的标准数据整理（0 台时三厂收益均为 0，随机器数递增），建议对照原图核对。

第10页：排序问题（一）

设有 n 个工件需要在机床 A、B 上加工，每个工件都必须先经过 A 而后 B 两道加工工序。以 ai、bi 分别表示工件 i（1 ≤ i ≤ n）在 A、B 上的加工时间。问应如何在两机床上安排各工件的加工顺序，使在机床 A 上加工第一个工件开始到在机床 B 上加工完最后一个工件为止，所用的加工总时间最少。

• 加工工件在机床 A、B 上都有加工顺序问题，两台机床上的加工顺序可以不同；若 B 上的顺序与 A 不同，会使机床 B 的等待时间加长，从而加长总加工时间
• 可以证明：最优加工顺序在两台机床上可同时实现，因此最优排序方案可以只在 A、B 上加工顺序相同的排序中寻找
• 即使如此，所有可能的方案仍有 n! 个，用穷举法是不现实的
• 当加工顺序排定之后，工件在 A 上没有等待时间，而在 B 上则常常需要等待，因此寻求最优排序方案只有尽量减少在 B 上等待加工的时间，才能使总加工时间最短

第11页：排序问题（二）

用动态规划法可以推出，为了节省等待时间，工件 i 应该排在工件 j 之前的条件为

min(ai, bj) ≤ min(aj, bi)

对于一个完整的排序，如果任意前后两个工件对的工时都满足上述不等式，那么这个排序就是工时最省的排序。根据这个条件，构造下列排序方法：

1. 建立各工件加工时间的工时矩阵 M = [a1 a2 … an；b1 b2 … bn]
2. 在工时矩阵 M 中找出最小元素（若不止一个最小元素，可任选其一）：若它在上行，则相应的工件排在最前位置；若它在下行，则相应的工件排在最后位置
3. 将排定位置的工件所对应的列从 M 中划去，然后对余下的工件再按 (2) 进行排序，如此进行下去，直到把所有工件都排完为止

例：设有 5 个工件需在机床 A、B 上加工，加工次序为先 A 后 B，每个工件需要的加工时间如下表（A 行：6、3、1、2、7；B 行：2、7、4、3、5 一类），试安排加工顺序，使总加工时间最少，并求出总加工时间。

源文件该页工时矩阵的数字被打散连排（如 6、3、1、2、7 与 2、7、4、3、5），工件与工时的对应关系建议对照原图核对。

第12页：离散确定型动态规划模型

投资决策问题：某公司准备投入 3 千万元资金对所属 3 个工厂进行技术改造，投资金额为 0、1、2、3 千万元四种额度。经测算，每个工厂的投资额与技术改造后每年新增的效益如下表。问如何投资使总收益最大？

（1）建模：k = 1, 2, 3；状态转移 xk+1 = xk - uk；递推方程 fk(xk) = max{ vk(xk, uk) + fk+1(xk+1) }；边界条件 f4(x4) = 0。

源文件该页效益表按投资额 3、2、1、0 的降序连排（如 2.0、1.2、0.5、0），表格按升序投资额重新排列，建议对照原图核对。

第13页：投资决策问题的求解

（2）求解：从 k = 3 开始逆推。

• 第三阶段（工厂3）：u3 = 0、1、2、3 时 f3(x3) 分别取 0、0.4、0.6、1.0（按 u3 与 x3 的对应关系）
• 第二阶段（工厂2）：f2(x2) 在 u2 = 0、1、2、3 时分别对应 2.2、1.8、1.9、0，取最大值得 f2 = 2.2（u2* = 3 一类）
• 第一阶段（工厂1）：x1 = 3 时，2.0 + 0 = 2.0、1.2 + 0.6 = 1.8、0.5 + 1.4 = 1.9、0 + 2.2 = 2.2，故 f1(3) = 2.2，对应的最优决策序列即为使总收益最大的投资方案

源文件该页为各阶段状态、决策与 f 值的连排数字（如 0.6、1.4、1.8、2.2、1.3、0.4 等），行列无法安全切分，故不作表格还原，具体的最优决策与总收益建议对照原图核对。