运筹学课件第七章动态规划.ppt

2019/6/28,运筹学,第七章 动 态 规 划 (Dynamic programming),动态规划的基本概念、基本思想,动态规划模型的建立和求解,动态规划的应用：背包问题；生产经营问题；设备更新问题；复合系统工作可靠性问题,2019/6/28,运筹学,第一节 动态规划 动态规划(Dynamic Programming)是用来解决多阶段决策过程最优化的一种数量方法。其特点在于，它可以把一个n 维决策问题变换为几个一维最优化问题，从而一个一个地去解决。 需指出：动态规划是求解某类问题的一种方法，是考察问题的一种途径，而不是一种算法。必须对具体问题进行具体分析，运用动态规划的原理和方法，建立相应的模型，然后再用动态规划方法去求解。,2019/6/28,运筹学,一、多阶段决策问题的典型例子： 1 . 生产决策问题：企业在生产过程中，由于需求是随时间变化的，因此企业为了获得全年的最佳生产效益，就要在整个生产过程中逐月或逐季度地根据库存和需求决定生产计划。,2. 机器负荷分配问题：某种机器可以在高低两种不同的负荷下进行生产。在高负荷下进行生产时，产品的年产量g和投入生产的机器数量u1的关系为 g=g(u1),1,2,n,状态,决策,状态,决策,状态,状态,决策,2019/6/28,运筹学,这时，机器的年完好率为a，即如果年初完好机器的数量为u，到年终完好的机器就为au, 0a1。,在低负荷下生产时，产品的年产量h和投入生产的机器数量u2的关系为 h=h(u2),假定开始生产时完好的机器数量为s1。要求制定一个五年计划，在每年开始时，决定如何重新分配完好的机器在两种不同的负荷下生产的数量，使在五年内产品的总产量达到最高。,相应的机器年完好率b, 0 b1。,2019/6/28,运筹学,3. 航天飞机飞行控制问题：由于航天飞机的运动的环境是不断变化的，因此就要根据航天飞机飞行在不同环境中的情况，不断地决定航天飞机的飞行方向和速度（状态），使之能最省燃料和实现目的（如软着落问题）。,不包含时间因素的静态决策问题（本质上是一次决策问题）也可以适当地引入阶段的概念，作为多阶段的决策问题用动态规划方法来解决。,4 . 线性规划、非线性规划等静态的规划问题也可以通过适当地引入阶段的概念，应用动态规划方法加以解决。,2019/6/28,运筹学,5 . 最短路问题：给定一个交通网络图如下，其中两点之间的数字表示距离（或花费），试求从A点到G点的最短距离（总费用最小）。,1,2,3,4,5,6,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,2019/6/28,运筹学,二、解题思路 三、应用范围 1、动态 2、静态 四、缺点 1、建模后，没有统一的方法 2、维数障碍,2019/6/28,运筹学,一、基本概念 1、阶段： 把一个问题的过程，恰当地分为若干个相互联系的阶段，以便于按一定的次序去求解。 描述阶段的变量称为阶段变量,用k表示。阶段的划分，一般是根据时间和空间的自然特征来进行的，但要便于问题转化为多阶段决策。,2、状态：表示每个阶段开始所处的自然状况或客观条件。通常一个阶段有若干个状态，描述过程状态的变量称为状态变量,用Sk表示。,一个数、一组数、一个向量,状态变量的取值有一定的允许集合或范围，此集合称为状态允许集合。,第二节 动态规划的基本概念,2019/6/28,运筹学,3、决策：表示当过程处于某一阶段的某个状态时，可以作出不同的决定，从而确定下一阶段的状态，这种决定称为决策。,描述决策的变量，称为决策变量,用Uk(Sk )。决策变量是状态变量的函数。可用一个数、一组数或一向量（多维情形）来描述。 在实际问题中决策变量的取值往往在某一范围之内，此范围称为允许决策集合,用Dk(Sk )表示。,4、状态转移方程,状态转移方程是确定过程由一个状态到另一个状态的演变过程。如果第k阶段状态变量sk的值、该阶段的决策变量一经确定，第k+1阶段状态变量sk+1的值也就确定。,2019/6/28,运筹学,图示如下：,能用动态规划方法求解的多阶段决策过程是一类特殊的多阶段决策过程，即具有无后效性的多阶段决策过程。,2019/6/28,运筹学,如果状态变量不能满足无后效性的要求，应适当地改变状态的定义或规定方法。,动态规划中能 处理的状态转移 方程的形式。,状态具有无后效性的多阶段决策过程的状态转移方程如下,无后效性(马尔可夫性),如果某阶段状态给定后，则在这个阶段以后过程的发展不受这个阶段以前各段状态的影响；,过程的过去历史只能通过当前的状态去影响它未来的发展；,构造动态规划模型时，要充分注意是否满足无后效性的要求；,状态变量要满足无后效性的要求；,2019/6/28,运筹学,5、策略：是一个按顺序排列的决策组成的集合。在实际问题中，可供选择的策略有一定的范围，称为允许策略集合。从允许策略集合中找出达到最优效果的策略称为最优策略。 全过程策略：U1(S1), U2(S2), Un(Sn) P1n=Ui(Si), i=1,n 子过程策略：Uk(Sk), Uk+1(Sk+1), Un(Sn) Pkn=Ui(Si), i=k,n 6、阶段指标：Vk(Sk, Uk),k阶段，Sk状态下，作出Uk决策带来的效果。在不同的问题中，指标的含义是不同的，它可能是距离、利润、成本、产量或资源消耗等。 7、指标函数：Vkn(Sk, Pkn),k阶段，Sk状态下，作出Pkn子策略带来的效果。动态规划模型的指标函数，应具有可分离性，并满足递推关系。,2019/6/28,运筹学,阶段指标与指标函数的关系有两种： 1）指标函数是它所含有的各阶段的阶段指标之和。 即Vkn(Sk,Pkn）= Vj(Sj, Uj),j=k,n 那么有Vkn(Sk,Pkn）= Vk (Sk,Uk）+ Vk+1 n(Sk+1,Pk+1 n） 2）指标函数是它所含有的各阶段的阶段指标之积。 即Vkn(Sk,Pkn）= Vj(Sj, Uj),j=k,n 那么有Vkn(Sk,Pkn）= Vk (Sk,Uk） Vk+1 n(Sk+1,Pk+1 n） 8、最优指标函数：指标函数的最优值，称为最优值函数。用fk(Sk)=optVkn(Sk,Pkn) opt表示最优化，常取max或min。,2019/6/28,运筹学,1、Bellman最优性定理 一个过程的最优策略具有这样的性质：即无论初始状态及初始决策如何，对于先前决策所形成的状态而言，其以后所有的决策应构成最优策略。 换句话说，最优策略只能由最优子策略构成。 2、思想方法：在求解过程中，各阶段的状态和决策，对其后面的阶段来说，只影响其初始状态，而不影响后面的最优策略。无后效性 方法：“顺序编号，逆序求解”,二、动态规划的基本思想和基本方程,2019/6/28,运筹学,3、基本方程 根据最优性定理，可以写出动态规划递推方程，即基本方程： Vkn(Sk,Pkn）= Vj(Sj, Uj),j=k,n时， fk(Sk)=opt Vk (Sk,Uk）+ fk+1(Sk+1) fn+1(Sn+1)=0 Vkn(Sk,Pkn）= Vj(Sj, Uj),j=k,n时， fk(Sk)=opt Vk (Sk,Uk） fk+1(Sk+1) fn+1(Sn+1)=1 其中的fn+1(Sn+1)为边界条件。,2019/6/28,运筹学,三、建立动态规划模型的步骤 1、划分阶段 划分阶段是运用动态规划求解多阶段决策问题的第一步，在确定多阶段特性后，按时间或空间先后顺序，将过程划分为若干相互联系的阶段。对于静态问题要人为地赋予“时间”概念，以便划分阶段。 2、正确选择状态变量 选择变量既要能确切描述过程演变又要满足无后效性，而且各阶段状态变量的取值能够确定。一般地，状态变量的选择是从过程演变的特点中寻找。 3、确定决策变量及允许决策集合 通常选择所求解问题的关键变量作为决策变量，同时要给出决策变量的取值范围，即确定允许决策集合。,2019/6/28,运筹学,4、确定状态转移方程 根据k 阶段状态变量和决策变量，写出k+1阶段状态变量，状态转移方程应当具有递推关系。 5、确定阶段指标函数和最优指标函数，建立动态规划基本方程 阶段指标函数是指第k 阶段的收益，最优指标函数是指从第k 阶段状态出发到第n 阶段末所获得收益的最优值，最后写出动态规划基本方程。,以上五步是建立动态规划数学模型的一般步骤。由于动态规划模型与线性规划模型不同，动态规划模型没有统一的模式，建模时必须根据具体问题具体分析，只有通过不断实践总结，才能较好掌握建模方法与技巧。,2019/6/28,运筹学,例一、从A 地到D 地要铺设一条煤气管道,其中需经过两级中间站，两点之间的连线上的数字表示距离，如图所示。问应该选择什么路线，使总距离最短？,A,B1,B2,C1,C2,C3,D,2,4,3,3,3,3,2,1,1,1,4,第三节 动态规划应用举例 一、最短路径问题,2019/6/28,运筹学,解：整个计算过程分三个阶段，从最后一个阶段开始。,第三阶段（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,显然有 f3 (C1 ) = 1 ； f3(C2 ) = 3 ； f3 (C3 ) = 4,2019/6/28,运筹学,d( B1,C1 ) + f3 (C1 ) 3+1 f2 ( B1 ) = min d( B1,C2 ) + f3 (C2 ) = min 3+3 d( B1,C3 ) + f3 (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,(最短路线为B1C1 D),2019/6/28,运筹学,d( B2,C1 ) + f3 (C1 ) 2+1 f2 ( B2 ) = min d( B2,C2 ) + f3 (C2 ) = min 3+3 d( 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),2019/6/28,运筹学,第一阶段（ A B ）： A 到B 有二条路线。,f3(A)1 = d(A, B1 ) f2 ( B1 ) 246 f3 (A)2 = d(A, B2 ) f2 ( B2 ) 437, f1 (A) = min = min6,7=6,d(A, B1 ) f2 ( B1 ) d(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,2019/6/28,运筹学,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,2019/6/28,运筹学,表上作业法,K=3,C1,C2,C3,D,D,D,1,3,4,D,D,D,0,0,0,D,D,D,K=2,B1,C1,3,C1,1,3,4,1,3,4,C2,C3,3,1,C2,C3,4,6,5,C1,B2,C1,C2,3,1,2,C1,C2,C3,1,3,4,3,6,K=1,A,B2,B1,2,4,B1,B2,C1,4,3,6,7,B1,5,C3,2019/6/28,运筹学,求从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,练习：,1,2019/6/28,运筹学,现有数量为a的资源，用于生产n种产品，第i种产品分配xi，带来gi(xi)收益，问如何分配使总收益最大？,据此，有下式：,二、资源分配问题 1、一维资源分配,2019/6/28,运筹学,求解： 阶段： k=1，2，,n,对应第k种产品分配资源的过程 状态Sk:表示可供分配第k种到第n种资源的总量 决策变量xk:表示分配给第k种产品的资源量 状态转移方程: Sk+1= Sk xk 阶段指标函数:V k= gk(xk) 基本方程: fk(Sk)=maxgk(xk) +fk+1(Sk+1)(k=n,n-1,1) fn+1(Sn+1)=0,2019/6/28,运筹学,例:两台设备分配给三个工厂,这三个工厂使用这几台设备所产生的效益分别为如下表,问如何分配使效益最大?,阶段： k=1，2，3,对应第k个工厂分配设备的过程 状态Sk:表示可供分配第k个到第3个工厂的设备的台数 决策变量xk:表示分配给第k个工厂的设备数 状态转移方程: Sk+1= Sk xk 阶段指标函数:V k= gk(xk) 基本方程: fk(Sk)=maxgk(xk) +fk+1(Sk+1) (k=3,2,1) f4(S4)=0,2019/6/28,运筹学,K=3,0,2,1,0,1,2,0,4,6,0,0,0,0,0,0,0,4,6,0,1,2,K=2,0,0,0,0,0,0,0,1,0,1,0,1,4,4,5,0,0,5,1,2,0,1,2,0,5,10,2,1,6,4,0,6,9,10,0,2,K=1,2,0,1,2,0,3,7,2,1,0,10,5,0,10,8,7,0,因此z*=10,X*=(0,2,0),*,*,*,2019/6/28,运筹学,练习：某公司打算在3个不同的地区设置4个销售点，根据市场部门估计，在不同地区设置不同数量的销售点每月可得到的利润如表所示。试问在各地区如何设置销售点可使每月总利润最大。,x1=2，x2=1，x3=1，f3(4)=47,2019/6/28,运筹学,有一个徒步旅行者，其可携带物品重量的限度为a 公斤，设有n 种物品可供他选择装入包中。已知每种物品的重量及使用价值（作用），问此人应如何选择携带的物品（各几件），使所起作用（使用价值）最大？,这就是背包问题。类似的还有工厂里的下料问题、运输中的货物装载问题、人造卫星内的物品装载问题等。,三、背包问题,2019/6/28,运筹学,设xj 为第j 种物品的装件数（非负整数）则问题的数学模型如下：,2019/6/28,运筹学,例题：求下面背包问题的最优解,2019/6/28,运筹学,用动态规划方法求解,阶段： k=1，2，3,对应第k种物品的选择过程 状态Sk:表示可供分配第k种到第3种物品的重量 决策变量xk:表示分配给第k种物品的件数 状态转移方程: S1 =5,S2= S1 2x2, S3= S2 2x3 阶段指标函数:V 1= 8x1, V 2= 5x2 ,V 3= 12x3 基本方程: fk(Sk)=maxVk +fk+1(Sk+1)(k=3,2,1) f4(S4)=0 求解见板书,2019/6/28,运筹学,练习：某厂生产三种产品，各种产品重量与利润的关系如表所示。现将此三种产品运往市场出售，运输能力总重量不超过 6 吨，问如何安排运输，使总利润最大？,最优方案：X1 =（0.2.0）X2 =（1.0.1）Z=260,2019/6/28,运筹学,四、复合系统工作可靠性问题,某种机器的工作系统由n个部件串联组成，只要有一个部件失灵，整个系统就不能正常工作。为了提高系统工作的可靠性，在每个部件上均装有主要元件的备用件，并设计了备用元件自动投入装备，显然，备用元件越多，整个系统工作的可靠性就越大，但备用元件增多也会导致系统的成本、重量体积相应增大，工作精度降低，因此，在考虑上述限制条件下，如何选择各部件的备用元件数，使整个系统的工作可靠性最大？ 建模：设部件i装有xi个备用元件时，正常工作的概率为Pi(xi),那么整个系统正常工作的概率Z= Pi(xi)（i=1，,n）,设部件i的单位重量级wi,那么总重量不超过w的情况下,如何配备备用件,使Z最大?,2019/6/28,运筹学,用动态规划方法求解,阶段： k=1，2，n,对应给第k个部件分配配件的过程 状态Sk:表示可供分配第k个到第n个部件的总重量 决策变量xk:表示分配给第k个部件配备的备用件数 状态转移方程: Sk+1 =Skwkxk 阶段指标函数:V k=Pk(xk) 基本方程: fk(Sk)=maxVk fk+1(Sk+1)(k=n,2,1) fk+1(Sk+1)=1,2019/6/28,运筹学,例:三个科研小组分别对某一项目的一个部件研究,成功率分别为0.6,0.4,0.2,为提高成功率,可以给各组增加人员,现有三个人可以加入到研究工作中,问如何分配人手,使项目总成功率最大?,阶段： k=1，2，3,对应给第k个小组分配人手的过程 状态Sk:表示可供分配第k个到第3个小组的总人数 决策变量xk:表示分配给第k个小组的人数 状态转移方程: Sk+1 =Skxk 阶段指标函数:V k=Pk(xk) 基本方程: fk(Sk)=maxVk fk+1(Sk+1)(k=3,2,1) f4(S4)=1,2019/6/28,运筹学,K=3,0,2,1,0,1,2,0.2,0.5,0.7,0,0,0,1,1,1,0.2,0.5,0.7,0,1,2,K=2,0,0,0.4,0,0.2,0.08,0,1,0,1,0.4,1,0.5,0.2,0.6,0,0.2,0.12,0,2,0,1,2,0.4,0.6,0.8,2,1,0.7,0.5,0.2,0.28,0.30,0.16,0,1,K=1,2,0,1,2,0.6,0.8,0.85,2,1,0,0.3,0.2,0.08,0.18,0.16,0.068,0,因此z*=0.18,X*=(0,1,1),*,*,*,2019/6/28,运筹学,例:分割问题,阶段： k=1，2，,n,对应给第k个变量赋值的过程 状态Sk:表示可供分配第k个到第n个变量赋值的总和 决策变量xk:表示给第k个变量赋的值 状态转移方程: Sk+1 =Skxk 阶段指标函数:V k=xk 基本方程: fk(Sk)=maxVk fk+1(Sk+1)(k=n,2,1) fn+1(Sn+1)=1,2019/6/28,运筹学,Maxz=x1x22x3 x1+x2+x3=C xi0,2019/6/28,运筹学,五、生产与库存问题 某厂要对一种产品制订今后四个时期的生产计划,拒估计在今后四个时期内，市场对于该产品的需求量见表.假定该厂生产每批产品的固定成本为3千元,若不生产则为0,每单位产品成本为1千元,每个时期生产能力所允