ch8动态规划.ppt

《ch8动态规划.ppt》由会员分享，可在线阅读，更多相关《ch8动态规划.ppt（60页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第八章 动态规划Dynamic Programming,8.1 动态规划数学模型Mathematical Model of DP 8.2 资源分配问题 Resource Assignment Problem8.3 生产与存储问题Production and inventory problem8.4 背包问题 Knapsack Problem8.5 其它动态规划模型 Other Model of DP,运筹学Operations Research,8.1 动态规划数学模型Mathematical Model of DP,v2,v3,v4,v7,v5,v9,v6,v8,v10,2,8,5,12,1

2、3,10,7,10,13,11,2,8,6,5,8,8,5,4,0,5,8,4,7,【例8-1】最短路径问题 图81表示从起点A到终点E之间各点的距离。求A到E的最短路径。,图81,v1,第1阶段,第2阶段,第3阶段,第4阶段,阶段：,第5阶段,12,17,14,20,19,2019年10月22日星期二,2,3,4,7,5,9,6,8,10,2,8,5,12,13,10,7,10,13,11,2,8,6,5,8,8,5,4,图82,1,第1阶段,第2阶段,第3阶段,第4阶段,阶段：,第5阶段,用WinQSB软件计算时,需要对状态重新编号,如下图所示.,8.1 动态规划数学模型Mathemati

3、cal Model of DP,2019年10月22日星期二,1,2,3,4,8,5,7,6,9,10,2,8,5,12,13,10,M,10,4,13,11,11,2,8,6,5,8,8,6,4,用WinQSB软件计算时,当某状态没有路到下阶段某状态时，添加一条虚拟决策（线条），距离很大，如下图点3到点5.,8.1 动态规划数学模型Mathematical Model of DP,2019年10月22日星期二,动态规划问题具有以下基本特征,1. 问题具有多阶段决策的特征。阶段可以按时间划分，也可以按空间划分。,2. 每一阶段都有相应的“ 状态”与之对应。,3. 每一阶段都面临一个决策，选择不

4、同的决策将会导致下一阶段不同的状态，同时，不同的决策将会导致这一阶段不同的目标函数值。,4. 每一阶段的最优解问题可以递归地归结为下一阶段各个可能状态的最优解问题，各子问题与原问题具有完全相同的结构。能否构造这样的递推归结，是解决动态规划问题的关键。这种递推归结的过程，称为“ 不变嵌入”。,8.1 动态规划数学模型Mathematical Model of DP,2019年10月22日星期二,5 . 状态具有无后效性 当某阶段状态确定后，此阶段以后过程的发展不受此阶段以前各阶段状态的影响。如下图所示：,C2,9,0,8.1 动态规划数学模型Mathematical Model of DP,20

5、19年10月22日星期二,动态规划基本原理是将一个问题的最优解转化为求子问题的最优解，研究的对象是决策过程的最优化，其变量是流动的时间或变动的状态，最后到达整个系统最优。,基本原理一方面说明原问题的最优解中包含了子问题的最优解，另一方面给出了一种求解问题的思路，将一个难以直接解决的大问题，分割成一些规模较小的相同子问题，每一个子问题只解一次，并将结果保存起来以后直接引用，避免每次碰到时都要重复计算，以便各个击破，分而治之，即分治法，是一种解决最优化问题的算法策略。,动态规划求解可分为三个步骤：分解、求解与合并。,8.1 动态规划数学模型Mathematical Model of DP,2019

6、年10月22日星期二,（1）阶段(Stage)：表示决策顺序的时段序列，阶段可以按时间或空间划分，阶段数k可以是确定数、不定数或无限数,8.1.2基本概念,（3）决策（Decision）xk：从某一状态向下一状态过度时所做的选择。决策变量记为xk，xk是所在状态sk的函数。 在状态sk下，允许采取决策的全体称为决策允许集合，记为Dk(sk)。各阶段所有决策组成的集合称为决策集。,（2）状态（State）：描述决策过程当前特征并且具有无后效性的量。状态可以是数量，也可以是字符，数量状态可以是连续的，也可以是离散的。每一状态可以取不同值，状态变量记为sk。各阶段所有状态组成的集合称为状态集。,8.

7、1 动态规划数学模型Mathematical Model of DP,2019年10月22日星期二,(4) 策略(Strategy)：从第1阶段开始到最后阶段全过程的决策构成的序列称为策略，第k阶段到最后阶段的决策序列称为子策略。,（5）状态转移方程(State transformation function)：某一状态以及该状态下的决策，与下一状态之间的函数关系，记为sk+1=T(sk,xk),（6）指标函数或收益函数(Return function)：是衡量对决策过程进行控制的效果的数量指标，具体可以是收益、成本、距离等指标。分为k阶段指标函数、k子过程指标函数及最优指标函数。,8.1 动

