运筹学第七章：动态规划.pdf_动态规划多阶段决策例子

动态规划

需积分: 48 158 浏览量更新于2023-03-03 评论 2 收藏 464KB PDF 举报

身份认证购VIP最低享 7 折!

领优惠券(最高得80元）

资源详情

资源评论

资源推荐

运筹学第七章：动态规划

Charles007

November 23, 2020

动态规划是解决多阶段决策过程最优化问题的一种方法。它可用于解决最优路径问题、资源分配问题、生产

计划与库存、投资、装载、排序等问题及生产过程的最优控制等。由于它有独特的解题思路，在处理某些优化问

题时，比线性规划或非线性规划方法更有效。

动态规划模型的分类：离散确定型；离散随机型；连续确定型；连续随机型。其中离散确定型是最基本的，

文中主要针对这类问题介绍动态规划的基本思想、原理和方法。不过这些对其他类型的问题也适用。

1 多阶段决策过程的最优化

多阶段决策过程，是指可以按时间顺序分为若干阶段，而每个阶段都需要做出决策，以使整个活动过程的总

体效果最优的过程。由于各段决策间有机地联系在一起，本阶段决策的执行会影响到下阶段的决策，以至于影响

总体效果，所以决策者在每阶段决策时不应仅考虑本阶段最优，还应考虑对最终目标的影响，从而做出对全局来

讲是最优的决策。

动态规划方法与“时间”关系密切，随着时间过程的发展而决定各时段的决策，产生一个决策序列，这就是

“动态”的意思。然而它也可以处理与时间无关的静态问题，如某些线性规划或非线性规划问题，只要在问题中

人为地引入“时段”因素，将问题看成多阶段决策过程即可。

2 动态规划的基本概念和基本原理

2.1 动态规划的基本概念

动态规划的基本概念有５个：阶段；状态；决策和策略；状态转移方程；指标函数。

(1) 阶段。将所给问题的过程，按时间或空间特征分成若干互相联系的阶段，以便按次序去求每阶段的解，常

用字母 k 表示阶段变量。

(2) 状态。各阶段开始时的客观条件叫做状态。描述各阶段状态的变量称为状态变量，常用 s

表示第 k 阶段

的状态变量，状态变量 s

的取值集合称为状态集合，用 S

表示。动态规划中的状态应具有如下性质：当

某阶段状态给定以后，在这阶段以后过程的发展不受这段以前各段状态的影响。也就是说，当前的状态是

过去历史的一个完整总结，过程的过去历史只能通过当前状态去影响它未来的发展，这称为无后效性。如

果所选定的变量不具备无后效性，就不能作为状态变量来构造动态规划模型。

(3) 决策和策略。当各阶段的状态取定以后，就可以做出不同的决定 (或选择)，从而确定下一阶段的状态，这

种决定称为决策。表示决策的变量，称为决策变量，常用 u

) 表示第 k 阶段当状态为 s

时的决策变量。

在实际问题中，决策变量的取值往往限制在一定范围内，我们称此范围为允许决策集合，常用 D

) 表示

第 k 阶段从状态 s

出发的允许决策集合，显然有 u

) ∈ D

)。

(4) 状态转移方程。动态规划中本阶段的状态往往是上一阶段状态和上一阶段的决策结果。如果给定了第 k 阶

段的状态为 s

，决策为 u

)。那么，第 k + 1 阶段的状态 s

k+1

也就完全确定，它们的关系可表示如下：

k+1

= T

, u

)

这就是状态转移方程。

(5) 指标函数。用于衡量所选定策略优劣的数量指标称为指标函数。它分为阶段指标函数和过程指标函数两种。

阶段指标函数是指第 k 阶段，从状态 s

出发；采取决策 u

时的效益，用 d(s

, u

) 表示。而一个 n 阶段

决策过程，从１到 n 叫作问题的原过程，对于任意一个给定的 k(1 ≤ k ≤ n)，从第 k 到 n 阶段的过程称为

原过程的一个后部子过程。V

1,n

, p

1,n

) 表示初始状态为 s

采用策略 p

1,n

时原过程的指标函数。最优指

标函数记为 f

)，它表示从第 k 阶段状态 s

