北京理工大学：《运筹学》课程电子教案（PPT教学课件）第五章 动态规划

运券学课件 占置 蓝面再是量 证 三看飞 制作:北京理工大学吴祈泉等

运筹学课件 第五章 动态规划 制作：北京理工大学 吴祈宗等

第五章动态规为 本章内容重点 多阶段决策过程的最优化 动态规划的基本概念和基本原理 动态规划方法的基本步骤 动态规划方法应用举例

2 第五章 动态规划 多阶段决策过程的最优化 动态规划的基本概念和基本原理 动态规划方法的基本步骤 动态规划方法应用举例 本章内容重点

1.多阶段决敢程的龙化 多阶段决策问题 MMulti-Stage decision process) 多阶段决草过程特点 决蕈u1决蕈U2 决 决un 状态 阶段1状变 阶段2态状态w即米态状阶段n米 →● Xk Xk+1 m+1 Tn

一 、多阶段决策问题 (Multi-Stage decision process) 多阶段决策过程特点: 状态 x1 阶段1 T1 决策u1 状态 x2 决策u2 阶段2 T2 状态 x3 ...状态 xk 决策uk 阶段k Tk 状态 xk+1 ...状态 xn 决策un 阶段n Tn 状态 xn+1 1.多阶段决策过程的最优化

1.多阶段决敢过程的最化 动态规划方法与“时间”关系很 密切,随着时间过程的发展而决定各 时段的决策,产生一个决策序列,这 就是“动态”的意思。然而它也可以 处理与时间无关的静态问题,只要在 向题中人为地引入“时段”因素,就 可以将其转化为一个多阶段决策问题。 在本章中将介绍这种处理方法

1.多阶段决策过程的最优化 动态规划方法与“时间”关系很 密切，随着时间过程的发展而决定各 时段的决策，产生一个决策序列，这 就是“动态”的意思。然而它也可以 处理与时间无关的静态问题，只要在 问题中人为地引入“时段”因素，就 可以将其转化为一个多阶段决策问题。 在本章中将介绍这种处理方法

身要阶段来求过程的艇戏化 二、多阶段决策问题举例 属于多阶段决策类的问题很多 例如: 1)工厂生产过程:由于市场需 求是一随着时间而变化的因素。因 此,为了取得全年最佳经济效益, 就要在全年的生产过程中,遝月或 者遝季度地根据库存和姗求情况决 定生产讣划安排

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

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

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

身要阶段来求过程的艇戏化 3)连续生产过程的控制问题:一般化 工生产过程中,常包含一系列完成生 产过程的设备,前一工序设备的输出 则是后一工序设备的输入,因此,应 该如何根据各工序的运行工况,控制 生产过程中各设备的输入和输出,以 使总产量最大

7 1.多阶段决策过程的最优化 3)连续生产过程的控制问题：一般化 工生产过程中，常包含一系列完成生 产过程的设备，前一工序设备的输出 则是后一工序设备的输入，因此，应 该如何根据各工序的运行工况，控制 生产过程中各设备的输入和输出，以 使总产量最大

1.多阶段决敢过程的录化 许多问题的发展过程都与时间因素有关。 在这类多阶段决策问题中,阶段的划分 常取时间区段来表示,并且各个阶段上 的决策往往也与时间因素有关。这就使 它具有了“动态”的含义,所以把处理 这类动态问题的方法称为动态规划方法。 实际中尚有许多不包含时间因素的一类 静态”决策问题,就其本质而言是 次决策问题,是非动态决策问题,但是 也可以人为地引入阶段的概念当作多阶 段决策问题,应用动态规划方法加以解 决

1.多阶段决策过程的最优化 ➢许多问题的发展过程都与时间因素有关。 在这类多阶段决策问题中，阶段的划分 常取时间区段来表示，并且各个阶段上 的决策往往也与时间因素有关。这就使 它具有了“动态”的含义，所以把处理 这类动态问题的方法称为动态规划方法。 ➢实际中尚有许多不包含时间因素的一类 “静态”决策问题，就其本质而言是一 次决策问题，是非动态决策问题，但是 也可以人为地引入阶段的概念当作多阶 段决策问题，应用动态规划方法加以解 决

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

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

身要阶来求过程的艇戏花 5)运输网络问题:如图5-所示的运 输网络,点间连线上的数字表示两地 距离(也可是运费、时间等),要求从 f(k)至v的最短路线。 这种运输网络问题也是静态决策 乌问题。但是,按照网络中点的分布 可以把它分为4个阶段,而作为多阶 段决策问题来研究

10 1.多阶段决策过程的最优化 5）运输网络问题：如图5-1所示的运 输网络，点间连线上的数字表示两地 距离(也可是运费、时间等)，要求从 fk (sk )至v10的最短路线。 这种运输网络问题也是静态决策 问题。但是，按照网络中点的分布， 可以把它分为4个阶段，而作为多阶 段决策问题来研究