运筹08(第八章动态规划)ppt课件.ppt

《运筹08(第八章动态规划)ppt课件.ppt》由会员分享，可在线阅读，更多相关《运筹08(第八章动态规划)ppt课件.ppt（58页珍藏版）》请在三一办公上搜索。

1、2022/11/26,1,运筹学OPERATIONS RESEARCH,2022/11/26,2,第八章 动态规划,1多阶段决策最优化问题举例2基本概念、基本方程与最优化原理3离散确定性动态规划求解4离散随机性动态规划求解5一般数学规划模型的动态规划解法,2022/11/26,3,1多阶段决策过程最优化问题举例,例1 最短路径问题 下图表示从起点A到终点E之间各点的距离。求A到E的最短路径。,B,C,B,D,B,C,D,E,C,4,1,2,3,1,2,3,1,2,3,2,2,1,6,4,7,2,4,8,3,8,6,7,5,6,1,10,6,3,7,5,1,2022/11/26,4,用穷举法的计

2、算量: 如果从A到E的站点有k个，除A、E之外每站有3个位置则总共有3k-12条路径； 计算各路径长度总共要进行 (k+1) 3k-12次加法以及3k-12-1次比较。随着 k 的值增加时，需要进行的加法和比较的次数将迅速增加； 例如当 k=20时，加法次数为 4.25508339662271015 次，比较 1.37260754729771014 次。若用1亿次/秒的计算机计算需要约508天。,2022/11/26,5,讨论： 1、求从A到E的最短路径问题，可以转化为四个性质完全相同，但规模较小的子问题，即分别从Di 、Ci、Bi、A到E的最短路径问题。 第四阶段：两个始点D1和D2，终点只

3、有一个； 分析得知：从D1和D2到E的最短路径唯一。,2022/11/26,6,第三阶段：有三个始点C1，C2，C3，终点有D1，D2，对始点和终点进行分析和讨论分别求C1，C2，C3到D1，D2 的最短路径问题： 表-2 分析得知：如果经过C1，则最短路为C1-D2-E； 如果经过C2，则最短路为C2-D2-E； 如果经过C3，则最短路为C3-D1-E。,2022/11/26,7,第二阶段：有4个始点B1,B2,B3,B4，终点有C1,C2,C3。对始点和终点进行分析和讨论分别求B1,B2,B3,B4到C1,C2,C3 的最短路径问题： 表-3 分析得知：如果经过B1，则走B1-C2-D2-

4、E； 如果经过B2，则走B2-C3-D1-E； 如果经过B3，则走B3-C3-D1-E； 如果经过B4，则走B4-C3-D1-E。,2022/11/26,8,第一阶段：只有1个始点A，终点有B1,B2,B3,B4 。对始点和终点进行分析和讨论分别求A到B1,B2,B3,B4的最短路径问题： 表10-4最后，可以得到：从A到E的最短路径为A B4 C3 D1 E,2022/11/26,9,以上计算过程及结果，可用图2表示，可以看到，以上方法不仅得到了从A到D的最短路径，同时，也得到了从图中任一点到E的最短路径。 以上过程，仅用了22次加法，计算效率远高于穷举法。,B,C,B,D,B,C,D,E,

5、C,4,1,2,3,1,2,3,1,2,3,3,2,1,6,4,7,2,4,8,3,8,6,7,5,1,6,10,6,0,10,6,12,11,11,12,13,14,14,12,7,5,1,2,2022/11/26,10,动态规划是用来解决多阶段决策过程最优化的一种方法。 多阶段决策：是动态决策问题的一种特殊形式； 系统的动态过程可以按照时间等进程分为状态相互联系 而又相互区别的各个阶段； 每个阶段都要进行决策,目的是使整个过程的决策 达到最优效果,2022/11/26,11,动态规划问题具有以下基本特征,1. 问题具有多阶段决策的特征。阶段可以按时间划分，也可以按空间划分。,2. 每一阶段

6、都有相应的“状态”与之对应。,3. 每一阶段都面临一个决策，选择不同的决策将会导致下一阶段不同的状态，同时，不同的决策将会导致这一阶段不同的目标函数值。,4. 每一阶段的最优解问题可以递归地归结为下一阶段各个可能状态的最优解问题，各子问题与原问题具有完全相同的结构。能否构造这样的递推归结，是解决动态规划问题的关键。这种递推归结的过程，称为“ 不变嵌入”。,2022/11/26,12,5 . 状态具有无后效性 当某阶段状态确定后，此阶段以后过程的发展不受此阶段以前各阶段状态的影响。,动态规划基本原理是将一个问题的最优解转化为求子问题的最优解，研究的对象是决策过程的最优化，其变量是流动的时间或变动

