课件动态规划2013

1、第七章 动态规划,1 多阶段决策过程最优化问题举例 2 基本概念、基本方程与最优化原理 3 动态规划的应用,引言,动态规划Dynamic Programming 动态规划是运筹学的一个分支，是解决多阶段决策过程最优化的一种数学方法。 1951年，美国数学家贝尔曼等人提出了 “最优性原理”，即根据一类多阶段决策问题的特点，把多阶段决策问题变换为一系列相互联系的单阶段决策问题，然后分阶段逐个加以解决。 从而创建了解决最优化问题的一种新的方法 动态规划。,引言,动态规划是解决某一类问题的一种方法，是分析问题的一种途径，而不是一种特殊算法（如线性规划是一种算法）。因此，在学习动态规划时，除了对基本概念

2、和方法正确地理解外，应以丰富的想象力去建立模型，用创造性的技巧去求解。,1 多阶段决策过程及实例,多阶段决策过程（Multi-Stage decision process） 整个决策过程可按时间或空间顺序分解成若干相互联系的阶段，每一阶段都需作出决策，全部过程的决策是一个决策序列。 多阶段决策过程最优化的目标： 达到整个活动过程的总体效果最优，而非各单个阶段最优的简单总和。,多阶段决策问题的典型例子： 1 . 生产决策问题：企业在生产过程中，由于需求是随时间变化的，因此企业为了获得全年的最佳生产效益，就要在整个生产过程中逐月或逐季度地根据库存和需求决定生产计划。,2. 机器负荷分配问题：某种机

3、器可以在高低两种不同的负荷下进行生产。在高负荷下进行生产时，产品的年产量g和投入生产的机器数量u1的关系为 g=g(u1),1,2,n,状态,决策,状态,决策,状态,状态,决策,这时，机器的年完好率为a，即如果年初完好机器的数量为u，到年终完好的机器就为au, 0a1。,在低负荷下生产时，产品的年产量h和投入生产的机器数量u2的关系为 h=h(u2),假定开始生产时完好的机器数量为s1。要求制定一个五年计划，在每年开始时，决定如何重新分配完好的机器在两种不同的负荷下生产的数量，使在五年内产品的总产量达到最高。,相应的机器年完好率b, 0 b1。,3. 航天飞机飞行控制问题：由于航天飞机的运动的

4、环境是不断变化的，因此就要根据航天飞机飞行在不同环境中的情况，不断地决定航天飞机的飞行方向和速度（状态），使之能最省燃料和实现目的（如软着落问题）。,4 .不包含时间因素的线性规划、非线性规划等静态决策问题（本质上是一次决策问题）也可以适当地引入阶段的概念，作为多阶段的决策问题用动态规划方法来解决。,5 . 最短路问题. 某产品从A城运至F城，其间要经过若干 个城镇和若干条道路，路线结构如图所示， 图中给出了每段道路的运费（元），试选 择一条合理的运输路线，使总运费最小？,分析：方案 ：AB1C1E1F 运费：26元 方案 : AB3C3E3F 运费：22元 方案 : AB2C1E2F 运费：

5、18元 最优方案：方案,2 动态规划的基本概念和基本原理,1、阶段（stage） 把所给问题恰当地划分为若干个相互联系又有区别的子问题，通常根据时间顺序或空间特征来划分，以便按阶段的次序逐段解决整个过程的优化问题。 描述阶段的变量叫作阶段变量，阶段变量通常用k表示（k = 1，2，3，n）。,一、动态规划的基本概念,2、状态（state） 各阶段开始时的客观条件称为状态。 描述各阶段状态的变量称为状态变量 状态变量 sk（state variable） 状态集合 Sk（set of admissible states）,状态应具有无后效性，即：当某阶段状态给定以后，在这阶段以后过程的发展不受这

6、段以前各段状态的影响，也就是说，当前的状态是过去历史的一个完整总结，过程的过去历史只能通过当前状态去影响它的未来发展。 构造动态规划模型时，要充分注意是否满足无后效性的要求,状态变量要满足无后效性的要求,3、决策（decision） 决策：确定系统过程发展的方案。 决策的实质是关于状态的选择，是决策者从给定阶段状态出发对下一阶段状态作出的选择。 决策变量 uk（sk）（decision variable） 决策集合 Dk（sk）（set of admissible decision）,4、策略（policy） 各段决策确定后，整个问题的决策序列就构成了一个策略。 策略pk，n (sk)：从第k

