运筹学10-动态数规划课件.ppt

《运筹学10-动态数规划课件.ppt》由会员分享，可在线阅读，更多相关《运筹学10-动态数规划课件.ppt（74页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第十章 动态规划10.1 多阶段过程决策问题多阶段过程决策问题10.2 动态规划原理动态规划原理10.3 动态规划应用举例动态规划应用举例5/26/20231多阶段决策过程的最优化多阶段决策过程的最优化多阶段决策过程：多阶段决策过程：整个决策过程可按时间或空间顺序分解成若干整个决策过程可按时间或空间顺序分解成若干相互联系相互联系的阶段，每一阶段都需作出决策，全部过程的决策是一个决的阶段，每一阶段都需作出决策，全部过程的决策是一个决策序列。策序列。多阶段决策过程最优化的目标：多阶段决策过程最优化的目标：达到整个活动过程的总体效果最优，而非各单个阶段最达到整个活动过程的总体效果最优，而非各单个阶段

2、最优的简单总和。优的简单总和。请看如下典例请看如下典例最短路线问题最短路线问题10.1 多阶段过程决策问题5/26/20232n从生产厂从生产厂Q到某公司到某公司T选择那条路线选择那条路线,使总运费最低使总运费最低(路程路程最短最短)？最短路问题 QTA1A2A3B1B2B3C1C124374642442514633334生生产产商商某某公公司司出出口口港港进进口口港港城城市市阶段阶段1阶段阶段2阶段阶段3阶段阶段45/26/20233n这是一个多阶段决策问题，它可分为四个阶段：这是一个多阶段决策问题，它可分为四个阶段：q第一阶段：从第一阶段：从Q(制造厂制造厂)到到A(出口港出口港)；q第二

3、阶段：从第二阶段：从A(出口港出口港)到到B(进口港进口港)；q第三阶段：从第三阶段：从B(进口港进口港)到到C(城市城市)；q第四阶段：从第四阶段：从C(城市城市)到到T(某公司某公司)。n每个阶段选取的路线不同，对应从每个阶段选取的路线不同，对应从Q到到T就有一系列不同就有一系列不同的运输路线的运输路线:q从始点从始点Q到终点到终点T共有共有3321=18条不同路线条不同路线q现在的问题是如何选择一条费用最小的路线？现在的问题是如何选择一条费用最小的路线？5/26/20234多阶段决策问题的典型例子多阶段决策问题的典型例子v企企业业在在生生产产过过程程中中，由由于于需需求求是是随随着着时时

4、间间变变化化的的因因素素，因因此此企企业业为为了了获获得得全全年年最最佳佳经经济济效效益益，就就要要在在整整个个生生产产过程中逐月或逐季的根据库存和需求决定生产计划。过程中逐月或逐季的根据库存和需求决定生产计划。v某某种种机机器器，可可以以在在高高、低低两两种种负负荷荷下下生生产产。高高负负荷荷下下生生产产的的产产量量多多，但但每每生生产产一一个个阶阶段段后后机机器器的的完完好好率率低低；低低负负荷荷下下生生产产时时的的情情况况则则相相反反。现现在在需需要要安安排排该该种种机机器器在在多多个个阶阶段段内内的的生生产产，问问应应该该如如何何决决定定各各阶阶段段中中机机器器的的使使用，使整个计划期

5、内的总产量最大。用，使整个计划期内的总产量最大。v化化工工生生产产过过程程包包含含一一系系列列的的过过程程设设备备，如如反反应应器器、蒸蒸馏馏塔塔、吸吸收收器器等等等等，前前一一设设备备的的输输出出是是后后一一设设备备的的输输入入。因因此此，应应该该如如何何控控制制生生产产过过程程中中各各个个设设备备的的输输出出和和输输入入，使总产量最大。使总产量最大。5/26/20236v某台设备，例如汽车，刚买来时故障少，耗油低，出车某台设备，例如汽车，刚买来时故障少，耗油低，出车时间长，处理价值和经济效益高。随着使用时间的增加时间长，处理价值和经济效益高。随着使用时间的增加则变为故障多，耗油高，维修费用

6、增加，经济效益差。则变为故障多，耗油高，维修费用增加，经济效益差。使用时间愈长，处理价值也愈低。另外，每次更新都要使用时间愈长，处理价值也愈低。另外，每次更新都要付出更新费用。因此，应当如何决定设备的使用年限，付出更新费用。因此，应当如何决定设备的使用年限，使总的效益最佳。使总的效益最佳。v发射一枚火箭去击中运动中的目标。由于目标的行动是发射一枚火箭去击中运动中的目标。由于目标的行动是不断改变的，因此应如何根据目标运动情况，不断调整不断改变的，因此应如何根据目标运动情况，不断调整火箭飞行的方向与速度，使之最快地命中目标，等等。火箭飞行的方向与速度，使之最快地命中目标，等等。5/26/20237

