动 态 规划.doc

第五章动态规划
【教学内容】
动态规划问题,动态规划问题的基本要素和最优化原理,动态规划应用,用LINGO软件求解动态规划问题。
【教学要求】
要求学生掌握什么是多阶段决策过程、动态规划的基本概念、动态规划的基本原理及基本方程,掌握静态规划怎样转化为动态规划来解,学会分析解决动态规划的问题的方法并用LINGO软件求解。
【教学重点】
多阶段决策过程、动态规划的基本概念、动态规划的基本原理及基本方程,动态规划应用,用LINGO软件求解动态规划问题。
【教学难点】
动态规划的基本概念、动态规划的基本原理及基本方程,动态规划应用。
【教材内容及教学过程】
动态规划(Dynamic Programming)是求解多阶段决策过程最优化的数学方法。1951年,,提出了著名的最优化原理,把多阶段过程转化为一系列单阶段问题,逐个求解,创立了解决这类过程优化问题的新方法——动态规划。1957年他的名著“Dynamic Programming”在普林斯顿大学出版,这是该领域的第一本著作。
动态规划所研究的对象是多阶段决策问题。所谓多阶段决策问题是指一类活动过程,它可以分为若干个互相联系的阶段,在每个阶段都需要做出决策。这个决策不仅决定这一阶段的效益,而且决定下一阶段的初始状态。每个阶段的决策确定以后,就得到一个决策序列,称为策略。多阶段决策问题就是求一个策略,使各阶段的效益的和达到最优。
虽然动态规划主要用于求解以时间划分阶段的动态过程的优化问题,但是一些与时间无关的静态规划(如线性规划、非线性规划),只要人为地引进时间因素,把它视为多阶段决策过程,也可以用动态规划方法方便地求解。
动态规划问世以来,在工程技术、经济管理、生产调度、最优控制,以及军事等领域得到了广泛的应用。例如最短路线、库存管理、资源分配、生产调度、设备更新、排序、装载等问题,用动态规划方法比用其它方法求解更为方便,而且许多问题用动态规划方法去处理,也比线性规划或非线性规划更有成效。
第一节动态规划问题
§ 多阶段决策问题
我们将多阶段决策问题描述如下:
有一个系统,可以分成若干个阶段,任意一个阶段,系统的状态可以用表示可以是数量、向量、集合等。在每一阶段的每一状态都有一个决策集合,在中选定一个决策,状态就转移到新的状态,并且得到效益。我们的目的就是在每一个阶段都从它的决策集合中选择一个决策,使所有阶段的总效益达到最优。
这样的多阶段决策问题称为动态规划,表示它是一个多步最优化问题。前面介绍的线性规划、整数规划和目标规划都是静态规划。动态规划与线性规划、整数规划和目标规划不同之处还在于,一般动态规划没有一个统一的数学表达式。
§ 动态规划问题举例
,给定一个网络,从点铺设一条煤气管道到点,必须经过五个中间站,第一站可以在中选择,其余类似。能用管道相连的两站之间的距离已经给定;如果两点之间没有连线,则表示这两点之间不能铺设管道。要求选择一条由到的管道铺设路线,使总距离最短。

可以看出,这是一个多阶段决策问题:从到可以分为6个阶段。从出发到或为第一阶段,这时有两个选择:走到或走到,若我们选择走到的决策,则就是下一个阶段的起始点。在下一阶段,我们从点出发,有一个可供选择的决策集合。很明显,前面各阶段的决策如何选择,直接影响着其余各阶段的行进路线。我们的目的就是在每个阶段选择一个决策,使由它们决定的总路程最短。
工厂生产某种产品,每单位的成本为(千元),每次开工的固定成本为(千元),工厂每季度的最大生产能力为(千件)。经调查,市场对该产品的需求量第一、二、三、四季度分别为(单位)。如果工厂在第一、二季度将全年的需求都生产出来,自然可以降低成本(少付固定成本费),但是对于第三、四季度才能上市的产品需付存储费,每季每单位产品的存储费为
(千元)。还规定年初和年末这种产品均无库存。试制订一个生产计划,即安排每个季度的产量,使一年的总费用(生产成本和存储费)最少。
这是一个明显的多阶段问题,可以按照计划时间自然划分阶段。
第二节动态规划问题的基本要素和最优化原理
虽然动态规划模型一般不存在一个统一的表达式,但是,经过对问题的进一步分析,可以归结为一个固定的框架。
§ 动态规划模型的基本要素
一个多阶段决策过程最优化问题的动态规划模型通常包含以下要素:
阶段
阶段是对整个过程的自然划分。通常根据时间顺序或空间特征来划分阶段,以便按阶段的次序解优化问题。描述阶段的变量称为阶段变量,常用表示。,=1,2,…,6。
状态
状态表示每个阶段开始时过程所处的自然状况或客观条件