7、的状态，最后到达整个系统最优。,基本原理一方面说明原问题的最优解中包含了子问题的最优解，另一方面给出了一种求解问题的思路，将一个难以直接解决的大问题，分割成一些规模较小的相同子问题，每一个子问题只解一次，并将结果保存起来以后直接引用，避免每次碰到时都要重复计算，以便各个击破，分而治之，即分治法，是一种解决最优化问题的算法策略。,动态规划求解可分为三个步骤：分解、求解与合并。,2022/11/26,13,例2 资源分配问题 设有某种机器数台，用于完成两类工作A，B。由于机器使用后有一定的损坏率，所以每年初的机器数量是变化的；A、B两项工作产生的收益也不同。如何合理的分配机器的使用，可使得三年的总

8、收益最大? 假设第k年年初完好机器数是SK，用于A生产的机器数是XK，则用于B生产的机器数是（SK- XK）； 用于A工作的设备的完好率是：a%，用于B工作的设备的完好率是：b%。则下一年初的完好机器数是SK+1= a% XK+ b% （SK- XK）第k年的收益： h(XK)+ g(SK- XK),2022/11/26,14,例3 背包问题 设有n种物品，每一种物品数量无限。第i种物品每件重量为wi公斤，每件价值ci元。现有一只可装载重量为W公斤的背包，求各种物品应各取多少件放入背包，使背包中物品的价值最高。 这个问题可以用整数规划模型来描述。设xi为第i种物品装入背包的件数（i =1, 2