8、态规划数学模型Mathematical Model of DP,2019年10月22日星期二,k阶段指标函数,从k阶段状态sk出发，选择决策xk所产生的第k阶段指标，称为k阶段指标函数,记为vk(sk,xk)。,从k阶段状态sk出发，选择决策xk,xk+1,xn所产生的过程指标，称为k子过程指标函数或简称过程指标函数，记为Vk(sk,xk,xk+1,xn)或Vk，n为阶段数。,过程指标函数,最优指标函数,从k阶段状态sk出发，对所有的子策略，最优的过程指标函数称为最优指标函数，记为fk(sk)，通常取Vk的最大值或最小值。,（Optoptimization表示“max”或“min”,8.1 动

9、态规划数学模型Mathematical Model of DP,2019年10月22日星期二,动态规划要求过程指标满足递推关系 ，即,(8-2),8.1 动态规划数学模型Mathematical Model of DP,2019年10月22日星期二,动态规划数学模型由式(8-4)或(8-6)、边界条件及状态转移方程构成。如连和形式的数学模型,8.1 动态规划数学模型Mathematical Model of DP,2019年10月22日星期二,对于可加性指标函数，上式可以写为,上式中“ opt”表示“ max”或“ min”。对于可乘性指标函数，上式可以写为,上式称为动态规划最优指标的递推方程

10、，是动态规划的基本方程。,终端条件：为了使以上的递推方程有递推的起点，必须要设定最优指标的终端条件，即确定最后一个状态n下最优指标fn(sn)的值。,8.1 动态规划数学模型Mathematical Model of DP,2019年10月22日星期二,用逆序法列表求解例8-1,k=n=5 时，f5(v10)0,k=4，递推方程为,8.1 动态规划数学模型Mathematical Model of DP,2019年10月22日星期二,k=3，递推方程为,表8-2,8.1 动态规划数学模型Mathematical Model of DP,2019年10月22日星期二,k=2，递推方程为,表8-3

11、,8.1 动态规划数学模型Mathematical Model of DP,2019年10月22日星期二,k=1，递推方程为,表8-4,最优值是表8-4中f1(s1)的值，从v1到v10的最短路长为19。最短路线从表8-4到表8-1回朔，查看最后一列最优决策，得到最短路径为：,v1 v2 v5 v7 v10,8.1 动态规划数学模型Mathematical Model of DP,8.2 资源分配问题Resource Assignment Problem,2019年10月22日星期二,【例8-2】公司有资金8万元，投资A、B、C三个项目，一个单位投资为2万元。每个项目的投资效益率与投入该项目的

12、资金有关。三个项目A、B、C的投资效益(万元)和投入资金（万元）的关系见表8-5。求对三个项目的最优投资分配，使总投资效益最大。,8.2 资源分配问题Resource Assignment Problem,表8-5,【解】设xk为第k个项目的投资，该问题的静态规划模型为,2019年10月22日星期二,阶段k：每投资一个项目作为一个阶段，k=1,2,3,4。k=4为虚设的阶段状态变量sk：投资第k个项目前的资金数决策变量xk：第k个项目的投资额决策允许集合：0xksk状态转移方程：sk+1=skxk阶段指标：vk(sk，xk)见表8-5中的数据,递推方程：,终端条件：f4(s4)=0数学模型为,

13、8.2 资源分配问题Resource Assignment Problem,2019年10月22日星期二,k=4，终端条件f4(s4)=0。 k=3，0x3s3，s4=s3x3,8.2 资源分配问题Resource Assignment Problem,2019年10月22日星期二,k=2，0x2s2，s3=s2x2,8.2 资源分配问题Resource Assignment Problem,2019年10月22日星期二,k=1，0x1s1，s2=s1x1,最优解为:s1=8, x1*=0, s2=s1x1*=8, x2*=4, s3=s2x2*=4, x3*=4, s4=s3x3*=0。投资

14、的最优策略是，项目A不投资，项目B投资4万元，项目C投资4万元，最大效益为48万元,8.2 资源分配问题Resource Assignment Problem,2019年10月22日星期二,【例8-3】某种设备可在高低两种不同的负荷下进行生产，设在高负荷下投入生产的设备数量为x,产量为g=10x，设备年完好率为a=0.75；在低负荷下投入生产的设备数量为y，产量为h=8y，年完好率为b=0.9。假定开始生产时完好的设备数量s1=100。制定一个五年计划，确定每年投入高、低两种负荷下生产的设备数量，使五年内产品的总产量达到最大。,阶段k：运行年份（k=1,2,3,4,5,6），k=1表示第一年初

