运筹学07动态规划.ppt

1,动态规划 Dynamic Programming,多阶段决策过程的最优化动态规划的基本概念和基本原理动态规划模型的建立与求解动态规划方法应用举例,2,1 多阶段决策过程的最优化,概述多阶段决策过程及其最优化多阶段决策过程举例动态规划求解的多阶段决策问题的特点动态规划方法导引,3,概述,动态规划是解决多阶段决策过程最优化问题的一种方法。由美国数学家贝尔曼(R Bellman)等人于20世纪50年代初提出，贝尔曼于1957年出版动态规划专著。动态规划用于解决最优路径问题、资源分配问题、生产计划与库存、投资、装载、排序等问题及生产过程的最优控制。动态规划分为离散确定型、离散随机型、连续确定型、连续随机型等类型。主要介绍离散确定型动态规划。,4,多阶段决策过程及其最优化,多阶段决策过程指这样一类特殊的活动过程，它们可以按时间顺序分解成若干相互联系的阶段，称为时段，在每一个时段都要做出决策，全部过程的决策是一个决策序列。故多阶段决策问题属序贯决策问题。多阶段决策过程最优化的目标是要达到整个活动过程的总体效果最优。决策者在每段决策时不仅考虑本阶段最优，还考虑对最终目标的影响，从而做出全局最优决策。动态规划方法虽与时间关系紧密，但问题中引入时段因素即可看出多阶段决策过程。,5,多阶段决策过程举例,属于多阶段决策类的问题很多，例如：例1：工厂生产过程。由于市场需求是一随着时间而变化的因素，因此，为了取得全年最佳经济效益，就要在全年的生产过程中，逐月或者逐季度地根据库存和需求情况决定生产计划安排。,6,例2：设备更新问题。一般企业用于生产活动的设备，刚买来时故障少，经济效益高，即使进行转让，处理价值也高，随着使用年限的增加，就会逐渐变为故障多，维修费用增加，可正常使用的工时减少，加工质量下降，经济效益差，并且，使用的年限越长、处理价值也越低，自然，如果卖去旧的买新的，还需要付出更新费。因此就需要综合权衡决定设备的使用年限，使总的经济效益最好。,7,例3：连续生产过程的控制问题。一般化工生产过程中，常包含一系列完成生产过程的设备，前一工序设备的输出则是后一工序设备的输入，因此，应该如何根据各工序的运行工况，控制生产过程中各设备的输入和输出，以使总产量最大。,8,以上所举问题的发展过程都与时间因素有关，因此在这类多阶段决策问题中，阶段的划分常取时间区段来表示，并且各个阶段上的决策往往也与时间因素有关，这就使它具有了“动态”的含义，所以把处理这类动态问题的方法称为动态规划方法。不过，实际中尚有许多不包含时间因素的一类“静态”决策问题，就其本质而言是一次决策问题，是非动态决策问题，但是也可以人为地引入阶段的概念当作多阶段决策问题，应用动态规划方法加以解决。,9,例4：资源分配问题。某工业部门或公司，拟对其所属企业进行稀缺资源分配，为此需要制定出收益最大的资源分配方案。这种问题原本要求一次确定出对各企业的资源分配量，它与时间因素无关，不属动态决策，但是，我们可以人为地规定一个资源分配的阶段和顺序，从而使其变成一个多阶段决策问题。,10,例5：运输网络最短路问题。如图所示的运输网络，顶点之间连线上的数字表示两地距离(也可以是运费、时间等)，要求从v1至v10的最短路线。这种运输网络问题也是静态决策问题。但是，按照网络中点的分布，可以把它分为4个阶段，而作为多阶段决策问题来研究。该图中圆圈里是网络顶点，带箭头的是网络上的弧(应该全部是弧)，弧上的数字是两个顶点之间的距离。顶点处括号内的值是各顶点到v10的最短距离。最短距离=18；最短路=v1-v3-v7-v9-v10。,11,12,动态规划求解的多阶段决策问题的特点,通常多阶段决策过程的发展是通过状态的一系列变换来实现的。一般情况下，系统在某个阶段的状态转移除与本阶段的状态和决策有关外，还可能与系统过去经历的状态和决策有关。因此，问题的求解就比较困难复杂。而适合于用动态规划方法求解的只是一类特殊的多阶段决策问题，即具有“无后效性”的多阶段决策过程。所谓无后效性，又称马尔柯夫性，是指系统从某个阶段往后的发展，仅由本阶段所处的状态及其往后的决策所决定，与系统以前经历的状态和决策(历史)无关。,13,动态规划方法导引,例6：为了说明动态规划的基本思想方法和特点，下面以例5图所示为例讨论求最短路问题的方法。第一种方法：全枚举法或穷举法。它的基本思想是列举出所有可能发生的方案和结果，再对它们一一进行比较，求出最优方案。这里从v1到v10的路程可以分为4个阶段。第一段的走法有三种，第二三两段的走法各有两种，第四段的走法仅一种，因此共有322112条可能的路线，分别算出各条路线的距离，最后进行比较，可知最优路线是v1 v3 v7 v9 v10，最短距离是18。,14,显然，当组成交通网络的节点很多时，用穷举法求最优路线的计算工作量将会十分庞大，而且其中包含着许多重复计算第二种方法：即所谓“局部最优路径”法，是说某人从k出发，他并不顾及全线是否最短，只是选择当前最短途径，“逢近便走”，错误地以为局部最优会致整体最优，在这种想法指导下，所取决策必是v1v3v5v8v10，全程长度是20；显然，这种方法的结果常是错误的。,15,第三种方法：动态规划方法。动态规划方法寻求该最短路问题的基本思想是，首先将问题划分为4个阶段，每次的选择总是综合后继过程的最优进行考虑，在各段所有可能状态的最优后继过程都已求得的情况下，全程的最优路线便也随之得到。为了找出所有可能状态的最优后继过程，动态规划方法总是从过程的最后阶段开始考虑，然后逆着实际过程发展的顺序，逐段向前递推计算直至始点。,16,从v10开始，因为v10是终点，再无后继过程，故可以接着考虑第4阶段上所有可能状态v8,v9的最优后续过程。因为从v8,v9到v10的路线是唯一的，所以v8,v9的最优决策和最优后继过程就是到v10，它们的最短距离分别是5和3。接着考虑阶段3上可能的状态v5,v6,v7到v10的最优决策和最优后继过程。在状态v5上，虽然到v8是8，到v9是9，但是综合考虑后继过程整体最优，取最优决策是到v9，最优后继过程是v5v9v10，最短距离是12。同理，状态v6的最优决策是至v8；v7的最优决策是到v9。,17,同样，当阶段3上所有可能状态的最优后继过程都已求得后，便可以开始考虑阶段2上所有可能状态的最优决策和最优后继过程，如v2的最优决策是到v5，最优路线是v2v5v9v10，最短距离是15。依此类推，最后可以得到从初始状态v1的最优决策是到v3最优路线是v1v3v7v9v10，全程最短距离是18。图中粗实线表示各点到的最优路线，每点上方括号内的数字表示该点到终点的最短路距离。,18,综上所述，全枚举法虽可找出最优方案，但不是个好算法，局部最优法则完全是个错误方法，只有动态规划方法较科学有效。动态规划方法基本思想是，把一个比较复杂的问题分解为一系列同类型的更易求解的子问题，便于应用计算机。整个求解过程分为两个阶段，先按整体最优的思想逆序地求出各个子问题中所有可能状态的最优决策与最优值，然后再顺序地求出整个问题的最优策略和最优路线。,19,2 动态规划的基本概念和基本原理,基本概念阶段和阶段变量状态、状态变量和可能状态集决策、决策变量和允许决策集合策略和允许策略集合状态转移方程指标函数最优解基本原理多阶段决策问题的数学模型动态规划方法的基本思想,20,阶段和阶段变量,为了便于求解和表示决策及过程的发展顺序，而把所给问题恰当地划分为若干个相互联系又有区别的子问题，称之为多段决策问题的阶段(stage)。一个阶段，就是需要作出一个决策的子问题，通常阶段是按决策进行的时间或空间上先后顺序划分的。用以描述阶段的变量叫作阶段变量，一般以k表示阶段变量。阶段数等于多段决策过程从开始到结束所需作出决策的数目。例5所示的最短路问题就是一个四阶段决策过程。k=1,2,3,4。,21,状态、状态变量和可能状态集,用以描述事物(或系统)在某特定的时间与空间域中所处位置及运动特征的量，称为状态(state)。反映状态变化的量叫做状态变量。状态变量必须包含在给定的阶段上确定全部允许决策所需要的信息。按照过程进行的先后，每个阶段的状态可分为初始状态和终止状态，或称输入状态和输出状态，阶段k的初始状态记作sk，终止状态记为sk+1。但为了清楚起见，通常定义阶段的状态即指其初始状态。,22,一般状态变量的取值有一定的范围或允许集合，称为可能状态集，或可达状态集。可能状态集实际上是关于状态的约束条件。通常可能状态集用相应阶段状态sk的大写字母Sk表示，skSk。可能状态集可以是离散取值的集合，也可以为连续取值区间，视具体问题而定。在例5所示的最短路问题中，第一阶段状态为v1，状态变量s1的状态集合S1=v1；第二阶段S2=v2,v3,v4；第三阶段S3=v5,v6,v7；第四阶段S4=v8,v9。,23,决策、决策变量和允许决策集合,所谓决策(decision)，就是确定系统过程发展的方案。决策的实质是关于状态的选择。用以描述决策变化的量称之决策变量。和状态变量一样，决策变量可以用一个数、一组数或一向量来描述，也可以是状态变量的函数，记以uk=uk(sk)，表示于阶段k状态sk时的决策变量。决策变量的取值往往也有一定的允许范围，称之允许决策集合。决策变量uk(sk)的允许决策集用Uk(sk)表示，uk(sk)Uk(sk)。允许决策集合实际是决策的约束条件。,24,策略和允许策略集合,策略有全过程策略和k部子策略之分。全过程策略是指具有n个阶段的全部过程。由依次进行的n个阶段决策构成的决策序列，简称策略(policy)，表示为p1,n=u1,u2,un。从第k阶段到第n阶段依次进行阶段决策构成的决策序列称为k部子策略，pk,n=uk,uk+1,un。各个阶段可供选择的决策的不同组合构成决策序列(策略)，由它们组成的集合，称为允许策略集合，记作P1,n，从允许策略集中，找出具有最优效果的策略称为最优策略。,25,状态转移方程,系统在阶段k处于状态sk，执行决策uk(sk)的结果是系统状态的转移，即系统由阶段k的初始状态sk转移到终止状态sk+1。多阶段决策过程的发展用阶段状态的相继演变来描述。对于具有无后效性的多阶段决策过程，系统由阶段k到阶段k+1的状态转移完全由阶段k的状态sk和决策uk(sk)所确定，与系统过去的状态s1,s2,sk-1及其决策u1(s1),u2(s2),uk-1(sk-1)无关。通常称sk+1=Tk(sk,uk(sk)为多阶段决策过程的状态转移方程，可以简写为sk+1=T(sk,uk)。,26,指标函数,用来衡量策略或子策略或决策的效果的某种数量指标，就称为指标函数。它是定义在全过程或各子过程或各阶段上的确定数量函数。对不同问题，指标函数可以是诸如费用、成本、产值、利润、产量、耗量、距离、时间、效用，等等。例5的指标函数就是各弧上的运费。,27,(1)阶段指标函数(也称阶段效应)。用gk(sk,uk)表示第k段处于sk状态且所作决策为uk(sk)时的指标，则它就是第k段指标函数，简记为gk。例5的gk值就是从状态sk到状态sk+1的距离。譬如，gk(v2,v5)=3，即v2到v5的距离为3。(2)过程指标函数(也称目标函数)。用Rk(sk,uk)表示第k子过程的指标函数。例5的Rk(sk,uk)表示处于第k段sk状态且所作决策为uk时，从sk点到终点v10的距离。由此可见，Rk(sk,uk)不仅跟当前状态sk有关，还跟该子过程策略pk(sk)有关，因此它是sk和pk(sk)的函数。,28,适于用动态规划求解的问题的过程指标函数(即目标函数)，必须具有关于阶段指标的可分离形式。对于子过程的指标函数可以表示为：Rk,n=Rk,n(sk,uk,sk+1,uk+1,sn,un)=gk(sk,uk)gk+1(sk+1,uk+1)gn(sn,un)。式中，表示某种运算，可以是加、减、乘、除、开方等。,29,多阶段决策问题中，常见的目标函数形式之一是取各阶段效应之和的形式，即：Rk=gi(si,ui)|i=k,n有些问题，如系统可靠性问题，其目标函数是取各阶段效应的连乘积形式，如：Rk=gi(si,ui)|i=k,n总之，具体问题的目标函数表达形式需要视具体问题而定。,30,最优解,用fk(sk)表示第k子过程指标函数在状态sk下的最优值，即fk(sk)=optRk(sk,Pk(sk),k=1,2,n,pkPk(sk)称fk(sk)为第k子过程上的最优指标函数；与它相应的子策略称为sk状态下的最优子策略，记为pk*(sk)；而构成该子策赂的各段决策称为该过程上的最优决策，记为pk*(sk)=uk*(sk),uk+1*(sk+1),un*(sn),k=1,2,n；简记为pk*=uk*,uk+1*,un*,k=1,2,n,31,特别当k=1且s1取值唯一时，f1(s1)就是问题的最优值，而p1*就是最优策略。如例5只有唯一始点v1即s1取值唯一，故f1(s1)=18就是最优值，而p1*=v3,v7,v9,v10就是最优策略。但若取值不唯一，则问题的最优值记为f0，最优策略即为s1=s1*。我们把最优策略和最优值统称为问题的最优解。按上述定义，所谓最优决策是指它们在全过程上整体最优(即所构成的全过程策略为最优)，而不一定在各阶段上单独最优。,32,多阶段决策问题的数学模型,综上所述，适于应用动态规划方法求解的一类多阶段决策问题，亦即具有无后效性的多阶段决策问题的数学模型呈以下形式：f=opt R=R(s1,u1,s2,u2,sn,un)sk+1=Tk(sk,uk)skSkukUkk=1,2,n式中opt表示最优化，取max或min。上述数学模型求取一个(或多个)最优策略u1*,u2*,un*，最优路线s1*,s2*,sn*,sn+1*,33,动态规划方法的基本思想,(1)将多阶段决策过程划分阶段，恰当地选取状态变量、决策变量及定义最优指标函数。(2)求解时从边界条件开始，逆(或顺)过程行进方向，逐段递推寻优。在每一个子问题求解时，都要使用它前面已求出的子问题的最优结果，最后一个子问题的最优解就是整个问题的最优解。(3)动态规划方法是既把当前一段与未来各段分开，又把当前效益与未来效益结合起来考虑的一种最优化方法，因此每段的最优决策选取是从全局考虑的。,34,3 动态规划模型的建立与求解,建立动态规划模型的步骤逆序解法顺序解法标号解法基本方程分段求解时的几种常用算法,35,建立动态规划模型的步骤,(1)分析问题，识别问题的多阶段特性，按时间或空间的顺序适当划分为满足递推关系的若干阶段，对非时序的静态问题要人为赋予时段概念。(2)正确选择状态变量，使之具备两个必要特征：可知性和无后效性。(3)根据状态变量和决策变量的含义，写出状态转移方程sk+1=Tk(sk,uk)或状态转移规则。(4)明确指标函数Vk,n，最优指标函数fk(sk)以及k阶段指标vk(sk,uk)，写出最优指标函数的递推关系及边界条件。,36,例7：投资分配问题。某公司有资金10万元，若投资于项目i(i=1,2,3)时的投资额为xi时收益分别为g1(x1)=4x1、g2(x2)=9x2、g3(x3)=2x32。问如何分配投资额可使总收益最大？解答：(1)这是一个静态最优化问题，模型为max z=4x1+9x2+2x32x1+x2+x310 xi0(i=1,2,3)(2)可以人为赋予时段概念，分为对项目1投资、对项目2投资和对项目3投资这三个阶段。设uk=xk(k=1,2,3)。s1=10，sk+1=sk-uk。Rk,3=gi(xi)，fk(sk)=maxgk(xk)+fk+1(sk+1)，f4(s4)=0。余略。,37,例8：最短路问题。用动态规划求如图从A到F的最短路。,38,逆序解法,k=6时，s6=F，则f6(F)=0，u6(F)=Fk=5时，s5E1,E2，则f5(E1)=d(E1,F)+f6(F)=4+0=4，u5(E1)=Ff5(E2)=d(E2,F)+f6(F)=3+0=3，u5(E2)=Fk=4时，s4D1,D2,D3，则f4(D1)=min(3+4,5+3)=7，u4(D1)=E1f4(D2)=min(6+4,2+3)=5，u4(D2)=E2f4(D3)=min(1+4,3+3)=5，u4(D3)=E1,39,k=3时，s3C1,C2,C3,C4，则f3(C1)=min(5+7,8+5)=12，u3(C1)=D1f3(C2)=min(4+7,5+5)=10，u3(C2)=D2f3(C3)=min(3+5,4+5)=8，u3(C3)=D2,D3f3(C4)=min(8+5,4+5)=9，u3(C4)=D2,D3k=2时，s2B1,B2，则f2(B1)=min(2+12,3+10,6+18)=13,u2(B1)=C2f2(B2)=min(8+10,7+8,7+9)=15，u2(B2)=C3k=1时，s1=A，则f1(A)=min4+13,5+15=17，u1(A)=B1结论：最短路长=17，最短路=A-B1-C2-D2-E2-F,40,顺序解法,k=0时，f0(s1)=f0(A)=0，这是边界条件。k=1时，s2B1,B2，则f1(B1)=4，u1(B1)=Af1(B2)=5，u1(B2)=Ak=2时，s3C1,C2,C3,C4，则f2(C1)=2+4=6，u2(C1)=B1f2(C2)=min3+4,8+5=7，u2(C2)=B1f2(C3)=min6+4,7+5=10，u2(C3)=B1f2(C4)=7+5=12，u2(C4)=B2,41,k=3时，s4D1,D2,D3，则f3(D1)=11，u3(D1)=C1或C2f3(D2)=12，u3(D2)=C2f3(D3)=14，u3(D3)=C3k=4时，s5E1,E2，则f4(E1)=14，u4(E1)=D1f4(E2)=14，u4(E2)=D2k=5时，s6=F，则f5(F)=17，u5(F)=E2结论：最短路长=17，最短路为A-B1-C2-D2-E2-F,42,标号法,为进一步阐明动态规划方法的基本思路，我们介绍一种只适用于这类最优路线问题的特殊解法标号法。标号法是借助网络图通过分段标号来求出最优路线的一种简便、直观的方法。通常标号法采取“逆序求解”的方法来寻找问题的最优解，即从最后阶段开始，逐次向阶段数小的方向推算，最终求得全局最优解。例5图显示了标号解法的全过程。,43,标号法的一般步骤：1.从最后一段标起，该段各状态(即各始点)到终点的距离用数字分别标在各点上方的方格内，并用粗箭线连接各点和终点。2.向前递推，给前一阶段的各个状态标号。每个状态上方方格内的数字表示该状态到终点的最短距离。将刚标号的点沿着最短距离所对应的已标号的点用粗箭线连接起来。3.逐次向前递推，直到将第一阶段的状态(即起点)也标号。,44,用标号法计算例8的最短路。下图就是完整计算过程。结果：与前相同。,45,用标号法来求解下例,例9：最短路问题。如下网络图表示某城市的局部道路分布图。一货运汽车从S出发，最终到达目的地E。其中Ai(i=1,2,3),Bj(j=1,2)和Ck(k=1,2)是可供汽车选择的途经站点，各点连线上的数字表示两个站点问的距离。问此汽车应走哪条路线，使所经过的路程最短?,46,47,解答,第一步：k=4，s4C1,C2，边界条件f5(E)=0，f4(C1)=5，f4(C2)=8。对E、C1、C2标号。第二步：k=3，s3B1,B2。(1)s3=B1：指标函数d3(B1,C1)=6，d3(B1,C2)=5。因此有f3(B1)=mind3(B1,C1)+f4(C1),d3(B1,C2)+f4(C2)=min(6+5,5+8)=11。最短路是11，对应的决策u3(B1)=C1。(2)s3=B2：f3(B2)=mind3(B2,C1)+f4(C1),d3(B2,C2)+f4(C2)=min(9+5,8+8)=14。最短路是14，且u3(B2)=C1。对B1和B2分别标号为11和14。,48,第三步：k=2，s2Al,A2,A3。(1)s2=A1：f2(A1)=mind2(A1,B1)+f3(B1),d2(A1,B2)+f3(B2)=min6+11,5+14=17，最短路为17，且u3(A1)=B1。(2)s2=A2：f2(A2)=mind2(A2,B1)+f3(B1),d2(A2,B2)+f3(B2)=min8+11,6+14=19，最短路为19，且u3(A2)=B1。(3)s2=A3：f2(A3)=mind2(A3,B1)+f3(B1),d2(A3,B2)+f3(B2)=min7+11,4+14=18，最短路为18，对应的u2(A3)=B1或B2。分别给A1,A2,A3标号17、19、18。,49,第四步：k1，s1=S。f1(S)=mind1(S,A1)+f2(A1),d1(S,A2)+f2(A2),d1(S,A3)+f2(A3)=min4+17,3+19,3+18=21，最短路为21，且u1(S)=A1或A3。给S标号21。结论：从S到E共有三条最短路线：S-A1-B1-C1-E、S-A3-B1-C1-E、S-A3-B2-C1-E。最短距离为21。标号结果见下图。,50,51,基本方程分段求解时的几种常用算法,离散变量的分段枚举法连续变量的逆序解法、顺序解法、离散化解法高维问题的降维法、疏密格子点法(以上方法有的已经在前面的例子中有所体现，有的尚未提及，从略。),52,4 动态规划方法应用举例,动态规划学习建议生产计划问题求最短路问题(自己完成)资源分配问题背包问题设备负荷问题生产库存问题设备更新问题,53,动态规划学习建议,第一步：理解条件、情况及求解目标第二步：分析“四大要素、一个方程”状态变量及其可能集合 xk Xk；决策变量及其允许集合ukUk；状态转移方程xk+1=Tk(xk,uk)；阶段效应rk(xk,uk)。一个方程：fn+1(xn+1)=0(边界条件)；fk(xk)=optrk(xk,uk)+fk+1(xk+1)，k=n,1。第三步：整理求解思路第四步：求解第五步：对照理论分析成败,54,生产计划问题,例10：设备利用计划。某种机器可以在高、低两种负荷下生产。高负荷生产条件下机器完好率为0.7，即如果年初有u台完好机器投入生产，则年末完好的机器数量为0.7u台。系数0.7称为完好率。年初投入高负荷运行的u台机器的年产量为8u吨。系数8称为单台产量。低负荷运行时，机器完好率为0.9，单台产量为5吨。设开始时有1000台完好机器，要制订五年计划，每年年初将完好的机器一部分分配到高负荷生产，剩下的机器分配到低负荷生产，使五年的总产量为最高。,55,解：首先构造这个问题的动态规划模型。1.变量设置(1)设阶段变量k表示年度，阶段总数n=5。(2)状态变量sk表示k年度初完好机床台数。(3)决策变量uk表示第k年度中分配于高负荷下生产的机床台数。于是sk-uk便为该年度中分配于低负荷下生产的机床台数。Sk=0.6可以表示一台机器在k年度中正常工作时间只占6/10；uk=0.4就表示一台机床在k年度只有4/10的时间于高负荷下工作。,56,2.状态转移方程sk+1=0.7uk+0.9(sk-uk)，k=1,2,63.允许决策集合在第k段为Uk(sk)=uk|0ukxk4.目标函数设gk(sk,uk)为第k年度的产量，则gk(sk,uk)=8uk+5(sk-uk)，目标函数Rk=gk(sk,uk)，最优值fk(sk)=max(xk)，k=1,2,3,4,55.条件最优目标函数递推方程sk+1=max8uk+5(sk-uk)+fk+10.7uk+0.9(sk-uk)，k=1,2,3,4,5。6.边界条件：f6(s6)=0,57,采用逆序递推计算法当k=5时有f5(s5)=max8u5+5(s5-u5)。当u5*=s5时，有最大值f5(s5)=8s5。当k=4时有f4(s4)=max8u4+5(s4-u4)+f5(0.7u4+0.9(s4-u4)=max8u4+5(s4-u4)+8(0.7u4+0.9(s4-u4)=max1.4u4+12.2s4。当u4*=s4时，有最大值f4(s4)=13.6s4。当k=3时有f3(s3)=max8u3+5(s3-u3)+13.6(0.7u3+0.9(s3-u3)=max0.28u3+17.24s3。当u3*=s3时，有最大值f3(s3)=17.52s3。,58,当k=2时有f2(s2)=max8u2+5(s2-u2)+17.52(0.7u2+0.9(s2-u2)=max20.768s2-0.504u2。当取u2*=0时有最大值f2(s2)=20.768s2，其中s2=0.7u1+0.9(s1-u1)当k=1时有f1(s1)=max5s1+3u1+20.768(0.9s1-0.2u1)=max23.6912s1-1.1536u1。u1*=0时有最大值f1(s1)=23.6912s1。又因为s1=1000，故f1(s1)=23691.2个产品。按照上述计算顺序寻踪可得相应计算结果。,59,求最短路径(自己完成),60,资源分配问题,例11：有资金4万元，投资A、B、C三个项目，每个项目的投资效益与投入该项目的资金有关。三个项目A、B、C的投资效益(万吨)和投入资金(万元)关系见下表。求对三个项目的最优投资分配，使总投资效益最大。,61,阶段k：每投资一个项目作为一个阶段；状态变量xk：投资第k个项目前的资金数；决策变量dk：第k个项目的投资；决策允许集合：0dkxk状态转移方程：xk+1=xk-dk阶段指标：vk(xk,dk)见表中所示；递推方程：fk(xk)=maxvk(xk,dk)+fk+1(xk+1)终端条件：f4(x4)=0分阶段计算：k=4，f4(x4)=0k=3，0d3x3，x4=x3-d3k=2，0d2x2，x3=x2-d2k=1，0d1x1，x2=x1-d1,62,63,64,最优解：项目A投资1万元，项目B投资0万元，项目C投资3万元x1=4,d1*=1；x2=x1-d1*=3,d2*=0；x3=x2-d2*=3,d3*=3；x4=x3-d3*=0。最大收益：60万吨。,65,背包问题,设有n种物品，每一种物品数量无限。第i种物品每件重量为wi，每件价值ci。现有一只可装载重量为W的背包，求各种物品应各取多少件放入背包，使背包中物品的价值最高。这个问题可以用整数规划模型来描述。设第i种物品取xi件(i=1,2,n，xi为非负整数)，背包中物品的价值为z，则max z=c1x1+c2x2+cnxnw1x1+w2x2+wnxnWx1,x2,xn为正整数例12：对于一个具体问题c1=65，c2=80，c3=30；w1=2，w2=3，w3=1；以及W=5。用动态规划求解。略。,66,生产库存问题,例13：一个工厂生产某种产品，1-7月份生产成本和产品需求量的变化情况如下表。为了调节生产生产和需求，工厂设有一个产品仓库，库容量H=9。已知期初库存量为2，要求期末(七月低)库存量为0。每个月生产的产品在月末入库，月初根据当月需求发货。求七个月的生产量，能满足各月的需求，并使生产成本最低。,67,设备更新问题,例14：一台设备的价格为P，运行寿命为n年，每年的维修费用是设备役龄的函数，记为C(t)，新设备的役龄为t=0。旧设备出售的价格是设备役龄的函数，记为S(t)。在n年末，役龄为t的设备残值为R(t)。现有一台役龄为T的设备，在使用过程中，使用者每年都面临“继续使用”或“更新”的策略。,