运筹学与最优化方法修改动态规划.pptx

11.1.多阶段决策过程的最优化多阶段决策过程(Multi-Stagedecision process)：前一个阶段的决策要影响到后一个阶段的决策，从而影响整个过程。各个阶段所确定的决策就构成了一个决策序列，称为一个策略。一般来说，由于每一阶段可供选择的决策往往不止一个，因此，对于整个过程，就会有许多可供选择的策略。第1页/共122页21.1.多阶段决策过程的最优化最优策略：若对应于一个策略，可以由一个量化的指标来确定这个策略所对应的活动过程的效果，那么不同的策略就有各自的效果。在所有可供选择的策略中，对应效果最好的策略称为最优策略。把一个问题划分成若干个相互联系的阶段选取其最优策略，这类问题就是多阶段决策问题。第2页/共122页31.1.多阶段决策过程的最优化 多多阶阶段段决决策策过过程程最最优优化化的的目目标标是是要要达达到到整整个个活活动动过过程程的的总总体体效效果果最最优优。由由于于各各段段决决策策间间有有机机地地联联系系着着，本本段段决决策策的的执执行行将将影影响响到到下下一一段段的的决决策策，以以至至于于影影响响总总体体效效果果，所所以以决决策策者者在在每每段段决决策策时时不不应应仅仅考考虑虑本本阶阶段段最最优优，还还应应考考虑虑对对最最终终目目标标的的影影响响，从从而而作作出出对对全全局局来来讲讲是是最最优优的的决决策策。动动态态规规划就是符合这种要求的一种决策方法。划就是符合这种要求的一种决策方法。第3页/共122页41.1.多阶段决策过程的最优化二、多阶段决策问题举例 1)1)工厂生产过程：由于市场需求是一随着时间而变化的因素，因此，为了取得全年最佳经济效益，就要在全年的生产过程中，逐月或者逐季度地根据库存和需求情况决定生产计划安排。属于多阶段决策类的问题很多，例如：第4页/共122页51.1.多阶段决策过程的最优化 2)2)设备更新问题：一般企业用于生产活动的设备，刚买来时故障少，经济效益高，即使进行转让，处理价值也高，随着使用年限的增加，就会逐渐变为故障多，维修费用增加，可正常使用的工时减少，加工质量下降，经济效益差，并且，使用的年限越长、处理价值也越低，自然，如果卖去旧的买新的，还需要付出更新费因此就需要综合权衡决定设备的使用年限，使总的经济效益最好。第5页/共122页61.1.多阶段决策过程的最优化 3)3)连续生产过程的控制问题：一般化工生产过程中，常包含一系列完成生产过程的设备，前一工序设备的输出则是后一工序设备的输入，因此，应该如何根据各工序的运行工况，控制生产过程中各设备的输入和输出，以使总产量最大。第6页/共122页71.1.多阶段决策过程的最优化 以上所举问题的发展过程都与时间因素有关，因此在这类多阶段决策问题中，阶段的划分常取时间区段来表示，并且各个阶段上的决策往往也与时间因素有关，这就使它具有了“动态”的含义，所以把处理这类动态问题的方法称为动态规划方法。不过，实际中尚有许多不包含时间因素的一类“静态”决策问题，就其本质而言是一次决策问题，是非动态决策问题，但是也可以人为地引入阶段的概念当作多阶段决策问题，应用动态规划方法加以解决。第7页/共122页81.1.多阶段决策过程的最优化 4 4）资源分配问题：属于这类静态问题。如：某工业部门或公司，拟对其所属企业进行稀缺资源分配，为此需要制定出收益最大的资源分配方案。这种问题原本要求一次确定出对各企业的资源分配量，它与时间因素无关，不属动态决策，但是，我们可以人为地规定一个资源分配的阶段和顺序，从而使其变成一个多阶段决策问题(后面我们将详细讨论这个问题)。第8页/共122页91.1.多阶段决策过程的最优化 5 5）运输网络问题：如下页图1 1所示的运输网络，点间连线上的数字表示两地距离(也可是运费、时间等)，要求从v v1 1 至v v1010的最短路线。这种运输网络问题也是静态决策问题。但是，按照网络中点的分布，可以把它分为4 4个阶段，而作为多阶段决策问题来研究。第9页/共122页101.1.多阶段决策过程的最优化图11 运输网络图示第10页/共122页111.1.多阶段决策过程的最优化 三、动态规划求解的多阶段决策问题的特点三、动态规划求解的多阶段决策问题的特点 通常多阶段决策过程的发展是通过状态的一系列变换来实现的。一般情况下，系统在某个阶段的状态转移除与本阶段的状态和决策有关外，还可能与系统过去经历的状态和决策有关。因此，问题的求解就比较困难复杂。而适合于用动态规划方法求解的只是一类特殊的多阶段决策问题，即具有“无后效性”的多阶段决策过程。所谓无后效性，又称马尔柯夫性，是指系统从某个阶段往后的发展，仅由本阶段所处的状态及其往后的决策所决定，与系统以前经历的状态和决策(历史)无关。第11页/共122页12多阶段决策过程特点:要点：阶段，状态，决策，状态转移方程，k-后部子过程状态 x1阶段1T1决策u1状态 x2决策u2阶段2T2状态 x3.状态 xk决策uk阶段kTk状态 xk+1.状态 xn决策un阶段nTn状态 xn+11.1.多阶段决策过程的最优化第12页/共122页131.1.多阶段决策过程的最优化四、动态规划方法导引例1 1：为了说明动态规划的基本思想方法和特点，下面以图1所示为例讨论的求最短路问题的方法。第一种方法称做全枚举法或穷举法。它的基本思想是列举出所有可能发生的方案和结果，再对它们一一进行比较，求出最优方案。这里从v v1 1到v v1010的路程可以分为4 4个阶段。第一段的走法有三种，第二三两段的走法各有两种，第四段的走法仅一种，因此共有322132211212条可能的路线，分别算出各条路线的距离，最后进行比较，可知最优路线是v v1 1 v v3 3 v v7 7 v v9 9 v v1010 ,最短距离是1818第13页/共122页141.1.多阶段决策过程的最优化 显然，当组成交通网络的节点很多时，用穷举法求最优路线的计算工作量将会十分庞大，而且其中包含着许多重复计算 第二种方法即所谓“局部最优路径”法，是说某人从k出发，他并不顾及全线是否最短，只是选择当前最短途径，“逢近便走”，错误地以为局部最优会致整体最优，在这种想法指导下，所取决策必是v1 v3 v5 v8 v10，全程长度是20；显然，这种方法的结果常是错误的第14页/共122页151.1.多阶段决策过程的最优化 第三种方法是动态规划方法。动态规划方法寻求该最短路问题的基本思想是，首先将问题划分为4个阶段，每次的选择总是综合后继过程的一并最优进行考虑，在各段所有可能状态的最优后继过程都已求得的情况下，全程的最优路线便也随之得到。为了找出所有可能状态的最优后继过程，动态规划方法总是从过程的最后阶段开始考虑，然后逆着实际过程发展的顺序，逐段向前递推计算直至始点。第15页/共122页161.1.多阶段决策过程的最优化结论：全枚举法虽可找出最优方案，但不是个好算法；局部最优法则完全是个错误方法；动态规划方法属较科学有效的算法：它的基本思想是，把一个比较复杂的问题分解为一系列同类型的更易求解的子问题，便于应用计算机。整个求解过程分为两个阶段，先按整体最优的思想逆序地求出各个子问题中所有可能状态的最优决策与最优路线值，然后再顺序地求出整个问题的最优策略和最优路线。计算过程中，系统地删去了所有中间非最优的方案组合，从而使计算工作量比穷举法大为减少。第16页/共122页17 2.2.动态规划的基本概念 使用动态规划方法解决多阶段决策问题，首先要将实际问题写成动态规划模型，同时也为了今后叙述和讨论方便，这里需要对动态规划的下述一些基本术语进一步加以说明和定义基本术语进一步加以说明和定义：第17页/共122页18 2.2.动态规划的基本概念 (一)阶段和阶段变量 为了便于求解和表示决策及过程的发展顺序，而把所给问题恰当地划分为若干个相互联系又有区别的子问题，称之为多段决策问题的阶段。一个阶段，就是需要作出一个决策的子问题，通常，阶段是按决策进行的时间或空间上先后顺序划分的。用以描述阶段的变量叫作阶段变量，一般以k k表示阶段变量阶段数等于多段决策过程从开始到结束所需作出决策的数目。第18页/共122页19 2.2.动态规划的基本概念 （二）状态、状态变量和可能状态集 1.状态与状态变量。用以描述事物(或系统)在某特定的时间与空间域中所处位置及运动特征的量，称为状状态态。反映状态变化的量叫做状状态态变变量量。状态变量必须包含在给定的阶段上确定全部允许决策所需要的信息。按照过程进行的先后，每个阶段的状态可分为初始状态和终止状态，或称输入状态和输出状态，阶段k k的初始状态记作s sk k，终止状态记为s sk+1k+1。但为了清楚起见，通通常常定定义义阶阶段段的的状状态态即即指指其其初初始状态始状态。第19页/共122页202.2.动态规划的基本概念 2可能状态集 一般状态变量的取值有一定的范围或允许集合，称为可能状态集，或可达状态集。可能状态集实际上是关于状态的约束条件。通常可能状态集用相应阶段状态sk的大写字母Sk表示，skSk，可能状态集可以是一离散取值的集合，也可以为一连续的取值区间，视具体问题而定第20页/共122页21 （三）决策、决策变量和允许决策集合 所谓决决策策，就是确定系统过程发展的方案。决策的实质是关于状态的选择，是决策者从给定阶段状态出发对下一阶段状态作出的选择。用以描述决策变化的量称之决策变量,和状态变量一样，决策变量可以用一个数，一组数或一向量来描述，也可以是状态变量的函数，记以u uk k=u uk k(s sk k)，表示于阶段k k状态s sk k时的决策变量。决策变量的取值往往也有一定的允许范围，称之允许决策集合。决策变量u uk k(s sk k)的允许决策集用U Uk k(s sk k)表示,u uk k(s sk k)U Uk k(s sk k)允许决策集合实际是决策的约束条件。2.2.动态规划的基本概念第21页/共122页22 （四）、策略和允许策略集合 策略(Policy)Policy)也叫决策序列策略有全过程策略和k k部子策略之分，全过程策略是指具有n n个阶段的全部过程，由依次进行的n n个阶段决策构成的决策序列，简称策略，表示为p p1,1,n n u u1 1,u u2 2,u un n。从k k阶段到第n n阶段，依次进行的阶段决策构成的决策序列称为k k部子策略,表示为p pk,nk,n u uk k,u uk k+1+1,u un n ，显然当k k=1=1时的k k部子策略就是全过程策略。在实际问题中，由于在各个阶段可供选择的决策有许多个，因此，它们的不同组合就构成了许多可供选择的决策序列(策略)，由它们组成的集合，称之允许策略集合，记作P P1,1,n n ，从允许策略集中，找出具有最优效果的策略称为最优策略。2.2.动态规划的基本概念第22页/共122页23 （五）状态转移方程 系统在阶段k处于状态sk，执行决策uk(sk)的结果是系统状态的转移，即系统由阶段k的初始状态sk转移到终止状态sk+1，或者说，系统由k阶段的状态sk转移到了阶段k+1的状态sk+1，多阶段决策过程的发展就是用阶段状态的相继演变来描述的。对于具有无后效性的多阶段决策过程,系统由阶段k k到阶段k k+1+1的状态转移完全由阶段k k的状态s sk k和决策u uk k(s(sk k)所确定，与系统过去的状态s s1 1,s s2 2,s sk k-1-1及 其 决 策u u1 1(s s1 1),),u u2 2(s s2 2)u uk k-1 1(s sk k-1-1)无关。系统状态的这种转移，用数学公式描述即有：2.2.动态规划的基本概念(1)第23页/共122页24 通常称式(1)为多阶段决策过程的状态转移方程。有些问题的状态转移方程不一定存在数学表达式，但是它们的状态转移，还是有一定规律可循的。(六)指标函数 用来衡量策略或子策略或决策的效果的某种数量指标，就称为指标函数。它是定义在全过程或各子过程或各阶段上的确定数量函数。对不同问题，指标函数可以是诸如费用、成本、产值、利润、产量、耗量、距离、时间、效用，等等。2.2.动态规划的基本概念第24页/共122页25 (1)阶段指标函数（也称阶段效应）。用gk(sk,uk)表示第k段处于sk状态且所作决策为uk(sk)时的指标，则它就是第k段指标函数，简记为gk。(2)过程指标函数（也称目标函数）。用Rk(sk,uk)表示第k子过程的指标函数。如图5-1的Rk(sk,uk)表示处于第k段sk状态且所作决策为uk时，从sk点到终点v10的距离。由此可见，Rk(sk,uk)不仅跟当前状态sk有关，还跟该子过程策略pk(sk)有关，因此它是sk和pk(sk)的函数，严格说来，应表示为:2.2.动态规划的基本概念第25页/共122页26 不过实际应用中往往表示为R Rk k(s sk k,u uk k)或R Rk k(s sk k)。还跟第 k k 子过程上各段指标函数有关，过程指标函数R Rk k(s sk k)通常是描述所实现的全过程或k k后部子过程效果优劣的数量指标，它是由各阶段的阶段指标函数g gk k(s sk k,u uk k)累积形成的，适于用动态规划求解的问题的过程指标函数（即目标函数），必须具有关于阶段指标的可分离形式对于 k k 部子过程的指标函数可以表示为：式中，表示某种运算，可以是加、减、乘、除、开方等。2.2.动态规划的基本概念(2)第26页/共122页27 多阶段决策问题中，常见的目标函数形式之一是取各阶段效应之和的形式，即:(3)(3)有些问题，如系统可靠性问题，其目标函数是取各阶段效应的连乘积形式，如：(4)(4)总之，具体问题的目标函数表达形式需要视具体问题而定。2.2.动态规划的基本概念第27页/共122页282.2.动态规划的基本概念 (七)最优解 用fk(sk)表示第k子过程指标函数 在状态sk下的最优值,即 称fk(sk)为第k子过程上的最优指标函数；与它相应的子策略称为sk状态下的最优子策略，记为pk*(sk)；而构成该子策赂的各段决策称为该过程上的最优决策，记为有简记为第28页/共122页29 特别当k=1且s1取值唯一时，f1(s1)就是问题的最优值，而p1*就是最优策略。如例1只有唯一始点v1即s1取值唯一,故f1(s1)=18就是例1的最优值，而 就是例1的最优策略。但若取值不唯一,则问题的最优值记为f0有 最优策略即为s1=s1*状态下的最优策略：我们把最优策略和最优值统称为问题的最优解。2.2.动态规划的基本概念第29页/共122页30 按上述定义，所谓最优决策 是指它们在全过程上整体最优(即所构成的全过程策略为最优)，而不一定在各阶段上单独最优。(八)多阶段决策问题的数学模型综上所述，适于应用动态规划方法求解的一类多阶段决策问题，亦即具有无后效性的多阶段决策问题的数学模型呈以下形式:2.2.动态规划的基本概念（5）第30页/共122页31 式中“OPT”表示最优化，视具体问题取max或min。上述数学模型说明了对于给定的多阶段决策过程，求取一个(或多个)最优策略或最优决策序列 ，使之既满足式(5)给出的全部约束条件，又使式(5)所示的目标函数取得极值，并且同时指出执行该最优策略时，过程状态演变序列即最优路线2.2.动态规划的基本概念第31页/共122页32最优化原理 （贝尔曼最优化原理）作为一个全过程的最优策略具有这样的性质：对对于于最最优优策策略略过过程程中中的的任任意意状状态态而而言言，无无论论其其过过去去的的状状态态和和决决策策如如何何，余余下下的的诸诸决决策策必必构构成成一一个个最最优优子子策策略略。该原理的具体解释是，若某一全过程最优策略为：动态规划的基本原理 则对上述策略中所隐含的任一状态而言，第k子过程上对应于该状态的最优策略必然 包含在上述全过程最优策略p1*中，即为第32页/共122页333.3.动态规划方法的基本步骤 1应将实际问题恰当地分割成n个子问题(n个阶段)。通常是根据时间或空间而划分的，或者在经由静态的数学规划模型转换为动态规划模型时，常取静态规划中变量的个数n，即k=n。2正确地定义状态变量sk，使它既能正确地描述过程的状态，又能满足无后效性动态规划中的状态与一般控制系统中和通常所说的状态的概念是有所不同的，动态规划中的状态变量必须具备以下三个特征：第33页/共122页343.3.动态规划方法的基本步骤 (1)要能够正确地描述受控过程的变化特征。(2)(2)要满足无后效性。即如果在某个阶段状态已经给定，那么在该阶段以后，过程的发展不受前面各段状态的影响，如果所选的变量不具备无后效性，就不能作为状态变量来构造动态规划的模型。(3)(3)要满足可知性。即所规定的各段状态变量的值，可以直接或间接地测算得到。一般在动态规划模型中，状态变量大都选取那种可以进行累计的量。此外，在与静态规划模型的对应关系上，通常根据经验，线性与非线性规划中约束条件的个数，相当于动态规划中状态变量s sk k的维数而前者约束条件所表示的内容，常就是状态变量s sk k所代表的内容。第34页/共122页353.3.动态规划方法的基本步骤 3正确地定义决策变量及各阶段的允许决策集合Uk(sk)，根据经验，一般将问题中待求的量，选作动态规划模型中的决策变量。或者在把静态规划模型(如线性与非线性规划)转换为动态规划模型时，常取前者的变量xj为后者的决策变量uk。4.能够正确地写出状态转移方程，至少要能正确反映状态转移规律。如果给定第k阶段状态变量sk的值，则该段的决策变量uk一经确定，第k+1段的状态变量sk+1的值也就完全确定，即有sk+1=Tk(sk,uk)第35页/共122页363.3.动态规划方法的基本步骤 5根据题意,正确地构造出目标与变量的函数关系目标函数，目标函数应满足下列性质：(1)可分性，即对于所有k后部子过程，其 目 标 函 数 仅 取 决 于 状 态sk及 其 以 后 的 决 策 uk,uk+1,un,就是说它是定义在全过程和所有后部子过程上的数量函数。(2)要满足递推关系，即 (3)函数 对其变元Rk+1来说要严格单调。第36页/共122页37 6写出动态规划函数基本方程例如常见的指标函数是取各段指标和的形式 其中 表示第i i阶段的指标，它显然是满足上述三个性质的。所以上式可以写成 ：3.3.动态规划方法的基本步骤第37页/共122页38 学习方法建议：第一步 先看问题，充分理解问题的条件、情况及求解目标。第二步 结合前面讲到的理论和解题过程，考虑如何着手进行求解该问题的工作。分析针对该动态规划问题的“四大要素、一个方程”这一步在开始时会感到困难，但是一定要下决心去思考，在思考过程中深入理解前文讲到的概念和理论。4.动态规划方法应用举例第38页/共122页39 第三步 动手把求解思路整理出来，或者说，把该问题作为习题独立的来做。第四步 把自己的求解放到一边，看书中的求解方法，要充分理解教材中的论述。第五步 对照自己 的求解，分析成败。4.动态规划方法应用举例第39页/共122页42求 最 短 路 径第42页/共122页43 求 最 短 路 径例5.5第43页/共122页44将问题分成五个阶段，第k k阶段到达的具体地点用状态变量x xk k表示，例如：x x2 2=B B3 3表示第二阶段到达位置B B3 3，等等。这里状态变量取字符值而不是数值。将决策定义为到达下一站所选择的路径，例如目前的状态是x2=B3，这时决策允许集合包含三个决策，它们是D2(x2)=D2(B3)=B3C1,B3C2,B3C3求 最 短 路 径第44页/共122页45最优指标函数f fk k(x xk k)表示从目前状态到E E的最短路径。终端条件为f f5 5(x x5 5)=)=f f5 5(E E)=0)=0其含义是从E E到E E的最短路径为0 0。第四阶段的递推方程为:求 最 短 路 径第45页/共122页46其中*表示最优值，在上表中，由于决策允许集合D D4 4(x x4 4)中的决策是唯一的，因此这个值就是最优值。由此得到f f4 4(x x4 4)的表达式。由于这是一个离散的函数，取值用列表表示：求 最 短 路 径第46页/共122页47第三阶段的递推方程为：求 最 短 路 径第47页/共122页48由此得到f f3 3(x x3 3)的表达式：求 最 短 路 径第48页/共122页49求 最 短 路 径第49页/共122页50由此得到f f2 2(x x2 2)的表达式：求 最 短 路 径第50页/共122页51第一阶段的递推方程为：求 最 短 路 径第51页/共122页52由此得到f f1 1(x x1 1)的表达式求 最 短 路 径第52页/共122页53【课堂练习例题】用动态规划法求解例1的最短路问题 AB1B2C1C2C3C4D1D2D3E1E2 E3F1F2G531368766835338422123335526643第53页/共122页54此问题的基本方程为 fk(sk)Min dk(uk)+fk+1(sk+1)ukDk(sk)k6,5,4,3,2,1 f7(s7)0按基本方程由后向前递推有:第54页/共122页55AB1B2C1C2C3C4D1D2D3E1E2 E3F1F2G531368766835338422123335526643当k=6时第55页/共122页56当k=5时AB1B2C1C2C3C4D1D2D3E1E2 E3F1F2G531368766835338422123335526643第56页/共122页57当k=4时AB1B2C1C2C3C4D1D2D3E1E2 E3F1F2G531368766835338422123335526643第57页/共122页58当k=3时AB1B2C1C2C3C4D1D2D3E1E2 E3F1F2G531368766835338422123335526643第58页/共122页59当k=2时AB1B2C1C2C3C4D1D2D3E1E2 E3F1F2G531368766835338422123335526643第59页/共122页60当k=1时AB1B2C1C2C3C4D1D2D3E1E2 E3F1F2G531368766835338422123335526643 由此可以看出，A到G的最短路长为18，路径为：AB1C2D1E2F2G第60页/共122页61用动态规划解决实际问题的用动态规划解决实际问题的基本过程基本过程是是：（1）正确划分阶段，选择阶段变量k.（2）对每个阶段，正确选择状态变量xk.选择状态变量时应当注意两点：一是要能够正确描述受控过程的演变特性，二是要满足无后效性.（3）对每个阶段，正确选择决策变量uk.（4）列出相邻阶段的状态转移方程：xk+1=Tk(xk,uk).（5 5）列出按阶段可分的准则函数V1,n.(6)(6)写出递推方程和边界条件，建立基本方程；(7)(7)按照基本方程递推求解。以上步骤是动态规划法处理问题的基本步骤，其中的前六步是建立动态规划模型的步骤。第61页/共122页62资 源 分 配 问 题第62页/共122页63 例5.6:5.6:有资金4 4万元，投资A A、B B、C C三个项目，每个项目的投资效益与投入该项目的资金有关。三个项目A A、B B、C C的投资效益（万吨）和投入资金（万元）关系见下表：求对三个项目的最优投资分配，使总投资效益最大。资 源 分 配 问 题第63页/共122页641.阶段k：每投资一个项目作为一个阶段；2.状态变量xk：投资第k个项目前的资金数；3.决策变量dk：第k个项目的投资；4.决策允许集合：0dkxk5.状态转移方程：xk+1=xk-dk6.阶段指标：vk(xk,dk)见表中所示；7.递推方程：fk(xk)=maxvk(xk,dk)+fk+1(xk+1)8.终端条件：f4(x4)=0资 源 分 配 问 题第64页/共122页65k=4，f4(x4)=0k=3，0d3x3，x4=x3-d3资 源 分 配 问 题第65页/共122页66k=2，0d2x2，x3=x2-d2资 源 分 配 问 题第66页/共122页67k=1，0d1x1，x2=x1-d1资 源 分 配 问 题第67页/共122页68背包问题第68页/共122页69背 包 问 题第69页/共122页70则 MaxMax z z=c c1 1x x1 1+c c2 2x x2 2+c cn nx xn n s.ts.t.w w1 1x x1 1+w w2 2x x2 2+w wn nx xn nW W x x1 1,x,x2 2,x,xn n为正整数1.1.阶 段k k：第k k次 装 载 第k k种 物 品（k k=1,2,=1,2,n n）2.2.状态变量x xk k：第k k次装载时背包还可以装载的重量；3.3.决策变量d dk k：第k k次装载第k k种物品的件数；背 包 问 题第70页/共122页714.4.决策允许集合：D Dk k(x xk k)=)=d dk k|0|0 d dk k x xk k/w wk k，d dk k为整数；5.5.状态转移方程：x xk k+1+1=x xk k-w wk kd dk k6.6.阶段指标：v vk k=c ck kd dk k7.7.递推方程 f fk k(x xk k)=max)=maxc ck kd dk k+f fk k+1+1(x xk k+1+1)=max =maxc ck kd dk k+f fk k+1+1(x xk k-w wk kd dk k)8.8.终端条件：f fn+1n+1(x xn+1n+1)=0)=0背 包 问 题第71页/共122页72 例5.7:5.7:对于一个具体问题c c1 1=65=65，c c2 2=80=80，c c3 3=30=30；w w1 1=2=2，w w2 2=3=3，w w3 3=1=1；以及W W=5=5用动态规划求解 f f4 4(x x4 4)=0)=0 对于k k=3=3背 包 问 题第72页/共122页73第73页/共122页74第74页/共122页75第75页/共122页76第76页/共122页77 机器负荷分配问题第77页/共122页78第78页/共122页79 构造动态规划模型如下：阶段k k：运行年份（k k=1,2,3,4,5,6=1,2,3,4,5,6），其中k k=1=1表示第一年初，依次类推；k k=6=6表示第五年末（即第六年初）。状态变量x xk k：第k k年初完好的机器数（k k=1,2,3,4,5,6=1,2,3,4,5,6），其中x x6 6表示第五年末（即第六年初）的完好机器数。决策变量d dk k：第k k年投入高负荷运行的机器数；状态转移方程：x xk k+1+1=0.7=0.7d dk k+0.9(+0.9(x xk k-d dk k)决策允许集合：D Dk k(x xk k)=)=d dk k|0|0 d dk k x xk k 阶段指标：v vk k(x xk k,d dk k)=8)=8d dk k+5(+5(x xk k-d dk k)终端条件：f f6 6(x x6 6)=0)=0 机器负荷分配问题第79页/共122页80递推方程：f fk k(x xk k)=max)=maxv vk k(x xk k,d dk k)+)+f fk k+1+1(x xk k+1+1)d dk k D Dk k(x xk k)=max8max8d dk k+5(+5(x xk k-d dk k)+)+f fk k+1+10.70.7d dk k+0.9(+0.9(x xk k-d dk k)0 dk xk 机器负荷分配问题第80页/共122页81f5(x5)=max8d5+5(x5-d5)+f6(x6)0 d5 x5=max3d5+5x5=8x5,d5*=x50 d5 x5f4(x4)=max8d4+5(x4-d4)+f5(x5)0 d4 x4=max8d4+5(x4-d4)+8x50 d4 x4=max8d4+5(x4-d4)+80.7d4+0.9(x4-d4)0 d4 x4=max1.4d4+12.3x4=13.7x4,d4*=x40 d4 x4 机器负荷分配问题第81页/共122页82f3(x3)=max8d3+5(x3-d3)+f4(x4)0 d3 x3=max8d3+5(x3-d3)+13.7x40 d3 x3=max8d3+5(x3-d3)+13.70.7d3+0.9(x3-d3)0 d3 x3=max0.28d3+17.24x3=17.52x3,d3*=x30 d3 x3 机器负荷分配问题第82页/共122页83f f2 2(x x2 2)=max8)=max8d d2 2+5(+5(x x2 2-d d2 2)+)+f f3 3(x x3 3)0 0 d d2 2 x x2 2 =max8 =max8d d2 2+5(+5(x x2 2-d d2 2)+17.52)+17.52x x3 3 0 0 d d2 2 x x2 2 =max8max8d d2 2+5(+5(x x2 2-d d2 2)+17.520.7)+17.520.7d d2 2+0.9(+0.9(x x2 2-d d2 2)0 0 d d2 2 x x2 2 =max-=max-0.5040.504d d2 2+20.77+20.77x x2 2=20.77=20.77x x2 2,d d2 2*=0*=0 0 0 d d2 2 x x2 2 机器负荷分配问题第83页/共122页84f f1 1(x x1 1)=max8)=max8d d1 1+5(+5(x x1 1-d d1 1)+)+f f2 2(x x2 2)0 0 d d1 1 x x1 1 =max8 =max8d d1 1+5(+5(x x1 1-d d1 1)+20.77)+20.77x x2 2 0 0 d d1 1 x x1 1 =max8max8d d1 1+5(+5(x x1 1-d d1 1)+20.770.7)+20.770.7d d1 1+0.9(+0.9(x x1 1-d d1 1)0 0 d d1 1 x x1 1 =max-=max-0.050.05d d1 1+23.69+23.69x x1 1=23.69=23.69x x1 1,d d1 1*=0 *=0 0 0 d d1 1 x x1 1 机器负荷分配问题第84页/共122页85由此可以得到：f1(x1)=23.69x1,d1*=0f2(x2)=20.77x2,d2*=0f3(x3)=17.52x3,d3*=x3f4(x4)=13.60 x4,d4*=x4f5(x5)=8x5 d5*=x5用x1=1000代入，得到五年最大产量为f1(x1)=f1(1000)=23690 机器负荷分配问题第85页/共122页86每年投入高负荷运行的机器数以每年初完好的机器数为：x1=1000d1*=0,x2=0.7d1+0.9(x1-d1)=900d2*=0,x3=0.7d2+0.9(x2-d2)=810d3*=x3=810,x4=0.7d3+0.9(x3-d3)=567d4*=x4=567,x5=0.7d4+0.9(x4-d4)=397d5*=x5=397,x6=0.7d5+0.9(x5-d5)=278 机器负荷分配问题第86页/共122页87 在这个例子中，状态变量的终端值x x6 6是未加约束的，如果要求在第五年末（即第六年初）完好的机器数不少于500500台，这时决策变量d d5 5的决策允许集合将成为：D D5 5(x x5 5)=)=d d5 5|0.7|0.7d d5 5+0.9(+0.9(x x5 5-d d5 5)500,500,d d5 5 00即 0.90.9x x5 5-0.2-0.2d d5 5 500500d d5 5 0 0 或 0 d5 4.5x5-2500 容易想象，这时的最大产量将比x6是自由的情况下小。这个例子可以推广到一般情况。设高负荷生产时机器的完好率为k1，单台产量为p1；低负荷完好率为k2，单台产量为p2。若有t满足:机器负荷分配问题第87页/共122页88则从1 1t t-1-1年，年初将全部完好机器投入低负荷运行，从t tn n年，年初将全部完好机器投入高负荷运行，这样的决策，将使总产量达到最大。机器负荷分配问题第88页/共122页89生 产 库 存 问 题第89页/共122页90 例例5.95.9：一个工厂生产某种产品,1-,1-7 7月份生产成本和产品需求量的变化情 况如下表：生 产 库 存 问 题第90页/共122页91阶段k：月份，k=1,2,7,8；状态变量xk：第k个月初（发货以前）的库存量；决策变量dk：第k个月的生产量；状态转移方程：xk+1=xk-rk+dk；决策允许集合：Dk(xk)=dk|dk0,rk+1xk+1H =dk|dk0,rk+1xk-rk+dkH；阶段指标：vk(xk,dk)=ckdk；终端条件：f8(x8)=0,x8=0；生 产 库 存 问 题第91页/共122页92递推方程：f fk k(x xk k)=min)=minv vk k(x xk k,d,dk k)+)+f fk k+1+1(x xk k+1+1)d dk k D Dk k(x(xk k)=min =minc ck kd dk k+f fk k+1+1(x xk k-r rk k+d dk k)d dk k D Dk k(x xk k)对于k k=7=7因为 x x8 8=0=0，有 d d7 7=0=0递推方程为：f f7 7(x x7 7)=min)=minc c7 7d d7 7+f f8 8(x x8 8)=0)=0 d d7 7=0=0生 产 库 存 问 题第92页/共122页93对于k k=6=6因为d d7 7=0=0，所以 x x7 7=r r7 7=4=4而x x6 6-r r6 6+d d6 6=x x7 7=4=4因此有 d d6 6=x x7 7+r r6 6-x x6 6=4+7-=4+7-x x6 6=11-=11-x x6 6也是唯一的决策。因此递推方程为：f f6 6(x x6 6)=min)=minc c6 6d d6 6+f f7 7(x x7 7)d d6 6=11-=11-x x6 6=10=10d d6 6=10(11-=10(11-x x6 6)=110-10)=110-10 x x6 6生 产 库 存 问 题第93页/共122页94对于k k=5=5f f5 5(x x5 5)=min)=minc c5 5d d5 5+f f6 6(x x6 6)d d5 5 D D5 5(x x5 5)=min20 =min20d d5 5+110-10+110-10 x x6 6 d d5 5 D D5 5(x x5 5)=min20 =min20d d5 5+110-10(+110-10(x x5 5-r r5 5+d d5 5)d d5 5 D D5 5(x x5 5)=d d5 5 H H+r r5 5-x x5 5 =d d5 5|d d5 5 0,9-0,9-x x5 5 d d5 5 11-11-x x5 5 min20min20d d5 5+110-10(+110-10(x x5 5-2+-2+d d5 5)d d5 5 D D5 5(x x5 5)=min10 =min10d d5 5-10-10 x x5 5+130+130 d d5 5 D D5 5(x x5 5)D D5 5(x x5 5)=)=d d5 5|d d5 5 0,0,r r6 6 x x5 5-r r5 5+d d5 5 H H =d d5 5|d d5 5 0,0,r r6 6+r r5 5-x x5 5生 产 库 存 问 题第94页/共122页95因为x x5 5 H H