第10章动态规划课件.ppt

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

1、第十章第十章 动态规划动态规划4-1引言及内容框架引言及内容框架4-2基本概念、模型与最优化原理基本概念、模型与最优化原理4-3动态规划的应用动态规划的应用14-1引引 言言 动态规划的研究对象动态规划的研究对象 动态规划问题的特点动态规划问题的特点 静态决策问题的动态处理静态决策问题的动态处理2一、动态规划的研究对象一、动态规划的研究对象 多阶段的决策问题多阶段的决策问题1多阶段决策问题动态决策将时间作为变量的决策问题称为动态决策。其基本特点是多次决策。多阶段决策问题是一类特殊形式的动态决策问题。是指这样一类活动过程：系统的动态动态过程可以按照时间进程分为状态相互联系又相互区别的阶段，而且每

2、个阶段都进行决策，当每个阶段决策确定以后，就完全确定了一个过程确定的线路。3多阶段决策问题的典型例子多阶段决策问题的典型例子企业生产过程中，由于需求是随着时间变化的因素，因此企业为了获得全年最佳经济效益，就要在整个过程中进行逐月和逐季的根据库存和需求决定生产计划。某种机器，可以在高、低两种负荷下生产。高负荷下生产时的产量多，但每生产一个阶段的机器完好率低；低负荷下生产时的情况则相反。现在需要安排该种机器在多个阶段内的生产，问应如何决定各个阶段中机器的使用，使这个计划期内的总产量最大？4某台设备。例如汽车，刚买来时故障低，耗油少，出车时间长，处理价值和经济效益高；随着使用时间的增加则变为故障多、

3、耗油高、维修费用增加，经济效益差，使用时间越长，处理价值越低。另外每次更新都要付出更新费用。因此应如何决定设备的使用年限，使总的效益最佳？化工生产过程包括一系列的过程设备，如反映器、蒸馏塔、吸收器等，前一设备的输出是后一设备的输入。因此，应如何控制生产过程中各个设备的输出和输入，使总产量最大？5什么是动态规划？什么是动态规划？DP是OR中的一个分支，是解决多阶段决策过程最优化的一种方法或是一种分析多阶段决策过程的数学方法。这种方法可根据人们所采取的措施，一步步地控制过程的发展，来实现预定的要求。这一运筹学分支最初有美国数学家BELLMAN等人根据一类多阶段决策问题的特性，提出了解决这类问题的最

4、优化原理，并研究了许多实际问题而建立起来的。6动态规划的特点动态规划的特点优点优点许多问题用动态规划研究求解比线性规划、非线性规划更有效，特别是离散性问题，解析数学无用武之地。而动态规划成为得力工具；某些情况下，用动态规划处理不仅能定性描述分析，且可利用计算机给出求其数值解的方法。二、动态规划问题的特点二、动态规划问题的特点7缺点缺点没有统一的处理方法，求解时要根据问题的性质，结合多种数学技巧。因此实践经验及创造性思维将起重要的引导作用；“维数障碍”，当变量个数太多时，由于计算机内存和速度的限制导致问题无法解决。有些问题由于涉及的函数没有理想的性质使问题只能用动态规划描述，而不能用动态规划方法

5、求解。8不包含时间因素的决策问题称为静态决策问题，是一次性决策（如线性规划）。但若能恰当地人为引入“时段”概念，就可以把问题转化成一个多阶段决策问题，这样就能用动态规划处理了。拓宽了动态规划的应用范围。这样的例子是大量的，如最短线路问题，资源分配问题等等。三、静态决策问题的动态处理三、静态决策问题的动态处理9DP中描述多阶段决策过程的基本概念主要有：阶段和阶段变量状态和状态变量决策、决策变量和决策序列状态转移方程阶段效应和目标函数4-2 基本概念、模型与最优化原理基本概念、模型与最优化原理10把所研究的多阶段决策过程恰当地划分为若干个相互独立又相互联系的部分，每个部分称为一个阶段。事实上一个阶

6、段也就是需要作出一个决策的子问题部分。通常阶段是按照过程进行的时间和空间上的先后顺序划分的。并用阶段变量k表示。阶段数等于多段决策过程中从开始到结束所需要作出决策的数目。划分阶段的目的是便于求解。1、阶段和阶段变量、阶段和阶段变量11状态是描述系统状况所必须的信息。一般定义为某一阶段的初始点、初始位置和初始情况。状态变量必须包含在给定的阶段上确定全部允许决策所需要的信息，阶段k的状态变量表示为sk。比如：在最短路问题中，状态就是网络中各个节点。2、状态和状态变量、状态和状态变量12状态变量的取值有一定的允许范围，称为状态可能集。状态可能集可以是一个离散取值的集合，也可以是一个连续的区间，视所给

