第10章 动态规划

《第10章 动态规划》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第十章动态规划§4-1引言及内容框架§4-2基本概念、模型与最优化原理§4-3动态规划的应用1§4-1引言■动态规划的研究对象■动态规划问题的特点■静态决策问题的动态处理2一、动态规划的研究对象——多阶段的决策问题1多阶段决策问题动态决策——将时间作为变量的决策问题称为动态决策。其基本特点是多次决策。多阶段决策问题是一类特殊形式的动态决策问题。是指这样一类活动过程：系统的动态动态过程可以按照时间进程分为状态相互联系又相互区别的阶段，而且每个阶段都进行决策，当每个阶段决策确定以后，就完全确定了一个过程确定的线路。3多阶段决策问题的典型例子

2、※企业生产过程中，由于需求是随着时间变化的因素，因此企业为了获得全年最佳经济效益，就要在整个过程中进行逐月和逐季的根据库存和需求决定生产计划。※某种机器，可以在高、低两种负荷下生产。高负荷下生产时的产量多，但每生产一个阶段的机器完好率低；低负荷下生产时的情况则相反。现在需要安排该种机器在多个阶段内的生产，问应如何决定各个阶段中机器的使用，使这个计划期内的总产量最大？4※某台设备。例如汽车，刚买来时故障低，耗油少，出车时间长，处理价值和经济效益高；随着使用时间的增加则变为故障多、耗油高、维修费用增加，经济效益差，使用时间越长，处理价值越低

3、。另外每次更新都要付出更新费用。因此应如何决定设备的使用年限，使总的效益最佳？※化工生产过程包括一系列的过程设备，如反映器、蒸馏塔、吸收器等，前一设备的输出是后一设备的输入。因此，应如何控制生产过程中各个设备的输出和输入，使总产量最大？5什么是动态规划？DP是OR中的一个分支，是解决多阶段决策过程最优化的一种方法或是一种分析多阶段决策过程的数学方法。这种方法可根据人们所采取的措施，一步步地控制过程的发展，来实现预定的要求。这一运筹学分支最初有美国数学家BELLMAN等人根据一类多阶段决策问题的特性，提出了解决这类问题的最优化原理，并研究

4、了许多实际问题而建立起来的。6动态规划的特点优点①许多问题用动态规划研究求解比线性规划、非线性规划更有效，特别是离散性问题，解析数学无用武之地。而动态规划成为得力工具；②某些情况下，用动态规划处理不仅能定性描述分析，且可利用计算机给出求其数值解的方法。二、动态规划问题的特点7缺点①没有统一的处理方法，求解时要根据问题的性质，结合多种数学技巧。因此实践经验及创造性思维将起重要的引导作用；②“维数障碍”，当变量个数太多时，由于计算机内存和速度的限制导致问题无法解决。有些问题由于涉及的函数没有理想的性质使问题只能用动态规划描述，而不能用动态规

5、划方法求解。8不包含时间因素的决策问题称为静态决策问题，是一次性决策（如线性规划）。但若能恰当地人为引入“时段”概念，就可以把问题转化成一个多阶段决策问题，这样就能用动态规划处理了。拓宽了动态规划的应用范围。这样的例子是大量的，如最短线路问题，资源分配问题等等。三、静态决策问题的动态处理9DP中描述多阶段决策过程的基本概念主要有：●阶段和阶段变量●状态和状态变量●决策、决策变量和决策序列●状态转移方程●阶段效应和目标函数§4-2基本概念、模型与最优化原理10把所研究的多阶段决策过程恰当地划分为若干个相互独立又相互联系的部分，每个部分称为

6、一个阶段。事实上一个阶段也就是需要作出一个决策的子问题部分。通常阶段是按照过程进行的时间和空间上的先后顺序划分的。并用阶段变量k表示。阶段数等于多段决策过程中从开始到结束所需要作出决策的数目。划分阶段的目的是便于求解。1、阶段和阶段变量11状态是描述系统状况所必须的信息。一般定义为某一阶段的初始点、初始位置和初始情况。状态变量必须包含在给定的阶段上确定全部允许决策所需要的信息，阶段k的状态变量表示为sk。比如：在最短路问题中，状态就是网络中各个节点。2、状态和状态变量12状态变量的取值有一定的允许范围，称为状态可能集。状态可能集可以是一

7、个离散取值的集合，也可以是一个连续的区间，视所给问题而定。状态可能集是关于状态的约束条件。状态可能集用相应阶段状态sk的大写字母Sk表示，其中sk∈Sk13决策就是决策者从本阶段出发对下一阶段状态的选择。多段决策过程的发展是用各个阶段的状态演变描述的。因此用状态描述的过程具有无后效性，因此在进行阶段决策时，只须根据当前的状态而无须考虑过去的历史。在阶段k如果给出了决策变量xk随状态变量sk变化的函数，称为决策函数，表示为：xk(sk)。3、决策和决策变量和决策序列14决策变量的允许取值范围，称为允许决策集合。允许决策集合是决策变量的约束

8、条件。xk的允许决策集合表示为Xk。xk∈Xk，Xk要根据相应的状态可能集Sk并结合具体问题来确定。决策序列就叫策略，策略有全过程策略和子策略之分。全过程策略是整个问题n个段决策过程依次进行的n个阶段决策构