7、阶段开始到最后第n阶段的决策序列，称k子策略 或后部子策略。 p1，n (s1)即为全过程策略。,5、状态转移方程（equation of state transition） 系统在阶段k处于状态sk，执行决策uk(sk)的结果是系统状态的转移，即系统由k阶段的状态sk转移到了k+1阶段的状态sk+1 ， 对于具有无后效性的多阶段决策过程,系统由阶段k到阶段k+1的状态转移完全由阶段k的状态sk和决策uk(sk)所确定，与系统过去的状态及其决策无关。系统状态的这种转移，用数学公式描述即有： sk+1 = Tk（sk，uk） k =1，2，n,6、指标函数（objective function）

8、 用来衡量策略或决策的效果的某种数量指标，就称为指标函数。 阶段指标函数 vk(sk, uk)：从状态 sk 出发，选择决策 uk 所产生的第 k 阶段指标。 过程指标函数Vk，n(sk, uk, uk+1, un)：从状态sk出发，选择决策uk, uk+1, un所产生的过程指标。,定义在整个过程（1到n阶段）上的指标函数记为： V1，n（s1，u1，s2，sn，un）， 定义在后部子过程（k到n阶段）上的指标函数记为：Vk，n（sk，uk，sn，un）， 或简记为：Vk，n（sk， pk，n ）。,多阶段决策过程数学描述,例 从A 地到D 地要铺设一条煤气管道,其中需经过两级中间站，两点之

9、间的连线上的数字表示距离，如图所示。问应该选择什么路线，使总距离最短？,A,B1,B2,C1,C2,C3,D,2,4,3,3,3,3,2,1,1,1,4,二、最短路问题,解：整个计算过程分三个阶段，从最后一个阶段开始。,第三阶段（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,d( B1,C1 ) + f3 (C1 ) 3+1 f2 ( B1 ) = min d( B1,C2 ) + f3 (C2 ) = m

10、in 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),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