7、问题而定。状态可能集是关于状态的约束条件。状态可能集用相应阶段状态sk的大写字母Sk表示，其中skSk13决策就是决策者从本阶段出发对下一阶段状态的选择。多段决策过程的发展是用各个阶段的状态演变描述的。因此用状态描述的过程具有无后效性，因此在进行阶段决策时，只须根据当前的状态而无须考虑过去的历史。在阶段k如果给出了决策变量xk随状态变量sk变化的函数，称为决策函数，表示为：xk(sk)。3、决策和决策变量和决策序列、决策和决策变量和决策序列14决策变量的允许取值范围，称为允许决策集合。允许决策集合是决策变量的约束条件。xk的允许决策集合表示为Xk。xkXk，Xk要根据相应的状态可能集Sk并结合

8、具体问题来确定。决策序列就叫策略，策略有全过程策略和子策略之分。全过程策略是整个问题n个段决策过程依次进行的n个阶段决策构成的序列，简称策略，表示为：x1,x2,xn15从阶段k到阶段n依次进行的阶段决策构成的决策序列称为k-子策略。表示为：xk,xk+1,xn当k=1时，k-子策略就是全过程策略。在n段决策过程中，各阶段的状态可能集合和决策允许集合决定了决策的允许范围。特别，过程的初始状态不同，决策和策略也就不同，即策略是初始状态的函数。16状态转移方程表示从阶段k到阶段k+1的状态转移规律的表达式。多阶段过程的发展就是用阶段状态的演变来描述的。对具有无后效性的多阶段决策过程，系统由从阶段k

9、到阶段k+1的状态转移方程表示为：sk+1=Tk(sk,xk(sk)4、状态转移方程、状态转移方程17即阶段的状态完全由阶段的状态和决策确定，与系统过去的状态s1,s2,sk-1及其决策x1(s1),x2(s2),xk-1(sk-1)无关。Tk(sk,xk)称为变换函数或变换算子。变换函数可以分为确定型和随机型两种类型，据此形成确定型动态规划和随机型动态规划。问：状态转移方程是否一定是数学意义上的方程？18多阶段决策过程中，在阶段k状态sk执行决策xk，不仅带来系统状态的转移，而且也带来对目标函数的影响。阶段效应就是执行阶段决策时所带来的目标函数的增量。在具有无后效性的多阶段决策过程中，阶段效

10、应完全由阶段k的状态sk和决策xk决定，与阶段以前的状态和决策无关，表示为：Tk(sk,xk)5、阶段效应和目标函数、阶段效应和目标函数19多阶段决策过程关于目标函数的总效应是由各阶段的阶段效应积累形成。适应于动态规划求解的问题的目标，必须具有关于阶段效应的可分离形式、递推性。201、构模条件一个大前提：恰当的划分问题的阶段，把问题化为多阶段决策过程；四个条件：1）正确地选择状态变量能描述过程的演变特征；满足无后效性可知性各阶段状态变量的值直接和间接均为已知。2）能确定决策变量及各阶段的允许决策集合：二、二、多阶段决策过程的数学模型多阶段决策过程的数学模型213）能写出状态转移方程；4）能根据

11、题意列出阶段效应和目标函数；在明确四个条件（或四个要素）的基础上，写出动态规划基本方程。DP模型的数学表达一般形式：式中OPT指最优化，根据问题要求取Max或Min22问：动态规划模型有那些部分组成？具体的DP模型包括：四个条件和一个方程（动态规划基本方程）232、求解要求求出最优策略或最优线路求出最优目标函数值24三、三、最优化原理最优化原理最优策略具有的基本性质是：无论初始状态和初始决策如何，对于前面决策所造成的某一状态而言，下余的决策序列必须构成最优决策。2533动态规划应用动态规划应用例例1 最短路径问题最短路径问题 下图表示从起点A到终点E之间各点的距离。求A到E的最短路径。BACB

12、DBCDEC41231231232216472483867561106375126讨论：1、以上求从A到E的最短路径问题，可以转化为四个性质完全相同，但规模较小的子问题，即分别从Di、Ci、Bi、A到E的最短路径问题。第四阶段：两个始点D1和D2，终点只有一个；表10-1分析得知：从D1和D2到E的最短路径唯一。阶段4本阶段始点（状态）本阶段各终点（决策）到E的最短距离本阶段最优终点（最优决策)ED1D2106106EE27第三阶段：有三个始点C1，C2，C3，终点有D1，D2，对始点和终点进行分析和讨论分别求C1，C2，C3到D1，D2的最短路径问题：表10-2分析得知：如果经过C1，则最短

13、路为C1-D2-E；如果经过C2，则最短路为C2-D2-E；如果经过C3，则最短路为C3-D1-E。阶段3本阶段始点（状态）本阶段各终点（决策）到E的最短距离本阶段最优终点（最优决策)D1D2C1C2C38+10=187+10=17 1+10=11 6+6=125+6=116+6=12121111D2D2D128第二阶段：有4个始点B1,B2,B3,B4，终点有C1,C2,C3。对始点和终点进行分析和讨论分别求B1,B2,B3,B4到C1,C2,C3的最短路径问题：表10-3分析得知：如果经过B1，则走B1-C2-D2-E；如果经过B2，则走B2-C3-D1-E；如果经过B3，则走B3-C3-

