动态剡 本章内容重点 √多阶段决策过程的录优化 √动态规划的基本概念和基本原理 √动态规划方法的基本步栗 √动态规划方油应用举例
动态规划 本章内容重点 ✓多阶段决策过程的最优化 ✓动态规划的基本概念和基本原理 ✓动态规划方法的基本步骤 ✓动态规划方法应用举例
动态视 动态规划是解决多阶段决簟过程最优化的一种数学方 法。1951年美国数学家贝尔曼等人根据一类多阶段决策问 题的特点,把多阶段决簟闷題变换为一糸列互相联糸的 阶段闷题,然后逐个加以解决。贝尔曼的《动态规划》于 1957年出版。 动态规划方油与“时间”头糸很密切,随着时间过程 的发展而决定各肘段的决簟,产生一个决簟序列,这就是 “动态”的意思。然而它也可以处理与肘问无关的静态问 题,只要在问题中人为地引入“附段”因素,就可以将其 转化为一个多阶段决簟问题。在本章中将介绍这种处理方 法
动态规划 动态规划是解决多阶段决策过程最优化的一种数学方 法。1951年美国数学家贝尔曼等人根据一类多阶段决策问 题的特点，把多阶段决策问题变换为一系列互相联系的单 阶段问题，然后逐个加以解决。贝尔曼的《动态规划》于 1957年出版。 动态规划方法与“时间”关系很密切，随着时间过程 的发展而决定各时段的决策，产生一个决策序列，这就是 “动态”的意思。然而它也可以处理与时间无关的静态问 题，只要在问题中人为地引入“时段”因素，就可以将其 转化为一个多阶段决策问题。在本章中将介绍这种处理方 法
动态视 所谓多阶段决策闷题是指这样的决问题:其过程可分 为若干个相互联的阶段,每一阶段都对应着一组可供选择 的决策,每一决簟的选定即依赖于当前面临的状态,又影 响以后总体的效果。当每一阶段的决簟选定以后,就构成 个决策序列,称为一个簟略,它对应着一个确定的效果。 多阶段决策问题就是寻找使此效果录好的策略。 决戴决簟2 决Uk 决策Un 状态醉段1犬态醉段2状态找态醉段k状态状态醉段n状毒 3 k k+1 n n+1 2
动态规划 所谓多阶段决策问题是指这样的决策问题:其过程可分 为若干个相互联的阶段，每一阶段都对应着一组可供选择 的决策，每一决策的选定即依赖于当前面临的状态，又影 响以后总体的效果。当每一阶段的决策选定以后，就构成 一个决策序列，称为一个策略，它对应着一个确定的效果。 多阶段决策问题就是寻找使此效果最好的策略。 状态 x1 阶段1 T1 决策u1 状态 x2 决策u2 阶段2 T2 状态 x3 ... 状态 xk 决策uk 阶段k Tk 状态 xk+1 ... 状态 xn 决策un 阶段n Tn 状态 xn+1
多阶殷决策间题 工厂生产过程:由于市场需求是一随着肘间而变化的因素, 因此,为了取得金年录佳经济效益,就要在金年的生产过 程中,遜月或者逐季度地根据庠存和需求情况决定生产计 划安排。 设备更新闷题:一般企业用于生产活动的设备,刚买来时故 障少,经济效益高,即使迸行转让,处理价值也高,随着 使用年限的增加,就会還渐`为故障多,维修费用增加, 可正常使用的工肘减少,加工质量下降,经济效益差,并 且,使用的年限越长、处狸价值也越低,自然,如果卖去 旧的买新的,还需要付出更新费、因此就需要综合权衡决 定设备的使用年限,使恿的经济效益最好
多阶段决策问题 工厂生产过程:由于市场需求是一随着时间而变化的因素， 因此，为了取得全年最佳经济效益，就要在全年的生产过 程中，逐月或者逐季度地根据库存和需求情况决定生产计 划安排。 设备更新问题:一般企业用于生产活动的设备，刚买来时故 障少，经济效益高，即使进行转让，处理价值也高，随着 使用年限的增加，就会逐渐变为故障多，维修费用增加， 可正常使用的工时减少，加工质量下降，经济效益差，并 且，使用的年限越长、处理价值也越低，自然，如果卖去 旧的买新的，还需要付出更新费．因此就需要综合权衡决 定设备的使用年限，使总的经济效益最好
多阶殷决策间题 连生产过程的控制问题:一般化工生产过程中,常包含一 糸列完成生产过程的设备,前一工序设备的輪出则是后一 工序设备的輪入,因此应该如何根据各工序的运行工况, 控制生产过程中各设备的輪入和輪出,以使总产量最大。 资源分配问题:资源分配问题属于静态问题。如某工业部门 或公司,拟对其所属企业进行稀缺资源分配,为此需要制 定出收益录大的资源分配方。这种问题原本要求一次确 定出对各企业的资源分配量,它与肘间因素无关,不属动 态决策,但是,我们可以人为地规定一个资憑分配的阶段 和顺序,从而使其变成一个多阶段决策问题
多阶段决策问题 连续生产过程的控制问题:一般化工生产过程中，常包含一 系列完成生产过程的设备，前一工序设备的输出则是后一 工序设备的输入，因此应该如何根据各工序的运行工况， 控制生产过程中各设备的输入和输出，以使总产量最大。 资源分配问题:资源分配问题属于静态问题。如某工业部门 或公司，拟对其所属企业进行稀缺资源分配，为此需要制 定出收益最大的资源分配方案。这种问题原本要求一次确 定出对各企业的资源分配量，它与时间因素无关，不属动 态决策，但是，我们可以人为地规定一个资源分配的阶段 和顺序，从而使其变成一个多阶段决策问题
动态剡范解的特点 √通常多阶段决簟过程的发畏是通过状态的一糸列变换来 实现的。 一般情况下,糸统在某个阶段的状态转移除与本 阶段的状态和决箓有关外,还可能与糸统过去经历的 状态和决策有关。 √烫合于用动态规划方法求解的只是一类特殊的多阶段决 策问题,即具有“无后效性”的多阶段决策过程。 无后效性(又称马尔柯夫性)是指糸统从某个阶段往 后的发長,仅由本阶段所处的状态及其往后的决策所 决定,与糸统以前经历的状态和决簟(历史)无关
动态规划求解的特点 ✓ 通常多阶段决策过程的发展是通过状态的一系列变换来 实现的。 一般情况下，系统在某个阶段的状态转移除与本 阶段的状态和决策有关外，还可能与系统过去经历的 状态和决策有关。 ✓ 适合于用动态规划方法求解的只是一类特殊的多阶段决 策问题，即具有“无后效性”的多阶段决策过程。 无后效性(又称马尔柯夫性)是指系统从某个阶段往 后的发展，仅由本阶段所处的状态及其往后的决策所 决定，与系统以前经历的状态和决策(历史)无关
动态视州问氩实俐 例6-1给定一个线路网络,要从A向F铺设一条輪油管, 各点间连线上的数字表示距离,问应选择什么路线,可 使总距离最短? 2 E1人3 B,K3 E G B
A 动态规划问题实例 C4 C2 D3 D2 G B2 B1 C1 C3 D1 E3 E2 E1 F2 F1 5 3 1 3 6 8 7 6 6 8 3 5 3 3 8 4 2 2 1 2 3 3 3 5 5 2 6 6 4 3 例6-1 给定一个线路网络，要从A向F铺设一条输油管， 各点间连线上的数字表示距离，问应选择什么路线，可 使总距离最短？
动态视
A 动态规划C4 C2 D 3 D 2 G B 2 B 1 C 1 C 3 D 1 E 3 E 2 E 1 F 2 F 1 53 1 36 8 7 6 6 8 353384 2212 3 3 3 5 52 6 6 4 3
动态說剡的基本食 1.阶段与阶段变量 为了便于求解和表示决策及过程的发畏顺序, 而把所给问题恰当地划分为若干个相互联糸又有 区别的子闷题,称为多段决簟问题的阶段。 描述阶段的变量称为阶段变量,常用k表示。 阶段的划分,一般是根据肘间和空间的自然特征 来进行的,但要便于问题转化为多阶段决策
1.阶段与阶段变量 为了便于求解和表示决策及过程的发展顺序， 而把所给问题恰当地划分为若干个相互联系又有 区别的子问题，称为多段决策问题的阶段。 描述阶段的变量称为阶段变量，常用k表示。 阶段的划分，一般是根据时间和空间的自然特征 来进行的，但要便于问题转化为多阶段决策。 动态规划的基本概念
动态說剡的基本食 2状态、状态变量与可能状态集 描述事物(或糸统)在某特定的肘间与空间城中所处 位置及运动特征的量,称为状态。反映状态化的量叫 做状态变量。状态变量包含在给定的阶段上确定金部允 许决簟所需要的信息。 每个阶段的状态可分为初始状态和终止状态,或称 輪入状态和输出状态,阶段k的初始状态记作Sk,终止状 态记为Sk1通霈定义阶段的状态即指其初始状态。 般状态变量的取值有一定的范圄或允许集合,称 为可能状态集,或可达状态集。可能状态集实际上是关 于状态的约柬条件。通常可能状态集用相应阶段状态Sk 的火写字母Sk表示,Sk∈Sk
动态规划的基本概念 2.状态、状态变量与可能状态集 描述事物(或系统)在某特定的时间与空间域中所处 位置及运动特征的量，称为状态。反映状态变化的量叫 做状态变量。状态变量包含在给定的阶段上确定全部允 许决策所需要的信息。 每个阶段的状态可分为初始状态和终止状态，或称 输入状态和输出状态，阶段k的初始状态记作sk，终止状 态记为sk+1。通常定义阶段的状态即指其初始状态。 一般状态变量的取值有一定的范围或允许集合，称 为可能状态集，或可达状态集。可能状态集实际上是关 于状态的约束条件。通常可能状态集用相应阶段状态sk 的大写字母Sk表示，sk∈Sk