9、, , n），背包中物品的总价值为z，则 Max z = c1x1+c2x2+ +cnxn s.t. w1x1+w2x2+wnxnW x1, x2, , xn0 且为整数。,2022/11/26,15,一、基本概念： 1、阶段(stage)k：表示决策顺序的离散的量，阶段可以按时间或空间划分。(顺序编号法、逆序编号法） 2、状态(state)sk：反应前一阶段决策的结果，又是本阶段组作决策的依据和出发点（能确定地表示决策过程当前特征的量）。状态可以是数量，也可以是字符，数量状态可以是连续的，也可以是离散的。 3、决策(decision)xk：从某一状态向下一状态过渡时所做的选择。决策是所在状态

10、的函数，记为xk(sk)。 决策允许集合Dk(sk)：在状态sk下，允许采取决策的全体 xk(sk)Dk(sk),2基本概念、基本方程与最优化原理,2022/11/26,16,4、策略Pk,n(sk)：从第k阶段开始到最后第n阶段的决策序列，称k子策略。P1,n(s1)即为全过程策略。5、状态转移方程 Sk+1=Tk(Sk, Xk)：某一状态以及该状态下的决策，与下一状态之间的函数关系。,6、指标函数或收益函数(Return function)：是衡量对决策过程进行控制的效果的数量指标，具体可以是收益、成本、距离等指标。分为k阶段指标函数、k子过程指标函数及最优指标函数。,k阶段指标函数,从k

11、阶段状态sk出发，选择决策xk所产生的第k阶段指标，称为k阶段指标函数,记为vk(sk,xk)。,2022/11/26,17,从k阶段状态sk出发，选择决策xk,xk+1,xn所产生的过程指标，称为k子过程指标函数或简称过程指标函数，记为Vk(sk,xk,xk+1,xn)或Vk，n为阶段数。,过程指标函数,最优指标函数,从k阶段状态sk出发，对所有的子策略，最优的过程指标函数称为最优指标函数，记为fk(sk)，通常取Vk的最大值或最小值。,（Optoptimization表示“max”或“min”,2022/11/26,18,动态规划要求过程指标满足递推关系 ，即,(8-2),2022/11/

12、26,19,动态规划数学模型由式(8-4)或(8-6)、边界条件及状态转移方程构成。如连和形式的数学模型,2022/11/26,20,对于可加性指标函数，上式可以写为,上式中“ opt”表示“ max”或“ min”。对于可乘性指标函数，上式可以写为,上式称为动态规划最优指标的递推方程，是动态规划的基本方程。,终端条件：为了使以上的递推方程有递推的起点，必须要设定最优指标的终端条件，即确定最后一个状态n下最优指标fn(sn)的值。,2022/11/26,21,三、最优化原理 作为整个过程的最优策略具有如下性质： 不管在此最优策略上的某个状态以前的状态和决策如何，对该状态来说，以后的所有决策必定

13、构成最优子策略。就是说，最优策略的任意子策略都是最优的。,2022/11/26,22,用逆序法列表,k=n=5 时，f5(v10)0,k=4，递推方程为,2022/11/26,23,k=3，递推方程为,表8-2,2022/11/26,24,k=2，递推方程为,表8-3,2022/11/26,25,k=1，递推方程为,表8-4,最优值是表8-4中f1(s1)的值，从v1到v10的最短路长为19。最短路线从表8-4到表8-1回朔，查看最后一列最优决策，得到最短路径为：,v1 v2 v5 v7 v10,2022/11/26,26,例4.有9支巡逻队负责3个要害部门A、B、C的巡逻，每部位可派2-4支

14、巡逻队，队数不同各部位可能损失有差别，如表，问各部位应各派多少队，使总预期损失最小。,3离散确定性动态规划模型求解,2022/11/26,27,解：设将向三个部位A，B，C派巡逻队作为三个阶段，K=1，2，3。,决策变量 表示向第K个部位派遣的巡逻队数。,状态变量 表示第K个阶段时可供派遣的巡逻队数量。,状态转移方程：,阶段指标函数： 派遣 支巡逻队时第K阶段产生的预期损失；,过程指标函数： 第K阶段到第3阶段的预期损失。,最优指标函数：,决策允许集合Dk(sk)=xk|2xk4,(k=1,2,3,4),2022/11/26,28,逆序解法： 边界条件,当K=3时，给C派巡逻队，,2 3 4,

15、3,2,4,5,24 -,24,2,24 22 -,22,3,24 22 21,21,4,24 22 21,21,4,2022/11/26,29,当K=2时，给B派巡逻队， ，,38+22 35+24 -,59,3,38+21 35+22 31+24,55,4,38+21 35+21 31+22,53,4,2022/11/26,30,当K=1时，给A派巡逻队， ，,最优方案：A派3支巡逻队，B派4支巡逻队，C派2支巡逻队； 或：A派4支巡逻队，B派3支巡逻队，C派2支巡逻队,18+53 14+55 10+59,69,3,4,2022/11/26,31,例5 资源分配问题 设有某种机器100，用

16、于完成两类工作A，B。由于机器使用后有一定的损坏率，所以每年初的机器数量是变化的，设用于A工作的设备的完好率是：2/3，用于B工作的设备的完好率是：9/10；A、B两项工作产生的收益与机器台数有关且分别为g(x)=10 x(万元)，h(x)=7x (万元) 。如何合理的分配机器的使用，可使得三年的总收益最大?,2022/11/26,32,解：按年份分为三个阶段，K=1，2，3；,决策变量xk表示用于生产产品A的机器数；,状态变量sk表示第K年初完好机器数；,状态转移方程：,阶段指标函数：,过程指标函数： 第K阶段到第3阶段的最大收益为,最优指标函数：,决策允许集合Dk(sk)=xk|0 xks

17、k,(k=1,2,3),sK+1=2/3 xK+0.9（sK- XK）,Vk(sk,xk)=10 xk+7(sk-xk)表示第k年的收益,2022/11/26,33,逆序解法： 边界条件f4 (s4)=0,当K=3时,第三年初分配机器x3台生产A,s3-x3台生产B,显然当x3=s3时达到最大值，因而此阶段的最优决策为x3*=s3,2022/11/26,34,当K=2时,第二年初分配机器x2台生产A,s2-x2台生产B,显然s3是关于s2,x2的状态转移，因而有,2022/11/26,35,最优方案：s1=100, x1*=0,s1x1=100,s2=90,x2*=90, s2x2*=0, s

18、3=60, x3*=60, s3x3*=0。第一年所有机器100台用于生产B， 第二年初完好机器90台；第二年所有机器90台用于生产A， 第三年初完好机器60台；第三年所有机器60台用于生产A， 第四年初完好机器40台。,当K=1时,第二年初分配机器x1台生产A,s1-x1台生产B, s1 =100,2022/11/26,36,【例】公司有资金6万元，投资A、B、C三个项目，一个单位投资为2万元。每个项目的投资效益率与投入该项目的资金有关。三个项目A、B、C的投资效益(万元)和投入资金（万元）的关系见表8-5。求对三个项目的最优投资分配，使总投资效益最大。,【解】设xk为第k个项目的投资,20

19、22/11/26,37,阶段k：每投资一个项目作为一个阶段，k=1,2,3,4。k=4为虚设的阶段状态变量sk：投资第k个项目前的资金数决策变量xk：第k个项目的投资额决策允许集合：0 xksk状态转移方程：sk+1=skxk阶段指标：vk(sk，xk)见表8-5中的数据,递推方程：,终端条件：f4(s4)=0数学模型为,2022/11/26,38,k=4，终端条件f4(s4)=0。 k=3，0 x3s3，s4=s3x3 ，s3=0，2，4，6,0246,0 0 0 0+0=0* 0 0,2 0 10 10+0=10* 10 2,4 0 28 28+0=28* 28 4,6 0 35 35+0

20、=35* 35 6,2022/11/26,39,k=2，0 x2s2，s3=s2x2 ，s2=0，2，4，6,0246,0 0 0 0 0+0=0* 0 0,0 2 0 10 0+10=10*,2 0 9 0 9+0=9,10 0,0 4 0 28 0+28=28*,2 2 9 10 9+10=19,4 0 20 0 20+0=20,28 0,0 6 0 35 0+35=35,2 4 9 28 9+28=37*,4 2 20 10 20+10=30,6 0 35 0 35+0=35,37 2,2022/11/26,40,k=1，0 x1s1，s2=s1x1，s1=6,最优解为:s1=6, x1

21、*=0, s2=s1x1=6, x2*=2, s3=s2x2*=4, x3*=4, s4=s3x3=0。投资的最优策略是，项目A不投资，项目B投资2万元，项目C投资4万元，最大效益为37万元,0 6 0 37 0+37=37*,2 4 8 28 8+28=36,4 2 15 10 15+10=25,6 0 30 0 30+0=30,37 0,2022/11/26,41,4离散随机动态规划模型求解,随机动态规划：状态转移规律不定，在给定的状态和决策下，下一阶段到达的状态是具有确定概率分布的随机变量。,第k+1阶段可能状态,Pi：在决策Xk下出现状态i的概率,Ci：在决策Xk下出现状态i时的指标函

22、数,2022/11/26,42,由于下一阶段的状态和阶段的效益值不确定，因而随机动态规划中，对指标函数进行优化时，要根据各阶段的期望效益进行优化。基本方程改写为：,其中E（）表示期望值，边界条件fn+1(sn+1)的应根据问题的具体情况确定。,2022/11/26,43,2022/11/26,44,决策变量xk：表示第K个阶段决定投产的数量。,状态转移律：,阶段指标函数：第k阶段的费用支出,最优指标函数 fk(sk) ：表示第K阶段在 Sk 状态下，做决策xk时，到最后一个阶段的最小期望费用。,允许决策集合Dk (sk)： Dk (sk)=1,2,N(当sk=1)，,Dk (sk)=0(当sk

23、=0)；,2022/11/26,45,易知：,2022/11/26,46,逆序解法： 边界条件 当K=3时，第三阶段之后的最小期望费用，,01,001500,1 1350,2 1117,3 994,4 946,5 948,0946,04,2022/11/26,47,当K=2时，第二阶段之后的最小期望费用，,01,00946,1 981,2 870,3 830,4 837,0830,03,2022/11/26,48,当K=1时，第一阶段之后的最小期望费用，s1=1,最优方案：第一期投产3台；第二期投产3台；第三期投产4台。最小期望费用796。,1,0830,1903,2819,3796,4814

24、,796,3,2022/11/26,49,5一般数学规划模型的动态规划解法,用动态规划的方法求解一般数学规划模型思想：将取定每个变量的值作为一个阶段，则有n个变量的数学规划问题，可看作是有n 个阶段的多阶段决策问题。右端向量可看成资源数，用状态变量表示约束的个数决定决策变量的维数,用动态规划的方法求解一般数学规划模型的条件：1.目标函数可以分解为单变量函数的和或积即,f(x1,x2,xn)=f1(x1)+f2(x2)+fn(xn)或f(x1,x2,xn)=f1(x1) f2(x2)fn(xn),2.约束为线性不等式，变量可以是连续变量或整数变量,2022/11/26,50,例：P212，例7,

25、用动态规划方法求解非线性规划问题。,2022/11/26,51,解：,设将确定变量 的值作为两个阶段，K=1，2。 决策变量 表示第K个变量的取值。 状态变量 表示第K个阶段初约束条件右端项的剩余值。 状态转移方程： 阶段指标函数： 确定 取值对目标函数值的贡献； 最优指标函数：具体的 边界条件,2022/11/26,52,当K=2时，第二个变量的取值为,令 ， 求其最大值,2022/11/26,53,当K=1时，第一个变量的取值为,于是,2022/11/26,54,2022/11/26,55,【例】用动态规划方法求解下列非线性规划,【解】阶段数为3，决策变量为xk，状态变量sk为第k阶段初约束条件右端常数的剩余值，状态转移方程为sk+1=skakxk，阶段指标是xk，递推方程为,2022/11/26,56,终端条件,k3时，决策变量允许集合,递推方程,2022/11/26,57,k2时，决策变量允许集合,状态转移方程s3=s25x2,递推方程,2022/11/26,58,k1时，决策变量允许集合,状态转移方程s2=20 x1,递推方程,得到最优解,