15、，k=6表示第五年末（即第六年初）；状态变量sk：第k年初完好的机器数（k=1,2,3,4,5,6），也是第k1年末完好的机器数，其中s6表示第五年末（即第六年初）的完好机器数，s1100。决策变量xk：第k年初投入高负荷运行的机器数；状态转移方程：sk+1=0.75xk+0.9(skxk),8.2 资源分配问题Resource Assignment Problem,2019年10月22日星期二,决策允许集合：Dk(sk)=xk|0xksk阶段指标：vk(sk，xk)=10xk+8(skxk)终端条件：f6(s6)=0递推方程：,8.2 资源分配问题Resource Assignment Pr

16、oblem,2019年10月22日星期二,8.2 资源分配问题Resource Assignment Problem,2019年10月22日星期二,8.2 资源分配问题Resource Assignment Problem,2019年10月22日星期二,因为s1=100，五年的最大总产量为f1(s1)=25.75251003443.75。由x1*= x2*= x3*=0，x4*s4，x5*s5，设备的最优分配策略是，第一年至第三年将设备全部用于低负荷运行，第四年和第五年将设备全部用于高负荷运行。每年投入高负荷运行的机器数以及每年初完好的机器数为：,s1=100x1*=0,s2=0.75x1+0

17、.9(s1x1)=90x2*=0,s3=0.75x2+0.9(s2x2)=81x3*= 0， s4=0.75x3+0.9(s3x3)=73x4*= s4=73， s5=0.75x4+0.9(s4x4)=55x5*= s5=55， s6=0.75x5+0.9(s5x5)=41第五年末还有41台完好设备。,8.2 资源分配问题Resource Assignment Problem,2019年10月22日星期二,一般地，设一个周期为n年，高负荷生产时设备的完好率为a，单台产量为g；低负荷完好率为b，单台产量为h。若有t满足,则最优设备分配策略是：从1t1年，年初将全部完好设备投入低负荷运行，从tn年

18、，年初将全部完好设备投入高负荷运行，总产量达到最大 .,在例8-3中，n=5，a=0.75，b=0.9，g=10，h=8，(g-h)/g(b-a)=1.3333式(8-7)的求和式是完好率a的i次方累加.由a0=11.3333a0+a11.75知，nt10，t=4，则13年低负荷运行，45年为高负荷运行,8.2 资源分配问题Resource Assignment Problem,(8-7),8.3 生产与存储问题Production and inventory problem,2019年10月22日星期二,8.3 生产与存储问题Production and inventory problem,

19、【8-4】一个工厂生产某种产品，16月份生产成本和产品需求量的变化情况见表8-9,表8-9,没有生产准备成本，单位产品一个月的存储费为hk0.6元，月底交货。分别求下列两种情形6个月总成本最小的生产方案。（1）1月初与6月底存储量为零，不允许缺货，仓库容量为S=50件，生产能力无限制；（2）其它条件不变，1月初存量为10,2019年10月22日星期二,8.3 生产与存储问题Production and inventory problem,【解】动态规划求解过程如下。阶段k：月份，k=1,2,7状态变量sk：第k个月初的库存量决策变量xk：第k个月的生产量状态转移方程：sk+1=sk+xkdk,

20、决策允许集合:,阶段指标：,终端条件：f7(s7)=0, s7=0,递推方程：,2019年10月22日星期二,8.3 生产与存储问题Production and inventory problem,当k=6时，因为s7=0，有,当k=5时，,由于s550，则当25s50时x5的值取“0”，决策允许集合为,2019年10月22日星期二,8.3 生产与存储问题Production and inventory problem,k=4时，,决策允许集合为,2019年10月22日星期二,8.3 生产与存储问题Production and inventory problem,显然该决策不可行,x5=0，s

21、4+x4=65d4+d5，s5=s4+x4d4=65-40=25，与s525矛盾。因此有,k=3，当0s440时，,2019年10月22日星期二,8.3 生产与存储问题Production and inventory problem,当40s450时，,当k=2时，由,x2的决策允许集合为,2019年10月22日星期二,8.3 生产与存储问题Production and inventory problem,当k=1时，由,只要期初存量s120，则x1的决策允许集合为,(1)期初存储量s1=0，由各阶段的最优决策xj*及状态转移方程，回朔可求出最优策略。,2019年10月22日星期二,8.3 生

22、产与存储问题Production and inventory problem,x1=20， s2=s1+x1d1=0+20200，x2=80， s3=s2+x2d2=0+803050，x3=855035， s4=s3+x3d3=50+35355040，x40， s5=500401025，x525s515， s6=1015250，x645。 总成本为2876,(2)期初存储量s1=10，与前面计算类似，得到x110，x280，x335，x40，x515，x645。,16月份生产、存储详细计划表见表8-10所示。,2019年10月22日星期二,8.3 生产与存储问题Production and i

