《运筹学》第五章 动态规划

第五章动态规划 本章内容重点 多阶段决策过程的最优化 动态规划的基本概念和基本原理

第五章 动态规划 多阶段决策过程的最优化 动态规划的基本概念和基本原理 本章内容重点

动态规划是解决多阶段决策过程最 优化问题的一种方法。由美国数学家贝尔曼 ( Ballman)等人在20世纪50年代提出。他 们针对多阶段决策问题的特点,提出了解决 这类问题的“最优化原理”,并成功地解决 了生产管理、工程技术等方面的许多实际 问题

动态规划是解决多阶段决策过程最 优化问题的一种方法。由美国数学家贝尔曼 （Ballman）等人在20世纪50年代提出。他 们针对多阶段决策问题的特点，提出了解决 这类问题的“最优化原理”，并成功地解决 了生产管理 、 工程技术等方面的许多实际 问题

动親划的基本原理 多阶段决策过程最优化 多阶段决策过程是指这样一类特殊的活 动过程,他们可以按时间顺序分解成若干相 互联系的阶段,在每个阶段都要做出决策, 全部过程的决策是一个决策序列,所以多阶 段决策问题也称为序贯决策问题

动态规划的基本原理 多阶段决策过程最优化 多阶段决策过程是指这样一类特殊的活 动过程，他们可以按时间顺序分解成若干相 互联系的阶段，在每个阶段都要做出决策， 全部过程的决策是一个决策序列，所以多阶 段决策问题也称为序贯决策问题

决草1决草U2 决策l 决草un 状态,状淹阶段2状态状阶段状,状产阶K/状态 1 23 1 Xn Tn

状态 x1 阶段1 T1 决策u1 状态 x2 决策u2 阶段2 T2 状态 x3 ...状态 xk 决策uk 阶段k Tk 状态 xk+1 ...状态 xn 决策un 阶段n Tn 状态 xn+1

多阶段决策问题举例 属于多阶段决策类的问题很多,例如: 1)工厂生产过程:由于市场需求是一随着时 间而变化的因素,因此,为了取得全年最佳经济 效益,就要在全年的生产过程中,逐月或者逐季 度地根据库存和需求情况决定生产计划安排。显 然,可以把每个月作为一个阶段,全年分为12个 阶段逐次决策

多阶段决策问题举例 属于多阶段决策类的问题很多，例如： 1)工厂生产过程：由于市场需求是一随着时 间而变化的因素，因此，为了取得全年最佳经济 效益，就要在全年的生产过程中，逐月或者逐季 度地根据库存和需求情况决定生产计划安排。显 然，可以把每个月作为一个阶段，全年分为12个 阶段逐次决策

2)设备更新问题:一般企业用于生产活动的设备, 刚买来时故障少,经济效益高,即使进行转让,处理 价值也高,随着使用年限的增加,就会逐渐变为故障 多,维修费用增加,可正常使用的工时减少,加工质 量下降,经济效益差,并且,使用的年限越长、处理 价值也越低,自然,如果卖去旧的买新的,还需要付 出更新费.因此就需要综合权衡决定设备的使用年限, 使总的经济效益最好

2)设备更新问题：一般企业用于生产活动的设备， 刚买来时故障少，经济效益高，即使进行转让，处理 价值也高，随着使用年限的增加，就会逐渐变为故障 多，维修费用增加，可正常使用的工时减少，加工质 量下降，经济效益差，并且，使用的年限越长、处理 价值也越低，自然，如果卖去旧的买新的，还需要付 出更新费．因此就需要综合权衡决定设备的使用年限， 使总的经济效益最好

许多问题的发展过程都与时间因素有关。在这 类多阶段决策问题中,阶段的划分常取时间区 段来表示,并且各个阶段上的决策往往也与时 间因素有关。这就使它具有了“动态”的含义, 所以把处理这类动态问题的方法称为动态规划 方法

➢许多问题的发展过程都与时间因素有关。在这 类多阶段决策问题中，阶段的划分常取时间区 段来表示，并且各个阶段上的决策往往也与时 间因素有关。这就使它具有了“动态”的含义， 所以把处理这类动态问题的方法称为动态规划 方法

实际中尚有许多不包含时间因素的一类“静态” 决策问题,就其本质而言是一次决策问题,是 非动态决策问题,但是也可以人为地引入阶段 的概念当作多阶段决策问题,应用动态规划方 法加以解决

➢实际中尚有许多不包含时间因素的一类“静态” 决策问题，就其本质而言是一次决策问题，是 非动态决策问题，但是也可以人为地引入阶段 的概念当作多阶段决策问题，应用动态规划方 法加以解决

3)资源分配问题:便属于这类静态问题。如: 某工业部门或公司,拟对其所属企业进行稀缺资源 分配,为此需要制定出收益最大的资源分配方案 这种问题原本要求一次确定出对各企业的资源分配 量,它与时间因素无关,不属动态决策,但是,我 们可以人为地规定一个资源分配的阶段和顺序,从 而使其变成一个多阶段决策问题

3）资源分配问题：便属于这类静态问题。如： 某工业部门或公司，拟对其所属企业进行稀缺资源 分配，为此需要制定出收益最大的资源分配方案。 这种问题原本要求一次确定出对各企业的资源分配 量，它与时间因素无关，不属动态决策，但是，我 们可以人为地规定一个资源分配的阶段和顺序，从 而使其变成一个多阶段决策问题

4)运输网络问题: 12 11

4）运输网络问题：