采用最优策略 p

∗

k,n

到过程终止时的最佳效益值。f

) 与

k,n

, p

k,n

) 间的关系为

) = V

k,n

, p

∗

k,n

) = opt

k,n

∈P

k,n

, p

k,n

)

当 k = 1 时，f

) 就是从初始状态 s

到全过程结束的整体最优函数。

2.2 动态规划的基本思想和最优化原理

动态规划的基本思想可以总结为：

(1) 将多阶段决策过程划分阶段，恰当地选取状态变量、决策变量及定义最优指标函数，从而把问题化成一族

同类型的子问题，然后逐个求解。

(2) 求解时从边界条件开始，逆 (或顺) 过程行进方向，逐段递推寻优。在每一个子问题求解时，都要使用它前

面已求出的子问题的最优结果，最后一个子问题的最优解，就是整个问题的最优解。

(3) 动态规划方法是既把当前一阶段与未来各阶段分开，又把当前效益和未来效益结合起来考虑的一种最优化

方法，因此每段的最优决策选取是从全局考虑的，与该段的最优选择一般是不同的。动态规划的基本方程

是递推逐段求解的根据，一般的动态规划基本方程可以表示为



) = opt

∈D

)

, u

) + f

k+1

)] k = n, n − 1, · · · , 1

n+1

) = 0

(1)

式中 opt 可根据题意取 min 或 max，v

, u

) 是状态为 s

，决策为 u

时对应的第 k 阶段的指标函数值。

动态规划的最优化原理。动态规划方法基于贝尔曼等人提出的最优化原理。其可表述为：“一个过程的最优

策略具有这样的性质：即无论初始状态及初始决策如何，对于先前决策所形成的状态而言，其以后的所有决策应

构成最优策略。”利用此原理，可以把多阶段决策问题求解过程表示成一个连续的递推过程，由后向前逐步计算。

在求解时，前面的各状态与决策，对后面的子过程来说，只相当于初始条件，并不影响后面子过程的最优决策。

3 动态规划模型的建立与求解

3.1 动态规划模型的建立

一般地，建立动态规划模型的要点如下：

1. 分析题意，识别问题的多阶段特性，按时间或空间的先后顺序适当地划分为满足递推关系的若干阶段，对

非时序的静态问题要人为地赋予“时段”的概念。

2. 正确地选择状态变量，使其具备两个必要特征：

(1) 可知性：即过程演变的各阶段状态变量的取值，能直接或间接地确定。

(2) 能够确切地描述过程的演变且满足无后效性。即由第 k 阶段的状态 s

出发的后部子过程，可以看作

是一个以 s

为初始状态的独立过程。这一点并不是每个问题都很容易满足的。例如“货郎担问题”，

就不能像前面处理最短路问题一样，把城镇位置作为状态变量，而需要把含该城镇在内及以前走过的

全部城镇的集合定义为状态，才能实现无后效性。

3. 根据状态变量与决策变量的含义，正确写出状态转移方程 s

k+1

= T

, u

) 或转移规则。

4. 根据题意明确指标函数 V

k,n

，最优指标函数 f

) 以及 k 阶段指标 v

, u

) 的含义，并正确列出最优指

标函数的递推关系及边界条件 (即基本方程)。

剩余11页未读，继续阅读

KnowledgeIsMagic

粉丝: 2
资源: 15

会员权益专享

运筹学第七章：动态规划.pdf

评论0

会员权益专享

最新资源

运筹学第七章：动态规划.pdf

评论0

运筹学习题答案 (第四版)

运筹学-动态规划

matlab 动态规划的实现

python 运筹学

运筹学导论塔哈pdf

02375运筹学基础自考教材pdf

运筹学中目标规划的优缺点

神经网络与运筹学的关系

运筹学教程第四版胡运权pdf

动态规划问题 运筹学

多目标动态规划优化运筹

02375运筹学基础pdf教材

运筹学动态规划机器负荷问题

动态规划的理论意义与实际意义

运筹学与最优化MATLAB编程

动态规划算法MATLAB代码

运筹学规划部分习题有详细答案

会员权益专享

最新资源

动态规划问题运筹学