《第五章 动态规划问题.ppt》由会员分享，可在线阅读，更多相关《第五章 动态规划问题.ppt（55页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第五章第五章 动态规划问题动态规划问题动态规划是1951年由美国学者R.Bellman等人在解决所谓多阶段决策问题时提出的一种优化方法，该方法在工程技术、企业管理和军事等方面多有着广泛的应用。许多问题用动态规划方法解决，比其他常用方法如线性规划或非线性规划等方法更为有效。特别是对于离散的问题，由于目标函数或约束条件难以用解析的方式表达时，此时，动态规划方法就成为非常有效的工具。动态规划模型的分类一般根据其状态的性质或多少来分类。动态规划有离散确定型、离散随机型、连续确定型、连续随机型、一维动态规划模型和多维动态规划模型之分。这里主要介绍一维离散确定型动态规划模型。第一节第一节 多阶段决策过程及
2、其问题举例多阶段决策过程及其问题举例一、多阶段决策过程一、多阶段决策过程在生产决策中，若某一活动过程可以分为若干相互联系的阶段，每一阶段又需要作出决策，从而使整个过程达到最好的活动效果。这种把一个问题看作是一个前后关联具有链状结构的多阶段过程（如图51所示）就称为多阶段决策过程，这种问题就称为多阶段决策问题。12n状态状态决策决策状态状态状态状态状态状态状态状态决策决策决策决策图图51二、多阶段决策问题举例二、多阶段决策问题举例例5.1 最短路问题如图52，给定一个线路网络，两点之间连线上的数字表示两点间的距离（或费用、时间等），试求一条由A到E的线路，使总距离为最短（或费用最小、时间最少等）
3、。B1AC1B2C3ED1C4C2D3D23531686673583384232图图52例5.2 生产与存储问题假设某厂某车间每月底都要供应总装车间一定数量的部件，但由于生产条件的变化，该车间每月生产单位部件所耗费的工时不同，各月份的生产量于当月的月底以前，全部要存入仓库以备后用。已知总装车间各个月份的需求量以及在加工车间生产该部件每单位数量所需工时如表51所示。设库存容量H=9，开始时库存量为2，期终库存量为0，现要求制定一个半年逐月生产计划，使得既满足需求和库存容量的限制，又使总耗费的工时最少。月月份份k0123456月需求量月需求量dk0853274单位工时单位工时ak111813172
4、010第二节第二节 动态规划的基本概念与基本方程动态规划的基本概念与基本方程一、动态规划的基本概念一、动态规划的基本概念（1）阶段）阶段对于多阶段决策问题，按问题的特点可将其划分为若干个相互联系的阶段，阶段就是问题所处的地段或时段。描述阶段的变量称为阶段变量，通常用k表示。例5.1中，阶段为问题所处的地段，且k=1，2，3，4；例5.2中，阶段为问题所处的时段（月），且k=0，1，6；（2）状态状态就是在各阶段开始时问题的自然状况。如例5.1中，各阶段的起始位置就是该问题的状态；例5.2中，各阶段开始（月初）时的库存量即为问题的状态。描述过程状态的变量称为状态变量。通常用Sk表示第k阶段的状态
5、集合，用sk表示第k阶段的某一具体的状态。如例5.1中，S2=B1，B2=s2（1），s2（2），S3=C1，C2，C3，C4；例5.2中，S0=2，S1=8，9，S2=5，6，7，8，9。对于动态规划，其状态必须满足两个条件，即：能描述问题的过程；满足无后效性。所谓能描述问题的过程就是当各阶段的状态确定之后，整个问题的过程就已确定。所谓无后效性是指如果某阶段的状态给定以后，则在这阶段以后过程的发展不受这阶段以前各状态的影响，即过程的过去历史只能通过当前的状态去影响它的未来的发展，当前的状态是以往历史的一个总结。（3）决策决策表示当过程处于某一阶段的某一状态时，为确定下一阶段的某一状态所作出的
6、决定或者选择。如例5.1中，决策就是一种可行路径的选择。例5.2中，决策就是月初在某一库存量情况下生产量的决定。描述决策的变量称为决策变量。通常用uk（sk）表示第k阶段在状态为sk时所作出的决策，用Dk（sk）表示第k阶段在状态为sk处所有可行决策构成的决策集合，显然有uk（sk）Dk（sk）。如例5.1中，D1（A）=B1，B2=u1（1）（A），u1（2）（A），D2（B1）=C1，C2，C3；例5.2中，D0（2）=6，7，D1（8）=5，6，7，8，9，D1（9）=4，5，6，7，8等。（4）状态转移方程描述相邻两阶段状态与决策相互关系的方程称为状态转移方程。不同的问题，这种关系的形
7、式是不同的，对于某一具体问题，状态转移方程的形式一般也是确定的。状态转移方程的一般形式可描述为sk+1=Tk（sk，uk），它描述了由k阶段到k+1阶段的状态转移规律，Tk称为状态转移函数。如例5.1中，状态转移方程的形式为sk+1=uk（sk）；例5.2中的状态转移方程为sk+1=sk+ukdk。（5）策略对于n阶段决策问题，从初始状态出发到终段状态的全过程中，每阶段的决策uk（sk）（k=1，2，n）所构成的决策序列就称为一个整体策略，简称策略。记为：p1，n（s1）=u1（s1），u2（s2），un（sn）另外，称下式所描述的为后部k段子策略 pk，n（sk）=uk（sk），uk+1（s
8、k+1），un（sn）称下式所描述的为前部k段子策略 p1，k（s1）=u1（s1），u1（s1），uk（sk）在实际问题中，可供选择的策略有一定的范围，此范围称为允许策略集合，用P表示。允许策略集合中使问题达到最优效果的策略称为最优策略。例5.1中，任一条从A到E的可行路线均构成一个策略。如p1，4（1）（A）=B1，C1，D1，E；p1，4（2）（A）=B2，C2，D1，E等。（6）指标函数把描述问题优劣的数量指标与问题策略或子策略关系的函数称为指标函数。即，衡量问题的优劣必须有数量指标，而该数量指标可以是定义在问题策略或子策略上的函数，通常用Vk，n表示。即 Vk，n=Vk，n（pk，n
9、（sk）k=1，2，n对于动态规划模型来说，指标函数应满足可分离性，即可以描述成sk、uk、Vk+1，n的函数。记为 Vk，n（pk，n（sk）=ksk，uk，Vk+1，n（pk+1，n（sk+1）动态规划的指标函数的形式一般有如下两种阶段指标和的形式，即过程或子过程的指标为各阶段指标的和，用公式描述如下其中，vj（sj，uj）表示j阶段在状态为sj作出决策为uj时的指标，即所谓的阶段指标。本章例5.1和例5.2的指标函数均为阶段指标和的形式。显然，这种形式还可以描述成即满足指标函数的可分离性即满足指标函数的可分离性阶段指标积的形式，即过程或子过程的指标为各阶段指标的积，用公式描述如下显然，这
10、种形式的指标函数也满足可分离性，即最优策略对应的指标函数值就称为最优指标值，通常用fk（sk）表示。由于最优指标值是采取最优策略所得到的，因此最优指标值可用如下公式描述，即其中：“opt”是最优化（optimization）的缩写，可根据题意取min或max；Pk，n（sk）为第k阶段在状态为sk处所有可行策略构成的集合；pk，*n（sk）为第k阶段在状态为sk处的最优策略。二、动态规划的最优性原理二、动态规划的最优性原理20世纪50年代，R.Bellman 等人根据研究多阶段决策问题的成果，提出了最优性原理，该原理作为动态规划的理论基础，解决了很多类型决策过程最优化问题。动态规划规划的最优性
11、原理描述如下：“作为整个过程的最优策略具有这样的性质：即无论过去的状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。”简言之，一个最优策略的子策略总是最优的。三、动态规划基本方程三、动态规划基本方程根据上述动态规划原理，可提出n阶段决策问题的递推关系，即动态规划基本方程。对于指标函数为阶段指标和的形式的问题，其动态规划方程形式为：对于指标函数为阶段指标积的形式的问题，其动态规划方程形式为：从上述基本概念和基本方程可归纳出动态规划的基本思想：动态规划方法的关键在于正确地写出基本的递推关系式（基本方程）。要做到这一点，必须首先将问题的过程划分成若干个相互联系的阶段，正确地
12、选择问题的状态变量和决策变量以及定义指标函数的具体形式，从而将一个大问题化成一簇同类型的子问题，然后逐个求解。即从问题的边界条件开始，逐段递推寻优，在每一个子问题的求解中，均利用它前面的子问题的优化结果，依次进行，最后一个子问题所得到的最优解就是整个问题的最优解。在多阶段决策过程中，动态规划方法是既把当前一段和未来各段分开，又把当前效益和未来效益结合起来考虑的一种最优化方法。因此，每段决策的选取是从全局来考虑的，与该段的最优选择答案一般是不同的。在求整个问题的最优策略时，由于初始状态是已知的，而每段的决策都是该段状态的函数，故最优策略所经过的各段状态便可逐次变换得到，从而确定了最优路线。第三节
13、第三节 动态规划方法解题动态规划方法解题一、动态规划解题步骤一、动态规划解题步骤1建立问题的动态规划模型 包括划分阶段、选择问题的状态变量与决策变量、写出状态转移方程、描述问题的指标函数、列出问题的动态规划方程。2递推计算 即按第一步所描述的动态规划方程分阶段逐一计算，若问题是离散的，则，每阶段的每一个状态都要计算。3寻找最优策略 以第二步递推计算的结果为基础，以状态转移方程为纽带，按与递推计算相反的方向寻找最优策略。二、动态规划解题举例二、动态规划解题举例例5.3 用动态规划方法求解第一节图52所描述的最短路问题。1建立问题的动态规划模型阶段：按地段划分阶段，则k=1，2，3，4；状态：各阶
14、段初的起始位置，用sk表示；决策：各阶段在给定状态sk条件下的路径选择，用uk（sk）表示；状态转移方程：sk+1=uk（sk）指标函数：衡量问题优劣的数量指标为距离，指标函数的形式为各阶段指标的和，即，其中vj（sj，uj）分别标注在图52中的相应线段上。动态规划方程：2递推计算k=4时同理有 f4（D2）=2 u*4（D2）=E f4（D3）=2 u*4（D3）=E k=3时同理有k=2时时k=1时3.寻找最优策略k=1 s1 =A u*1（A）=B1k=2 s2=u*1（s1）=B1 u*2（B1）=C2k=3 s3=u*2（s2）=C2 u*3（C2）=D1k=4 s4=u*3（s3）
15、=D1 u*4（D2）=E即最优策略为B1，C2，D1，E，或者说该问题的最短路为AB1C2D1E。三、逆序解法与顺序解法三、逆序解法与顺序解法从问题的最后阶段逐步向前进行递推计算的称为动态规划的逆序解法.递推计算可以从前向后进行的解法即所谓的动态规划顺序解法。对于动态规划的顺序解法，状态转移方程可以描述为如下形式 sk=Tk（sk+1，uk）于是可得动态规划顺序解法的基本方程为四、静态规划的动态规划解法四、静态规划的动态规划解法对于某些静态规划问题，引入时间的因素，把它看作是按阶段进行的一个动态规划问题，这就使得动态规划成为求解一些简单的线性规划或非线性规划的有效方法。例5.4 用动态规划发
16、求解下列静态规划问题解：按变量划分阶段，即k=1，2，3；x1、x2、x3仍然为决策变量；状态变量为s3=x3，s2=x2+x3，s1=x1+x2+x3=c；在上述定义的基础上，状态转移方程为：sk+1=sk xk指标函数的形式为：其中v1（s1，x1）=x1，v2（s2，x2）=x22、v3（s3，x3）=x3；动态规划方程为于是，用上述动态规划方程，从后向前依次递推计算有由 得 且 故x2=（2/3）s2为h2（x2）的极大点。所以有 同样用微分法易知 根据上述递推计算结果，从前向后寻优有k=1 s1=c k=2 s2=s1x1*=k=3 s3=s2x2*=即，问题的最优解；最大值为例5.
17、5 用动态规划法求解下列静态规划问题解：令y1=3x1，y2=2x2，y3=x3，将问题改写成如下形式按变量划分阶段，即k=1，2，3；y1、y2、y3为决策变量；状态变量为s3=y3，s2=y2+y3，s1=y1+y2+y3 9；在上述定义的基础上，状态转移方程为：sk+1=sk yk；指标函数的形式为：其中v1（s1，y1）=(4/9)y12，v2（s2，y2）=(1/4)y22,v3（s3，y3）=2y32；动态规划方程为用上述动态规划方程，从后向前依次递推计算有k=3 k=2 令 得 故y2只能在0，s2的端点处取得极大值。因此有k=1 令 得 又 故h1（y1）在处取得极小值。因此，
18、故y1也只能在0，s1的端点处取得极大值。因此有 根据上述递推计算结果，从前向后寻优有k=1 y*1=s1k=2 s2=s1y1*=s10=s1 y*2=0k=3 s3=s2y2*=s10=s1 y*3=0最后 因此问题的最优解为：y*1=s*1=9，y*2=0，y*3=0；即 x*1=3，x*2=0，x*3=0第四节第四节 动态规划应用动态规划应用一、资源分配问题一、资源分配问题（一）一维资源分配问题问题描述 设有某种资源，总数量为a，用于生产n种产品（或用于n种生产）。若分配数量xi用于第i种产品，其收益为gi（xi）。问应如何分配，才能使生产n种产品的总收入最大？该问题的静态规划数学模型
19、为该问题的动态规划模型为阶段：按生产划分阶段，k=1，n；状态变量：sk表示可用于分配给第k至第n阶段（生产）的资源数量；决策变量：xk表示可用于分配给第k阶段（生产）的资源数量；状态转移方程：sk+1=skxk允许决策集合：Dk（sk）=xk|0 xksk k=1，n-1；动态规划方程利用该递推方程逐阶段计算，最后可得问题的最优分配方案。例5.6 某公司现有资源A五个单位，可分配给所属甲、乙、丙三个分公司。各分公司获得不同数量的资源A可为总公司获得不同的利润，具体数据如表52所示。问如何分配资源A给各分公司，使总公司利润最大。表52 单位：万元分公司分公司资源资源A甲甲乙乙丙丙0123450
20、45709010512002045751101500507080100130解：（1）建立其动态规划数学模型阶段：按分公司划分阶段，k=1，2，3（分别代表分公司甲、乙、丙）；状态变量：sk表示可用于分配给第k至第3阶段（分公司）的资源A的数量；决策变量：xk表示可用于分配给第k阶段（分公司）的资源A的数量；状态转移方程：sk+1=skxk允许决策集合：Dk（sk）=xk|0 xksk k=1，2；动态规划方程：其中，gk（xk）（k=1，2，3）分别列于表52中。（2）递推计算 k=3时根据动态规划方程有：f3（s3）=g3（s3），因此有 表53s3g3（s3）f3（s3）x*301234
21、505070801001300507080100130012345k=2时根据动态规划方程有：f2（s2）=因此有 s2x2s3=s2-x2g2(x2)f3(s3)g2+f3f2(s2)x*20000000010110020500502050020122100204570500707045700or13012332100204575807050080909575952401234432100204575110100807050010010011512511012535012345543210020457511015013010080705001301201251451601501604k=1时
22、根据动态规划方程有：f1（s1）=可行的状态仅有s1=5，因此有s1x1s2=s1x1g1(x1)f2(s2)g1+f2f1(s1)x*15012345543210045709010512016012595705001601701651601551201701（3）寻优k=1 s1=5 x*1=1k=2 s2=s1x*1=4 x*2=3k=3 s3=s2x*2=1 x*3=1即，分公司甲、乙、丙分得资源A的数量分别为1、3和1个单位，总公司获得最大利润170万元。例5.7某某公公司司计计划划研研制制三三种种新新产产品品，若若不不增增加加研研制制投投资资，三三种种产产品品的的不不成成功功的的概概
23、率率分分别别为为0.7、0.8和和0.7。为为降降低低不不成成功功的的概概率率，公公司司决决定定增增加加研研制制投投资资15万万元元。各各产产品品增增加加研研制制费费后后，不不成成功功的的概概率率如如表表53所所示示。设设三三种种产产品品成成功功与与否否相相互互独独立立，试试用用动动态态规规划法计算使三种产品均不成功的概率最小的研制费分配方案。划法计算使三种产品均不成功的概率最小的研制费分配方案。表表53产产品品增加研制费增加研制费(万元万元)ABC0510150.70.50.30.30.80.50.20.20.70.40.30.1解解:（1 1）建立其动态规划数学模型）建立其动态规划数学模型
24、阶段：按产品划分阶段，阶段：按产品划分阶段，k=1，2，3（分别代表产品（分别代表产品A、B、C）；）；状态变量：状态变量：sk表示可用于分配给第表示可用于分配给第k至第至第3阶段（产品）的研制费；阶段（产品）的研制费；决策变量：决策变量：xk表示可用于分配给第表示可用于分配给第k阶段（产品）的研制费；阶段（产品）的研制费；状态转移方程：状态转移方程：sk+1=skxk允允 许许 决决 策策 集集 合合：Dk（sk）=xk|0 xksk (k=1，2)；D3（s3）=x3|x3=s3动态规划方程：根据概率论的知识有动态规划方程：根据概率论的知识有其中，其中，gk（xk）（）（k=1，2，3）分
25、别列于表分别列于表53中。中。（2 2）递推计算）递推计算将上述三阶段的递推计算综合在一个表格中计算如下将上述三阶段的递推计算综合在一个表格中计算如下P133（3）寻优 k=1 s1=15 x*1=0 k=2 s2=s1x*1=15 x*2=0 k=3 s3=s2x*2=15 x*3=15或 k=1 s1=15 x*1=0 k=2 s2=s1x*1=15 x*2=10 k=3 s3=s2x*2=5 x*3=5即，三种产品的研制费分配方案为A、B、C分别分配0、0和15万元或0、10万元和5万元，公司三种产品不成功的概率最小（0.056）。（二）二维资源分配问题问题描述 设设有有两两种种原原料料
26、，数数量量各各为为a和和b单单位位，需需要要分分别别用用于于生生产产n种种产产品品。若若第第一一种种原原料料以以数数量量xi为为单单位位，第第二二种种原原料料以以数数量量yi为为单单位位，用用于于生生产产第第i种种产产品品，其其收收益益为为gi（xi，yi）。问问应应如如何何分分配配这这两种原料于两种原料于n种产品的生产使总收入最大？种产品的生产使总收入最大？该问题的该问题的静态规划数学模型为数学模型为用用动态规划方法来解，状态变量和决策变量要取二维的。方法来解，状态变量和决策变量要取二维的。P134136二、生产与存储问题二、生产与存储问题问问题题描描述述设设某某公公司司对对某某产产品品要要
27、制制定定一一个个n阶阶段段的的生生产产（或或购购买买）计计划划。已已知知第第k阶阶段段社社会会对对该该产产品品的的需需求求量量为为dk；单单位位产产品品的的存存储储费费为为hk，生生产产单单位位产产品品的的成成本本费费为为ck，生生产产每每批批产产品品的的固固定定成成本本为为C，若若不不生生产产则则为为零零；每每次次生生产产的的上上限限为为m；开开始始时时库库存存量量为为零零，在在n阶阶段段末末的的终终结结库库存存量量也也为为零零。问问在在保保证证供供应应的的情情况况下下，该该公公司司如如何何制制定定每每个个阶阶段段的的生生产（或采购）计划产（或采购）计划，从而时使总成本最小。，从而时使总成本
28、最小。该问题的动态规划模型为该问题的动态规划模型为状态变量：各阶段初的库存量，用：各阶段初的库存量，用sk表示；表示；决策变量：各阶段的生产量（或定购量），用：各阶段的生产量（或定购量），用uk表示；表示；状态转移方程：sk+1=sk+ukdk指标函数：Vk，n=vk（sk，uk）+vn（sn，un）其中其中动态规划方程为：其中其中Dn（sn）=un|un=dnsn 例5.8三、多阶段配置问题三、多阶段配置问题问题描述有有某某种种资资源源，总总数数量量为为s1，可可以以用用用用于于两两种种形形式式的的生生产产：A和和B。已已知知这这两两种种生生产产的的收收益益函函数数分分别别为为g（x）和和h
29、（x），其其中中x为为资资源源的的投投入入量量，且且满满足足g（0）=h（0）=0。假假设设这这两两种种资资源源用用于于生生产产后后还还可可以以回回收收一一部部分分再再用用于于生生产产。这这两两种种生生产产的的回回收收率率分分别别为为a和和b（0a1，0b1）。现现要要求求对对总总数数量量为为s1的的资资源源进进行行n个个阶阶段段的的生生产，每个阶段如何分配投入到产，每个阶段如何分配投入到A和和B的资源数量使总收益最大。的资源数量使总收益最大。设设ui为为第第i阶阶段段投投入入到到A生生产产的的资资源源数数量量，则则第第i阶阶段段投投入入到到B生生产产的的资资源源数数量量为为siui，其其中中
30、si=aui1+b（si1ui1），这这样样该该问问题题的的静态规划数学模型可描述为数学模型可描述为该问题的动态规划数学模型如下该问题的动态规划数学模型如下状态变量：第：第k阶段可投入到阶段可投入到A、B两种生产的资源数量，用两种生产的资源数量，用sk来表示；来表示；决策变量：第第k阶阶段段投投入入到到A生生产产的的资资源源数数量量，用用uk表表示示，则则skuk表表示示投投入入到到B生生产产的的资资源源数数量量；且且允允许许决决策策集集合合为为Dk（sk）=uk|0uksk（k=1，n）。）。状态转移方程：sk+1=auk+b（skuk）指标函数形式：Vk，n=g（uk）+h（skuk）+g
31、（un）+h（snun）动态规划方程按此关系式，可求出按此关系式，可求出n阶段资源的最优投入计划。阶段资源的最优投入计划。例5.9P140四、随机采购问题四、随机采购问题前前面面我我们们讨讨论论的的都都是是确确定定性性的的多多阶阶段段决决策策问问题题。但但是是，在在人人们们的的实实践践活活动动中中，常常常常会会遇遇到到多多阶阶段段的的随随机机决决策策问问题题。这这里里讨讨论论的的随随机机采采购购问问题题就就是是其其中中一一例例。下下面面举举一一个个简简单单的的例例子子来来说说明明此此类类问问题的求解。题的求解。例5.10某某部部门门打打算算在在近近五五周周内内采采购购一一批批原原料料。事事先先
32、可可估估计计出出来来五五周周的每周内可能有三种价格，而每种价格的概率变化如表的每周内可能有三种价格，而每种价格的概率变化如表55所示。所示。表表55该该部部门门由由于于生生产产需需要要，必必须须在在这这五五周周内内采采购购此此种种原原料料。如如果果第第一一周周内内价价格格偏偏高高，可可以以等等待待到到第第二二周周或或第第三三周周或或第第四四周周，以以至至于于在在最最后后一一周周（即即第第五五周周）进进行行采采购购；如如果果第第一一周周及及第第二二周周价价格格都都偏偏高高，可可以以等等待待到到第第三三周周或或第第四四周周后后最最后后一一周周进进行行采采购购；以以此此类类推推，如如果果认认为为前前四四周周价价格格都都偏偏高高，则则在在第第五五周周（即即最最后后一一周周）不不管管市市场场价价格格如如何何都都必必须须购购买买。现现在在的的问问题题是是，究究竟竟在在哪哪一一周周、按按什什么么价价格格进进行行采采购才是最佳的决策。购才是最佳的决策。价格价格概率概率4504705000.250.350.40