运筹学课程07-动态规划.ppt

动态规划,Dynamic Programming,不要过河拆桥 追求全局最优, 多阶段决策过程的最优化 动态规划的基本概念和基本原理 动态规划方法的基本步骤 动态规划方法应用举例,本章内容,一、多阶段决策过程的最优化,示例1（工厂生产安排）： 某种机器可以在高、低两种负荷下生产。高负荷生产条件下机器完好率为0.7，即如果年初有u台完好机器投入生产，则年末完好的机器数量为0.7u台。系数0.7称为完好率。年初投入高负荷运行的u台机器的年产量为8u吨。系数8称为单台产量。低负荷运行时，机器完好率为0.9，单台产量为5吨。设开始时有1000台完好机器，要制订五年计划，每年年初将完好的机器一部分分配到高负荷生产，剩下的机器分配到低负荷生产，使五年的总产量为最高。,设有数量为y的某种资源，将它分别投入两种生产方式A和B，已知收益函数分别是g(x)和h(x)，x为资源投入量。设这种资源用于生产后还可以回收一部分用于生产，A、B的回收率分别为a和b（ 0a1，0b1 ）， 问：对总数量为y的资源进行n个阶段的生产，应如何分配每个阶段投入A、B的资源数量，才能使总收益最大？,推广：多阶段资源分配问题,示例2（设备更新问题）：,一般企业用于生产活动的设备，刚买来时故障少，经济效益高，即使进行转让，处理价值也高，随着使用年限的增加，就会逐渐变为故障多，维修费用增加，可正常使用的工时减少，加工质量下降，经济效益差，并且，使用的年限越长、处理价值也越低，自然，如果卖去旧的买新的，还需要付出更新费因此就需要综合权衡决定设备的使用年限，使总的经济效益最好。,一般化工生产过程中，常包含一系列完成生产过程的设备，前一工序设备的输出则是后一工序设备的输入，因此，应该如何根据各工序的运行工况，控制生产过程中各设备的输入和输出，以使总产量最大。,示例3 （连续生产过程的控制问题）：,示例4、最短路径问题,给定一个交通网络图如下，其中两点之间的数字表示距离（或花费），试求从A点到G点的最短距离（总费用最小）。,1,2,3,4,5,6,A,B1,B2,C1,C2,C3,C4,D1,D2,D3,E1,E2,E3,F1,F2,G,5,3,1,3,6,8,7,6,3,6,8,5,3,3,8,4,2,2,2,1,3,3,3,5,2,5,6,6,4,3,示例5（生产与存储问题）： 某工厂生产并销售某种产品。已知今后四个月市场需求预测及每月生产j个单位产品的费用如下： 每月库存i个单位产品的费用E(i)=0.5i(千元），该厂最大库存容量为3个单位，每月最大生产能力为6个单位，计划开始和计划期末库存量都是零，试制定四个月的生产计划，在满足用户需求条件下，使总费用最小。,每个月视为一个阶段，,每个阶段都须决定生产几个、库存几个,上一个阶段的决策直接影响下一个阶段的决策,由于航天飞机的运动的环境是不断变化的，因此就要根据航天飞机飞行在不同环境中的情况，不断地决定航天飞机的飞行方向和速度（状态），使之能最省燃料和实现目的（如软着落问题）。,示例6（航天飞机飞行控制问题）：,10,所谓多阶段决策问题是指一类活动过程，它可以分为若干个相互联系的阶段，在每个阶段都需要作出决策。这个决策不仅决定这一阶段的效益，而且决定下一阶段的初始状态。 每个阶段的决策均确定以后，就得到一个决策序列，称为策略。多阶段决策问题就是求一个策略，使各阶段的效益的总和达到最优。 动态规划是用来解决多阶段决策过程最优化的一种数量方法。其特点在于，它可以把一个n 维决策问题变换为几个一维最优化问题，从而一个一个地去解决。,1,2,n,状态,决策,状态,决策,状态,状态,决策,不包含时间因素的静态决策问题（本质上是一次决策问题）也可以适当地引入阶段的概念，作为多阶段的决策问题用动态规划方法来解决。,某些线性规划、非线性规划等静态规划问题也可以通过适当地引入阶段的概念，应用动态规划方法加以解决。,DP是上个世纪五十年代贝尔曼(B.E.Bellman)为代表 的研究成果，属于现代控制理论的一部分。其最优化原理， 可归结为一个递推公式。,注意：动态规划是求解某类多阶段决策问题的一种方法，是考察问题的一种途径，不是一种算法。必须对具体问题进行具体分析，运用动态规划的原理和方法，建立相应的模型，然后再用动态规划方法去求解。,动态规划思想示例：,B,C,B,D,B,C,D,E,C,4,1,2,3,1,2,3,1,2,3,2,2,1,6,4,7,2,4,8,3,8,6,7,5,6,1,10,6,3,7,5,1,以上求从A到E的最短路径问题，可以转化为四个性质完全相同，但规模较小的子问题，即分别从 A到E的最短路径问题。,第四阶段：两个始点 和 ，终点只有一个；,分析得知：从 和 到E的最短路径唯一。,第三阶段：有三个始点C1，C2，C3，终点有D1，D2，对始点 和终点进行分析和讨论分别求C1，C2，C3到D1，D2 的最短路 径问题： 分析得知：如果经过C1，则最短路为C1-D2-E； 如果经过C2，则最短路为C2-D2-E； 如果经过C3，则最短路为C3-D1-E。,第二阶段：有4个始点B1,B2,B3,B4，终点有C1,C2,C3。对始点和终点进行分析和讨论分别求B1,B2,B3,B4到C1,C2,C3 的最短路径问题： 分析得知：如果经过B1，则走B1-C2-D2-E； 如果经过B2，则走B2-C3-D1-E； 如果经过B3，则走B3-C3-D1-E； 如果经过B4，则走B4-C3-D1-E。,第一阶段：只有1个始点A，终点有B1,B2,B3,B4 。对始点和终 点进行分析和讨论分别求A到B1,B2,B3,B4的最短路径问题： 最后，可以得到：从A到E的最短路径为A B4 C3 D1 E,以上计算过程及结果，可用下图表示，可以看到，以上方法不仅得到了从A到D的最短路径，同时，也得到了从图中任一点到E的最短路径。 以上过程，仅用了22次加法，计算效率远高于穷举法。,B,C,B,D,B,C,D,E,C,4,1,2,3,1,2,3,1,2,3,3,2,1,6,4,7,2,4,8,3,8,6,7,5,1,6,10,6,0,10,6,12,11,11,12,13,14,14,12,7,5,1,2,二、动态规划的基本概念和基本原理,基本概念 1、阶段： 把一个问题的过程，恰当地分为若干个相互联系的阶段，以便于按一定的次序去求解。 描述阶段的变量称为阶段变量。阶段的划分，一般是根据时间和空间的自然特征来进行的，但要便于问题转化为多阶段决策。,2、状态：表示每个阶段开始所处的自然状况或客观条件。通常一个阶段有若干个状态，描述过程状态的变量称为状态变量。,一个数一组数一个向量,状态变量的取值有一定的允许集合或范围，此集合称为状态允许集合。,3、决策：表示当过程处于某一阶段的某个状态时，可以作出不同的决定，从而确定下一阶段的状态，这种决定称为决策。,描述决策的变量，称为决策变量。决策变量是状态变量的函数。可用一个数、一组数或一向量（多维情形）来描述。 在实际问题中决策变量的取值往往在某一范围之内，此范围称为允许决策集合。,系统在某一阶段的状态转移不但与系统的当前的状态和决策有关，而且还与系统过去的历史状态和决策有关。,4、多阶段决策过程,可以在各个阶段进行决策，去控制过程发展的多段过程；,其发展是通过一系列的状态转移来实现的；,图示如下：,状态转移方程是确定过程由一个状态到另一个状态的演变过程。如果第k阶段状态变量sk的值、该阶段的决策变量一经确定，第k+1阶段状态变量sk+1的值也就确定。,其状态转移方程如下（一般形式）,能用动态规划方法求解的多阶段决策过程是一类特殊的多阶段决策过程，即具有无后效性的多阶段决策过程。,如果状态变量不能满足无后效性的要求，应适当地改变状态的定义或规定方法。,动态规划中能 处理的状态转移 方程的形式。,状态具有无后效性的多阶段决策过程的状态转移方程如下,无后效性(马尔可夫性),如果某阶段状态给定后，则在这个阶段以后过程的发展不受这个阶段以前各段状态的影响；,过程的过去历史只能通过当前的状态去影响它未来的发展；,状态变量要满足无后效性的要求；,5、策略：是一个按顺序排列的决策组成的集合。在实际问题中，可供选择的策略有一定的范围，称为允许策略集合。从允许策略集合中找出达到最优效果的策略称为最优策略。,6、状态转移方程：是确定过程由一个状态到另一个状态的演变过程，描述了状态转移规律。,7、指标函数和最优值函数：用来衡量所实现过程优劣的一种数量指标，为指标函数。指标函数的最优值，称为最优值函数。在不同的问题中，指标函数的含义是不同的，它可能是距离、利润、成本、产量或资源消耗等。 动态规划模型的指标函数，应具有可分离性，并满足递推关系。,小结:,指标函数形式:,和、,积,无后效性,可递推,原过程的一个后部子过程：,原过程的一个后部子过程的策略：,对于任意给定的k（1 kn），从第k段到第n段的过程称为原过程的一个后部子过程,最优策略,解多阶段决策过程问题，求出,f1(s1),从 k 到终点最优策略 子策略的最优目标函数值,问题分成4个阶段：,k=1，2，3，4,线路：,线路：,k=1：,k=3：,阶段,状态,第一阶段的状态：,第二阶段的状态：,sk,s4,Sk =sk,S3 =s3,=5，6，7,注：n个阶段的决策过程有个n+1状态变量,sn+1表示sn演变的结果,S5 =10,决策,决策,可取值为：5，6，7,=5，6，7,允许决策集合,策略,最短路问题：,策略,= 行进方案,如 ,允许策略集合,最优策略：使整个问题达到最优效果的策略,策略： ,最优策略=最短的行进路线,策略, , , ,最短路问题：,原过程的一个策略：, ,后部子过程的策略, ,后部子过程的策略,后部子过程的策略,or ,每月库存i个单位产品的费用E(i)=0.5i(千元），该厂最大库存容量为3个单位，每月最大生产能力为6个单位，计划开始和计划期末库存量都是零，试制定四个月的生产计划，在满足用户需求条件下，使总费用最小。,k=1，2，3，4,阶段,第k阶段的状态变量sk,S1=0，,S2=0,1,2,3，,S3=0,1,2,3，,S4=0,1,2,3,=第k个月月初的库存量,（生产与存储问题）某工厂生产并销售某种产品。已知今四个月市场需求预测如下表，又每月生产j个单位产品的费用为,=2,3,4,5,=2,3,4,5,=0,1,2,3,=3,一个策略=一个生产方案,2，5，0，4,2，3，2，4,费用：21（千元）,费用：23（千元）,最优策略：,使总费用最小的生产方案,最优化原理（基本原理） 作为整个过程的最优策略具有这样的性质：无论过去的状态和决策如何，相对于前面的决策所形成的当前状态而言，余下的决策序列必然构成最优子策略。”也就是说，一个最优策略的子策略也是最优的。,对最短路问题：,最短路问题的基本方程：,k=4,3,2,1,从最后一阶段开始，用由后向前的方法，求出各点到终点的 最短路线，最后，求得由起点到终点的最短路线。,对于生产与存储问题：某工厂生产并销售某种产品。已知今四个月市场需求预测如下表，又每月生产j个单位产品费用为 每月库存i个单位产品的费用E(i)=0.5i(千元），该厂最大库存容量为3个单位，每月最大生产能力为6个单位，计划开始和计划期末库存量都是零，试制定四个月的生产计划，在满足用户需求条件下，使总费用最小。,阶段k=1，2，3，4,状态变量 =第k个月月初的库存量,状态转移方程：,当k=4时，,u4(s4)对应的总费用=生产费+库存费,库存费E(i)=0.5i，,最大库存容量为3个单位，,最大生产能力为6个单位，,计划开始和计划期末库存量为零,0,1,2,3,4,7,4,3,6.5,3,2,6,2,1,5.5,1,当k=3时，,库存费E(i)=0.5i，,最大库存容量为3个单位，,最大生产能力为6个单位，,计划开始和计划期末库存量为零,0,1,2,3,0,1,2,3,0,u3(3)对应的总费用=生产费+库存费,库存费E(i)=0.5i，,最大库存容量为3个单位，,最大生产能力为6个单位，,计划开始和计划期末库存量为零,0,2 3 4 5,12,12 .5,13,13.5,12,2,1,1 2 3 4,11.5,12,12.5,13,11.5,1,2,0 1 2 3,8 11.5 12 12.5,8,0,3,0 1 2,8,8,0,11.5,12,0,1,2,3,4,7,4,3,6.5,3,2,6,2,1,5.5,1,当k=2时，,u2(s2)对应的总费用=生产费+库存费,0,2 3 4 5,12,12 .5,13,13.5,12,2,1,1 2 3 4,11.5,12,12.5,13,11.5,1,2,0 1 2 3,8 11.5 12 12.5,8,0,3,0 1 2,8 11.5 12,8,0,k=3,当k=2时，,0,1,2,3,3 4 5 6,18,18.5,16,17,16,5,2 3 4 5,17.5 18 15.5 16.5,1 2 3 4,17,0 1 2 3,13.5 17 14.5 15.5,15.5,4,15,3,13.5,0,17.5,15,16,当k=1时，,u1(0)对应的总费用=生产费,k=2,0,1,2,3,3 4 5 6,18,18.5,16,17,16,5,2 3 4 5,17.5 18 15.5 16.5,1 2 3 4,17 17.5 15 16,0 1 2 3,13.5 17 14.5 15.5,15.5,4,15,3,13.5,0,当k=1时，,0,2 3 4 5,22 21.5,21,2,21,21.5,生产存储问题的基本方程：,最短路问题的基本方程：,k=4,3,2,1,三、动态规划方法建模基本要求与步骤,建模要素：,1)阶段数 k,2)状态变量 sk,3)决策变量 uk（ sk ）,4)指标函数 Vk,n,状态转移方程,5)最优值函数 fk(sk),DP建模基本要求：,1）所研究的问题必须能够分成几个相互联系的阶段，而且在每一个阶段都具有需要进行决策的问题。,2）在每一阶段都必须有若干个与该阶段相关的状态，建模时总是从与决策有关的条件中，或是从问题的约束条件中去选择状态变量。,一般情况下，状态是所研究系统在该阶段可能处于的情况或条件,3) 具有明确的指标函数，且阶段指标值可以计算,4) 能正确列出最优值函数的递推公式和边界条件,（b）能通过现阶段的决策，使当前状态转移成下一阶段的状态（反映过程的演变性）,即 能够给出状态转移方程,（c）状态的无后效性,状态的选取必须注意以下几个要点：,（a）在所研究问题的各阶段，都能直接或间接确定状态变量的取值（可知性）,建立DP模型的步骤 1、划分阶段 划分阶段是运用动态规划求解多阶段决策问题的第一步，在确定多阶段特性后，按时间或空间先后顺序，将过程划分为若干相互联系的阶段。对于静态问题要人为地赋予“时间”概念，以便划分阶段。 2、正确选择状态变量 选择变量既要能确切描述过程演变又要满足无后效性，而且各阶段状态变量的取值能够确定。一般地，状态变量的选择是从过程演变的特点中寻找。 3、确定决策变量及允许决策集合 通常选择所求解问题的关键变量作为决策变量，同时要给出决策变量的取值范围，即确定允许决策集合。,4、确定状态转移方程 根据k 阶段状态变量和决策变量，写出k+1阶段状态变量，状态转移方程应当具有递推关系。 5、确定阶段指标函数和最优指标函数，建立动态规划基本方程 阶段指标函数是指第k 阶段的收益，最优指标函数是指从第k 阶段状态出发到第n 阶段末所获得收益的最优值，最后写出动态规划基本方程。,以上五步是建立动态规划数学模型的一般步骤。由于动态规划模型与线性规划模型不同，动态规划模型没有统一的模式，建模时必须根据具体问题具体分析，只有通过不断实践总结，才能较好掌握建模方法与技巧。,四、动态规划方法应用举例,动态规划常用基本方程：,从A 地到D 地要铺设一条煤气管道,其中需经过两级中间站，两点之间的连线上的数字表示距离，如图所示。问应该选择什么路线，使总距离最短？,A,B1,B2,C1,C2,C3,D,2,4,3,3,3,3,2,1,1,1,4,1、最短路径问题,解：整个计算过程分三个阶段，从最后一个阶段开始。,第一阶段（C D）： C 有三条路线到终点D 。,A,B1,B2,C1,C2,C3,D,2,4,3,3,3,3,2,1,1,1,4,D,C1,C2,C3,显然有 f1 (C1 ) = 1 ； f1(C2 ) = 3 ； f1 (C3 ) = 4,d( B1,C1 ) + f1 (C1 ) 3+1 f2 ( B1 ) = min d( B1,C2 ) + f1 (C2 ) = min 3+3 d( B1,C3 ) + f1 (C3 ) 1+4 4 = min 6 = 4 5,第二阶段（B C）： B 到C 有六条路线。,A,B1,B2,C1,C2,C3,D,2,4,3,3,3,3,2,1,1,1,4,D,C1,C2,C3,B1,B2,(最短路线为B1C1 D),d( B2,C1 ) + f1 (C1 ) 2+1 f2 ( B2 ) = min d( B2,C2 ) + f1 (C2 ) = min 3+3 d( B2,C3 ) + f1 (C3 ) 1+4 3 = min 6 = 3 5,A,B1,B2,C1,C2,C3,D,2,4,3,3,3,3,2,1,1,1,4,D,C1,C2,C3,B1,B2,(最短路线为B2C1 D),第三阶段（ A B ）： A 到B 有二条路线。,f3(A)1 = d(A, B1 ) f2 ( B1 ) 246 f3 (A)2 = d(A, B2 ) f2 ( B2 ) 437, f3 (A) = min = min6,7=6,d(A, B1 ) f2 ( B1 ) d(A, B2 ) f2 ( B2 ),(最短路线为AB1C1 D),A,B1,B2,C1,C2,C3,D,2,4,3,3,3,3,2,1,1,1,4,D,C1,C2,C3,B1,B2,A,A,B1,B2,C1,C2,C3,D,2,4,3,3,3,3,2,1,1,1,4,D,C1,C2,C3,B1,B2,A,最短路线为 AB1C1 D 路长为 6,2、资源分配问题,某公司有资金a万元，拟投资于n个项目，已知对第i个项目投资xi万元，收益为g i (xi)，问应如何分配资金可使总收益最大？,解：阶段k=1,2, ,n,状态变量sk,决策变量uk,：第k个项目的投资额,：在第k阶段时可以用于投资 第k到第n个项目的资金数,状态转移方程：,sk+1 = sk -uk,指标函数Vk,n,第k至第n个项目的最大总收益,最优值函数,边界条件：,k=n,n-1, ,2,1,资源分配问题的动态规划基本方程：,建立递推公式：,投资额,收益,工厂,某有色金属公司拟拨出50万元对所属三家冶炼厂进行技术改造，若以十万元为最少分割单位，各厂收益与投资的关系如下表：,问：对三个工厂如何分配， 才能使总收益达到最大？,状态变量 sk：,阶段 k=1，2，3,决策变量 uk：,给工厂k的投资额,在第k阶段时可供工 厂k到工厂3分配的 资金数,状态转移方程：,sk+1 = sk -uk,g k (uk)=给工厂k投资 uk （十万元）的收益,指标函数 Vk,n,资源分配问题示例,fk（ sk ）,投资工厂k至工厂3所得的最大总收益,求f1（ 5 ）,=在工厂k，可供分配的资金数为sk时，,基本方程：,k=3,0,0,1,1,2,2,3,3,0,5,7,8,4,5,4,5,10,13,投资额,收益,工厂,k=2,0,0,0,0,1,0,2,3,0 1 2 3,8,9,9.5,7.5,2,9.5,4,5,投资额,收益,工厂,sk+1 = sk -uk,0,0,1,1,2,2,3,3,0,5,7,8,4,5,4,5,10,13,k=1,sk+1 = sk -uk,投资额,收益,工厂,5,16,0 1 2 3 4 5,12,1,17,最大总收益：,最优策略：,0,0,0,0,1,0,2,3,0 1 2 3,8,9,9.5,7.5,2,9.5,4,5,系统由n个部件串联组成，每一个部件上装有备用件，部件i(i=1,2, ,n)上装有xi个备用元件时，正常工作的概率为pi （ xi ）。设装一个i部件的设备元件费用为ci ，重量wi为，要求总费用不超过C，总重量不超过W，问如何选择各个部件的备用元件数，使整个系统的工作可靠性最大？,3、复合系统工作可靠性问题,设A-整个系统正常工作，Ai部件i正常工作,满足：,非线性规划问题,解： n个部件=n个阶段,决策变量uk =,部件k上所装的备用元件数xk,状态变量：,sk,=第k个到第n个部件可使用的总费用,yk,=第k个到第n个部件容许的总重量,状态转移方程：,指标函数Vk,n,最优指标函数fk(sk， yk ）=,在部件k，可使用 的总费用为 sk，总重量为 yk 时，从部件k 到部件n的系统工作可靠性的最大值,复合系统工作可靠性的动态规划基本方程为：,与问题无关,有一个徒步旅行者，其可携带物品重量的限度为a 公斤，设有n 种物品可供他选择装入包中。已知每种物品的重量及使用价值（作用），问此人应如何选择携带的物品（各几件），使所起作用（使用价值）最大？,这就是背包问题。类似的还有工厂里的下料问题、运输中的货物装载问题、人造卫星内的物品装载问题等。,4、背包问题,设xj 为第j 种物品的装件数（非负整数）则问题的数学模型如下：,用动态规划方法求解，令 fx(y) = 总重量不超过 y 公斤，包中只装有前k 种物品时的最大使用价值。 其中y 0， k 1,2, , n 。所以问题就是求 fn(a),其递推关系式为：,当 k=1 时，有：,求下面背包问题的最优解,解：a5 ，问题是求 f3(5),所以，最优解为 X（1 . 1 . 0），最优值为 Z = 13。,一种机器能在高低两种不同的负荷状态下工作。设机器在高负荷下生产时，产量函数为P1=8u1，其中u1为在高负荷状态下生产的机器数目，年完好率为a=0.7，即到年底有70的机器保持完好。在低负荷下生产时，产量函数为P2=5u2，其中u2为在低负荷状态下生产的机器数目，年完好率为b=0.9。设开始生产时共有1000台完好的机器，请问每年应该如何把完好机器分配给高、低两种负荷下生产，才能使得5年内生产的产品总产量最高。,5、机器负荷分配问题,解 建立动态规划模型： 分为5个阶段，每个阶段为1年。设状态变量sk表示在第k阶段初拥有的完好机器数目；k=1,2,3,4,5。 决策变量xk表示第k阶段中分配给高负荷状态下生产的机器数目；k=1,2,3,4,5。显然sk-xk为分配给低负荷状态下生产的机器数目。 状态转移方程为 阶段指标 rk(sk,xk)=8xk+5(sk-xk) 最优指标函数 其中k=1,2,3,4,5。 f6(s6)=0。,第5阶段： 因为f5(s5)是x5的线性单调增函数，故有x5* =s5， 于是有f5(s5)=8s5。 第4阶段：,同样地，f4(s4)是x4的线性单调增函数，有x4*=s4 ， f4(s4)=13.6s4。 对前几个阶段依次类推，可得 f3(s3)=17.5s3， f2(s2)=20.75s2， f1(s1)=23.72s1。 因为期初共有完好机器1000台，故s1=1000。有f1(s1)=23.72s1 23720，即5年最大的产量为23720台。得最优解为 ， ， ， 。 这意味着前两年应把年初完好机器完全投入低负荷生产， 后三年应把年初完好机器完全投入高负荷生产。,下一步工作是确定每年初的状态，按照从前向后的顺序依次计算出每年年初完好的机器数目。已知s1=1000,根据状态转移方程，有:,上面所讨论的最优策略过程，初始端状态s1=1000台是固定的，终点状态s6没有要求。这种情况下得到最优决策称为初始端固定终点自由的最优策略。 如果终点附加一定的条件，则问题就称为“终端固定问题”。例如，规定在第5年度结束时仍要保持500台机器完好（而不是278台），应如何安排生产才能使得总产量最大？ 下面来分析： 根据终点条件有 可得,显然，由于固定了终点的状态，x5的取值受到了 约束。因此有 类似， 容易解得 ，f4(s4)=21.7s4-7500。,依次类推，得 f3(s3)=24.5s3-7500 f2(s2)=27.1s2-7500 f1(s1)=29.4s1-7500 再采用顺序方法递推计算各年的状态，有 s1=1000，,可见，为了使终点完好的机器数量增加到500台，需要安排前四年中全部完好机器都要投入低负荷生产，且在第5年，也只能全部投入高负荷。 相应的最优指标为 f1(s1)=29.4s1-750021900。 可以看到，因为增加了附加条件，总产量f1(s1)要比终点自由情况下的产量要低。,一台设备的价格为P，运行寿命为n年，每年的维修费用是设备役龄的函数，记为C(t)，新设备的役龄为t=0。旧设备出售的价格是设备役龄的函数，记为S(t)。在n年末，役龄为t的设备残值为R(t)。现有一台役龄为T的设备，在使用过程中，使用者每年都面临“继续使用”或“更新”的策略，,7、设备更新问题,设具体数据如下：,97,由以上计算可知，本问题有两个决策，它们对应的最小费用都是115。,这两个决策是,例（季节工问题）某工厂的生产任务随季节波动，为降低成本宜用季节临时工，但熟练的生产工人临时难以聘到，培训新手费用又高，各季节工人需用量如下表所示，每季节超过需用量聘用，每人浪费2000元，聘用或解聘费为200元乘上两个季节聘用人数之差的平方，问厂长一年中应如何聘用工人可使总花费最小？（假定工资按实际工作时间计算，则聘用人数可为分数）,季度i 春 夏 秋 冬 春,需用量gk 255 220 240 200 255,方案1：,255 220 240 200 255,总费用：,+200352,200552,+200202,+200402,=1249000,方案2：,255 245 245 245 255,总费用：,+200102,200102,+200025,+20005,+200045,=190000,解：,阶段1,，状态变量sk第k-1季度聘用人数,决策变量uk第k季度聘用人数,状态转移方程：,sk+1 = uk,fk（sk）=第k-1季度聘用人数为sk人时，第k季度到 第4季度的最小总费用,220s2255,gkuk255,季度i 春 夏 秋 冬 春,需用量gk 255 220 240 200 255,2,3,4,k=1,2,34,s1=255,240s3255,200s4255,已知：每季节超过需用量聘用，每人浪费2000元，聘用 和解聘费为200元乘上两个季节聘用人数之差的平方,=min ,+fk+1（sk+1）,+2000(uk gk),gkuk255,200(uk uk-1)2,求f1（255）,=min ,+fk+1（uk）,+2000(uk gk),gkuk255,200(uk sk)2,基本方程：,fk（sk）=,min ,+fk+1（uk）,f5（s5）=0,求f1（255）,+2000(uk gk),gkuk255,200(uk sk)2,min ,f4（s4）=,+2000(u4 g4),g4u4255,200(u4 s4)2,u*4=255,=200(255 s4)2,200s4255,当k=4时,min ,f3（s3）=,+f4（u3）,+2000(u3 g3),200(u3 s3)2,g3u3255,=min ,+2000(u3 200),200(u3 s3)2,200u3255,+200(255 u3)2,当k=3时,240s3255,k=4,3,2,1,f3（s3）,=min ,+2000(u3 200),200(u3 s3)2,200u3255,+200(255 u3)2,所以f3（s3）=,当k=3时,240s3255,min ,min ,f2（s2）=,+f3（u2）,+2000(u2 g2),200(u2 s2)2,g2u2255,fk（sk）=,+fk+1（uk）,+2000(uk gk),gkuk255,200(uk sk)2,已知：,f3（s3）,当k=2时,220s2255,=min ,+2000(u2 240),200(u2 s2)2,240u2255,+f3（u2）,=min ,240u2255,状态转移方程：,sk+1 = uk,f2（s2）,当k=2时,220s2255,=min ,240u2255,所以f2（s2）=,min ,fk（sk）=,+fk+1（uk）,+2000(uk gk),gkuk255,200(uk sk)2,已知：,f2（s2）,当k=1时,，s1=255,min ,f1（255）=,+f2（u1）,+2000(u1 g1),g1u1255,200(u1 s1)2,=min ,+2000(u1 220),220u1255,200(u1 255)2,状态转移方程：,sk+1 = uk,f1（255）=185000,f4（s4）=,u*4=255,200(255 s4)2,f2（s2）,f1（255）=185000,最优策略：,=245,=247.5,u*4=255,最少总费用：为185000元,状态转移方程：,sk+1 = uk,最佳聘用方案：,夏季247.5人，秋季245人，冬季247.5人，春季255人时，,7、 用动态规划方法求解某些非线性优化问题,