14、D1-E；如果经过B4，则走B4-C3-D1-E。阶段2本阶段始点（状态）本阶段各终点（决策）到E的最短距离本阶段最优终点（最优决策)C1C2C3B1B2B3B42+12=144+12=164+12=167+12=19 1+11=127+11=188+11=195+11=166+11=172+11=13 3+11=141+11=1212131412C2C3C3C329第一阶段：只有1个始点A，终点有B1,B2,B3,B4。对始点和终点进行分析和讨论分别求A到B1,B2,B3,B4的最短路径问题：表10-4最后，可以得到：从A到E的最短路径为AB4C3D1E阶段1本阶段始点(状态)本阶段各终点（

15、决策）到E的最短距离本阶段最优终点(最优决策)B1B2B3B4A4+12=16 3+13=163+14=172+12=1414B430 以上计算过程及结果，可用图2表示，可以看到，以上方法不仅得到了从A到D的最短路径，同时，也得到了从图中任一点到E的最短路径。BACBDBCDEC4123123123321647248386751610601061211111213141412751231 资源分配问题资源分配问题(离散型离散型)例2.某公司拟将某种设备5台，分配给所属的甲、乙、丙三个工厂。各工厂获得此设备后，预测可创造的利润如表10-5所示，问这5台设备应如何分配给这3个工厂，使得所创造的总利

16、润为最大？表10-5盈利工厂设备台数甲厂乙厂丙厂00001354271063911114121112513111232解：将问题按工厂分为三个阶段，甲、乙、丙三个厂分别编号为1、2、3厂。设sk=分配给第k个厂至第3个厂的设备台数（k=1、2、3）。xk=分配给第k个厂设备台数。已知s1=5,并有从与的定义，可知以下我们从第三阶段开始计算。表格法表格法33 第三阶段:显然将台设备都分配给第3工厂时，也就是时，第3阶段的指标值（即第3厂的盈利）为最大，即由于第3阶段是最后的阶段，故有其中可取值为0,1,2,3,4,5。其数值计算见表106。34 表表106 012345000014 412662

17、3111134121245121253 3 动态规划的应用动态规划的应用(1)35其中表示取3子过程上最优指标值时的决策，例如在表10-6中可知当=4时，有有此时，即当时，此时取（把4台设备分配给第3厂）是最优决策，此时阶段指标值（盈利）为12，最优3子过程最优指标值也为12。第二阶段：当把台设备分配给第2工厂和第3工厂时，则对每个值，有一种最优分配方案，使最大盈利即最优2子过程最优指标函数值为 36因为上式也可写成其数值计算如表107所示。表107 0123450001045120654102301156110 1424012114110 161,2501251211611411021237

18、其中在的这一行里，当时当时，这里从表105中可知，把1台设备交给乙厂所得盈利数即可，知，这里从表106查即可知=11。同样可知当时，可知;当时，；当时，；当时，；由于，不可能分2厂5台设备，故时，栏空着不填。从这些数值中取得最大即得，即有=16。在此行中我们在取最大值的上面加一横以示区别，也可知这时的最优决策为1或2。38第一阶段：把台设备分配给第1，第2，第3厂时，最大盈利为其中可取值0,1,2,3,4,5.数值计算见表108表10-8然后按计算表格的顺序推算，可知最优分配方案有两个：1.由于，根据，查表107可知，再由，求得。即分配给甲厂0台，乙厂2台，丙厂3台。2.由于，根据，查表107

19、可01234553169+1012+513+0210,239知，再由,求得，即分配给甲厂2台，乙厂2台，丙厂1台。这两种分配方案都能得到最高的总盈利21万元。40解：将问题按工厂分为三个阶段，甲、乙、丙三个厂分别编号为1、2、3厂。设sk=分配给第k个厂至第1个厂的设备台数（k=1、2、3）。xk=分配给第k个厂设备台数。设s1=0,1,5并有s2=0,1,5s3=5以下我们从第一阶段开始计算。用解析法计算用解析法计算41 第一阶段:显然将台设备都分配给第1工厂时，也就是时，第1阶段的指标值（即第1厂的盈利）为最大，即由于第3阶段是最后的阶段，故有其中x1可取值为0,1,2,3,4,5。42第

20、二阶段：当把台设备分配给第1工厂和第2工厂时，则对每个s2值，有一种最优分配方案，使最大盈利,即最优2阶段子过程最优指标函数值为43444546第三阶段：当把s3=5台设备分配给第1工厂、第2工厂和第3工厂时，即最优3阶段子过程最优指标函数值为474849资源分配问题资源分配问题(连续型连续型)将问题划分为三个阶段将问题划分为三个阶段,设状态变量为设状态变量为s1,s2,s3,并并s3=10,取取x1,x2,x3为各阶段的决策变量为各阶段的决策变量,各阶段的指标函数按各阶段的指标函数按加法方式结合加法方式结合,令最优函数令最优函数fk(sk)表示第表示第k阶段结束状阶段结束状态为态为sk,第第1阶段至第阶段至第k阶段的最大值阶段的最大值.505152