运筹学教学课件ppt动态规划

第七章第七章 动态规划动态规划 .1 动态规划问题和基本概念 .2 动态规划的基本原理 .3 动态规划的应用 引言引言 动态规划与多阶段决策：动态规划与多阶段决策： 多阶段决策是指这样一类特殊的活动过程, 它们可以按时间顺序分 解成若干相互联系的阶段, 每个阶段都要作出决策, 全部过程的决策是 一个决策序列, 所以多阶段决策问题又称为序贯决策问题。 多阶段决策的目标是要达到整个活动过程的总体效果最优, 所以多 阶段决策又叫做过程最优化。 所谓动态规划，就是解决多阶段决策和过程最优化问题的一 种规划方法。 例.1 最短路问题 设A地的某一企业要把一批货物由A地运到E城销售, 其间 要经过八个城市,各城市间的交通路线及距离如下图所示, 问应 选择什么路线才能使总的距离最短? .1 动态规划问题和基本概念 例中，路线图(共18条路线,3321=18) 枚举法： 例中，路线图(共18条路线,3321=18) 为解决这个最短路径问题，首先给出几个定义。 1）、阶段 (stage) 将所给问题的过程，按时间或空间特征分解成若干相互联系的段落， 以便按次序求解就形成了阶段,阶段变量常用字母 K来表示。如例.1 有四个阶段，K就等于 1,2,3,4。第一阶段共有3 条路线即(A,B1), (A,B2) 和(A,B3),第二阶段有 9条路线，第3 阶段有6条路线,第4 阶段有2 条 路线。 1234 2）、 状态 ( state) 各阶段开始时的出发点称作状态。 描述各阶段状态的变量，称作状态变量，用sk 表示。 在例.1 中，第一阶段的状态为 A，第二阶段的状态为城市 B1，B2 和B3。 所以状态变量 S1 的集合 S1=A,S2 的集合是S2=B1,B2,B3, 依次有 S3=C1,C2,C3, S4=D1,D2 。 1234 3）、 决策（Decision ) 当各阶段的状态确定以后，就可以做出不同的决定或选择，从而确 定下一阶段的状态，这种决定就是决策，表示决策的变量称为决策变量。 常用 k X（ k s）表示第K阶段当状态为 k s时的决策变量， 在例.1中第二阶段如决定从B1出发，即S2=B1，可选择走C1或C2 ，C3 ，如果我们选择，从C2走，则此时的决策变量可表示x2(B1)=C2 。 1234 4）、策略（ Policy） 在各阶段决策确定以后，整个问题的决策序列就构成了一个策略, 用P1n(s1)表示。 如对于例.1总共可有18个策略，但最优策略只有一个。 12 34 5）、目标函数 用于衡量所选定策略优劣的数量指标称作目标函数。 一个n阶段的决策过程，从1到n 叫作问题的原过程。 目标函数的最优值称为最优目标函数，最优目标函 数记为fk(sk)，它表示从第K阶段的状态Sk出发采用的最优 策略。 当K=1时, f1(s1 )就是从初始状态S1到全过程结束的整体 最优目标函数。 , 在例.1中，目标函数就是距离。如在第2阶段，状 态为B2时，f2 (B2)则表示从B2到E的最短距离。本问题 的总目标是求f 1(A), 即从A到E的最短距离。 1234 6）、 状态转移方程 在动态规划中，本阶段的状态往往是上阶段决策的结果。所以如果给 定了第 K阶段的状态 k s和该阶段的决策 k x ( k s)，则第K+1段的状态 1+k s 由于 K阶段决策的完成也就完全确定了,它们之间的关系可用如下公式表示： 1+k s k T（ k s， k x） 其中， k T表示从状态 k s出发经过 k x向下一阶段的转移(Transfer)，换 言之，即 1+k s是从状态 k s出发经过决策 k x转移的结果。 由于上式表示了由 K段到第K+1段的状态转移规律，所以就称为状态 转移方程。在例 .1中,状态转移方程即 1+k s k x。 为了求出例.1的最短路线,一个简单的方法是,可以求出 所有从A到E的可能走法的路长并加以比较。不难知道,从A到 E共有18条不同的路线,每条路线有四个阶段,要做3次加法,要 求出最短路线需做54次加法运算和17次比较运算,这叫做穷举 法。 当问题的段数很多,各段的状态也很多时,这种方法的计算 量会大大增加,甚至使得寻优成为不可能。 下面应用动态规划方法求解例.1。运用逆序递 推方法求解,即由最后一段到第一段逐步求出各点到 终点的最短路线,最后求出A点到E点的最短路线。 运用逆序递推方法的好处是可以始终盯住目标,不 致脱离最终目标。 例.1是一个四阶段决策问题,一般可分为四步： 12 34 第一步,从K=4开始 1234 S1S2S3S4 逆序法求解最短路问题 状态变量S4可取两种状态D1, D2,它们到E点的距离 分别为4和3,这也就是由D1和D2到终点E 的最短距离 ， 即 f4(D1)=4, f4(D2)=3. 第二步 ,K=3 状态变量S3可取3个值即 C1,C2和C3。 为方便应用，规定用d(sk，sk+1)表示由状态sk出发，到达下一阶段sk+1时的 两点距离。 3 f（ 1 C）min + + )(),( )(),( 2421 1411 DfDCd DfDCd =min + + 35 43 =7 这说明,由 1 c到E 的最短距离为7,其路径为以 1 C 1 DE,相应的决策 为 * 3 x（ 1 C）= 1 D 1234 S1S2S3S4 + + )(),( )(),( 2422 1412 DfDCd DfDCd 3 f（ 2 C）min =min + + 32 46 =5 即从 C2到E的最短距离为5,其路径为 2 C 2 DE,相应的决策为 * 3 x（ 2 C）= 2 D 1234 S1S2S3S4 即从 C3到E的最短距离为5,其路径为C3D1E,相应的决策为 * 3 x（ 3 C）= 1 D。 3 f（ 3 C）min + + )(),( )(),( 2423 1413 DfDCd DfDCd =min + + 33 41 =5 1234 S1S2S3S4 第三步, K=2由于第 3段各点C1,C2,C3到终点E的最短距离f3(C1), f3(C2), f3(C3),已知,所以要求城市B1到E的最短距离,只需以它们为基础, 分别加上 B1到达C1,C2,C3 的一段距离,加以比较取其最短者即可。 即 B1到终点E的最短距离为9,其路径为B1C2D2E,本段的相应 决策为 * 2 x（ 1 B）= 2 C )( 12 Bf=min + + + )(),( )(),( )(),( 3331 2321 1311 CfCBd CfCBd CfCBd =min + + + 55 54 76 =9 1234 S1S2S3S4 同理有: )( 22 Bf =min + + + )(),( )(),( )(),( 3332 2322 1312 CfCBd CfCBd CfCBd =min + + + 56 57 78 =11 即 * 2 x（ 2 B） 3 C B2C3 D1 E 1234 S1S2S3S4 + )( 32 Bf=min + + )(),( )(),( )(),( 3333 2323 1313 CfCBd CfCBd CfCBd =min + + 59 58 77 =13 即 * 2 x（ 3 B） 2 C 1234 S1S2S3S4 B3C2 D2 E 第四步, K=1, 只有一个状态点 A,则 )( 1 Af =min + + + )(),( )(),( )(),( 333 232 121 BfBAd BfBAd BfBAd =min + + + 135 119 98 =17 1234 S1S2S3S4 从城市A到城市E的最短距离为17。把各段的最优决策按计算顺序 反推,即得到最优决策序列,即 * 1 x（A） 1 B, * 2 x（ 1 B）= 2 C, * 3 x（ 2 C） 2 D， * 4 x（ 2 D）E，所以最短路线为:AB1C2D2E. 12 34 图例.1各点到终点的最短路径 根据例.1,动态规划的基本思想可总结如下： 一、 将多阶段决策过程划分阶段,恰当地选取状态变量,决策变量和定 义最优目标函数,从而把问题化成一族同类型的子问题，然后逐个求解。 二、 求解时从边界开始， 沿过程行进方向，逐段递推寻优。在每一 个子问题求解时,都要利用它前边已求出的子问题的最优结果, 最后一个子问 题的最优解,就是整个问题的最优解。 三、 动态规划方法是既把当前一段与未来各段分开,又把当前效益和 未来效益结合起来考虑的一种最优化方法,因此,每段的最优决策的选取都 是从全局考虑的,它与该段的最优选择是不同的。 在例.1的求解过程中,各段的计算都利用了第K段和第K+1段的如下 关系： k f （ k s ）min k d （ k s ，sk+1） )( 11+kk sf (k=4,3,2,1) (1) )( 55 sf 0 (2) 这种递推关系称为动态规划的基本方程,(2)式称边界条件,容易算出, 运用动态规划方法解例.1只进行了17次加法运算,11次比较运算，就 获得了最优解,比穷举法的计算量明显地要少,而且随着问题段数的增加 和变量程度的提高,计算量将呈指数规律减少。其次,动态规划的计算结果 不仅得到了A到E的最短路线,而且得到了任意一点到E点的最优路线。 这可由图.2来描述(用彩色线表示最优路线,各点上的数字表最短距离) .2.1 最优化原理 动态规划方法是由美国数学家贝尔曼(R.Bellman)等人于本世纪 50年 代提出的。他们针对多阶段决策问题的特点,提出了解决这类问题的”最优 化原理”,并成功地解决了生产管理、工程技术许多方面的实际问题。最优化 原理可以表述为：“一个过程的最优策略具有这样的性质 , 即无论初始状态 和初始决策如何,对于先前决策所形成的状态而言,其以后的所有决策必构成 最优策略。” .2 .2 动态规划的基本原理动态规划的基本原理 简言之：最优策略的任一子策略都是最优的。 如果把最优化原理用数学语言描述,就得到了动态规划的基本方程： k f（ k s） opt)(),( 11+ + kkkkk sfxsd (k=n,n-1,1) 1+k f （1+k s ）0 其中 ,opt 可依题意取max 或min 7.2.2 动态规划求解的基本步骤 求解动态规划 , 就是分析问题并建立问题的动态规划基本方程。 成功地应用动态规划方法的关键;在于识别问题的多阶段特征,将问题 分解成可用递推关系式联系起来的若干子问题 ,或者说是要正确地建立具 体问题的基本方程。而正确地建立关于递推关系基本方程的关键，又 在于正确地选择状态变量保证各阶段的状态变量具有递推的状态转移关系。 1+k s),( kkk xsT。 这是建立动态规划模型的两个要点。 1234 S1S2S3S4 例P184 某公司有资金万元，拟投资于个项目，其收 益分别为 可建立以下模型： 7.2.2 动态规划求解的基本步骤 2. 状态变量 k s：表示第K段可用于剩余的n-k+1个项目的资金数, 显然有 1 s=10, 4 s=0 。 3. 决策变量 k x： 即应分配第K个项目上的投资额。 1.阶段：K=1，2， 4. 状态转移方程： kkk xss-= +1 5. 最优目标函数k f（ k s ）：表示当可投资金数为k s 时, 投资于剩余的 n-k+1个项目的最大收益。 6. 基本方程为： = += + + 0)( )()(max)( 11 11 nn kkkkkk sf sfxgsf k=3,2,1 (逆序解法) 投资问题: 设总投资额为 A万元, 拟投资于n个项目上，已知对第 i个项目投 资 i x万元,收益函数为)( ii xg,问应如何分配资金才可以使总收益最大? 这是一个与时间无明显关系的静态最优化问题,可先列出其静态模型为： 为了应用动态规划方法求解, 我们可以人为地赋予它“时段”的概 念。方法是将投资项目排序, 假想对各个投资项目有先后顺序。 首先考 虑对项目1的投资, 然后考虑对项目 2的投资, 依次最后考虑第 n项 投资.这样就把原问题转化为 n阶段的决策过程。接下来的问题，便是如 何选择正确的状态变量,并使各后部子过程间具有递推关系。 Max V = n i ii xg 1 )( s.t. Ax n i i =1 0 i x (i=1,2,n) 2. 状态变量 k s：表示第K段可用于剩余的n-k+1个项目的资金数, 显然有 1 s=A, 1+n s=0。 3. 决策变量 k x： 即应分配第K个项目上的投资额。 1.阶段：K=1，2，n 4. 状态转移方程： kkk xss-= +1 5. 最优目标函数k f（ k s ）：表示当可投资金数为k s 时, 投资于剩余的 n-k+1个项目的最大收益。 6. 基本方程为： = += + + 0)( )()(max)( 11 11 nn kkkkkk sf sfxgsf k=n,n-1,2,1 如果运用逆序递推寻优, 则)( 1 s1f就是所求的最大收益。 7.2.3 动态规划求解时的几种常用算法 离散变量的分段穷举法 如最短路问题的解法, 离散型资源分配问题等 连续变量的解法 根据方程的具体情况灵活选取求解方法 a.逆序解法 b.顺序解法 如连续型资源分配问题等 例 用动态规划方法求解下列问题 解：采用逆序解法 顺序解法的基本方程为： = + =+ 0)( )()( max) ( 1 4 4 k+1kkkkk sf sfxgsf k=3,2,1 当3时，有 可以看到,当 时, f3(s3)取得极大值 当时，有 求其极值点: 这是一个极小点, 为什么? 所以,极大值只可能在0,s2的端点取得, 则有 当1时，有 分两种情况: 讨论! 当 x1=0时, f1(10)=200, 达到最大值. 再由状态转移方程顺推,可求出: x2=0 x3=10 例 用动态规划方法求解下列问题 解：采用顺序解法 顺序解法的基本方程为： = + = 0)( ) ()( max) ( 1 kkkkkk sf sfxgsf k=3,2,1 当时，有 当时，有 当3时，有 记 求导，得 解得 此点仅为极小点 极大值应在0，s4=0，10的端点取得 当x3=0时，f3 (10)=90 当x3=10时，f3 (10)=200 再由状态转移方程逆推： 逆序解法的过程见书 P .3.1 资源分配问题 例 某企业共有设备5台,拟分给三个工厂,各工厂利用这些设备 为企业可提供的盈利 kk(x ) g各不相同 ( 见表.4) ,问应如何分配这四台 设备才能使企业获得的盈利最大? .3 .3 动态规划应用举例动态规划应用举例 表.4 有关资料 单位：万元 设备分配数 )( 11xg )( 22 xg )( 33 xg 0 1 2 3 4 5 0 3 7 9 12 13 0 5 10 11 11 11 0 4 6 11 12 12 甲厂 乙厂丙厂 Max z = 3 i ii xg 1 )( s.t. 5x n i i = =1 0 i x (i=1,2,n) 分析: 可建立如下模型 解： 1.将问题按工厂分为三个阶段，k=1,2,3 2.设 xk分配给第k个工厂的设备台数。 S1 S2S3S4 甲厂 x1 乙厂 x2 丙厂 x3 3.状态转移方程：Sk+1=Sk - xk 已知 s1=5 s2=s1-x1 s3=s2-x2 4.目标函数为: fk(sk)=maxgk(xk)+fk+1(sk+1) k=3,2,1 f4(s4)=0 设备分配数 )( 11xg )( 22 xg )( 33 xg 0 1 2 3 4 5 0 3 7 9 12 13 0 5 10 11 11 11 0 4 6 11 12 12 甲厂 乙厂丙厂 当K=3时 状态变量 3 s的取值范围为 3 s0，1，2，3，4,5 3 x的取值范围也是 3 D 0，1，2，3， 4, 5 , 33 s x = 0)( 44 =sf ,K=3时的结果如下表: x3 s3 f3(s3)=g3(x3)+ f4(s4) f3(s3) x3 012345 0 1 2 3 4 5 5.列表计算： 0 4 6 11 12 12 0 1 2 3 4 5 0 4 6 11 12 12 当K=2时 223 xss -= 322 ssx-= X2 s2 f2(s2)=g2(x2)+f3(s3) f2(s2) x2 012345 0 1 2 3 4 5 0+0 0+4 0+6 0+11 0+12 0+12 5+0 5+4 5+6 5+11 5+12 10+0 10+4 10+6 10+11 11+0 11+4 11+6 11+0 11+411+0 00 51 102 142 161,2 212 状态变量的取值范围为 s2=0,1,2,3,4,5, x2的取值范围也是 2 D 0，1，2，3， 4, 5 , 当k=1时，s1=5, x1的可取值为0,1,2,3,4,5 计算结果如下： x1 s1 f1(s1)=g1(x1)+f2(s2) f1(s1) x1 012345 5 最优分配方案有两个： x1=0, x2=2, x3=3 0+21 3+167+14 9+10 12+5 13+0210，2 x1=2, x2=2, x3=1 例 7.5 一运输商拟用一 10吨载重量的大卡车装载3种货物, 资料 如下表,问应如何组织装载,可使总价值最大? 解： 设装载第三种货物的件数为 i x，则有： Max z=4 1 x+5 2 x+6 3 x s.t . 3 1 x+4 2 x+5 3 x 10 0 xi 且为整数 货物编号 1 2 3 单位重量（吨） 单位价值(百元 ) 3 4 5 4 5 6 7.3.2背包问题 背包问题是动态规划的典型问题。一维背包问题的典型提法是：一 位旅行者能承受的背包最大重量是 b千克，现有n种物品供他选择装入 背包，第 i种物品单件重量为 i a千克，其价值(或重要性参数)为ci，总价 值是携带数量 i x的函数即 iix c，问旅行者应如何选择所携带物品的件数 以使总价值最大? 模型可表述为： = = n i iix cz 1 max s.t. bxa n i ii =1 0 i x 且为整数（i=1,2,n） 段。 用动态规划方法来求解 1. 阶段k：即需要装入的n种物品的次序,每段装入一种,共n 2. 状态变量 k s：即在第k段开始时,允许装入前k种物品的总重 量，显然有 1 s=b 3. 决策变量 k x：即装入第K种物品的件数 4. 状态转移方程： kkkk xass-= +1 允许的决策集合是： = k k kkkk a s xxsD0|)(且为整数 5. 目标函数是: ) = += + nk Sn+1 f sfxcsf k+1kkkkk ,.,2 , 1 0)( (max)( n+1 1 当K=3时，S3=0，1，2，10 ， f3(S3)=max6x3+0 x3 s3 6x3+0 f3(s3)x3 012 0 1 2 3 4 5 6 7 8 9 10 0 0 0 0 0 6 6 6 6 6 12 0 0 0 0 0 6 6 6 6 6 12 0 0 0 0 0 1 1 1 1 1 2 x2 s2 5x2+ f3(S3) f2(s2)x2012 0 1 2 3 4 5 6 7 8 9 10 当K=2时，S2=0，1，2，10， f2(S2)=max6x2+ f3(S3) 0 0 0 0 0 0+6 0+6 0+6 0+6 0+6 0+12 5+0 5+0 5+0 5+0 5+0 5+6 5+6 10+0 10+0 10+0 0 0 0 0 5 6 6 6 10 11 11 0 0 0 0 1 0 0 0 2 1 1 当K=1时，S1=10, f1(S1)=max4x1+ f2(S2) x1 s1 4x1+ f2(S2) f1(s1)x1 S20123 10 最优解为： X1*=2, X2*=1, X3*=0 Z*=13 0+114+68+512+01324 7.3.3 生产与存储问题 例 7.6 某厂生产的一种产品，以后四个月的订单如 下表： 月份1234 订货量（bk)3324 合同规定在各月底前交货，生产每批产品的固定成本 为3千元，每批生产的产品件数不限。每件产品的可 变成本为1千元，每批产品的最大生产能力为5件。产 品每件每月的存储费为500元。又知1月初有库存产品 1件，4月底不再留下产品。试在满足需要的前提下， 如何组织生产才能使总的成本最低。 解：1.设阶段变量为K,则每月为一个阶段,K=1,2,3,4 0xk 5, 4. 状态转移方程由下式确定： 1+k s kkk bxs-+ 其中, k d表示第K阶段的产品总成本，即 ),( kkk xsd = + )0(0.5sk )50(3 k k x xxk+0.5sk 2.每月初的产品库存量作为状态变量，由已知条件显然有S1=1，S5=0 3.决策变量是每月的产品生产量，由已知条件知： 5. 建立基本方程（即成本最小化） )(),(min)( 11+ += kkkkk U kk sfxsdsf k （k=4,3,2,1） 0)( 55 = s f 当K=4时，S4的最小可能值为0，即4月初没有存货。 S4的最大可能值=531（3 3 2），4=4 即 S4=0，1，2，3，4。 （K=4） s4 本阶段费用 s5f5(s5)d+ f5(s5)f4(s4) x4生产费 用 存储 费 d(s4,x4) 043+4070077 133+30.56.5006.56.5 223+2160066 313+11.55.5005.55.5 400220022 当K=3时，S3的最小值=52+16，6=5 即 S3=0,1,2,3,4,5 (k=3)