动规 Dynamic Programming(DP 第七章 动态规划
1 动态规划 Dynamic Programming（DP） 第七章 动态规划
动规划 Dynamie Programming(DP 动态规划—— Dynamic Programming 引 动态规划作为运筹学的一个重要分支是解决多阶段决策过程最优化 的一种非常有效的方法。1951年,美国数学家贝尔曼(R Bellman)等人,根据一类多阶段决策问题的特点,把多阶段决策 问题变换为一系列相互联系的单阶段决策问题,然后分阶段逐个加 以解决。贝尔曼等人在研究和解决了大量实际问题之后,提出了解 决这类问题的—所谓“最优性原理”,通常称为“贝尔曼最优化 原理”,从而创建了解决最优化问题的一种新的方法——动态规 划—( Dynamic Programming)。贝尔曼的名著《动态规划》 于1957年出版,这成了动态规划的第一本著作
2 动态规划 Dynamic Programming（DP） 动态规划——Dynamic Programming 引言 动态规划作为运筹学的一个重要分支是解决多阶段决策过程最优化 的一种非常有效的方法。1951年，美国数学家贝尔曼（ R . Bellman ）等人，根据一类多阶段决策问题的特点，把多阶段决策 问题变换为一系列相互联系的单阶段决策问题，然后分阶段逐个加 以解决。贝尔曼等人在研究和解决了大量实际问题之后，提出了解 决这类问题的——所谓“最优性原理”，通常称为“贝尔曼最优化 原理”，从而创建了解决最优化问题的一种新的方法 —— 动态规 划 ——（Dynamic Programming ）。贝尔曼的名著《动态规划》 于1957年出版，这成了动态规划的第一本著作
动规划 Dynamie Programming(DP 动态规划—— Dynamic Programming 引 动态规划的方法,在工程技术、企业管理、工农业生产及军事 等部门中有着广泛的应用,并且获得了显著的效果。在经济管理方 面,动态规划可以用来解决最优路径问题、资源分配问题、生产调 度问题、库存问题、装载问题、排序问题、设备更新问题、生产过 程最优控制问题等等,他是现代企业管理中的一种重要的决策方法。 许多实际问题采用动态规划方法去处理,常比线性规划或非线 性规划更加有效。特别对于离散性的问题,由于解析数学无法施展 其术,而动态规划的方法就成为一种非常有效的工具
3 动态规划 Dynamic Programming（DP） 动态规划——Dynamic Programming 引言 动态规划的方法，在工程技术、企业管理、工农业生产及军事 等部门中有着广泛的应用，并且获得了显著的效果。在经济管理方 面，动态规划可以用来解决最优路径问题、资源分配问题、生产调 度问题、库存问题、装载问题、排序问题、设备更新问题、生产过 程最优控制问题等等，他是现代企业管理中的一种重要的决策方法。 许多实际问题采用动态规划方法去处理，常比线性规划或非线 性规划更加有效。特别对于离散性的问题，由于解析数学无法施展 其术，而动态规划的方法就成为一种非常有效的工具
动规划 Dynamie Programming(DP 动态规划—— Dynamic Programming 引 应特别指出的是,动态规划是解决某一类问题的一种方法,是 分析问题的一种途径,而不是一种特殊算法(如线性规划是一种算 法)。因而,它不象线性规划那样有一个标准的数学表达式和明确 定义的一组规则,而必须对具体问题进行具体分析处理。因此,在 学习动态规划时,除了对基本概念和方法正确地理解外,应以丰富 的想象力去建立模型,用创造性的技巧去求解。正如贝尔曼本人所 说:“由于动态规划的最优化原理仅仅是一种基本原理,正是它的 某种不确定性为你提供了发挥你创造性思维的巨大空间 本部分我们主要研究离散决策过程,介绍动态规划的基本概念、 理论和方法,在通过一些典型的应用问题来说明它的应用
4 动态规划 Dynamic Programming（DP） 动态规划——Dynamic Programming 引言 应特别指出的是，动态规划是解决某一类问题的一种方法，是 分析问题的一种途径，而不是一种特殊算法（如线性规划是一种算 法）。因而，它不象线性规划那样有一个标准的数学表达式和明确 定义的一组规则，而必须对具体问题进行具体分析处理。因此，在 学习动态规划时，除了对基本概念和方法正确地理解外，应以丰富 的想象力去建立模型，用创造性的技巧去求解。正如贝尔曼本人所 说：“由于动态规划的最优化原理仅仅是一种基本原理，正是它的 某种不确定性为你提供了发挥你创造性思维的巨大空间 ! 本部分我们主要研究离散决策过程，介绍动态规划的基本概念、 理论和方法，在通过一些典型的应用问题来说明它的应用
动规 Dynamic Programming(DP 动态规划 Dynamic Programming 多阶段决策过程的最优化 多阶段决策过程: 整个决策过程可按时间或空间顺序分解成若干相互联系的阶段 每一阶段都需作出决策,全部过程的决策是一个决策序列。 多阶段决策过程最优化的目标: 达到整个活动过程的总体效果最优,而非各单个阶段最优的简 单总和。 Page199例1、2、3 请看如下典例—最短路线问题
5 动态规划 Dynamic Programming（DP） 动态规划——Dynamic Programming 多阶段决策过程的最优化 多阶段决策过程： 整个决策过程可按时间或空间顺序分解成若干相互联系的阶段， 每一阶段都需作出决策，全部过程的决策是一个决策序列。 多阶段决策过程最优化的目标： 达到整个活动过程的总体效果最优，而非各单个阶段最优的简 单总和。 Page 199 例1、2、3 请看如下典例——最短路线问题
动规 Dynamic Programming(DP 动态规划—— Dynamic Programming 动态规划的基本概念和基本原理 请看如下典例—最短路线问题
6 动态规划 Dynamic Programming（DP） 动态规划——Dynamic Programming 动态规划的基本概念和基本原理 请看如下典例——最短路线问题
动规划 Dynamie Programming(DP 动态规划—— Dynamic Programming 动态规划的基本概念和基本原理 7该点到G点的最短距离 2 13 3 B1)3 18 5 16 8 12 第一阶段⊥第二阶段1第三阶段⊥第四阶段1第五阶段1第六阶段7
7 动态规划 Dynamic Programming（DP） 动态规划——Dynamic Programming 动态规划的基本概念和基本原理 B1 A C3 F2 F1 E3 E2 E1 D3 D2 D1 C4 C2 C1 B2 G 第一阶段 第二阶段 第三阶段 第四阶段 第五阶段 第六阶段 5 3 1 3 6 8 7 6 6 8 3 5 3 4 2 1 3 8 2 2 3 3 3 5 5 2 6 6 4 3 4 3 7 5 9 7 6 8 13 10 9 12 13 16 18 该点到G点的最短距离
动规划 Dynamie Programming(DP 动态规划 Dynamic Programming 动态规划的基本概念和基本原理 1、阶段( stage) 对整个决策过程的自然划分,通常根据时间顺序或空间特征来 划分阶段,以便按阶段的次序逐段解决整个过程的优化问题。阶段 变量通常用k表示(k=1,2,3,…,n)。 2、状态( state) 每个阶段开始时过程所处的自然状况或客观条件。它应能描述 过程的特征并具有“无后效性”,即当前阶段状态给定时,这个阶 段以后过程的演变与该阶段以前各阶段的状态无关 状态变量—sk( state variable) 状态集合—Sk( set of admissible states)
8 动态规划 Dynamic Programming（DP） 动态规划——Dynamic Programming 动态规划的基本概念和基本原理 1、阶段（stage） 对整个决策过程的自然划分，通常根据时间顺序或空间特征来 划分阶段，以便按阶段的次序逐段解决整个过程的优化问题。阶段 变量通常用k表示（k = 1，2，3，…，n）。 2、状态（state） 每个阶段开始时过程所处的自然状况或客观条件。它应能描述 过程的特征并具有“无后效性”，即当前阶段状态给定时，这个阶 段以后过程的演变与该阶段以前各阶段的状态无关。 状态变量 —— sk（state variable） 状态集合 —— Sk（set of admissible states）
动规划 Dynamie Programming(DP 动态规划—— Dynamic Programming 动态规划的基本概念和基本原理 3、决策( decision) 当一个阶段的状态确定后,可以作出不同的决定或选择 从而演变到下一阶段的某个状态,这种决定或选择称为决策。 决策变量—uk(sk)( decision variable)简记为uk 决策集合 k( Sk)(set of admissible decision 4、策略( policy) 组有序的决策序列构成一个策略,从第k阶段至第n阶段 的一个策略称为后部子策略记为p,n→(uk,uk+1,…,un)
9 动态规划 Dynamic Programming（DP） 动态规划——Dynamic Programming 动态规划的基本概念和基本原理 3、决策（decision） 当一个阶段的状态确定后，可以作出不同的决定或选择， 从而演变到下一阶段的某个状态，这种决定或选择称为决策。 决策变量 —— uk（sk） （decision variable）简记为 uk 决策集合 —— Dk（sk）（set of admissible decision） 4、策略（policy） 一组有序的决策序列构成一个策略，从第k阶段至第n阶段 的一个策略称为后部子策略记为 pk，n →（uk，uk+1，…，un）
动规划 Dynamie Programming(DP 动态规划 Dynamic Programming 动态规划的基本概念和基本原理 5、状态转移方程( equation of state transition) 在确定型多阶段决策过程中,一旦某阶段的状态和决策为已知, 下一阶段的状态便完全确定,用状态转移方程反映这种状态间的演 变规律,写作: Sk+1= Tk(Sk, uk) k=1, 2,...,n 6、阶段指标值( objective value in a stage) 衡量在一个阶段某个状态下各决策所对应的某种数量指标或效 果,通常表示为vk(sk,uk)。 10
10 动态规划 Dynamic Programming（DP） 动态规划——Dynamic Programming 动态规划的基本概念和基本原理 5、状态转移方程（equation of state transition） 在确定型多阶段决策过程中，一旦某阶段的状态和决策为已知， 下一阶段的 状态便完全确定，用状态转移方程反映这种状态间的演 变规律，写作： sk+1 = Tk（sk，uk） k =1，2，…，n 6、阶段指标值（objective value in a stage） 衡量在一个阶段某个状态下各决策所对应的某种数量指标或效 果，通常表示为 vk（sk，uk）