7、什么是动态规划？什么是动态规划？n动动态态规规划划是是运运筹筹学学OROR的的一一个个分分支支，是是解解决决多多阶阶段段决决策策过过程程最最优优化化的的一一种种方方法法或或是是一一种种分分析析多多阶阶段段决决策策过过程程的的数数学学方方法法，这这种种方方法法可可根根据据人人们们所所采采取取的的措措施施，一一步步步步地地控制过程的发展，以实现预定的要求。控制过程的发展，以实现预定的要求。n这这一一运运筹筹学学分分支支最最初初是是由由美美国国数数学学家家BellmanBellman等等人人根根据据一一类类多多阶阶段段决决策策问问题题的的特特性性，提提出出了了解解决决这这类类问问题题的的最最优化原理

8、，并研究了许多实际问题而建立起来的。优化原理，并研究了许多实际问题而建立起来的。n贝贝尔尔曼曼的的名名著著动动态态规规划划于于19571957年年出出版版，这这成成了了动动态态规划的第一本著作。规划的第一本著作。5/26/20238L缺点：缺点：没有统一的处理方法，求解时要根据问题的性质，结没有统一的处理方法，求解时要根据问题的性质，结合多种数学技巧。因此，实践经验及创造性思维将起重要合多种数学技巧。因此，实践经验及创造性思维将起重要的引导作用。的引导作用。“维数障碍维数障碍”：当变量个数太多时，由于计算机内存和：当变量个数太多时，由于计算机内存和速度的限制导致问题无法解决。有些问题由于涉及的

9、函数速度的限制导致问题无法解决。有些问题由于涉及的函数没有理想的性质使问题只能用动态规划描述，而不能用动没有理想的性质使问题只能用动态规划描述，而不能用动态规划方法求解。态规划方法求解。5/26/202310 应特别指出的是，动态规划是解决某一类问题的一应特别指出的是，动态规划是解决某一类问题的一种方法，是分析问题的一种途径，而不是一种特殊算法种方法，是分析问题的一种途径，而不是一种特殊算法(如线性规划是一种算法如线性规划是一种算法)。因而，它不象线性规划那样。因而，它不象线性规划那样有一个标准的数学表达式和明确定义的一组规则，而必有一个标准的数学表达式和明确定义的一组规则，而必须对具体问题进

10、行具体分析处理。因此，在学习动态规须对具体问题进行具体分析处理。因此，在学习动态规划时，除了对基本概念和方法正确地理解外，应以丰富划时，除了对基本概念和方法正确地理解外，应以丰富的想象力去建立模型，用创造性的技巧去求解。正如贝的想象力去建立模型，用创造性的技巧去求解。正如贝尔曼本人所说：尔曼本人所说：“由于动态规划的最优化原理仅仅是一由于动态规划的最优化原理仅仅是一种基本原理，正是它的某种不确定性为你提供了发挥你种基本原理，正是它的某种不确定性为你提供了发挥你创造性思维的巨大空间创造性思维的巨大空间!5/26/202311n状态状态(state)q状态表示过程发展中某阶段的起始状况。状态表示过

11、程发展中某阶段的起始状况。q过程的发展可以通过各阶段状态的演变来描述。过程的发展可以通过各阶段状态的演变来描述。q状态可用一个变量来描述，称为状态可用一个变量来描述，称为状态变量状态变量状态变量状态变量，用，用Sk表示。表示。q选取的状态变量必须满足选取的状态变量必须满足无后效性无后效性无后效性无后效性。n某某阶阶段段的的状状态态给给定定后后，则则过过程程未未来来发发展展不不受受该该阶阶段段以前各阶段状态的影响。以前各阶段状态的影响。q第第 k 阶阶段段可可能能有有若若干干状状态态，用用Sk 表表示示阶阶段段k的的状状态态集集合，合，qsk(i)表示第表示第k阶段的第阶段的第 i 个状态。个状

12、态。5/26/202313q从从过过程程的的某某个个阶阶段段开开始始到到最最终终阶阶段段结结束束称称为为后后部部子子过过程程。从从第第k阶阶段段开开始始的的后后部部子子策策略略称称为为第第第第k k子子子子过过过过程程程程策略策略策略策略。pk,n(sk)=xk(sk),xk+1(sk+1),xn(sn)简记简记 pk,n=xk,xk+1,xnq每每一一阶阶段段有有若若干干状状态态,每每个个状状态态又又有有若若干干个个不不同同的的决决策策,即即有有许许多多策策略略可可供供选选择择。全全体体策策略略构构成成允允允允许许许许策策策策略略略略集合集合集合集合Pk,n(sk)。q能能使使预预期期目目标

