第5章 动态规划.doc

《第5章 动态规划.doc》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、第5章动态规划动态规划是解决多阶段策划过程最优化问题的一种方法。该方法是有美国数学家贝尔曼（RBellman）等人在20世纪50年代初提出的。他们针对多阶段决策问题的特点，提出了解决这类问题的最优化原理，并成功地解决了声场管理、工程技术等方面的修多实际问题，从而建立里了运筹学的一个新分支。1957年，RBellman发表了该分支领域的第一本专著《动态规划》（DynamicProgramming）。动态规划是现代企业管理中的一种重要决策方法，可用于解决最优路径问题、资源分配问题、生产计划与库存、投资、装载、排序等问题及生产过程的最优控制等。由于它有独特的解决思路，在处理某

2、些优化问题时，比线性规划或非线性规划方法更有效。动态规划模型的分类：①离散确定型；②离散随机型；③连续确定型；④连续随即型。其中离散确定型是最基本的，本章主要针对这种类型的问题，介绍动态规划的基本思想、原理和方法，这些对其他类型的问题也适用。然后通过几个典型的动态规划模型来介绍它的应用。第一节多阶段决策过程的最优化多阶段决策过程，本意是指这样一类特殊的活动过程，它们可以按时间顺序分解成若干相互联系的阶段，称为“时段”，在每一个时段都要做出决策，全部过程的决策是一个决策序列，所以多阶段决策问题属序贯决策问题。多阶段决策过程最优化的目标是要达到整个活动过程的总体效果最优。例

3、1生产与存贮问题某工厂每月需供应市场一定数量的产品，并将所余产品成本存入仓库。一般适当增加产量可降低生产成本，但超产部分存放仓库会增加库存费用。要求确定一个逐月的生产计划，在满足需求条件下，使一年的生产与存贮费用之和最小。例2投资决策问题某公司现有资金Q万元，在今后5年内给A，B，C，D4个项目投资，这些项目投资的回收期限、回报率均不相同，问访公司应如何确定这些项目每年的投资额，使到第5年末拥有资金的本利总额最大。例3设备更新问题企业在使用设备时都要考虑设备的更新问题，因为设备越陈旧所需的维修费用，但购买新设备则要一次性献出较大的费用。现某企业要决定一台设备未来8年的更

4、新计划，已预测了每时j年购买设备的价格为，设为设备经过j年后残值，为设备连续使用j－1年后在第j年的维修费（j=1,2,…,8），问应在哪些年更新设备可使总费用最小。这是一个8阶段决策问题，每年年初要做出决策，是继续使用旧设备，还是购买新设备。更多的例子将在后面结合求解介绍。第二节动态规划的基本概念和基本原理一、动态规划的基本概念使用动态规划方法解决多阶段决策问题，首先要将实际问题写成动态规划模型，此时要用到以下概念：⑴阶段；⑵状态；⑶决策和策略；⑷状态转移；⑸指标函数。下面我们结合例题说明这些概念。例4最短线路问题如图7-1所示，给定一个线路网络图，要从A地向F地铺设

5、一条输油管道，各点间边上的数学表示距离，问就选择什么路线，可使总距离最短？⑴阶段所给问题的过程，按时间或空间特征分解成若干互相联系泊阶段，以便按次序去求每阶段的胞妹，常用字母k表示阶段变量。例4中，从A到F可以分成从A到B（B有两种选择,),从B到C（C有四种选择，，，），从C到D（D有三种选择，，），从D到E（E有两种选择，），再从E到F五个阶段。K=1,2,3,4,5。⑵状态各阶段开始时的客观条件叫做状态。描述各阶段状态的变量称为状态变量，常用表示第k阶段的状态变量，状态变量的取值集合称为状态集合，用表示。动态规划中的状态应具有如下性质：当某阶段状态以后，在这阶段以

6、后过程的发展不受这段以前各段状态的影响。也就是说，当前的状态是过去历史的一个完整总结，过程的过去历史只能通过当前状态去影响它未来的发展，这称为无后效性。如果所选定的变量无后效性，就不能作为状态变量来构造动态规划模型。在例4中第一阶段状态为A，第二阶段则有二个状态：。状态变量的集合，后面各段的状态集合分别是：当某段的初始状态已选定某个点时，从这个点以后的铺管路线只与该点有关，有受以前铺管路线影响，所以满足状态的无后效性。⑶决策和策略当各段的状态以后，就可以做出不同的决策（或选择），从而确定下一阶段的状态，这种决定称为决策。表示决策的变量，称为决策变量，常用表示第k阶段当状

7、态为的决策变量。在实际问题中，决策变量的取值往往限制在一定范围内，我们称此范围为允许决策集合，常用表示第k阶段从状态出发的允许决策集合，显然有。在例4中，从第二阶段的状态出发，可选择下一段的，即其允许决策集合为：如我们决定选择，则亦可以表示为：各段决策确定后，整个问题的决策序列就构成一个策略，用表示。对每个实际问题，可供选择的策略有一定范围，称为允许策略集合，记作，使整个问题达到最优效果的策略就是最优策略。⑷状态转移方程动态规划中本阶段的状态往往是上上阶段状态和上一阶段的决策结果。如果给定了第k段的状态,本阶段决策为,则第k+1段的状态也