23、nventory problem,表8-10,2019年10月22日星期二,8.3 生产与存储问题Production and inventory problem,8.4 背包问题Knapsack Problem,2019年10月22日星期二,8.4 背包问题Knapsack Problem,背包问题数学模型为,式中：ck为第k种物品的单位价值，wk是第k种物品的单位重量或体积，W是背包的重量或体积限制。动态规划的有关要素如下。阶段k：第k次装载第k种物品（k=1,2,n）状态变量sk：第k次装载时背包还可以装载的重量(或体积)决策变量xk：第k次装载第k种物品的件数决策允许集合：Dk(sk)

24、=dk|0 xksk/wk，xk为整数状态转移方程：sk+1=skwkxk阶段指标：vk=ckxk,2019年10月22日星期二,8.4 背包问题Knapsack Problem,递推方程：,终端条件：fn1(sn1)=0,【例8-5】用动态规划方法求解下列整数规划,【解】终端条件： f4(x4)=0,k=3时，递推方程,2019年10月22日星期二,8.4 背包问题Knapsack Problem,表8-11,最优决策是；s3为04时，x30，s3为59时，x31，s310时，x32。,k=2时，递推方程,2019年10月22日星期二,8.4 背包问题Knapsack Problem,表8-

25、12,2019年10月22日星期二,第2阶段的最优决策见表8-13,表8-13,k=1时，递推方程,8.4 背包问题Knapsack Problem,2019年10月22日星期二,s110，w1=3，D1(s1)=0，1，2，3，计算结果见表8-14,表8-14,由表8-14、8-13、8-11，得到两个最优解：X1（0，5，0），X2（2，2，0），最优值Z200。,8.4 背包问题Knapsack Problem,8.5 其它动态规划模型 Other Model of DP,2019年10月22日星期二,8.5 其它动态规划模型 Other Model of DP,8.5.1求解线性规划模

26、型,【例8-6】用动态规划方法求解下列线性规划,【解】首先将问题转化为动态规划模型,阶段数为3，决策变量为xk，状态变量为第k阶段初各约束条件右端常数的剩余值，用s1k和s2k表示，状态转移方程为,s1,k+1=s1ka1kxk，s2,k+1=s2ka2kxk,终端条件,2019年10月22日星期二,8.5 其它动态规划模型 Other Model of DP,k=2时,决策变量x2的允许集合,k=3时,决策变量x3的允许集合,2019年10月22日星期二,8.5 其它动态规划模型 Other Model of DP,状态转移方程为,2019年10月22日星期二,8.5 其它动态规划模型 Ot

27、her Model of DP,k1时，决策变量x1的允许集合,状态转移方程,最优解:,2019年10月22日星期二,8.5 其它动态规划模型 Other Model of DP,8.5.1求解非线性规划模型,【例8-7】用动态规划方法求解下列非线性规划,【解】阶段数为3，决策变量为xk，状态变量sk为第k阶段初约束条件右端常数的剩余值，状态转移方程为sk+1=skakxk，阶段指标是xk，递推方程为,2019年10月22日星期二,8.5 其它动态规划模型 Other Model of DP,终端条件,k3时，决策变量允许集合,递推方程,2019年10月22日星期二,8.5 其它动态规划模型

28、Other Model of DP,k2时，决策变量允许集合,状态转移方程s3=s25x2,递推方程,2019年10月22日星期二,8.5 其它动态规划模型 Other Model of DP,k1时，决策变量允许集合,状态转移方程s2=20x1,递推方程,得到最优解,2019年10月22日星期二,8.5 其它动态规划模型 Other Model of DP,8.5.3设备更新问题,设备更新问题在第6章的例6.8曾用Dijkstra算法求解，也能用动态规划方法求解。设一台设备已使用了(役龄)T年，对一台使用寿命为n年的设备，怎样制定在n年中每年是更新(Keep)还是继续使用(Replace)策

29、略，使n年的总收益最大或总成本最低。下面以总成本最低为标准讨论设备更新的动态规划求解方法。,P(t)：第t年新设备的购置成本，t=0，1，2，n。C(t)是设备第t年的维修费用。这里的t从T年后开始计算，t=0，1，2，n，新设备的役龄为t=0。如设备已使用了两年(T=2)，继续使用时第1年t等于0，不是等于1。S(t)为旧设备第t年出售的价格；R(t)为在n年末，役龄为t的设备残值；,2019年10月22日星期二,阶段k：设备运行年份；状态变量sk：设备的役龄t；决策变量xk：,8.5 其它动态规划模型 Other Model of DP,状态转移方程,阶段指标是更新或继续使用的总成本：,2019年10月22日星期二,8.5 其它动态规划模型 Other Model of DP,递推方程,终端条件,fn(t)=R(t),