5动态规划.doc

- 104 - 第五章动态规划【教学内容】动态规划问题,动态规划问题的基本要素和最优化原理,动态规划应用,用 LINGO 软件求解动态规划问题。【教学要求】要求学生掌握什么是多阶段决策过程、动态规划的基本概念、动态规划的基本原理及基本方程, 掌握静态规划怎样转化为动态规划来解, 学会分析解决动态规划的问题的方法并用 LINGO 软件求解。【教学重点】多阶段决策过程、动态规划的基本概念、动态规划的基本原理及基本方程, 动态规划应用,用 LINGO 软件求解动态规划问题。【教学难点】动态规划的基本概念、动态规划的基本原理及基本方程,动态规划应用。【教材内容及教学过程】动态规划(Dynamic Programming) 是求解多阶段决策过程最优化的数学方法。 1951 年, 美国数学家 等人在研究多阶段决策过程的优化问题时, 提出了著名的最优化原理, 把多阶段过程转化为一系列单阶段问题, 逐个求解, 创立了解决这类过程优化问题的新方法——动态规划。 1957 年他的名著“ Dynamic Programming ”在普林斯顿大学出版,这是该领域的第一本著作。动态规划所研究的对象是多阶段决策问题。所谓多阶段决策问题是指一类活动过程,它可以分为若干个互相联系的阶段, 在每个阶段都需要做出决策。这个决策不仅决定这一阶段的效益,而且决定下一阶段的初始状态。每个阶段的决策确定以后,就得到一个决策序列, 称为策略。多阶段决策问题就是求一个策略,使各阶段的效益的和达到最优。虽然动态规划主要用于求解以时间划分阶段的动态过程的优化问题, 但是一些与时间无关的静态规划( 如线性规划、非线性规划), 只要人为地引进时间因素, 把它视为多阶段决策过程,也可以用动态规划方法方便地求解。动态规划问世以来, 在工程技术、经济管理、生产调度、最优控制, 以及军事等领域得到了广泛的应用。例如最短路线、库存管理、资源分配、生产调度、设备更新、排序、装载等问题, 用动态规划方法比用其它方法求解更为方便, 而且许多问题用动态规划方法去处理, 也比线性规划或非线性规划更有成效。- 105 - 第一节动态规划问题§ 多阶段决策问题我们将多阶段决策问题描述如下: 有一个系统, 可以分成若干个阶段, 任意一个阶段 k , 系统的状态可以用 kx 表示 kx( 可以是数量、向量、集合等) 。在每一阶段 k 的每一状态 kx 都有一个决策集合)( kkxQ ,在)( kkxQ 中选定一个决策)( kkkxQq?,状态 kx 就转移到新的状态),( 1kkkkqxTx??,并且得到效益),( kkkqxR 。我们的目的就是在每一个阶段都从它的决策集合中选择一个决策,使所有阶段的总效益),( kkk kqxR?达到最优。这样的多阶段决策问题称为动态规划, 表示它是一个多步最优化问题。前面介绍的线性规划、整数规划和目标规划都是静态规划。动态规划与线性规划、整数规划和目标规划不同之处还在于,一般动态规划没有一个统一的数学表达式。§ 动态规划问题举例例 . 1如图 . 1 ,给定一个网络,从 0A 点铺设一条煤气管道到 6A 点,必须经过五个中间站, 第一站可以在 1 1 , A B 中选择, 其余类似。能用管道相连的两站之间的距离已经给定; 如果两点之间没有连线, 则表示这两点之间不能铺设管道。要求选择一条由 0A 到6A 的管道铺设路线,使总距离最短。可以看出, 这是一个多阶段决策问题:从0A 到6A 可以分为 6 个阶段。从0A 出发到 1A 或 1B 为第一阶段, 这时有两个选择: 走到 1A 或走到 1B , 若我们选择走到的 1A 决策,则1A 就是下一个阶段的起始点。在下一阶段,我们从 1A 点出发,有一个可供选择的决策集合?? 222,,CBA 。很明显,前面各阶段的决策如何选择,直接影响着其余各阶段的行进路线。我们的目的就是在每个阶段选择一个决策,使由它们决定的总路程最短。例 . 2 工厂生产某种产品, 每单位的成本为 a ( 千元), 每次开工的固定成本为 b (千元) ,工厂每季度的最大生产能力为 a ( 千件) 。经调查,市场对该产品的需求量第一、二、三、四季度分别为 4321,,,dddd ( 单位) 。如果工厂在第一、二季度将全年的需求都生产出来, 自然可以降低成本( 少付固定成本费), 但是对于第三、四季度才能上市的产品需付存储费, 每季每单位产品的存储费为 r ( 千元)。还规定年初和年末这种产品均无库存。试制订一 0A 1A 1B 2A 2B 2C 2D 3A 3B 3C 4A 4B 4C 5A 5B 6A5 3 2368716 68353384 221233 355266 4 3 图 . 1-