• / 48
  • 下载费用:10 金币  

第十章动态规划

关 键 词:
第十章动态规划
资源描述:
Copyright © Li Yuxin. All Rights Reserved 第十章 动态规划 • §1 多阶段决策过程最优化问题举例 • §2 基本概念、基本方程与最优化原理 • §3 动态规划的应用(1) • §4 动态规划的应用(2) 1 Copyright © Li Yuxin. All Rights Reserved 2 动态规划是用来解决多阶段决策过程最优化的一种数 量方法。其特点在于,它可以把一个n 维决策问题变 换为几个一维最优化问题,从而一个一个地去解决。 动态规划 Copyright © Li Yuxin. All Rights Reserved 动态决策问题的特点 • 系统所处的状态和时刻是进行决策的重要因素 – 即在系统发展的不同时刻(或阶段)根据系统所处的 状态,不断地做出决策 • 找到不同时刻的最优决策以及整个过程的最优策略 • 需指出:动态规划是求解某类问题的一种方法,是 考察问题的一种途径,而不是一种算法。必须对具 体问题进行具体分析,运用动态规划的原理和方法 ,建立相应的模型,然后再用动态规划方法去求 解。 Copyright © Li Yuxin. All Rights Reserved 多阶段决策问题 • 是动态决策问题的一种特殊形式 • 在多阶段决策过程中,系统的动态过程可以按 照时间进程分为状态相互联系而又相互区别的 各个阶段 • 每个阶段都要进行决策,目的是使整个过程的 决策达到最优效果 12n  状态 决策 状态 决策 状态状态 决策 Copyright © Li Yuxin. All Rights Reserved 一、动态规划的基本概念 5 1 1、阶段:、阶段: 把一个问题的过程,恰当地分为若干个相互联系的把一个问题的过程,恰当地分为若干个相互联系的 阶段阶段,以便于按一定的次序去求解。,以便于按一定的次序去求解。 描述阶段的变量称为描述阶段的变量称为阶段变量阶段变量。阶段的划分,一般。阶段的划分,一般 是根据时间和空间的自然特征来进行的,但要便于问题是根据时间和空间的自然特征来进行的,但要便于问题 转化为多阶段决策。转化为多阶段决策。 2 2、状态:表示每个阶段开始所处的、状态:表示每个阶段开始所处的自然状况或客观条自然状况或客观条 件件。通常一个阶段有若干个状态,描述过程状态的变量。通常一个阶段有若干个状态,描述过程状态的变量 称为称为状态变量状态变量。。 年、月、 路段一个数、 一组数、 一个向量 状态变量的取值有一定的允许集合或范围,此集合状态变量的取值有一定的允许集合或范围,此集合 称为称为状态允许集合状态允许集合。。 Copyright © Li Yuxin. All Rights Reserved 6 3、决策:表示当过程处于某一阶段的某个状态时,可 以作出不同的决定,从而确定下一阶段的状态,这种 决定称为决策。 描述决策的变量,称为决策变量。决策变量是状态 变量的函数。可用一个数、一组数或一向量(多维情 形)来描述。 在实际问题中决策变量的取值往往在某一范围之内 ,此范围称为允许决策集合。 系统在某一阶段的状态转移不但与系统的当前的状态 和决策有关,而且还与系统过去的历史状态和决策有 关。 4、多阶段决策过程 可以在各个阶段进行决策,去控制过程发展的多段过 程; 其发展是通过一系列的状态转移来实现的; Copyright © Li Yuxin. All Rights Reserved 7 图示如下: 状态转移方程是确定 由一个状态到另一个 状态的演变过程。如 果第k阶段状态变量sk 的值、该阶段的决策 变量一经确定,第k+1 阶段状态变量sk+1的值 也就确定。 其状态转移方程如下(一般形式) 12 k  s1 u1 s2 u2 s3sk uk sk+1 能用动态规划方法求解的多阶段决策过程是一类 特殊的多阶段决策过程,即具有无后效性的多阶段 决策过程。 Copyright © Li Yuxin. All Rights Reserved 8 如果如果状态变量不能满足无后效性的要求,应适当地改状态变量不能满足无后效性的要求,应适当地改 变状态的定义或规定方法。变状态的定义或规定方法。 动态规划中能动态规划中能 处理的状态转移处理的状态转移 方程的形式。方程的形式。 状态状态具有无后效性的多阶段决策过程的状态转移方具有无后效性的多阶段决策过程的状态转移方 程如下程如下 无后效性无后效性( (马尔可夫性马尔可夫性) ) 如果 如果某阶段状态给定后,则在这个阶段以后过程某阶段状态给定后,则在这个阶段以后过程 的发展不受这个阶段以前各段状态的影响的发展不受这个阶段以前各段状态的影响;;过程的过过程的过 去历史只能通过当前的状态去影响它未来的发展去历史只能通过当前的状态去影响它未来的发展 构造构造动态规划模型时,要充分注意是否满足无后效性的动态规划模型时,要充分注意是否满足无后效性的 要求;要求; 状态变量要满足无后效性的要求; Copyright © Li Yuxin. All Rights Reserved 9 9 5 5、策略:是一个按顺序排列的决策组成的集合。在实、策略:是一个按顺序排列的决策组成的集合。在实 际问题中,可供选择的策略有一定的范围,称为际问题中,可供选择的策略有一定的范围,称为允许允许 策略集合策略集合。从允许策略集合中找出达到最优效果的策。从允许策略集合中找出达到最优效果的策 略称为略称为最优策略最优策略。。 6 6、状态转移方程:是确定过程由一个状态到另一个、状态转移方程:是确定过程由一个状态到另一个 状态的演变过程,描述了状态转移规律。状态的演变过程,描述了状态转移规律。 7 7、指标函数和最优值函数:用来衡量所实现过程优劣、指标函数和最优值函数:用来衡量所实现过程优劣 的一种数量指标的一种数量指标,称为,称为指标函数指标函数。指标函数的最优值。指标函数的最优值 ,称为,称为最优值函数最优值函数。在不同的问题中,指标函数的含。在不同的问题中,指标函数的含 义是不同的,它可能是距离、利润、成本、产量或资义是不同的,它可能是距离、利润、成本、产量或资 源消耗等。源消耗等。 动态规划模型的指标函数,应具有可分离性,并满动态规划模型的指标函数,应具有可分离性,并满 足足递推递推关系。关系。 Copyright © Li Yuxin. All Rights Reserved 1010 小结小结: : 方程方程 : :状态转移方程状态转移方程 概念概念 : : 阶段变量阶段变量 k k ﹑﹑状态变量状态变量 s sk k ﹑﹑决策变量决策变量 u uk k; ; 指标指标 : : 动态规划本质上动态规划本质上是一种多决策过程是一种多决策过程; ; 效益效益 指标函数形式指标函数形式: : 和、和、积积 无后效性无后效性 可递推可递推 Copyright © Li Yuxin. All Rights Reserved 11 解多阶段决策过程问题,求出 最优策略,即最优决策序列 f1(s1) 最优轨线,即执行最优策略时的状态序列 最优目标函数值 从 k 到终点最优策略 子策略的最优目标函数值 Copyright © Li Yuxin. All Rights Reserved 12 1 1、动态规划方法的关键在于、动态规划方法的关键在于正确地写出基本的递正确地写出基本的递 推关系式和恰当的边界条件(简称基本方程)推关系式和恰当的边界条件(简称基本方程)。。 • • 要要做到这一点,就必须将问题的过程分成几个相做到这一点,就必须将问题的过程分成几个相 互联系的阶段,恰当的选取状态变量和决策变量互联系的阶段,恰当的选取状态变量和决策变量 及定义最优值函数,从而把一个大问题转化成一及定义最优值函数,从而把一个大问题转化成一 组同类型的子问题,然后逐个求解组同类型的子问题,然后逐个求解。。 • • 即即从边界条件开始,逐段递推寻优,在每一个子从边界条件开始,逐段递推寻优,在每一个子 问题的求解中,均利用了它前面的子问题的最优问题的求解中,均利用了它前面的子问题的最优 化结果,依次进行,最后一个子问题所得的最优化结果,依次进行,最后一个子问题所得的最优 解,就是整个问题的最优解。解,就是整个问题的最优解。 二、动态规划的基本思想 Copyright © Li Yuxin. All Rights Reserved 13 2、在多阶段决策过程中,动态规划方法是既把当 前一段和未来一段分开,又把当前效益和未来效益结 合起来考虑的一种最优化方法。因此,每段决策的选 取是从全局来考虑的,与该段的最优选择答案一般是 不同的 最优化原理:作为整个过程的最优策略具有这样 的性质:无论过去的状态和决策如何,相对于前面的 决策所形成的状态而言,余下的决策序列必然构成最 优子策略。”也就是说,一个最优策略的子策略也是 最优的。 3 3、在求整个问题的最优策略时,由于初始状态、在求整个问题的最优策略时,由于初始状态 是已知的,而每段的决策都是该段状态的函数,故最是已知的,而每段的决策都是该段状态的函数,故最 优策略所经过的各段状态便可逐段变换得到,从而优策略所经过的各段状态便可逐段变换得到,从而确确 定最定最优优路线路线 Copyright © Li Yuxin. All Rights Reserved 14 三、三、建立动态规划模型的步骤建立动态规划模型的步骤 1 1、划分阶段、划分阶段 划分阶段是运用动态规划求解多阶段决策问题的第一划分阶段是运用动态规划求解多阶段决策问题的第一 步,在确定多阶段特性后,按时间或空间先后顺序,步,在确定多阶段特性后,按时间或空间先后顺序, 将过程划分为若干相互联系的阶段。对于静态问题要将过程划分为若干相互联系的阶段。对于静态问题要 人为地赋予人为地赋予““时间时间””概念,以便划分阶段。概念,以便划分阶段。 2 2、正确选择状态变量、正确选择状态变量 选择变量既要能确切描述过程演变又要满足无后效性选择变量既要能确切描述过程演变又要满足无后效性 ,而且各阶段状态变量的取值能够确定。一般地,状,而且各阶段状态变量的取值能够确定。一般地,状 态变量的选择是从过程演变的特点中寻找。态变量的选择是从过程演变的特点中寻找。 3 3、确定决策变量及允许决策集合、确定决策变量及允许决策集合 通常选择所求解问题的关键变量作为决策变量,同时通常选择所求解问题的关键变量作为决策变量,同时 要给出决策变量的取值范围,即确定允许决策集合。要给出决策变量的取值范围,即确定允许决策集合。 Copyright © Li Yuxin. All Rights Reserved 15 4 4、确定状态转移方程、确定状态转移方程 根据根据k k 阶段状态变量和决策变量,写出阶段状态变量和决策变量,写出 k k +1+1阶段状态变阶段状态变 量,状态转移方程应当具有递推关系。量,状态转移方程应当具有递推关系。 5 5、确定阶段指标函数和最优指标函数,建立动态规、确定阶段指标函数和最优指标函数,建立动态规 划基本方程划基本方程 阶段指标函数是指第阶段指标函数是指第k k 阶段的收益,最优指标函数阶段的收益,最优指标函数 是指从第是指从第k k 阶段状态出发到第阶段状态出发到第n n 阶段末所获得收益的阶段末所获得收益的 最优值,最后写出动态规划基本方程。最优值,最后写出动态规划基本方程。 以上五步是建立动态规划数学模型的一般步骤。由于以上五步是建立动态规划数学模型的一般步骤。由于 动态规划模型与线性规划模型不同,动态规划模型与线性规划模型不同,动态规划模型没有统动态规划模型没有统 一的模式,建模时必须根据具体问题具体分析一的模式,建模时必须根据具体问题具体分析,只有通过,只有通过 不断实践总结,才能较好掌握建模方法与技巧。不断实践总结,才能较好掌握建模方法与技巧。 Copyright © Li Yuxin. All Rights Reserved 四、动态规划问题典型应用 16 例例1 1、、从从 A A 地到地到 D D 地要铺设一条煤气管道地要铺设一条煤气管道, ,其中需其中需 经过两级中间站,两点之间的连线上的数字表示经过两级中间站,两点之间的连线上的数字表示 距离,如图所示。问应该选择什么路线,使总距距离,如图所示。问应该选择什么路线,使总距 离最短?离最短? A B1 B2 C1 C2 C3 D 2 4 3 3 3 3 2 1 1 1 4 1 、 最 短 路 径 问 题 Copyright © Li Yuxin. All Rights Reserved 17 解:整个计算过程分三个阶段,从最后一个阶段开 始。 第一阶段(C →D): C 有三条路线到终点D 。 A B1 B2 C1 C2 C3 D 2 4 3 3 3 3 2 1 1 1 4 D C1 C2 C3 显然有 f1 (C1 ) = 1 ; f1(C2 ) = 3 ; f1 (C3 ) = 4 Copyright © Li Yuxin. All Rights Reserved 18 d( B1,C1 ) + f1 (C1 ) 3+1 f2 ( B1 ) = min d( B1,C2 ) + f1 (C2 ) = min 3+3 d( B1,C3 ) + f1 (C3 ) 1+4 4 = min 6 = 4 5 第二阶段(B →C): B 到C 有六条路线。 A B1 B2 C1 C2 C3 D 2 4 3 3 3 3 2 1 1 1 4 D C1 C2 C3 B1 B2 (最短路线为B1→C1 →D) Copyright © Li Yuxin. All Rights Reserved 19 d( B2,C1 ) + f1 (C1 ) 2+1 f2 ( B2 ) = min d( B2,C2 ) + f1 (C2 ) = min 3+3 d( B2,C3 ) + f1 (C3 ) 1+4 3 = min 6 = 3 5 A B1 B2 C1 C2 C3 D 2 4 3 3 3 3 2 1 1 1 4 D C1 C2 C3 B1 B2 (最短路线为B2→C1 →D) Copyright © Li Yuxin. All Rights Reserved 20 第三阶段( A → B ): A 到B 有二条路线。 f3(A)1 = d(A, B1 )+ f2 ( B1 ) =2+4=6 f3 (A)2 = d(A, B2 )+ f2 ( B2 ) =4+3=7 ∴ f3 (A) = min = min{6,7}=6 d(A, B1 )+ f2 ( B1 ) d(A, B2 )+ f2 ( B2 ) (最短路线为A→B1→C1 →D) A B1 B2 C1 C2 C3 D 2 4 3 3 3 3 2 1 1 1 4 D C1 C2 C3 B1 B2 A Copyright © Li Yuxin. All Rights Reserved 21 A B1 B2 C1 C2 C3 D 2 4 3 3 3 3 2 1 1 1 4 D C1 C2 C3 B1 B2 A 最短路线为 A→B1→C1 →D 路长为 6 Copyright © Li Yuxin. All Rights Reserved 四、动态规划问题典型应用 22 现有现有数量为数量为 a a (万元)的资金,计划分配给(万元)的资金,计划分配给n n 个工厂个工厂, ,用于用于 扩大再生产。扩大再生产。 假设假设:: x x i i 为分配给第 为分配给第i i 个工厂的资金数量(万元)个工厂的资金数量(万元) ;; g gi i( (x xi i ) )为第为第i i 个工厂得到资金后提供的利润值(万元)。个工厂得到资金后提供的利润值(万元)。 问题问题是如何确定各工厂的资金数,使得总的利润为最大。是如何确定各工厂的资金数,使得总的利润为最大。 据此,有下式:据此,有下式: 2 、 投 资 分 配 问 题 Copyright © Li Yuxin. All Rights Reserved 2323 令:令: f fk k( (x x ) = ) = 以数量为以数量为x x 的资金分配给前的资金分配给前k k 个工厂,个工厂, 所得到的最大利润值。所得到的最大利润值。 用动态规划求解,就是求用动态规划求解,就是求 f fn n( (a a ) ) 的问题。的问题。 当当 k k =1 =1 时,时, f f1 1( (x x ) = ) = g g1 1( (x x ) ) ((因为只给一个工厂因为只给一个工厂 )) 当当1 1<< k k ≤≤ n n 时,其递推关系如下:时,其递推关系如下: 设:设:y y 为分给第为分给第k k 个工厂的资金(其中个工厂的资金(其中 0≤0≤y y ≤ ≤ x x )) ,此时还剩,此时还剩 x x -- y y (万元)的资金需要分配给前(万元)的资金需要分配给前 k k -1 -1 个工厂个工厂, ,如果采取最优策略,则得到的最大利润为如果采取最优策略,则得到的最大利润为 f f k k--1 1 ( (x x --y y) ,) ,因此总的利润为:因此总的利润为: g g k k( (y y ) ) ++ f f k k--1 1 ( ( x x--y y ) ) Copyright © Li Yuxin. All Rights Reserved 2424 如果如果a a 是以万元为资金分配单位,则式中的是以万元为资金分配单位,则式中的y y 只取非负整数只取非负整数0 0,,1 1,,2 2,,……,, x x 。上式可变为:。上式可变为: 所以,根据动态规划的最优化原理,有下式:所以,根据动态规划的最优化原理,有下式: Copyright © Li Yuxin. All Rights Reserved 25 例题例题:: 设设国家拨给国家拨给6060万元投资,供四个工厂扩建使用,每个万元投资,供四个工厂扩建使用,每个 工厂扩建后的利润与投资额的大小有关,投资后的利工厂扩建后的利润与投资额的大小有关,投资后的利 润函数如下表所示。润函数如下表所示。 投 资 利润 0102030405060 g1(x)0205065808585 g2(x)0204050556065 g3(x)0256085100110115 g4(x)0254050606570 解:依据题意,是要求解:依据题意,是要求 f f4 4( ( 6060) ) 。。 Copyright © Li Yuxin. All Rights Reserved 26 按顺序解法计算。按顺序解法计算。 第一阶段:求第一阶段:求 f f1 1( (x x ) )。显然有。显然有 f f1 1( (x x ) ) == g g1 1( (x x ) ),得到,得到 下表下表 投资 利润 0102030405060 f1(x) = g1(x) 0205065808585 最优策略0102030405060 第二阶段:求第二阶段:求 f f2 2( (x x ) )。此时需考虑第一、第二个工厂如。此时需考虑第一、第二个工厂如 何进行投资分配,以取得最大的总利润。何进行投资分配,以取得最大的总利润。 Copyright © Li Yuxin. All Rights Reserved 27 最优策略为(40,20),此时最大利润为120万元。 同理可求得其它 f2(x) 的值。 Copyright © Li Yuxin. All Rights Reserved 28 最优策略为(30,20),此时最大利润为105万元。 Copyright © Li Yuxin. All Rights Reserved 29 最优策略为(20,20),此时最大利润为90万元。 最优策略为(20,10),此时最大利润为70万元。 Copyright © Li Yuxin. All Rights Reserved 30 最优策略为(10,0)或( 0 , 10 ) ,此时最大利润 为20万元。 f2(0) =0。最优策略为(0,0),最大利润为0万元。 得到下表 最优策略为(20,0),此时最大利润为50万元。 Copyright © Li Yuxin. All Rights Reserved 31 投 资 利润 0102030405060 f2(x)020507090105120 最优策略(0,0 ) (10, 0) (0,1 0) (20, 0) (20, 10) (20,2 0) (30, 20) (40, 20) 第三阶段:求 f3(x)。此时需考虑第一、第二及第三个 工厂如何进行投资分配,以取得最大的总利润。 Copyright © Li Yuxin. All Rights Reserved 32 最优策略为(20,10,30),最大利润为155万元。 同理可求得其它 f3(x) 的值。得到下表 Copyright © Li Yuxin. All Rights Reserved 33 投 资 利润 0102030405060 f3(x)0256085110135155 最优 策略 (0,0, 0) (0,0, 10) (0,0,2 0) (0,0, 30) (20,0, 20) (20,0,3 0) (20,10, 30) 第四阶段:求 f4(60)。即问题的最优策略。 Copyright © Li Yuxin. All Rights Reserved 34 最优策略为(20,0,30,10),最大利润为160万元。 Copyright © Li Yuxin. All Rights Reserved 35 有一个徒步旅行者,其可携带物品重量的限度为有一个徒步旅行者,其可携带物品重量的限度为a a 公斤公斤 ,设有,设有 n n 种物品可供他选择装入包中。已知每种物品的重量种物品可供他选择装入包中。已知每种物品的重量 及使用价值(作用),问此人应如何选择携带的物品(各几及使用价值(作用),问此人应如何选择携带的物品(各几 件),使所起作用(使用价值)最大?件),使所起作用(使用价值)最大? 物品物品 1 21 2 …… j j …… n n 重量(公斤重量(公斤/ /件)件) a a1 1 a a 2 2 … … a a j j … … a an n 每件使用价值每件使用价值 c c1 1 c c 2 2 … … c c j j … … c cn n 这就是背包问题。类似的还有工厂里的下料问题、运输中的 货物装载问题、人造卫星内的物品装载问题等。 四、动态规划问题典型应用 3 、 背 包 问 题 Copyright © Li Yuxin. All Rights Reserved 36 设设 x x j j 为第为第j j 种物品的装件数(非负整数)则问题的数种物品的装件数(非负整数)则问题的数 学模型如下:学模型如下: 用动态规划方法求解,令用动态规划方法求解,令 f f k k (y(y) ) = = 总重量不超过总重量不超过 y y 公斤,包中只装有前公斤,包中只装有前k k 种种 物品时的最大使用价值。物品时的最大使用价值。 其中其中 y y ≥0 ≥0,, k k ==1,2, …, 1,2, …, n n 。。所以问题就是求所以问题就是求 f fn n (a)(a) Copyright © Li Yuxin. All Rights Reserved 37 其递推关系式为: 当 k=1 时,有: Copyright © Li Yuxin. All Rights Reserved 38 例题:求下面背包问题的最优解例题:求下面背包问题的最优解 物品 1 2 3 重量(公斤) 3 2 5 使用价值 8 5 12 解:a=5 ,问题是求 f3(5) Copyright © Li Yuxin. All Rights Reserved 39 Copyright © Li Yuxin. All Rights Reserved 40 Copyright © Li Yuxin. All Rights Reserved 41 Copyright © Li Yuxin. All Rights Reserved 42 Copyright © Li Yuxin. All Rights Reserved 43 所以,最优解为 X=(1 , 1 , 0),最优值为 Z = 13。 Copyright © Li Yuxin. All Rights Reserved • 例5.某科研项目组由三个 小组用不同的手段分别研 究,它们失败的概率各为 0.40,0.60,0.80。为了 减少三个小组都失败的可 能性,现决定给三个小组 中增派两名高级科学家, 到各小组后,各小组科研 项目失败概率如下表: • 问如何分派科学家才能使 三个小组都失败的概率( 即科研项目最终失败的概 率)最小? 高级科高级科 学家学家 小组 123 00.400.600.80 10.200.400.50 20.150.200.30 44 四、动态规划问题典型应用 4 、 系 统 可 靠 性 问 题 Copyright © Li Yuxin. All Rights Reserved • 阶段123 小组123 45 Copyright © Li Yuxin. All Rights Reserved • 计算 • 当n=3时, • 当n=2时, 46 s3 f3*(s3) x3* 00.800 10.501 20.302 x2 s2 f2(s2,x2)=P2(x2) ·f3*(s2-x2) f2*(s2) x2* 012 00.480.480 10.300.320.300 20.180.200.160.162 Copyright © Li Yuxin. All Rights Reserved • 当n=1时, • 最优解为 x1*=1,x2*=0,x3*=1;科研项目最终失败的 概率为0.060。 47 x1 s1 f1(s1,x1)=P1(x1) ·f2*(s1-x1)f2*(s2)x2* 012 20.064 0.060 0.072 0.060 1 Copyright © Li Yuxin. All Rights Reserved 本章作业 • P226 • 第1、2题
展开阅读全文
  麦档网所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
0条评论

还可以输入200字符

暂无评论,赶快抢占沙发吧。

关于本文
本文标题:第十章动态规划
链接地址:https://www.maidoc.com/p-15475488.html
关于我们 - 网站声明 - 网站地图 - 资源地图 - 友情链接 - 网站客服 - 联系我们

[email protected] 2018-2020 maidoc.com版权所有  文库上传用户QQ群:3303921 

麦档网为“文档C2C模式”,即用户上传的文档所得金币直接给(下载)用户,本站只是中间服务平台,本站所有文档下载所得的金币归上传人(含作者)所有。
备案号:蜀ICP备17040478号-3  
川公网安备:51019002001290号 

本站提供办公文档学习资料考试资料文档下载


收起
展开