动态规划(全套)课件

主要内容主要内容:7.17.1多阶段决策问题多阶段决策问题多阶段决策问题多阶段决策问题7.2 7.2 动态规划的基本概念和基本原理动态规划的基本概念和基本原理动态规划的基本概念和基本原理动态规划的基本概念和基本原理7.3 7.3 动态规划应用举例动态规划应用举例动态规划应用举例动态规划应用举例第第 七七 章章 动动 态态 规规 划划主要内容:第 七 章 动 态 规 划1例例 求解最短路问题求解最短路问题 例 求解最短路问题 2分阶段的最短路径：C1T 3-:B1C1T 4-：A2B1C1T 7-：QA2B1C1T 11 Q-A3B1C1T 11 Q-A3B2C2T 11分阶段的最短路径：C13最短路径最短路径34476117811最短路径344761178114最短路径解的特点1、可以将全过程求解分为若干阶段求解；-多阶段决策问题多阶段决策问题多阶段决策问题多阶段决策问题2、在全过程最短路径中，将会出现阶段的最优路径；-递推性递推性递推性递推性3、前面的终点确定，后面的路径也就确定了，且与前面的路径（如何找到的这个终点）无关；-无后效性无后效性无后效性无后效性3、逐段地求解最优路径，势必会找到一个全过程最优路径。-动态规划动态规划动态规划动态规划最短路径解的特点1、可以将全过程求解分为若干阶段求解；-57.17.1多阶段决策问题多阶段决策问题 动态规划是解决多阶段最优决策的方法动态规划是解决多阶段最优决策的方法,由美国数学家贝尔曼由美国数学家贝尔曼(R.Bellman)于于 1951年首先提出年首先提出;1957年贝尔曼发表动态规划方面的第一部年贝尔曼发表动态规划方面的第一部专著专著“动态规划动态规划”,标志着运筹学的一标志着运筹学的一 个个新分支的创立。新分支的创立。7.1多阶段决策问题 动态规划是解决多阶段最优决策的方法,6动态规划将复杂的多阶段决策问题分解为动态规划将复杂的多阶段决策问题分解为一系列简单的、离散的单阶段决策问题一系列简单的、离散的单阶段决策问题,采用顺序求解方法采用顺序求解方法,通过解一系列小问题通过解一系列小问题达到求解整个问题目的达到求解整个问题目的;动态规划的各个决策阶段不但要考虑本阶动态规划的各个决策阶段不但要考虑本阶段的决策目标段的决策目标,还要兼顾整个决策过程的还要兼顾整个决策过程的整体目标整体目标,从而实现整体最优决策从而实现整体最优决策.动态规划将复杂的多阶段决策问题分解为一系列简单的、离散的单阶7动态规划的分类动态规划的分类:离散确定型离散确定型离散随机型离散随机型连续确定型连续确定型连续随机型连续随机型动态规划的分类:离散确定型8动态规划的特点动态规划的特点:动态规划动态规划没有准确的数学表达式和定义没有准确的数学表达式和定义精确的算法精确的算法,它强调它强调具体问题具体分析具体问题具体分析,依赖分析者的经验和技巧依赖分析者的经验和技巧。与运筹学其他方法有很好的互补关系与运筹学其他方法有很好的互补关系,尤尤其在处理非线性、离散性问题时有其独其在处理非线性、离散性问题时有其独到的特点。到的特点。动态规划的特点:动态规划没有准确的数学表达式和定义精确的算9 通通常常多多阶阶段段决决策策过过程程的的发发展展是是通通过过状状态态的的一一系系列列变变换换来来实实现现的的。一一般般情情况况下下，系系统统在在某某个个阶阶段段的的状状态态转转移移除除与与本本阶阶段段的的状状态态和和决决策策有有关关外外，还还可可能能与与系系统统过过去去经经历历的的状状态态和和决决策策有有关关。因因此此，问问题题的的求求解解就就比比较较困困难难复复杂杂。而而适适合合于于用用动动态态规规划划方方法法求求解解的的只只是是一一类类特特殊殊的的多多阶阶段段决决策策问问题题，即即具具有有“无后效性无后效性”的多阶段决策过程。的多阶段决策过程。所所所所谓谓谓谓无无无无后后后后效效效效性性性性，又又又又称称称称马马马马尔尔尔尔柯柯柯柯夫夫夫夫性性性性，是是是是指指指指系系系系统统统统从从从从某某某某个个个个阶阶阶阶段段段段往往往往后后后后的的的的发发发发展展展展，仅仅仅仅由由由由本本本本阶阶阶阶段段段段所所所所处处处处的的的的状状状状态态态态及及及及其其其其往往往往后后后后的的的的决决决决策策策策所所所所决决决决定定定定，与与与与系统以前经历的状态和决策系统以前经历的状态和决策系统以前经历的状态和决策系统以前经历的状态和决策(历史历史历史历史)无关。无关。无关。无关。具具有有无无后后效效性性的的多多阶阶段段决决策策过过程程的的特特点点是是系系统统过过去去的的历历史史，只只能能通通过过现现阶阶段段的的状状态态去去影影响响系系统统的的未未来来，当当前前的的状状态态就就是是后过程发展的初始条件。后过程发展的初始条件。通常多阶段决策过程的发展是通过状态的一系列变换来实现的10动态规划的应用动态规划的应用动态规划在工程技术动态规划在工程技术,企业管理企业管理,军事部军事部门有广泛的应用门有广泛的应用;可解决资源分配可解决资源分配,生产生产调度调度,库存管理库存管理,路径优化路径优化,设备更新设备更新,投资规划投资规划,排序问题和生产过程的最优控排序问题和生产过程的最优控制等问题制等问题;动态规划的应用动态规划在工程技术,企业管理,军事部门有广11使用动态规划方法求解决策问题首先要将使用动态规划方法求解决策问题首先要将问题改造成符合动态规划求解要求的形式问题改造成符合动态规划求解要求的形式,要涉及以下概念要涉及以下概念:(1)(1)阶段阶段(2)(2)状态状态(3)(3)决策与策略决策与策略 (4)(4)状态转移方程状态转移方程 (5)(5)指标函数指标函数 (6)(6)基本方程基本方程7.2 7.2 动态规划的基本概念和基本思想动态规划的基本概念和基本思想一、基本概念一、基本概念使用动态规划方法求解决策问题首先要将问题改造成符合动态规划求12(1)划分阶段划分阶段 把一个复杂决策问题按时间或空间特把一个复杂决策问题按时间或空间特征分解为若干征分解为若干(n)(n)个相互联系的阶段个相互联系的阶段(stage),(stage),以便按顺序求解以便按顺序求解;阶段变量描述当前所处的阶段位置，一阶段变量描述当前所处的阶段位置，一般用下标般用下标 k 表示表示;(1)划分阶段13 每阶段有若干状态每阶段有若干状态(state),表示某一阶段决表示某一阶段决策面临的条件或所处位置及运动特征的量策面临的条件或所处位置及运动特征的量,称称为状态。反映状态变化的量叫作状态变量。为状态。反映状态变化的量叫作状态变量。k 阶段的状态特征可用状态变量阶段的状态特征可用状态变量 sk 描述描述;每一阶段的全部状态构成该阶段的状态集合每一阶段的全部状态构成该阶段的状态集合Sk，并有，并有sk Sk。每个阶段的状态可分为初始状。每个阶段的状态可分为初始状态和终止状态，或称输入状态和输出状态，态和终止状态，或称输入状态和输出状态，阶段的初始状态记作阶段的初始状态记作sk，终止状态记为，终止状态记为sk+1，也是下个阶段的初始状态。也是下个阶段的初始状态。(2)确定状态确定状态 每阶段有若干状态(state),表示某一阶段决策面临14(3)(3)决策、决策变量决策、决策变量 所谓决策就是确定系统过程发展的方案，所谓决策就是确定系统过程发展的方案，决策的实质是关于状态的选择，是决策者从决策的实质是关于状态的选择，是决策者从给定阶段状态出发对下一阶段状态作出的选给定阶段状态出发对下一阶段状态作出的选择。择。用以描述决策变化的量称之决策变量，用以描述决策变化的量称之决策变量，和状态变量一样，决策变量可以用一个数，和状态变量一样，决策变量可以用一个数，一组数或一向量来描述也可以是状态变量一组数或一向量来描述也可以是状态变量的函数，记以的函数，记以 ，表示于，表示于 k 阶段状阶段状态态 sk 时的决策变量时的决策变量 (3)决策、决策变量 所谓决策就是确定系统过程发展15 决策变量的取值往往也有一定的容许范围，决策变量的取值往往也有一定的容许范围，称之允许决策集合决策变量称之允许决策集合决策变量 xk(sk)的允许的允许决策集用决策集用 XK(SK)表示，表示，xk(sk)XK(SK),允允许决策集合实际是决策的约束条件。许决策集合实际是决策的约束条件。决策变量的取值往往也有一定的容许范围，称之允许决策16(4)(4)策略和允许策略集合策略和允许策略集合 策略策略(Policy)也叫决策序列策略有全过程也叫决策序列策略有全过程策略和策略和 k 部子策略之分，全过程策略是指具部子策略之分，全过程策略是指具有有n 个阶段的全部过程，由依次进行的个阶段的全部过程，由依次进行的 n 个个阶段决策构成的决策序列，简称策略，表示阶段决策构成的决策序列，简称策略，表示为为 。从。从 k 阶段到第阶段到第 n 阶段，阶段，依次进行的阶段决策构成的决策序列称为依次进行的阶段决策构成的决策序列称为 k 部子策略部子策略,表示为表示为 ，显然，显然当当 k=1时的时的 k 部子策略就是全过程策略。部子策略就是全过程策略。(4)策略和允许策略集合 策略(Policy)也叫决策序列17(5)状态转移方程状态转移方程 状态转移确定从一个状态到另一个状态的转状态转移确定从一个状态到另一个状态的转移过程移过程,由状态转移方程描述由状态转移方程描述:sk+1=T(sk,xk);状态转移方程在大多数情况下可以由数学公状态转移方程在大多数情况下可以由数学公式表达式表达,如如:sk+1=sk+xk；(5)状态转移方程 状态转移确定从一个状态到另一个状态的18(6)指标函数指标函数 用来衡量策略或子策略或决策的效果的用来衡量策略或子策略或决策的效果的某种数量指标，就称为指标函数。它是定义某种数量指标，就称为指标函数。它是定义在全过程或各子过程或各阶段上的确定数量在全过程或各子过程或各阶段上的确定数量函数。对不同问题，指标函数可以是诸如费函数。对不同问题，指标函数可以是诸如费用、成本、产值、利润、产量、耗量、距离、用、成本、产值、利润、产量、耗量、距离、时间、效用，等等。时间、效用，等等。(6)指标函数 用来衡量策略或子策略或决策的效果19 用用vk(sk,xk)表示第表示第 k 段处于状态段处于状态 sk且所且所作决策为作决策为 xk 时的指标，则它就是第时的指标，则它就是第 k 段指标段指标函数，简记为函数，简记为vk。用用f(sk,xk)表示第表示第k k子过程的指标函数。表子过程的指标函数。表示处于第示处于第 k 段段 sk 状态且所作决策为状态且所作决策为xk时，时，从从 sk 点到终点的距离。由此可见，点到终点的距离。由此可见，f(sk,xk)不仅跟当前状态不仅跟当前状态 sk 有关，有关，（2 2）过程指标函数）过程指标函数（也称目标函数）（也称目标函数）（1）阶段指标函数）阶段指标函数（也称阶段效应）（也称阶段效应）用vk(sk,xk)表示第 k 段处于状态 s20还跟该子过程策略还跟该子过程策略 pk(sk)有关有关,严格说来，严格说来，应表示为应表示为 fk(sk,pk(sk)。它是由各阶段的。它是由各阶段的阶段指标函数阶段指标函数 vk(sk,xk)累积形成的，对于累积形成的，对于 k 部子过程的指标函数可以表示为：部子过程的指标函数可以表示为：式式中中，表表示示某某种种运运算算，可可以以是是加加、减减、乘、除、开方等乘、除、开方等还跟该子过程策略 pk(sk)有关,严格说来，应表示为 f21 多阶段决策问题中，常见的目标函数形式多阶段决策问题中，常见的目标函数形式之一是取各阶段效应之和的形式，即之一是取各阶段效应之和的形式，即:有些问题，如系统可靠性问题，其目标函有些问题，如系统可靠性问题，其目标函数是取各阶段效应的连乘积形式，数是取各阶段效应的连乘积形式，多阶段决策问题中，常见的目标函数形式之一是取各阶段效应22(7)最优解最优解 用用 fk*(sk)表示第表示第 k 子过程指标函数子过程指标函数Fk(sk,pk(sk)在状态在状态 sk 下的最优值，即下的最优值，即:称称 fk(sk)为第为第 k 子过程上的最优指标函数；子过程上的最优指标函数；与它相应的子策略与它相应的子策略 pk(sk)称为状态称为状态 sk 下的最下的最优子策略，记为优子策略，记为 pk*(sk)(7)最优解 用 fk*(sk)表示第 k 子过程23例例例例 用动态规划求解最短路问题用动态规划求解最短路问题 例 用动态规划求解最短路问题 24最短路的求解最短路的求解最短路的求解最短路的求解:阶段阶段:可分为可分为4个阶段个阶段,k=1,.,4。状态状态:可用城市编号可用城市编号,S1=Q,S2=A1,A2,A3,S3=B1,B2,B3,S4=C1,C2,S5=T 决策决策:决策变量也可用城市编号决策变量也可用城市编号;状态转移方程状态转移方程:sk+1=xk;阶段指标函数：阶段指标函数：过程指标（阶段递推）函数过程指标（阶段递推）函数:最短路的求解:25 k=4f4(C1)=3,f4(C2)=4 k=3f3(B1)=min1+f4(C1)=4*,4+f4(C2)=8=4 f3(B2)=min6+f4(C1)=9,3+f4(C2)=7*=7 f3(B3)=min3+f4(C1)=6*,3+f4(C2)=7=6 k=2 f2(A1)=min7+f3(B1),4+f3(B2),6+f3(B3)=min11*,11*,12=11f2(A2)=min3+f3(B1),2+f3(B2),4+f3(B3)=min7*,9,10 =7 f2(A3)=min4+f3(B1),1+f3(B2),5+f3(B3)=min8*,8*,11 =8 k=1 f1(Q)=min2+f2(A1),4+f2(A2),3+f2(A3)=min13,11*,11*=11 最短路是：最短路是：Q A2 B1 C1 T，p=A2,B1,C1,T Q A3 B1 C1 T，p=A3,B1,C1,T Q A3 B2 C2 T，p=A3,B2,C2,T k=426整个过程的最优策略应具有这样的性质整个过程的最优策略应具有这样的性质:无论过去的状态和决策如何无论过去的状态和决策如何,对前面的决策对前面的决策所形成的状态而言所形成的状态而言,后续的诸决策必须构成后续的诸决策必须构成最优策略；最优策略；上一条成立的条件是阶段递推函数严格单上一条成立的条件是阶段递推函数严格单调。调。二、动态规划的最优性原理二、动态规划的最优性原理整个过程的最优策略应具有这样的性质:无论过去的状态和决策27在在例例题题中中，求求解解最最短短路路线线的的计计算算公公式式可可以以概概括写成：括写成：其其中中，vk 在在这这里里表表示示从从状状态态 sk 到到由由决决策策 xk 所所决决定定的的状状态态 sk+1 之之间间的的距距离离。f5(s5)=0 是是边边界条件，表示全过程到第四阶段终点结束。界条件，表示全过程到第四阶段终点结束。在例题中，求解最短路线的计算公式可以概括写成：其中，28 一般地，对于一般地，对于 n 个阶段的决策过程，假设只个阶段的决策过程，假设只考虑指标函数是考虑指标函数是“和和”与与“积积”的形式，第的形式，第 k 阶段和第阶段和第 k+1 阶段间的递推公式可表示如下：阶段间的递推公式可表示如下：当过程指标函数为下列当过程指标函数为下列“和和”的形式时的形式时 一般地，对于 n 个阶段的决策过程，假设只考虑指标29相应的函数基本方程为相应的函数基本方程为:相应的函数基本方程为:30 当过程指标函数为下列当过程指标函数为下列“积积”的形式时的形式时 当过程指标函数为下列“积”的形式时31相应的函数基本方程为相应的函数基本方程为:相应的函数基本方程为:32动态规划的优缺点动态规划的优点动态规划的优点动态规划的优点动态规划的优点可以解决线性可以解决线性,非线性非线性,整整数规划无法有效求解的复数规划无法有效求解的复杂问题杂问题;容易找到全局最优解容易找到全局最优解;可以得到一组解可以得到一组解;动态规划的缺点：动态规划的缺点：动态规划的缺点：动态规划的缺点：没有标准的模型可供应用没有标准的模型可供应用,构构模依赖于个人的经验和技巧模依赖于个人的经验和技巧;状态变量需满足无后效性状态变量需满足无后效性,有有较大的局限性较大的局限性;动态规划的维数灾难限制了动态规划的维数灾难限制了对规模较大问题的求解效率对规模较大问题的求解效率;动态规划的优缺点动态规划的优点动态规划的缺点：337.3 7.3 动态规划方法应用动态规划方法应用动态规划的步骤：动态规划的步骤：1.将问题按时间或空间划分为满足递推关系的将问题按时间或空间划分为满足递推关系的若干阶段若干阶段,对非时序问题可人为地引入对非时序问题可人为地引入“时时段段”概念概念;2.正确选择状态变量正确选择状态变量 sk,满足满足:可知性可知性:正确描述动态过程演变正确描述动态过程演变,可直接可直接或间接确定状态变量的值或间接确定状态变量的值;无后效性无后效性:后面的决策与前面的决策无关后面的决策与前面的决策无关;7.3 动态规划方法应用动态规划的步骤：343.确定决策变量确定决策变量 xk以及允许决策集合以及允许决策集合Xk;4.写出状态转移方程写出状态转移方程 sk+1=T(sk,xk);5.决策变量的取值范围决策变量的取值范围 6.写出过程指标函数（阶段函数）的递推写出过程指标函数（阶段函数）的递推关系关系,应满足应满足:a)是定义在所有阶段上的数量函数；是定义在所有阶段上的数量函数；b)具有可分离性，并满足递推关系；具有可分离性，并满足递推关系；c)阶段函数应严格单调。阶段函数应严格单调。3.确定决策变量 xk以及允许决策集合Xk;35动态规划应用举例：动态规划应用举例：1.最优路径问题最优路径问题2.资源配置问题资源配置问题3.生产与库存问题生产与库存问题4.机器负荷分配问题机器负荷分配问题5.复合系统工作可靠性问题复合系统工作可靠性问题6.二维背包问题二维背包问题7.设备更新问题设备更新问题8.货郎担问题货郎担问题9.非线性规划的求解非线性规划的求解动态规划应用举例：1.最优路径问题361.最优路径问题最优路径问题 某厂要确定一种新产品在今后五年内的价格，并已拟定只在5、6、7、8元这四种单价中进行选择。据预测，今后五年不同价格下每年盈利（万元）见下表，但是各相邻年度价格增减不得超过1元。问今后五年内每年定价各为多少，可逾七五年总利润最大。价格/元盈利/万元第一年第二年第三年第四年第五年5924586758647659738876641.最优路径问题 某厂要确定一种新产品在今后五年内的价37价格/元盈利/万元第一年第二年第三年第四年第五年592458675864765973887664131411843410182223172428283037353638价格/元盈利/万元第一年第二年第三年第四年第五年59245838解：1、建立动态规划模型：阶段：以年划分阶段，k=5,4,3,2,1；状态变量sk为每个阶段初的价格，则Sk=5,6,7,8；决策变量xk为每年所确定的价格，则Xk=5,6,7,8；状态转移方程：阶段指标函数vk(sk,xk)为每个阶段选择xk所取得的盈利；例如v(sk,)过程指标函数为第k阶段状态为sk时到最后一个阶段的总利润。基本函数方程为：解：1、建立动态规划模型：39、逆序求解：k=5f5(s5,x5)v5(s5,x5)+f6*(s6)f5*(s5)x5*s x 5 6 7 8 5 8+0 8 5 6 4+0 4 6 7 3+0 3 7 8 4+0 4 8、逆序求解：k=540k=4f4(s4,x4)v4(s4,x4)+f5*(s5)f4*(s4)x4*s x 5 6 7 8 5 5+8 5+4 13 5 6 6+8 6+4 6+3 14 5 7 7+4 7+3 7+4 11 6,8 8 6+3 6+4 10 7k=441k=3f3(s3,x3)v3(s3,x3)+f4*(s4)f3*(s3)x3*s x 5 6 7 8 5 4+13 4+14 18 6 6 8+13 8+14 8+11 22 7 7 9+14 9+11 9+10 23 6 8 6+11 6+10 17 7k=342k=2f2(s2,x2)v2(s2,x2)+f3*(s3)f2*(s2)x2*s x 5 6 7 8 5 2+18 2+22 24 6 6 5+18 5+22 5+23 28 7 7 5+22 5+23 5+17 28 7 8 7+23 7+17 30 7k=243k=1f1(s1,x1)v1(s1,x1)+f2*(s2)f1*(s1)x1*s x 5 6 7 8 5 9+24 9+28 37 6 6 7+24 7+28 7+28 35 6,7 7 6+28 6+28 6+30 36 8 8 8+28 8+30 38 8S1=8 X1=8 s2=8 x2=7 s3=7 x3=6 s4=6 x4=5 s5=5 x5=5k=1S1=8 X1=8 s2=8 442.资源配置问题资源配置问题如何将有限的资源分配给若干种生产活动，并使资源利如何将有限的资源分配给若干种生产活动，并使资源利用的收益最大是经济活动中常见的问题，动态规划可以用的收益最大是经济活动中常见的问题，动态规划可以求解一些线性规划无法解决的资源配置问题。求解一些线性规划无法解决的资源配置问题。一般的资源分配问题可以描述为如下的规划问题：一般的资源分配问题可以描述为如下的规划问题：maxmax:z z=g g1 1(x x1 1)+)+g g2 2(x x2 2)+.+)+.+g gn n(x xn n)x x1 1+x x2 2+.+.+x xn n=a ax xi i 0 0 i i=1,.,=1,.,n n2.资源配置问题 如何将有限的资源分配给若干种生产活动，并45例：某厂为扩大生产能力，拟订购某种成套例：某厂为扩大生产能力，拟订购某种成套例：某厂为扩大生产能力，拟订购某种成套例：某厂为扩大生产能力，拟订购某种成套4646套，以分配给其所辖套，以分配给其所辖套，以分配给其所辖套，以分配给其所辖1 1、2 2、3 3个分厂使用。预个分厂使用。预个分厂使用。预个分厂使用。预计个分厂分的不同套数的设备后，每年创造的计个分厂分的不同套数的设备后，每年创造的计个分厂分的不同套数的设备后，每年创造的计个分厂分的不同套数的设备后，每年创造的利润（万元）如下表所示。该厂应订购几套设利润（万元）如下表所示。该厂应订购几套设利润（万元）如下表所示。该厂应订购几套设利润（万元）如下表所示。该厂应订购几套设备并如何分配，才能使每年预计创利总额最大备并如何分配，才能使每年预计创利总额最大备并如何分配，才能使每年预计创利总额最大备并如何分配，才能使每年预计创利总额最大？分厂利润（万元）0套1套2套 3套 4套5套 6套1035676520467891030259887例：某厂为扩大生产能力，拟订购某种成套46套，以分配给其所46建立动态规划模型：建立动态规划模型：建立动态规划模型：建立动态规划模型：1.阶段阶段与分厂相联系与分厂相联系,阶段阶段 k 只考虑分配分厂只考虑分配分厂 k 的设备套数的设备套数;2.状态变量状态变量 sk 表示表示 k 分厂分厂可分配的设备套数可分配的设备套数;3.决策变量决策变量 xk 表示决定在表示决定在 k 分厂分厂使用的设备套数使用的设备套数;4.状态转移方程状态转移方程:sk+1=sk-xk;5.阶段函数阶段函数:vk(sk,xk)为为k分厂使用设备分厂使用设备xk时的获利时的获利，从第一分厂到第，从第一分厂到第k分厂的总获利分厂的总获利 6.fk(sk)=max vk(sk,xk)+fk+1(sk+1)7.6.基本状态方程基本状态方程建立动态规划模型：47k=3k=348k=2:s3=s2 x2k=2:s3=s2 x249k=1:s2=s1-x1因此得到：因此得到：x1=2,s2=6-2=4,x2=1,s3=4-1=3,x3=3 x1=1,s2=6-1=5,x2=2,s3=5-2=3,x3=3即：即：p=2，1，3或或1，2，3获利获利18万元万元k=1:s2=s1-x1因此得到：x1=2503.复合系统的工作可靠性问题复合系统的工作可靠性问题例例例例:为保证设备可靠运行为保证设备可靠运行,一些关键部件往往由多个一些关键部件往往由多个器件并联运行器件并联运行,如果器件如果器件 i 的失效概率为的失效概率为 pi,则则 xi 个个器件并联工作的可靠性为器件并联工作的可靠性为(1-pixi),假定每个器件假定每个器件的采购费用为的采购费用为 ci,在满足总采购费用不超过预算限在满足总采购费用不超过预算限制制 C 的前提下的前提下,使设备可靠性最高的规划问题可以使设备可靠性最高的规划问题可以描述为描述为:3.复合系统的工作可靠性问题51该问题为整数非线性规划，可以用动态规该问题为整数非线性规划，可以用动态规划求解，设关键器件数划求解，设关键器件数n=3，总费用为，总费用为120万元。器件的单价与可靠性如下表：万元。器件的单价与可靠性如下表：1300.1 2150.2 3200.5器件号器件号i 单价单价(万元万元)失效概率失效概率pi该问题为整数非线性规划，可以用动态规划求解，设关键器件数n52建立动态规划模型：建立动态规划模型：建立动态规划模型：建立动态规划模型：阶段与器件挂钩，第阶段与器件挂钩，第 k 阶段仅考虑器件阶段仅考虑器件k的采购数量的采购数量;sk 表示表示k 阶段可使用的采购费用阶段可使用的采购费用;xk 表示表示 k阶段决定购买阶段决定购买k 器件的数量；器件的数量；状态转移方程状态转移方程:sk+1=sk-ck xk；递推阶段函数递推阶段函数:vk(sk,xk)=1-pkxk总可靠性总可靠性fk(sk)=max (1-pkxk)fk+1(sk+1)基本状态方程：基本状态方程：建立动态规划模型：53k=3k=354k=2:s3=s2 c2x2k=2:s3=s2 c2x255k=1:s2=s1 c1 x1因此得到：因此得到：x1=1,s2=120-30=90,x2=2,s3=90-2*15=60,x3=3 即：即：p=1，2，3 可靠性为可靠性为0.756k=1:s2=s1 c1 x1因此得到：564、生产调度（生产与库存）问题 某厂根据市场预测，确认今后某厂根据市场预测，确认今后4个月该厂个月该厂的一种主要产品每月的需求的量的一种主要产品每月的需求的量d为为3，2，3，2万件。已知每月生产固定费用万件。已知每月生产固定费用b为为2千元，但若当月不生产则为千元，但若当月不生产则为0；产品成；产品成本本c为为1千元千元/件，贮存费用件，贮存费用h为为 0.2千元千元/万件万件/月。最大存贮能力月。最大存贮能力w为为4万件。若第万件。若第1月初五库存产品，第月初五库存产品，第4月末也不留库存，月末也不留库存，则该厂怎样安排生产，才能使今后则该厂怎样安排生产，才能使今后4个月个月的总费用最少？的总费用最少？4、生产调度（生产与库存）问题 某厂根据市场预测，确认57建立动态规划模型：建立动态规划模型：1、阶段与时间相联系、阶段与时间相联系,阶段阶段 k表示月份表示月份 2、状态变量、状态变量 sk 表示表示 k 月初的库存量月初的库存量;3、决策变量、决策变量 xk 表示表示 k月的产量月的产量;4、若、若dk为需求量，则状态转移方程为需求量，则状态转移方程:sk+1=sk+xk-dk;5、阶段函数、阶段函数:vk(sk,xk)为为k月月的生产费用的生产费用，过程函数：过程函数：fk(sk)为从第一月到第为从第一月到第k月的总生产费用月的总生产费用 fk(sk)=max vk(sk,xk)+fk+1(sk+1)6.基本状态方程基本状态方程建立动态规划模型：58k=4这是最后一个月，需求为这是最后一个月，需求为2，无库存，无库存s5=0。由。由状态方程知：状态方程知：s4=2-x4,x4 0,则则s4只能是只能是0，1，2k=459k=3这是第这是第3个月，需求为个月，需求为3。由状态方程知：。由状态方程知：s4=s3+x3-3,又由于又由于 2 s4 0,即即2 s3+x3-3 0,s3 w=4则则s3取值是取值是0,1，2，3，4。X3=x3|3s3+x35,s3=0,1,2,3,4k=360k=2这是第这是第2个月，需求为个月，需求为2。第一个月无库存第一个月无库存s1=0，s2=s1+x1-3=x1-3，又因，又因x1 5，则则s2取值取值是是0，1，2。由状态方程知：由状态方程知：s3=s2+x2-2,又由又由于于 4 s3 0,即即4 s2+x2-2 0;X2=x2|2s2+x26且且x2 5,s2=0,1,2k=261k=1这是第这是第1个月，需求为个月，需求为3。第一个月无库存第一个月无库存s1=0，s2=x1-3=x1-3，又因，又因x1 5，s2取值是取值是0，1，2。X1=x1|3x15k=1625 设备更新问题设备更新问题设备在使用全过程中会遭受磨损设备在使用全过程中会遭受磨损,使用一使用一段时间后就要维修段时间后就要维修,而且使用的时间越长而且使用的时间越长,维修费用越高维修费用越高,设备使用多少时间在经济设备使用多少时间在经济上最合算上最合算,就是设备更新问题。就是设备更新问题。5 设备更新问题设备在使用全过程中会遭受磨损,使用一段时间63例例:某设备的年效益和年均维修费用如下表某设备的年效益和年均维修费用如下表,如何在未来的如何在未来的5年内进行更新决策。年内进行更新决策。使用年限使用年限 0 1 2 3 4效益效益 r 5 4.5 4 3.75 3 维修费维修费u 0.5 1 1.5 2 2.5更新费更新费c 0.5 1.5 2.2 2.5 3例:某设备的年效益和年均维修费用如下表,如何在未来的5年64分析：分析：分析：分析：阶段阶段阶段阶段 k=k=1,2,3,4,5;1,2,3,4,5;s sk k 表示表示表示表示 k k 年初设备已使用的年限年初设备已使用的年限年初设备已使用的年限年初设备已使用的年限;x xk k 为为为为 k k 年初决定设备是继续使用还是更新的决年初决定设备是继续使用还是更新的决年初决定设备是继续使用还是更新的决年初决定设备是继续使用还是更新的决策变量策变量策变量策变量:x xk k=1 1表示继续使用表示继续使用表示继续使用表示继续使用,x xk k=0 0表示更新表示更新表示更新表示更新;状态转移方程状态转移方程状态转移方程状态转移方程:s sk k+1+1=s sk k+1+1，x xk k=1;=1;s sk k+1+1=1=1，x xk k=0=0分析：65阶段函数阶段函数:vk(sk)=r(skxk)-u(skxk)-c(sk)(1-xk)r(0)-u(0)-c(sk)(xk=0)vk(sk)=r(sk)-u(sk)(xk=1)递推函数递推函数:fk(sk)=maxvk(sk)+fk+1(sk+1)阶段函数:66 k=k=5 5 状态变量状态变量状态变量状态变量 s s5 5 可取可取可取可取 1,2,3,4 1,2,3,4f f5 5(1)=(1)=maxmaxx x1 1=0,1=0,1 r r(0)-(0)-u u(0)-(0)-c c(1),(1),r r(1)-(1)-u u(1)(1)=max max 5-0.5-1.5,5-0.5-1.5,4.5-14.5-1=3.5(=3.5(x x5 5*=1)*=1)f f5 5(2)=(2)=maxmax5-0.5-2.2,5-0.5-2.2,4-1.54-1.5=2.5(=2.5(x x5 5*=1)*=1)f f5 5(3)=(3)=maxmax 5-0.5-2.55-0.5-2.5,3.75-2=2 (,3.75-2=2 (x x5 5*=0)*=0)f f5 5(4)=(4)=maxmax 5-0.5-35-0.5-3,3-2.5=1.5 (,3-2.5=1.5 (x x5 5*=0)*=0)k=5 状态变量 s5 可取 1,2,3,467k=k=4 4状态变量状态变量状态变量状态变量 s s4 4 可取可取可取可取 1,2,3 1,2,3 f f4 4(1)=(1)=maxmax r r(0)-(0)-u u(0)-(0)-c c(1)+(1)+f f5 5(1),(1),r r(1)-(1)-u u(1)+(1)+f f5 5(2)(2)=max max 5-0.5-1.5+3.55-0.5-1.5+3.5,4.5-1+2.5=6.5 (,4.5-1+2.5=6.5 (x x4 4*=0)*=0)f f4 4(2)=(2)=max max 5-0.5-2.2+3.55-0.5-2.2+3.5,4-1.5+2=5.8 (,4-1.5+2=5.8 (x x4 4*=0)*=0)f f4 4(3)=(3)=max max 5-0.5-2.5+3.55-0.5-2.5+3.5,3.75-2+1.5 =5.5 (,3.75-2+1.5 =5.5 (x x4 4*=*=0)0)k=4状态变量 s4 可取 1,2,3 68 k=k=3 3状态变量状态变量状态变量状态变量 s s3 3 可取可取可取可取 1,2,1,2,f f3 3(1)=(1)=maxmax r r(0)-(0)-u u(0)-(0)-c c(1)+(1)+f f4 4(1),(1),r r(1)-(1)-u u(1)+(1)+f f4 4(2)(2)=max max 5-0.5-1.5+6.55-0.5-1.5+6.5,4.5-1+5.8=9.5 (,4.5-1+5.8=9.5 (x x3 3*=*=0)0)f f3 3(2)=(2)=max max 5-0.5-2.2+6.55-0.5-2.2+6.5,4-1.5+5.5=8.8 (,4-1.5+5.5=8.8 (x x3 3*=*=0)0)k=3状态变量 s3 可取 1,2,69k=k=2 2状态变量状态变量状态变量状态变量 s s2 2 可取可取可取可取 1,1,f f2 2(1)=(1)=maxmax r r(0)-(0)-u u(0)-(0)-c c(1)+(1)+f f3 3(1),(1),r r(1)-(1)-u u(1)+(1)+f f3 3(2)(2)=max max 5-0.5-1.5+9.55-0.5-1.5+9.5,4.5-1+8.8,4.5-1+8.8 =12.5 (=12.5 (x x2 2*=0)*=0)k=2状态变量 s2 可取 1,70最优策略为最优策略为最优策略为最优策略为:k k=1 12 23 34 45 5 不更新不更新不更新不更新 更新更新更新更新 更新更新更新更新 更新更新更新更新 不更新不更新不更新不更新k=k=1 1时状态变量时状态变量时状态变量时状态变量 s s1 1 只能取只能取只能取只能取 0 0 f f1(0)=1(0)=maxmax r r(0)-(0)-u u(0)-(0)-c c(0)+(0)+f f2(1),2(1),r r(0)-(0)-u u(0)+(0)+f f2(1)2(1)=maxmax5-0.5-0.5+12.5,5-0.5-0.5+12.5,5-0.5+12.55-0.5+12.5 =17 (=17 (x x1*=1)1*=1)最优策略为:k=1时状态变量 s1 只能取 0 716、机器负荷分配问题、机器负荷分配问题 有有某某种种机机床床，可可以以在在高高低低两两种种不不同同的的负负荷荷下下进进行行生生产产，在在高高负负荷荷下下生生产产时时，产产品品的的年年产产量量为为 g，与与年年初初投投入入生生产产的的机机床床数数量量 u1 的的关关系系为为 g=g(u1)=8u1，这这时时，年年终终机机床床完完好好台台数数将将为为，au1 (a为为机机床床完完好好率率，0 a 1，设设 a=0.7)。在在低低负负荷荷下下生生产产时时，产产品品的的年年产产量量为为 h，和和投投入入生生产产的的机机床床数数量量的的关关系系为为 h=h(u2)=5u2，相相应应的的机机床床完完好好率率为为 b(0b2，设设 b=0.9)，一一般般情情况况下下(a b )。假假设设某某厂厂开开始始有有 x1=1000 台台完完好好的的机机床床，现现要要制制定定一一个个五五年年生生产产计计划划，问问每每年年开开始始时时如如何何重重新新分分配配完完好好的的机机床床在在两两种种不不同同的的负负荷荷下下生生产产的的数数量量，以以使使在在5年内产品的总产量为最高。年内产品的总产量为最高。6、机器负荷分配问题72 解：解：首先构造这个问题的动态规划模型。首先构造这个问题的动态规划模型。1分分阶阶段段：设设阶阶段段变变量量 k 表表示示年年度度，因因此此，阶段总数阶段总数 n=5。2.状状态态变变量量：用用 sk 表表示示第第 k 年年度度初初拥拥有有的的完完好好机机床床台台数数，同同时时也也是是第第 k-1 年年度度末末时时的完好机床数量。的完好机床数量。3.决策变量：决策变量：用用 uk 表示第表示第 k 年度中分配年度中分配于高负荷下生产的机床台数。于是于高负荷下生产的机床台数。于是 sk-uk 便为该年度中分配于低负荷下生产的机床便为该年度中分配于低负荷下生产的机床台数。台数。解：首先构造这个问题的动态规划模型。1分阶段：设阶段变量734状态转移方程为：状态转移方程为：决策变量的取值：决策变量的取值：在第在第 k 段为段为 4状态转移方程为：决策变量的取值：在第 k 段为 746阶段指标函数阶段指标函数令令 vk(sk,uk)表表示示由由第第 k 年年的的状状态态 sk 出出发发，采采取取uk分配方案的产品产量分配方案的产品产量.7条件最优目标函数递推方程条件最优目标函数递推方程令令 fk(sk)表表示示由由第第 k 年年的的状状态态 sk 出出发发，采采取取最最优优分分配配方方案案到到第第5年年度度结结束束这这段段时时间间的的产产品品产量，根据最优化原理有以下递推关系产量，根据最优化原理有以下递推关系:6阶段指标函数令 vk(sk,uk)表示由第 k 年的75动态规划(全套)课件76下下面面采采用用逆逆序序递递推推计计算算法法,从从第第5年年度度开开始始递递推计算推计算K=5 时有时有显显然然，当当 u5*=s5 时时，f5(s5)有有最最大大值值，相相应应的有的有 f5(s5)=8s5。下面采用逆序递推计算法,从第5年度开始递推计算K=5 时有77K=4 K=4 时有：时有：K=4 时有：78 因此，当因此，当 u4*=s4 时，有最大值时，有最大值 f4(s4)=13.6s4K=3=3 时有：时有：可可见见，当当 u3*=s3 时时，有有最最大大值值 f3(s3)=17.55s3 。K=2=2 时有：时有：因此，当 u4*=s4 时，有最大值 f4(s4)=1379 此此 时时，当当 u2*=0 时时 有有 最最 大大 值值，即即 f2(s2)=20.8s2,其中其中 s2=0.7u1+0.9(s1-u1)K=1=1 时有：时有：此时，当 u2*=0 时有最大值，即 f2(s2)=280当当 u1*=0 时时,有最大值，即有最大值，即 f1(s1)=23.7s1,因为因为 s1=1000,故故 f1(s1)=23700 个产品。个产品。按照上述计算顺序寻踪得到下述计算结果：按照上述计算顺序寻踪得到下述计算结果：当 u1*=0 时,有最大值，即 f1(s1)=23.781 上面所讨论的最优决策过程是所谓始端上面所讨论的最优决策过程是所谓始端状态固定，终端状态自由如果终端也附加状态固定，终端状态自由如果终端也附加上一定的约束条件，那么计算结果将会与之上一定的约束条件，那么计算结果将会与之有所差别例如，若规定在第五个年度结束有所差别例如，若规定在第五个年度结束时，完好的机床数量为时，完好的机床数量为500台台(上面只有上面只有278台台)，问应该如何安排五年的生产，使之在，问应该如何安排五年的生产，使之在满足这一终端要求的情况下产量最高？满足这一终端要求的情况下产量最高？解：解：由状态转移方程由状态转移方程 上面所讨论的最优决策过程是所谓始端状态固定，终端82有有由此式得由此式得当当 k=5 时有时有当当 k=4 时有时有有由此式得当 k=5 时有当 k=4 时有83显显 然然，只只 有有 取取 u4*=0,有有 最最 大大 值值 f4(s4)=21.4s4-7500显然，只有取 u4*=0,有最大值 f4(s4)=2184当当 k=3 时有时有:显显然然，只只有有取取 u3*=0,f3(s3)有有最最大大值值 f3(s3)=24.5s3-7500 。当 k=3 时有:显然，只有取 u3*=0,f3(s3)85当当 k=2 时有时有:显显然然，只只有有取取 u2*=0,f2(s2)有有最最大大值值 f2(s2)=27.1s2-7500 。当 k=2 时有:显然，只有取 u2*=0,f2(s2)86当当 k=1 时有时有:显显然然，只只有有取取 u1*=0,f1(s1)有有最最大大值值 f1(s1)=29.4s1-7500 。当 k=1 时有:显然，只有取 u1*=0,f1(s1)87动态规划(全套)课件887、非线性规划问题求解、非线性规划问题求解某某公公司司拥拥有有资资金金 10 万万元元，若若投投资资于于项项目目 i(i1，2，3)的的投投资资额额为为 xi 时时，其其收收益益分分别别为为 g1(x1)=4x1 ,g2(x2)=9x2 ,g3(x3)=2x32,问问应应如如何何分配投资数额才能使总收益最大分配投资数额才能使总收益最大?这这是是一一个个与与时时间间无无明明显显关关系系的的静静态态最最优优化化问题，可列出其静态模型为：问题，可列出其静态模型为：7、非线性规划问题求解 这是一个与时间无明显关系的89满足满足 我们可以人为地赋予它我们可以人为地赋予它“时段时段”的概念，的概念，用动态规划方法求解用动态规划方法求解 解：解：（解法（解法1）首先用逆序构造动态规划模型。首先用逆序构造动态规划模型。1分分阶阶段段：设设阶阶段段变变量量 k 表表示示依依次次对对第第 k 个个项目投资，因此，阶段总数项目投资，因此，阶段总数 n=3。(k=1,2,3)满足 我们可以人为地赋予它“时段”的概念，用动态规划902.状状态态变变量量：用用 sk 表表示示已已经经对对第第 1 至至 第第 k-1 个个项项目目投投资资后后的的剩剩余余资资金金；即即第第 k 段段初初拥拥有有的的可可以以分分配配给给第第 k 到到第第3个个项项目目的的资金额资金额（单位：万元）（单位：万元）。3.决策变量：决策变量：用用 xk 表示对第表示对第 k 个项目投个项目投资资 的资金数量（单位：万元）。的资金数量（单位：万元）。决策变量的取值：决策变量的取值：0 xk sk 4状态转移方程为：状态转移方程为：2.状态变量：用 sk 表示已经对第 1 至 第 k-1916.基本方程为：基本方程为：最优指标函数最优指标函数 fk(sk)表示第表示第 k 阶段，初阶段，初始状态为始状态为 sk 时，从第时，从第 k 到第到第 3 个项目所获个项目所获最大收益最大收益 6.基本方程为：最优指标函数 fk(sk)92当当 k=3 时：时：当当 k=2 时：时：当 k=3 时：当 k=2 时：93极大值只可能在极大值只可能在 0，s2 端点取得，端点取得，极大值只可能在 0，s2 端点取得，94当当 k=1 时：时：当 k=1 时：95矛盾，所以舍去矛盾，所以舍去 sk 9/2矛盾，所以舍去 sk 9/296故故 极大值只能在极大值只能在 0，10 的端点取得，比的端点取得，比较较0，10两个端点的函数值两个端点的函数值 故 极大值只能在 0，10 的端点取得，比较0，197即全部资金投于第即全部资金投于第3个项目个项目 即全部资金投于第3个项目 98(解法解法2)用顺序解法用顺序解法 1.阶段划分阶段划分:（同上）（同上）和和决策变量决策变量 2.状态变量状态变量:用用 sk 表示可用于第表示可用于第1到第到第 k-1个项目投资的金额，即对第个项目投资的金额，即对第 k 个项目到第个项目到第3个项目投资后的剩余资金数量。个项目投资后的剩余资金数量。3.决策变量决策变量:（同上）（同上）4.状态转移方程状态转移方程:(解法2)用顺序解法 1.阶段划分:（同上）995.决策变量的取值范围：决策变量的取值范围：6.最优指标函数：最优指标函数：令令 fk(sk+1)表示第表示第 k 段投资额段投资额 sk+1 为时，第为时，第1到第到第 k 项目所获的最大收益，此时顺序解项目所获的最大收益，此时顺序解法的基本方程为：法的基本方程为：5.决策变量的取值范围：6.最优指标函数：令 fk100 当当 k=1 时，有时，有 当当 k=2 时，有时，有 当 k=1 时，有 当 k=2 时，有 101 当当 k3 时，有时，有 当 k3 时，有102 x3=9/4 为极小点。为极小点。极大值应在极大值应在0，s4 0，10 端点取得端点取得再由状态转移方程逆推：再由状态转移方程逆推：x3=9/4 为极小点。极大值应在0，103动态规划(全套)课件104