13、标达达到到最最优优效效果果的的策策略略称称为为最最最最优优优优策策策策略略略略P*k,n，q构成最优策略的各决策称为相应阶段的构成最优策略的各决策称为相应阶段的最优决策最优决策最优决策最优决策x*k。5/26/202315n状态转移方程状态转移方程q下下一一阶阶段段状状态态sk+1 是是本本阶阶段段状状态态变变量量sk 和和决决策策变变量量xk的的函数，即函数，即 sk+1=T(sk,xk(sk)=T(sk,xk)q从从状状态态sk出出发发到到下下一一阶阶段段状状态态sk+1的的转转移移规规律律称称为为状状状状态态态态转移方程转移方程转移方程转移方程。n指标函数指标函数q用用来来衡衡量量每每一

14、一阶阶段段决决策策效效果果的的优优劣劣的的数数量量指指标标，称称为为阶阶阶阶段段段段指指指指标标标标函函函函数数数数vk ，阶阶段段指指标标是是状状态态变变量量和和相相应应决决策策变变量的函数，即量的函数，即vk=vk(sk,xk)。n最最短短问问题题是是运运费费或或路路程程。对对阶阶段段的的不不同同状状态态，采采取取不同的决策，运费不同。不同的决策，运费不同。n指标函数也可以是利润、成本、产量等。指标函数也可以是利润、成本、产量等。5/26/202316n逆序算法：逆着阶段顺序的方向，由后向前推算。逆序算法：逆着阶段顺序的方向，由后向前推算。q把寻求最优策略看作连续递推过程，从最终阶段开始，

15、把寻求最优策略看作连续递推过程，从最终阶段开始，逆着实际过程的进展方向逐段求解；逆着实际过程的进展方向逐段求解；q在每一阶段求解过程中都是其后部子过程最优策略的基在每一阶段求解过程中都是其后部子过程最优策略的基础上，再考虑本阶段的指标函数，求出本阶段的最优策础上，再考虑本阶段的指标函数，求出本阶段的最优策略；略；q直到第一阶段为止。直到第一阶段为止。n最优性原理：美国运筹学家贝尔曼提出最优性原理：美国运筹学家贝尔曼提出q无无论论过过去去的的状状态态和和决决策策如如何何，对对前前面面的的决决策策所所形形成成的的状状态而言，余下的诸决策必须构成最优策略。态而言，余下的诸决策必须构成最优策略。q将将

16、决决策策问问题题划划分分为为若若干干个个阶阶段段，全全过过程程的的优优化化问问题题就就分分解解为为子子过过程程的的优优化化问问题题，由由后后向向前前逐逐步步倒倒推推，最最优优化化的的子过程逐渐成为全过程最优。子过程逐渐成为全过程最优。q作作为为全全过过程程的的最最优优策策略略P*1,n的的组组成成部部分分的的任任一一子子策策略略P*k,n(Sk)，一定是从状态，一定是从状态Sk 出发直至终点的最优策略。出发直至终点的最优策略。二、动态规划方法的基本思路二、动态规划方法的基本思路 5/26/202318n基本递推方程基本递推方程q据据最最优优性性原原理理，阶阶段段k的的阶阶段段指指标标vk(sk

17、,xk)加加上上(或或乘乘以以)从从下下一一阶阶段段k+1开开始始到到过过程程结结束束采采取取最最优优策策略略取取得得的的最最优优指指标标函函数数值值fk+1(sk+1)，再再从从中中选选出出最最优优，便便是是阶段阶段k从状态从状态sk出发到全过程结束的最优指标函数值。出发到全过程结束的最优指标函数值。5/26/202319阶段阶段1阶段阶段2阶段阶段k阶段阶段k+1阶段阶段n状态状态S1决决策策x1状态状态S2v1决决策策x2状态状态S3v2决决策策xk状态状态Sk+1vk决决策策xk+1vk+1决决策策xnvn寻求最优解的方向寻求最优解的方向5/26/202320逆序递推法逆序递推法(Ba

18、ckward Indication Method)将寻优过程看做连续递推的过程，从最终阶将寻优过程看做连续递推的过程，从最终阶段开始，段开始，逆着逆着实际决策过程的进展方向逐段求解，实际决策过程的进展方向逐段求解，在每一段求解中都要利用刚刚求解完那段的结果，在每一段求解中都要利用刚刚求解完那段的结果，直到初始阶段求出结果回到始点为止。直到初始阶段求出结果回到始点为止。顺序递推法顺序递推法(Forward Indication Method)从初始阶段向前递推，直到最终阶段为止。从初始阶段向前递推，直到最终阶段为止。顺序递推法本质上并无新的建树，只是对某顺序递推法本质上并无新的建树，只是对某些实

19、际问题的求解，应用起来较为简便而已。些实际问题的求解，应用起来较为简便而已。5/26/202321三、建立动态规划模型的步骤三、建立动态规划模型的步骤 1、划分阶段、划分阶段划划分分阶阶段段是是运运用用动动态态规规划划求求解解多多阶阶段段决决策策问问题题的的第第一一步步，在在确确定定多多阶阶段段特特性性后后，按按时时间间或或空空间间先先后后顺顺序序，将将过过程程划划分分为为若若干干相相互互联联系系的的阶阶段段。对对于于静静态态问问题题要要人人为为地地赋赋予予“时时间间”概念，以便划分阶段。概念，以便划分阶段。2、正确选择状态变量、正确选择状态变量选选择择变变量量既既要要能能确确切切描描述述过过

20、程程演演变变又又要要满满足足无无后后效效性性，而而且且各各阶阶段段状状态态变变量量的的取取值值能能够够确确定定。一一般般地地，状状态态变变量量的的选选择择是从过程演变的特点中寻找。是从过程演变的特点中寻找。3、确定决策变量及允许决策集合、确定决策变量及允许决策集合通通常常选选择择所所求求解解问问题题的的关关键键变变量量作作为为决决策策变变量量，同同时时要要给给出出决策变量的取值范围，即确定允许决策集合。决策变量的取值范围，即确定允许决策集合。5/26/202322四、动态规划模型的求解四、动态规划模型的求解例例 分配投资问题分配投资问题 某公司有资金某公司有资金 10 万元，若投资于项目万元，

21、若投资于项目 k(k=1，2，3)的的投资额为投资额为 xk 时，其收益分别为时，其收益分别为 g1(x1)=4x1，g2(x2)=9x2，g3(x3)=2x32，问应该如何分配投资数额才能使总收益最大？，问应该如何分配投资数额才能使总收益最大？该问题表面上看与时间无明显关系，其静态模型：该问题表面上看与时间无明显关系，其静态模型：Max z=4x1+9x2+2x32 x1+x2+x3=10 xi 0(i=1，2，3)5/26/202324 如何应用动态规划方法求解此类静态规划问题？一般我如何应用动态规划方法求解此类静态规划问题？一般我们可以人为地给它赋予们可以人为地给它赋予“时段时段”的概念

22、，将投资项目的概念，将投资项目按任意顺序进行排序，如首先考虑项目按任意顺序进行排序，如首先考虑项目1 的投资，然后的投资，然后考虑项目考虑项目2 的投资的投资，即将问题人为划分为若干个阶，即将问题人为划分为若干个阶段，每个阶段只决定对一个项目应投资的金额。这样，段，每个阶段只决定对一个项目应投资的金额。这样，可以将上述问题转化为一个可以将上述问题转化为一个 n 阶段决策过程。阶段决策过程。分配投资问题的分析求解如下：分配投资问题的分析求解如下：n阶段阶段 k=1，2，3，分别表示项目，分别表示项目1，2，3n状态变量状态变量 sk：第：第 k 段初拥有的资金总量段初拥有的资金总量(分配给第分配

23、给第 k 至至第第 3 个项目的资金数量个项目的资金数量)n决策变量决策变量 xk：第：第 k 段的投资量段的投资量(分配给第分配给第 k 个项目的资个项目的资金数量金数量)，决策集合决策集合 Dk(sk)=xk 0 xk sk n状态转移方程状态转移方程 sk+1=sk-xk 5/26/202325n阶段指标值阶段指标值(函数函数)vk(sk，xk)=gk(xk)n定义定义fk(sk)：第：第 k 段初拥有的资金总量为段初拥有的资金总量为 sk 时，第时，第 k 至至第第 3 段按最优投资策略所获得的第段按最优投资策略所获得的第 k 至第至第 3 段的总收益。段的总收益。n建立动态规划基本方

24、程：建立动态规划基本方程：(逆序递推方程逆序递推方程)fk(sk)=max gk(xk)+fk+1(sk+1)，k=3，2，10 xk skf4(s4)=05/26/202326k=1 当当f2(s2)=9s2，f1(10)=Max 4x1+f2(s2)0 x1 10=Max 9s1 5x1 =9s1，x1*=0 但此时但此时 s2=s1 x1=10-0 9/2 与与s2 9/2 矛盾，故舍去。矛盾，故舍去。当当f2(s2)=2s22，f1(10)=Max 4x1+f2(s2)0 x1 10=Max 4s1+2(s1 x1)2 同样可以证明极大值只可能在端点取得，比较两个端点：同样可以证明极大

25、值只可能在端点取得，比较两个端点：x1=0 时，时，f1(10)=200，x1=10 时，时，f1(10)=40所以所以 x1*=0 5/26/202328顺序确定顺序确定最优策略最优策略 s1=10 x1*=0s2=s1 x1*=10 9/2 x2*=0 s3=s2 x2*=10 x3*=10最优投资方案为全部资金投资于第最优投资方案为全部资金投资于第 3 3 个项目，可获最个项目，可获最大收益大收益 200 200 万元。万元。5/26/202329 解：整个计算过程分三个阶段，从最后一个阶段开始。解：整个计算过程分三个阶段，从最后一个阶段开始。第一阶段第一阶段(C D)：C 有三条路线到

26、终点有三条路线到终点D。AB1B2C1C2C3D24333321114DC1C2C3显然有显然有 f1(C1)=1 ；f1(C2)=3 ；f1(C3)=4 5/26/202331 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 有六条路线。有六条路线。AB1B2C1C2C3D24333321114DC1C2C3B1B2(最短路线为最短路线为B1C1 D)5/26/202332 d(B2,C1)+f1(C1)2+1 f2(B2)=mi

27、n d(B2,C2)+f1(C2)=min 3+3 d(B2,C3)+f1(C3)1+4 3 =min 6 =3 5AB1B2C1C2C3D24333321114DC1C2C3B1B2(最短路线为最短路线为B2C1 D)5/26/202333第三阶段第三阶段(A B)：A 到到B 有二条路线。有二条路线。f3(A)1=d(A,B1)f2(B1)246f3(A)2=d(A,B2)f2(B2)437 f3(A)=min =min6,7=6d(A,B1)f2(B1)d(A,B2)f2(B2)最短路线为最短路线为AB1C1 D，路长为路长为 6AB1B2C1C2C3D24333321114DC1C2C

28、3B1B2A5/26/202334q企业一年中的产品生产往往是分期分批生产的。企业一年中的产品生产往往是分期分批生产的。q组织每批产品的生产，都要花费一些生产准备费和存贮组织每批产品的生产，都要花费一些生产准备费和存贮费用。费用。n若某一时期增大生产批量则可减少生产批次，从而降若某一时期增大生产批量则可减少生产批次，从而降低生产成本。低生产成本。n与此同时，批量大了，必然增加库存而使存贮费用增与此同时，批量大了，必然增加库存而使存贮费用增加。加。q在企业产品的生产成本、存贮费用、市场需求量确定的在企业产品的生产成本、存贮费用、市场需求量确定的情况下，正确计划各时期的生产量，既满足市场需求，情况

29、下，正确计划各时期的生产量，既满足市场需求，又使总支出最少，这是一个多阶段决策问题。又使总支出最少，这是一个多阶段决策问题。二、生产与存储问题二、生产与存储问题 5/26/202335n例，例，某工厂与用户签订了某工厂与用户签订了4个月的交货合同如表所示个月的交货合同如表所示 该厂生产能力为每月该厂生产能力为每月5万件，该厂仓库的存货能力为万件，该厂仓库的存货能力为4万件。万件。已知生产费用为已知生产费用为c=1千元千元/万件，在进行生产的月份，万件，在进行生产的月份，工厂要支出固定费用工厂要支出固定费用b=2千元，每月仓库保管费用千元，每月仓库保管费用h=0.2千千元元/万件万件/月。月。假

30、定开始时及假定开始时及4月底交货后无存货，试问应在每月各生月底交货后无存货，试问应在每月各生产多少件产品，才能满足交货任务，又使总费用最小？产多少件产品，才能满足交货任务，又使总费用最小？月月1234需求量需求量dk(万件万件)32325/26/202336n动态规划的数学模型动态规划的数学模型q每个月为一个阶段，即阶段变量每个月为一个阶段，即阶段变量 k=1,2,3,4分别表示这四个月分别表示这四个月;q状态变量状态变量sk 表示第表示第k 月初的产品库存量，月初的产品库存量，0 sk 4;q决策变量决策变量xk 表示第表示第k月的生产量月的生产量，允允许决策集合许决策集合Xk(sk)=xk

31、 0 xk 5;q状态转移方程为状态转移方程为 sk+1=sk+xk dk;q阶阶段段指指标标vk(sk,xk)表表示示第第k 月月的的费费用用：本本月月若若不不安安排排生生产产，则则仅仅需需支支出出保保管管费费；本本月月若若安安排排生生产产，则则需需支支出出生生产产费费用用和和固固定费，同时还需交付保管费。定费，同时还需交付保管费。n当当xk=0时，时，vk(sk,xk)=h sk=0.2skn当当xk 0时，时，vk(sk,xk)=b+cxk+hsk=2+xk+0.2skq 最最优优指指数数函函数数fk(sk)表表示示第第k阶阶段段从从sk 开开始始到到最最后后阶阶段段采采用用最最优生产策

32、略实现的最低生产费用优生产策略实现的最低生产费用;5/26/202337n逆序求解逆序求解qK=4x4s4v4(s4,x4)=0.2 s4v4(s4,x4)=2+x4+0.2 s4f4(s4)x4*012012-4-3.2-0.4-43.20.4210d4=2，4月末无库存则月末无库存则s5=0，状态转移方程状态转移方程 s5=s4+x4 d4，则则 s4=d4 x4=2 x4x40,则则s4=2 x4=0,1,2s40,则则x4=2 s4=0,1,25/26/202338qk=3x3s30.2 s3+f4(s4)v3(s3,x3)+f4(s4)=2+x3+0.2 s3+f4(s4)f3(s3

33、)x3*012340 123457.46.65.84.6454300-9.09.27.4-8.28.46.6-7.47.65.8-4.66.85.0-44.2-d3=3，0s4 2，状态转移方程状态转移方程 s4=s3+x3 d3，则则 0 s3+x3 d3 2，即即 3 s3+x3 50s34，则则s3=0,1,2,3,4生产能力限制生产能力限制 0 x3 5，则，则x3=0,1,2,3,4,54月在库存量为月在库存量为s4下下的最低生产成本的最低生产成本5/26/202339qk=2x2s20.2 s2+f3(s3)v2(s2,x2)+f3(s3)=2+x2+0.2 s2+f3(s3)f2

34、(s2)x2*01201234511.410.67.8210-11.411.611.811.6-10.6 10.8 11.0 10.811.27.810.0 10.2 10.0 10.4-d2=2，0s3 4，状态转移方程状态转移方程 s3=s2+x2 d2，则则 0 s2+x2 d2 4，即即 2 s2+x2 6s1=0，则则s2=s1+x1 d1=x1 3；x1 5，则，则s2 2生产能力限制生产能力限制 0 x2 5，则，则x2=0,1,2,3,4,53月在库存量为月在库存量为s3下下的最低生产成本的最低生产成本5/26/202340nk=1x1s1v1(s1,x1)+f2(s2)=2+

35、x1+0.2 s1+f2(s2)f1(s1)x1*3452月在库存量为月在库存量为s2下下的最低生产成本的最低生产成本014.85顺序递推，得出结论顺序递推，得出结论第第1月生产月生产5万件万件s2=s1+x1 d1=0+5-3=2，第，第2月不生产月不生产s3=s2+x2 d2=2+0-2=0，第，第3月生产月生产5万件万件s4=s3+x3 d3=0+5-3=2，第，第4月不生产月不生产16.416.614.8d1=3，s1=0，状态转移方程则状态转移方程则s2=s1+x1 d1=x1 3；s20，则则 x1 3，生产能力限制生产能力限制 x1 5，则，则3 x1 5，x1=3,4,55/2

36、6/202341n资源分配问题：资源分配问题：q把有限的资源把有限的资源(如资金、材料、设备、人力等如资金、材料、设备、人力等)分配给若干分配给若干使用者，而使某一指标为最优的问题即为资源分配问题。使用者，而使某一指标为最优的问题即为资源分配问题。q资源可以有一种或若干种，资源可以有一种或若干种，q只有一种资源可供分配的问题称之为一维资源分配问题。只有一种资源可供分配的问题称之为一维资源分配问题。n一维资源分配问题一维资源分配问题三、资源分配问题三、资源分配问题 设备台数设备台数分厂分厂0123456I0356765II04678910III0259887如何分配设备，可使获利最大？如何分配设

37、备，可使获利最大？各分厂各分厂在不同在不同设备台设备台数下所数下所获利润获利润5/26/202342n动态规划的数学模型动态规划的数学模型q将三个分厂看作是三个阶段，即阶段变量将三个分厂看作是三个阶段，即阶段变量 k=1,2,3;q状态变量状态变量sk 表示第表示第k 阶段初可分配的设备台数阶段初可分配的设备台数,0 sk 6;q决策变量决策变量xk 表示第表示第k 阶段分配给分厂阶段分配给分厂k 的设备台数，的设备台数，允许决策集合允许决策集合Xk(sk)=xk 0 xk sk;q状态转移方程为状态转移方程为 sk+1=sk-xk;q阶阶段段指指标标vk(sk,xk)表表示示第第k 阶阶段段

38、从从sk台台设设备备中中分分配配给给k 分厂分厂xk 台设备的阶段效益台设备的阶段效益;q最最优优指指数数函函数数fk(sk)表表示示第第k阶阶段段从从sk 开开始始到到最最后后阶阶段段采采用最优分配策略取得的最大的效益值用最优分配策略取得的最大的效益值;q递推方程函数式递推方程函数式 5/26/202343n逆序求解逆序求解qK=3x3s3v3(s3,x3)f3(s3)x3*第第III分厂在不同设分厂在不同设备台数下所获利润备台数下所获利润012345601234560020250259025980259880259887025999901233335/26/202344qk=2x2s2v2

39、(s2,x2)+f3(s3)f2(s2)x2*第II分厂在不同设备台数下所获利润01234560123456004046046704678046789046789100469131516011,20,1123第III分厂在设备台数为s3下所获得的最大利润0+00+24+00+54+26+00+94+56+27+00+94+96+57+28+00+94+96+97+58+29+00+94+96+97+98+59+210+05/26/202345qk=1x1s1v1(s1,x1)+f2(s2)f1(s1)x1*第第I分厂在不同设分厂在不同设备台数下所获利润备台数下所获利润0123456第第II分厂

40、在设备台数为分厂在设备台数为s2下所获得的最大利润下所获得的最大利润60356765181,2顺序递推，得出结论顺序递推，得出结论第第I 分厂分厂1套或套或2套套第第II 分厂分厂2套或套或1套套第第III 分厂分厂3套套0+163+155+136+97+66+45+05/26/202346n有一种设备可以在高低两种不同的负荷下运行，在高负有一种设备可以在高低两种不同的负荷下运行，在高负荷下生产时，产品的年产量荷下生产时，产品的年产量Q1与投入生产的设备台数与投入生产的设备台数x1的关系为：的关系为：Q1=9x1，年完好率，年完好率(折损后折损后)a=0.75；在低负；在低负荷下生产时，年产量

41、荷下生产时，年产量Q2与投入生产的设备台数与投入生产的设备台数x2的关系的关系为为:Q2=6 x2，年完好率为，年完好率为b=0.96，若开始时拥有完好机，若开始时拥有完好机器台数为器台数为100台，要求制定一个台，要求制定一个4年计划，在每年初时应年计划，在每年初时应决定如何重新分配设备在高低不同的负荷下生产，使得决定如何重新分配设备在高低不同的负荷下生产，使得4年内产品的总产量达到最高。年内产品的总产量达到最高。四、机器负荷问题四、机器负荷问题 5/26/202347n动态规划的数学模型动态规划的数学模型q每年为一个阶段，即阶段变量每年为一个阶段，即阶段变量 k=1,2,3,4;q状态变量

42、状态变量sk 表示第表示第k年初所拥有的完好机器台数，年初所拥有的完好机器台数，s1=100;q决策变量决策变量xk 表示第表示第k年投入高负荷生产的机器数年投入高负荷生产的机器数，允许决策集合允许决策集合Xk(sk)=xk 0 xk sk;q状态转移方程为状态转移方程为 sk+1=a xk+b(sk xk)=0.75 xk+0.96(sk xk)=0.96sk 0.21xk;q阶段指标阶段指标vk(sk,xk)表示第表示第k年的产量年的产量：vk(sk,xk)=9xk+6(sk xk)=6sk+3xk;q最最优优指指数数函函数数fk(sk)表表示示第第k阶阶段段从从sk 开开始始到到最最后后

43、阶阶段段采采用用最最优优分配策略实现的最大产量分配策略实现的最大产量;5/26/202348nK=4f4(s4)是关于是关于x4 的单增函数，故的单增函数，故x*4=s4 时，时，f4(s4)最大，最大，f4(s4)=9 s4K=3f3(s3)是关于是关于x3 的单增函数，故的单增函数，故x*3=s3 时，时，f3(s3)最大，最大，f3(s3)=15.75 s35/26/202349K=2f2(s2)是关于是关于x2 的单减函数，故的单减函数，故x*2=0 时，时，f2(s2)最大，最大，f2(s2)=21.12 s2K=1f1(s1)是关于是关于x1 的单的单减函数减函数，故，故x*1=0

44、 时，时，f1(s1)最大，最大，f1(s1)=26.275 s15/26/202350n最优生产策略：最优生产策略：n x*1=0，x*2=0，x*3=s3，x*4=s4 n各阶段状态：各阶段状态：qs1=100，x*1=0，qs2=0.96s1 0.21x1=0.96s1=96，x*2=0，qs3=0.96s2 0.21x2=0.96s2=92.16，x*2=s3，qs4=0.96s3 0.21x3=0.75s3=69.12，x*4=s4qs5=0.96s4 0.21x4=0.75s4=51.845/26/202351五、复合系统可靠性问题五、复合系统可靠性问题当当系统中第系统中第 k 个

45、部件个部件(1，2，n)的冗余数量为的冗余数量为 xk 时，从而整个系统的时，从而整个系统的 可靠度为：可靠度为：P=pk(xk)下面研究一个简单例子下面研究一个简单例子例例 一台机器的三个重要部件对整台机器的正常运行起着一台机器的三个重要部件对整台机器的正常运行起着至关重要的作用，他们的可靠度及成本分别为：至关重要的作用，他们的可靠度及成本分别为：p1=0.9，p2=0.7，p3=0.6；c1=2，c2=1，c3=3；(单位：万元单位：万元)p1p2pn 5/26/202352 如果采用冗余技术来提高整台机器的可靠度，而提供的如果采用冗余技术来提高整台机器的可靠度，而提供的冗余经费仅有冗余经

46、费仅有 3 万元，这三个重要部件应该怎样冗余才能万元，这三个重要部件应该怎样冗余才能使整台机器的可靠度最高。使整台机器的可靠度最高。解：这实际上是一个解：这实际上是一个 3 万元如何分配使用在这三个重要部件万元如何分配使用在这三个重要部件冗余的资源分配问题，其动态规划结构图如下：冗余的资源分配问题，其动态规划结构图如下：sk sk+1=sk-ckxkk阶段阶段fk(sk)k+1阶段阶段fk+1(sk+1)max()pk(xk)0 xk sk/ck 且为整数且为整数 动态方程：动态方程：(逆序递推方程逆序递推方程)fk(sk)=max 1-(1-pk)1+xk *fk+1(sk+1)，k=3，2

47、，1f4(s4)=1 xk Dk(sk)5/26/202353逆序递推求解动态规划方程。逆序递推求解动态规划方程。k=3 s2 取值集合为：取值集合为：0 sk 3f3(s3)=max 1-(1-p3)1+x3 *f4(s4)f3(0 s3 3)=max 1-(1-0.6)1 *1 =0.6 x*3(s3 3)=0f3(s3=3)=max 1-(1-0.6)1+1 *1 =0.84 x*3(s3=3)=15/26/202354k=2 s2 取值集合为：取值集合为：1，3f2(1)=max(1-0.3)*f3(1)(1-0.32)*f3(0)=max0.7*0.60.91*0.6=0.546x*

48、2(1)=1f2(3)=max(1-0.3)*f3(3)(1-0.32)*f3(2)(1-0.33)*f3(1)(1-0.34)*f3(0)=max0.7*0.840.91*0.60.973*0.60.992*0.6=0.595x*2(3)=35/26/202355k=1 s1 取值集合为：取值集合为：3=0.541=maxf1(3)=max(1-0.1)*f2(3)(1-0.12)*f2(1)0.9*0.5950.99*0.546x*1(3)=1顺序确定顺序确定最优策略最优策略 s1=3s2=1s3=0 x*1=1x*2=1x*3=05/26/202356六、设备更新问题六、设备更新问题 在

49、工业和交通运输企业中，经常会遇到因设备陈旧或在工业和交通运输企业中，经常会遇到因设备陈旧或部分损坏需要更新的问题。那么，从经济上分析，一台部分损坏需要更新的问题。那么，从经济上分析，一台(一批一批)设备应该使用多少年后进行更新最为恰当，或合理设备应该使用多少年后进行更新最为恰当，或合理的更新年限是多少？从而使在某一时间内的总收入达到最的更新年限是多少？从而使在某一时间内的总收入达到最大大(或总成本达到最小或总成本达到最小)。这是设备更新问题所要研究的。这是设备更新问题所要研究的。设备更新问题的一般性描述：设备更新问题的一般性描述：已知一台设备的效益函数已知一台设备的效益函数r(t)，维修费用函

50、数，维修费用函数x(t)，更新，更新费用函数费用函数c(t)，在，在n 年内，每年年初都须作出决策，是继年内，每年年初都须作出决策，是继续使用续使用(Keep)旧设备还是更换旧设备还是更换(Replacement)一台新的设一台新的设备，使在备，使在n年内总净效益最大。年内总净效益最大。5/26/202357设：设：r k(t)在第在第k 年初设备已使用了年初设备已使用了t 年年(或称役龄为或称役龄为t年年)的设备在第的设备在第k 年再使用的效益。年再使用的效益。x k(t)在第在第k 年初设备已使用了年初设备已使用了t 年时继续使用的年时继续使用的第第k 年中的维修费用。年中的维修费用。c