[党团建设]动态规划.ppt

第十章 动 态 规 划,一 动态规划的基本思想,二 最短路径问题,三 投资分配问题,四 背包问题,动态规划是用来解决多阶段决策过程最优化的一种数量方法。其特点在于，它可以把一个n 维决策问题变换为几个一维最优化问题，从而一个一个地去解决。,主要应用于：,最优路径问题、资源分配问题、 投资决策问题、生产计划与库存问题、 货物装载问题、生产过程中的最优控制问题。,返 回,前一页,后一页,例1、从A 地到D 地要铺设一条煤气管道,其中需经过两级中间站，两点之间的连线上的数字表示距离，如图所示。问应该选择什么路线，使总距离最短？,A,B1,B2,C1,C2,C3,D,2,4,3,3,3,3,2,1,1,1,4,最短路径问题,返 回,前一页,后一页,方法一：穷举,A到D共6条路，求出所有路长后取最短者即为最佳。,返 回,前一页,后一页,方法二：,1、分成三个阶段,2、从第三阶段反推。,方法一共做了12次加法， 而方法二只做了8次加法！,动态规划的特点：,1、把整个问题分阶段考虑，变成几个子问题。,第三阶段到终点作为第一个子问题， 第二、三阶段与终点组成第二个子问题， 第一、二、三阶段与终点构成第三个子问题。 而第三个子问题就是原来的问题。,2、一个子问题的解决借助它所包含的子问题的解答， 逐级推算。,3、动态规划中运用的原理： 最优路线的一部分也是最优的。,-Bellman最优性原理,例2最短路问题：给定一个交通网络图如下，其中两点之间的数字表示距离（或花费），试求从A点到E点的最短距离（总费用最小）。,A,B1,B2,C1,C2,C3,C4,D1,D2,D3,E1,E2,F,5,3,1,3,6,8,7,6,3,6,8,5,3,3,8,4,3,3,5,2,5,6,6,4,返 回,前一页,后一页,（一） 基本概念 1、阶段： 把一个问题的过程，恰当地分为若干个相 互联系的阶段，以便于按一定的次序去求解。,2、状态：表示每个阶段开始所处的自然状况或客观 条件。记 做 ，称为状态变量或状态。,第k阶段所有可能的状态用状态集合 来描述。如例1中三个状态集合为：,一、动态规划的基本思想,返 回,前一页,后一页,例1中第三阶段的状态为：,3、决策：表示当处于某一阶段的某个状态时，作出决定从而确定下一阶段的状态，这种决定称为决策。,返 回,前一页,后一页,用 表示处于状态 时的决策，称为决策变量。,例1中,4、状态转移方程：在动态规划中，如果给定了第k阶段的起始状态 与决策变量 ，则第k+1阶段的状态 也就确定了，这种关系可用公式 来表示。它表示从k到k+1阶段状态转移的规律，被称为状态转移方程。,例1中的状态转移方程为：,5、策略：对于一个含N个阶段的决策问题，任何一个由初始状态到终止状态的选择称为全过程策略，简称策略。任何一个策略都是由N个决策组成的决策序列。,例1,各阶段的决策为：,策略,从k阶段状态到终止阶段状态的选择称为子过程策略，简称子策略。,记做,是一个子策略,例1,根据第k阶段的初始状态做出这一阶段的决策， 评价该决策的数量指标称为阶段指标函数，是阶段状态 和阶段决策 的函数。记为,例1,6、指标函数和最优指标函数： 评价决策结果的数量指标称为指标函数。在不同的问题中，指标函数的含义是不同的，它可能是距离、利润、成本、产量等。,分为阶段指标函数和过程指标函数。,返 回,前一页,后一页,过程指标函数与决策过程有关：,时的全过程指标函数值；,时的子过程指标函数值。,最优指标函数用 表示，它表示在k阶段，状态为 ，采用最优策略 的子过程指标最优值。,即,A,B1,B2,C1,C2,C3,D,2,4,3,3,3,3,2,1,1,1,4,最短路,例一、从A 地到D 地要铺设一条煤气管道,其中需经过两级中间站，两点之间的连线上的数字表示距离，如图所示。问应该选择什么路线，使总距离最短？,A,B1,B2,C1,C2,C3,D,2,4,3,3,3,3,2,1,1,1,4,用动态规划解题：,解：整个计算过程分三个阶段，从最后一个阶段开始。,第三阶段（C D）： 有三个状态,A,B1,B2,C1,C2,C3,D,2,4,3,3,3,3,2,1,1,1,4,D,C1,C2,C3,显然有 f3 (C1 ) = 1 ； f3(C2 ) = 3 ； f3 (C3 ) = 4,d2( B1,C1 ) + f3 (C1 ) 3+1 f2 ( B1 ) = min d2( B1,C2 ) + f3 (C2 ) = min 3+3 d2( B1,C3 ) + f3 (C3 ) 1+4 4 = min 6 = 4 5,第二阶段（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,(最短路线为B1C1 D),d2( B2,C1 ) + f3 (C1 ) 2+1 f2 ( B2 ) = min d2( B2,C2 ) + f3 (C2 ) = min 3+3 d2( B2,C3 ) + f3 (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,(最短路线为B2C1 D),第一阶段（ A B ）： 只有一个状态, f1 (A) = min = min6,7 =6,d1(A, B1 ) f2 ( B1 ) d1(A, B2 ) f2 ( B2 ),(最短路线为AB1C1 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,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,最短路线为 AB1C1 D 路长为 6,动态规划的一般模型为：,边界条件,最优指标函数的关系式：,（三）、建立动态规划模型的步骤 1、划分阶段 划分阶段是运用动态规划求解多阶段决策问题的第一步，在确定多阶段特性后，按时间或空间先后顺序，将过程划分为若干相互联系的阶段。对于静态问题要人为地赋予“时间”概念，以便划分阶段。 2、正确选择状态变量 选择变量既要能确切描述过程演变又要满足无后效性，而且各阶段状态变量的取值能够确定。一般地，状态变量的选择是从过程演变的特点中寻找。 3、确定决策变量 通常选择所求解问题的关键变量作为决策变量，同时要给出决策变量的取值范围，即确定允许决策集合。,4、确定状态转移方程 根据k 阶段状态变量和决策变量，写出k+1阶段状态变量，状态转移方程应当具有递推关系。 5、确定阶段指标函数和最优指标函数，建立动态规划基本方程 阶段指标函数是指第k 阶段的收益，最优指标函数是指从第k 阶段状态出发到第n 阶段末所获得收益的最优值，最后写出动态规划基本方程。,以上五步是建立动态规划数学模型的一般步骤。由于动态规划模型与线性规划模型不同，动态规划模型没有统一的模式，建模时必须根据具体问题具体分析，只有通过不断实践总结，才能较好掌握建模方法与技巧。,四、动态规划的求解步骤,1 列出本阶段所有可能的状态,2 对每一个状态 列出可能的决策,3 对每一对 ， 计算本阶段的阶段指标函数,4 利用状态转移方程 ， 对每对 ， 求出 的值。,5 计算每对 ， 的指标值,6、将第5步中各指标值进行比较，取最优者为从本阶 段状态 开始的子过程的最优指标 ，相应的 决策即为本阶段以 为起始状态的最优决策。,从最后一个阶段开始计算，逐段前推，直至求出全过程的最优解。,练习1：,A,B1,B2,C1,C2,C3,C4,D1,D2,D3,E1,E2,E3,F1,F2,G,5,3,1,3,6,8,7,6,3,6,8,5,3,3,8,4,2,2,2,1,3,3,3,5,2,5,6,6,4,最优路线为：A B1 C2 D1 E2 F2 G 路长18,求从A到G的最短路径,3,k=5，出发点E1、E2、E3,k=2, f2(B1)=13 u2(B1)=C2 f2(B2)=16 u2(B2)=C3,7 5 9,u5(E2)=F2,u6(F2)=G,最优策略,A,B1,B2,C1,C2,C3,C4,D1,D2,D3,E1,E2,E3,F1,F2,G,5,3,1,3,6,8,7,6,3,6,8,5,3,3,8,4,2,2,2,1,3,3,3,5,2,5,6,6,4,3,求从A到E的最短路径,路线为AB2C1 D1 E ，最短路径为19,A,B2,B1,B3,C1,C3,D1,D2,E,C2,5,2,14,1,12,6,10,10,4,3,12,11,13,9,6,5,8,10,5,2,练习2：,1,注意：动态规划是求解某类问题的一种方法，是考 察 问题的一种途径，而不是一种算法。必须对具 体问题进行具体分析，运用动态规划的原理和 方法，建立相应的模型，然后再用动态规划方 法去求解。,线性规划、非线性规划等静态的规划问题也可以通过适当地引入阶段的概念，应用动态规划方法加以解决。,返 回,前一页,后一页,例题： 设国家投资60万元供四个工厂扩建，每个工厂扩建后的利润与投资额的大小有关，投资后的利润函数如下表所示。问：如何确定各工厂的资金数，使得总的利润为最大。,三、投资分配问题,现有数量为a（万元）的资金，计划分配给n 个工厂,用于扩大再生产。 假设：xi 为分配给第i 个工厂的资金数量（万元） ；gi(xi)为第i 个工厂得到资金后提供的利润值（万元）。 问题是如何确定各工厂的资金数，使得总的利润为最大。,一般投资分配问题,分成n个阶段，考虑第k 阶段,1、第k阶段的状态：分到第k个工厂时剩余的资金数,2、决策：该阶段分配的资金数,3、第k阶段的决策的阶段指标函数为,4、状态转移方程,模型：,5、最优指标,例题： 设国家拨给60万元投资，供四个工厂扩建使用，每个工厂扩建后的利润与投资额的大小有关，投资后的利润函数如下表所示。,解：分成四个阶段。依据题意，是要求 f1(60) 。,第四阶段：求 f4(x)。显然有 f4(x) g4(x),第三阶段：求 f3(x)。此时需考虑第三、第四个工厂如何进行投资分配，以取得最大的总利润。,第三阶段状态的可能是：,60，50，40， 30，20，10，0,60，50，40，30，20，10，0,第四阶段状态的可能是：,最优策略为（20，40），此时最大利润为120万元。,同理可求得其它 f3(x) 的值。,最优策略为（20，30），此时最大利润为105万元。,最优策略为（20，20），此时最大利润为90万元。,最优策略为（10，20），此时最大利润为70万元。,最优策略为（0，20），此时最大利润为50万元。,最优策略为（10，0）或（ 0 ， 10 ） ，此时最大利润为20万元。,f3(0) 0。最优策略为（0，0），最大利润为0万元。,第二阶段：求 f2(x)。此时需考虑第二、第三及第四个工厂如何进行投资分配，以取得最大的总利润。,第二阶段的可能状态为：,60，50，40，30，20，10，0,最优策略为（30，10，20），最大利润为155万元。,同理可求得其它 f2(x) 的值。得到下表,第一阶段：求 f1(60)。即问题的最优策略。,第一阶段状态只能是：,60,最优策略为（10，30，0，20），最大利润为160万元。,练习： 求投资分配问题的最优策略，其中a50 万元，其余资料如表所示。,例：某公司打算在3个不同的地区设置4个销售点，根据市场部门估计，在不同地区设置不同数量的销售点每月可得到的利润如表所示。试问在各地区如何设置销售点可使每月总利润最大。,x1=2，x2=1，x3=1，f3(4)=47,有一个徒步旅行者，其可携带物品重量的限度为a 公斤，设有n 种物品可供他选择装入包中。已知每种物品的重量及使用价值（作用），问此人应如何选择携带的物品（各几件），使所起作用（使用价值）最大？,这就是背包问题。类似的还有工厂里的下料问题、运输中的货物装载问题、人造卫星内的物品装载问题等。,四、背包问题,分成n个阶段，考虑第k 阶段,1、第k阶段的状态：到第k件物品时可装载的重量,2、决策：第k件物品的件数,3、决策的阶段指标函数为,4、状态转移方程,模型：,5、最优指标,例题：求下面背包问题的最优解,解：a5 ，问题是求 f1(5),所以，最优解为 X（0 ， 1 ， 1），最优值为 Z = 13。,练习1：某厂生产三种产品，各种产品重量与利润的关系如表所示。现将此三种产品运往市场出售，运输能力总重量不超过 6 吨，问如何安排运输，使总利润最大？,最优方案：X1 =（0.2.0）X2 =（1.0.1）Z=260,动态规划与静态规划的关系 动态规划与静态规划（线性和非线性规划等）研究的对象本质上都是在若干约束条件下的函数极值问题。两种规划在很多情况下原则上可以相互转换。 动态规划可以看作求决策使指标函数达到最优（最大或最小）的极值问题，状态转移方程、端点条件以及允许状态集、允许决策集等是约束条件，原则上可以用非线性规划方法求解。 一些静态规划只要适当引入阶段变量、状态、决策等就可以用动态规划方法求解。,与静态规划相比，动态规划的优越性在于： （i）能够得到全局最优解。 由于约束条件确定的约束集合往往很复杂，即使指标函数较简单，用非线性规划方法也很难求出全局最优解。而动态规划方法把全过程化为一系列结构相似的子问题，每个子问题的变量个数大大减少，约束集合也简单得多，易于得到全局最优解。特别是对于约束集合、状态转移和指标函数不能用分析形式给出的优化问题，可以对每个子过程用枚举法求解，而约束条件越多，决策的搜索范围越小，求解也越容易。对于这类问题，动态规划通常是求全局最优解的唯一方法。,（ii）可以得到一族最优解。与非线性规划只能得到全过程的一个最优解不同，动态规划得到的是全过程及所有后部子过程的各个状态的一族最优解。有些实际问题需要这样的解族，即使不需要，它们在分析最优策略和最优值对于状态的稳定性时也是很有用的。当最优策略由于某些原因不能实现时，这样的解族可以用来寻找次优策略。 （iii）能够利用经验提高求解效率。如果实际问题本身就是动态的，由于动态规划方法反映了过程逐段演变的前后联系和动态特征，在计算中可以利用实际知识和经验提高求解效率。如在策略迭代法中，实际经验能够帮助选择较好的初始策略，提高收敛速度速度。,动态规划的主要缺点是： （i）没有统一的标准模型，也没有构造模型的通用方法，甚至还没有判断一个问题能否构造动态规划模型的准则。这样就只能对每类问题进行具体分析，构造具体的模型。对于较复杂的问题在选择状态、决策、确定状态转移规律等方面需要丰富的想象力和灵活的技巧性，这就带来了应用上的局限性。 （ii）用数值方法求解时存在维数灾（curse of dimensionality）。若一维状态变量有n个取值，那么对于m维问题，状态就nm有个值，对于每个状态值都要计算、存储函数，对于稍大（即使）的实际问题的计算往往是不现实的。目前还没有克服维数灾的有效的一般方法。,