11、,D,C1,C2,C3,B1,B2,(最短路线为B2C1 D),第一阶段（ A B ）： A 到B 有二条路线。,f1(A)1 = d(A, B1 ) f2 ( B1 ) 246 f1 (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,A,B1,B2,C1,C2,C3,D,2,4,3,3,3,3,2,1,1

12、,1,4,D,C1,C2,C3,B1,B2,A,最短路线为 AB1C1 D 路长为 6,标号法,标号法：只适用于这类最优路线问题的特殊解法。 标号法是借助网络图通过分段标号来求出最优路线的一种简便、直观的方法。 通常标号法采取“逆序求解”的方法来寻找问题的最优解，即从最后阶段开始，逐次向阶段数小的方向推算，最终求得全局最优解。,三、动态规划的基本方程,从上面的计算过程中可以看出，在求解的各个阶段，我们利用了K阶段与K+1阶段之间的递推关系：,动态规划的基本方程,基本方程（递推关系式）,假定过程的总效益（指标函数）与各阶段效益的关系为：,基本方程（递推关系式）,由于初始状态s1已知，故可逐步确定

13、出每阶段的决策及效益。,基本方程（递推关系式）,假定过程的总效益（指标函数）与各阶段效益的关系为：,四、动态规划的基本思想,基本思想总结：例最短路线问题 1、划分阶段。 2、求解从边界条件开始，逆向逐段递推。 3、每段的最优是从全局考虑的，并非仅考虑本阶段。,基本思想： 动态规划方法的关键:正确地写出基本方程。 1、将问题的过程划分为多个相互联系的多阶段决策过程，恰当地选取状态变量和决策变量及定义最优指标函数，把问题转化成一组同类型的子问题。 2、从边界条件开始，逆过程行进方向，逐段递推寻优。 3、在每个子问题求解时，均利用它前面已求出的子问题的最优化结果依次进行，最后一个子问题所得的最优解，

14、就是整个问题的最优解。,五、动态规划的最优性原理,在多阶段决策过程中，动态规划方法是既把当前的一段和未来的各段分开，又把当前效益和未来效益结合起来考虑的一种最优化方法。 因此，每阶段决策的选取是从全局来考虑，与该段的最优选择一般是不同的。 动态规划方法的基本思想体现了 多阶段性、无后效性、递归性、总体优化性。,Bellman 最优化原理： “一个过程的最优策略具有这样的性质， 即无论开始的状态及决策如何，对先前的决策所形成的状态而言，余下的诸决策必构成最优策略” 简言之，一个最优策略的子策略总是最优的。,六、动态规划求解方法,逆推解法（Backward Induction Method） 将寻

15、优过程看做连续递推的过程，从最终阶段开始，逆着实际决策过程的进展方向逐段求解，在每一段求解中都要利用刚刚求解完那段的结果，直到初始阶段求出结果回到始点为止。 顺推解法（Forward Induction Method） 从初始阶段向前递推，直到最终阶段为止。 一般地，当过程的终点给定时，用顺推法比较方便。,七、建立 动态规划 模型,建立动态规划模型的步骤： 1、正确、明确地划分阶段 k， k =1，2，3，n。 依据决策过程的时间和空间的顺序关系。 2、正确选择并确定状态变量 sk 及状态集合 Sk 。 状态变量的确定有时并非显而易见，要确定它，通常可对问题作如下分析而帮助确定状态变量 a.

16、什么关系将各个阶段联系在一起？ b. 为了决定今后的最优（子）策略，需要事件现状的哪些信息？,3、确定决策变量 uk 及决策集合 Dk（sk）。 4、写出状态转移方程 sk+1 = Tk（sk，uk）。 5、定义阶段指标值（函数） vk（sk，uk）。 6、定义第 k至 n 阶段（后部子过程）的最优指标（目标）函数fk（sk）。 7、作出动态规划结构图：,8、建立动态规划基本方程：（逆序递推方程）,9、逆序递推求解动态规划基本方程。 求出最优决策序列 u*n，u*n-1，u*2，u*1 10、顺序确定最优策略。 p*1,n = u*1，u*2，u*n ,3 动态规划的应用,1. 资源分配问题

17、2.机器负荷分配问题 3.背包问题 4. 生产与存贮问题 5.系统可靠性问题,1. 资源分配问题,分配问题就是将一定数量的一种或者若干种资源，适当地分配给若干个使用者，而使目标函数为最优。 设有某种原料，总数量为a， 若分配数量 xi用于生产i 种产品，收益为gi(xi)，问应如何分配，才能使n种产品的总收入最大？,数学模型如下：,可将它看作一个多阶段决策问题， 用动态规划方法求解。,设： 决策变量xk:投资第k个项目的资金数 状态变量sk：分配用于生产第k种产品至第n种产品的原料数量。 状态转移方程： sk+1=sk-xk。,最优值函数fk(sk):投资第k至n项所得的最大收益数。 动态规划

18、基本方程：,利用这个递推关系式进行逐段计算，最后求得f1(a), 即为所求问题的最大总收入,例1 某工业部门根据国家计划的安排，拟将某种高效的设备5台分配给所属的甲、乙、丙三个工厂，各工厂若获得这种设备之后，可以为国家提供的盈利如表所示。 问这5台设备如何分配给工厂才能使国家得到的盈利最大。,盈利表,解：将问题按工厂分3个阶段。 sk:分配给第k个工厂到第n个工厂的设备台数。 xk:分配给第k个工厂的设备台数。 sk+1= sk- xk:分配给第k+1个工厂到第n个工厂的设备台数。,vk(xk, sk):xk台设备分到第k个工厂所得的盈利值。 fk(sk):sk台设备分配给第k个工厂到第n个工

19、厂所得到的最大盈利值。 因而可以写出递推关系式为：,逆序法： 当k=3时， 设将s3台设备（s3 =0，1，2，3，4，5）全部分配给工厂丙时，则最大盈利值为：,因为此时只有一个工厂，有多少设备就全部分配给丙工厂，故它的盈利值就是该段的最大盈利值， 其数值计算如表7-2所示：,表7-2,当k=2时： 把s2台设备分配给工厂乙和工厂丙时， 则对每个x2值，有一种最优的分配方案， 使最大盈利值为：,表7-3,当k=1时： 设把s1(s1=5)台设备分配给工厂甲、工厂乙和工厂丙时，则最大盈利值为：,表7-4,最优分配方案有两个： x1*=0，根据s2=s1-x1*=5-0=5,查表7-3知，x2*=

20、2； s3=s2-x2*=5-2=3,查表7-2知x3*= s3=3， 即：甲工厂0台；乙工厂2台；丙工厂3台。 x1*=2，根据s2=s1-x1*=5-2=3,查表7-3知，x2*=2； s3=s2-x2*=3-2=1,查表7-2知x3*= s3=1， 即：甲工厂2台；乙工厂2台；丙工厂1台。,2.机器负荷分配问题,逆推求解,状态变量为,例3 设有n种物品，每一种物品数量无限。第i种物品每件重量为wi公斤，每件价值ci元。现有一只可装载重量为W公斤的背包，求各种物品应各取多少件放入背包，使背包中物品的价值最高。,3.背包问题,这个问题可以用整数规划模型来描述。 设x i为第 i 种 物品装入

21、背包的件数（i =1, 2, , n），背包中物品的总价值为z，则 Max z = c1x1+c2x2+ +cnxn s.t. w1x1+w2x2+wnxnW x1, x2, , xn0 且为整数。,下面用动态规划逆序解法求解它。设 阶段变量k：第k次装载第k种物品（k=1, 2, , n） 状态变量sk：第k次装载时背包还可以装载的重量； 决策变量uk = xk：第k次装载第k种物品的件数； 决策允许集合：Dk(sk) = xk | 0 xksk/wk，xk为整数；,状态转移方程： sk+1 = sk wkxk； 阶段指标： vk = ckxk； 最优过程指标函数fk(sk)：第k到n阶段容

22、许装入物品的最大使用价值； 递推方程： fk(sk) = max ckxk+fk+1(sk+1) = max ckxk+fk+1(sk wkxk)； xDk(sk) 终端条件： fn+1(sn+1) = 0。,实际上，背包问题我们也可以用整数规划来求解，如果背包携带物品重量的限制为W公斤，这N种物品中第i种物品的重量为 ，价值为 ，第i种物品的总数量的 ，我们可以设 表示携带第i种物品的数量，则其数学模型为： S.T. 且为整数。 我们不妨用此模型去求解例3，也一定得出同样的结果。,例4. 某公司为主要电力公司生产大型变压器，由于电力 采取预订方式购买，所以该公司可以预测未来几个月的需求 量。

23、为确保需求，该公司为新的一年前四个月制定一项生产 计划，这四个月的需求如表75所示。 生产成本随着生产数量而变化。调试费为4，除了调度费 用外，每月生产的头两台各花费为2，后两台花费为1。最大 生产能力每月为4台，生产成本如表76所示。 表75,4. 生产与存贮问题,表76 每台变压器在仓库中由这个月存到下个月的储存费为1， 仓库的最大储存能力为3台，另外，知道在1月1日时仓库里存 有一台变压器，要求在4月30日仓库的库存量为零。试问该公 司应如何制定生产计划，使得四个月的生产成本和储存总费 用最少？ 解：我们按月份来划分阶段，第i个月为第i阶段：（i=1,2,3,4). 设 为第k阶段期初库存量； k=1,2,3,4,为第k阶段生产量； k=1,2,3,4 为第k阶段需求量； k=1,2,3,4，这已在表7-5 中告诉我们。 因为下个月的库存量等于上个月的库存量加上个月的 产量减去上个月的需求量，我们就得到了如下状态转移方 程： 因为 ，故有 因为 ，故有,由于必须要满足需求，则有 通过移项得到 另一方面，第k阶段的生产量 必不大于同期的生产能力 （4台），也不大于第k阶段至第四阶段的需求之和与第k阶段 期初库存量