运筹学课件Ch8动态规划.ppt

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

2、5,12,13,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,2020年8月15日星期六,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 动态规划数学模型 Mat

3、hematical Model of DP,2020年8月15日星期六,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,2020年8月15日星期六,动态规划问题具有以下基本特征,1. 问题具有多阶段决策的特征。阶段可以按时间划分，也可以按空间划分。,2. 每一阶段都有相应的“ 状态”与之对应。,3. 每一阶段都面临一个决

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

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

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

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

8、,8.1 动态规划数学模型 Mathematical Model of DP,2020年8月15日星期六,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”或“mi

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

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

11、方程为,表8-3,8.1 动态规划数学模型 Mathematical Model of DP,2020年8月15日星期六,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,2020年8月15日星期六,作业：教材P188 T2,下一节：资源分配问题,8.1 动态规划数学模型 Mathematical Model of DP,8.2 资源分配问题 Resource Ass

12、ignment Problem,2020年8月15日星期六,【例8.2】公司有资金8万元，投资A、B、C三个项目，一个单位投资为2万元。每个项目的投资效益率与投入该项目的资金有关。三个项目A、B、C的投资效益(万元)和投入资金（万元）的关系见表8-5。求对三个项目的最优投资分配，使总投资效益最大。,8.2 资源分配问题 Resource Assignment Problem,表8-5,【解】设xk为第k个项目的投资，该问题的静态规划模型为,2020年8月15日星期六,阶段k：每投资一个项目作为一个阶段，k=1,2,3,4。k=4为虚设的阶段 状态变量sk：投资第k个项目前的资金数 决策变量xk

13、：第k个项目的投资额 决策允许集合：0 xksk 状态转移方程：sk+1=skxk 阶段指标：vk(sk，xk)见表8-5中的数据,递推方程：,终端条件：f4(s4)=0 数学模型为,8.2 资源分配问题 Resource Assignment Problem,2020年8月15日星期六,k=4，终端条件f4(s4)=0。 k=3，0 x3s3，s4=s3x3,8.2 资源分配问题 Resource Assignment Problem,2020年8月15日星期六,k=2，0 x2s2，s3=s2x2,8.2 资源分配问题 Resource Assignment Problem,2020年8月

14、15日星期六,k=1，0 x1s1，s2=s1x1,最优解为: s1=8, x1*=0, s2=s1x1=8, x2*=4, s3=s2x2*=4, x3=4, s4=s3x3=0。投资的最优策略是，项目A不投资，项目B投资4万元，项目C投资4万元，最大效益为48万元,8.2 资源分配问题 Resource Assignment Problem,2020年8月15日星期六,【例8.3】某种设备可在高低两种不同的负荷下进行生产，设在高负荷下投入生产的设备数量为x,产量为g=10 x，设备年完好率为a=0.75；在低负荷下投入生产的设备数量为y，产量为h=8y，年完好率为b=0.9。假定开始生产时

15、完好的设备数量s1=100。 制定一个五年计划，确定每年投入高、低两种负荷下生产的设备数量，使五年内产品的总产量达到最大。,阶段k：运行年份（k=1,2,3,4,5,6），k=1表示第一年初，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,2020年8月15日星期六,决策

16、允许集合：Dk(sk)=xk|0 xksk 阶段指标：vk(sk，xk)=10 xk+8(skxk) 终端条件：f6(s6)=0 递推方程：,8.2 资源分配问题 Resource Assignment Problem,2020年8月15日星期六,8.2 资源分配问题 Resource Assignment Problem,2020年8月15日星期六,8.2 资源分配问题 Resource Assignment Problem,2020年8月15日星期六,因为s1=100，五年的最大总产量为f1(s1)=25.75251003443.75。 由x1*= x2*= x3*=0，x4*s4，x5*

17、s5，设备的最优分配策略是，第一年至第三年将设备全部用于低负荷运行，第四年和第五年将设备全部用于高负荷运行。每年投入高负荷运行的机器数以及每年初完好的机器数为：,s1=100 x1*=0,s2=0.75x1+0.9(s1x1)=90 x2*=0,s3=0.75x2+0.9(s2x2)=81 x3*= 0， s4=0.75x3+0.9(s3x3)=73 x4*= s4=73， s5=0.75x4+0.9(s4x4)=55 x5*= s5=55， s6=0.75x5+0.9(s5x5)=41 第五年末还有41台完好设备。,8.2 资源分配问题 Resource Assignment Problem

18、,2020年8月15日星期六,一般地，设一个周期为n年，高负荷生产时设备的完好率为a，单台产量为g；低负荷完好率为b，单台产量为h。若有t满足,则最优设备分配策略是：从1t1年，年初将全部完好设备投入低负荷运行，从tn年，年初将全部完好设备投入高负荷运行，总产量达到最大 .,在例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),2020年8月15日星期六,作业：教材P188 T1，6，8，9,8.2 资源分配问题 Resource Assignment Problem,下一节：生产与存储问题,8.3 生产与存储问题 Production and inventory problem,2020年8月15日星期六,8.3 生产与存储问题 Production and inventory problem,【8.4】一个工厂生产某种产品，16