动态数规划优秀PPT.ppt

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

1、动态数规划第1页，本讲稿共74页多阶段决策过程的最优化多阶段决策过程的最优化多阶段决策过程：多阶段决策过程：整个决策过程可按时间或空间顺序分解成若干整个决策过程可按时间或空间顺序分解成若干相互联系相互联系的阶的阶段，每一阶段都需作出决策，全部过程的决策是一个决策序列。段，每一阶段都需作出决策，全部过程的决策是一个决策序列。多阶段决策过程最优化的目标：多阶段决策过程最优化的目标：达到整个活动过程的总体效果最优，而非各单个阶段最优的简单总达到整个活动过程的总体效果最优，而非各单个阶段最优的简单总和。和。请看如下典例请看如下典例最短路线问题最短路线问题10.1 多阶段过程决策问题2022/12/22

2、第2页，本讲稿共74页n从生产厂从生产厂Q到某公司到某公司T选择那条路线选择那条路线,使总运费最低使总运费最低(路程最短路程最短)？最短路问题 QTA1A2A3B1B2B3C1C124374642442514633334生生产产商商某某公公司司出出口口港港进进口口港港城城市市阶段阶段1阶段阶段2阶段阶段3阶段阶段42022/12/23第3页，本讲稿共74页n这是一个多阶段决策问题，它可分为四个阶段：这是一个多阶段决策问题，它可分为四个阶段：q第一阶段：从第一阶段：从Q(制造厂制造厂)到到A(出口港出口港)；q第二阶段：从第二阶段：从A(出口港出口港)到到B(进口港进口港)；q第三阶段：从第三阶

3、段：从B(进口港进口港)到到C(城市城市)；q第四阶段：从第四阶段：从C(城市城市)到到T(某公司某公司)。n每个阶段选取的路线不同，对应从每个阶段选取的路线不同，对应从Q到到T就有一系列不同的运输路线就有一系列不同的运输路线:q从始点从始点Q到终点到终点T共有共有3321=18条不同路线条不同路线q现在的问题是如何选择一条费用最小的路线？现在的问题是如何选择一条费用最小的路线？2022/12/24第4页，本讲稿共74页n最短路径：最短路径：Q A3 B1 C1TQTA1A2A3B1B2B3C1C224374642442514633334阶段1阶段2阶段3阶段403,T4,T4,C17,C26

4、,C111,B1,B28,B18,B111,A3 2022/12/25第5页，本讲稿共74页多阶段决策问题的典型例子多阶段决策问题的典型例子v企企业业在在生生产产过过程程中中，由由于于需需求求是是随随着着时时间间变变化化的的因因素素，因因此此企企业业为为了了获获得得全全年年最最佳佳经经济济效效益益，就就要要在在整整个个生生产产过过程程中中逐逐月月或或逐逐季季的根据库存和需求决定生产计划。的根据库存和需求决定生产计划。v某某种种机机器器，可可以以在在高高、低低两两种种负负荷荷下下生生产产。高高负负荷荷下下生生产产的的产产量量多多，但但每每生生产产一一个个阶阶段段后后机机器器的的完完好好率率低低；

5、低低负负荷荷下下生生产产时时的的情情况况则则相相反反。现现在在需需要要安安排排该该种种机机器器在在多多个个阶阶段段内内的的生生产产，问问应应该该如如何何决决定定各各阶阶段段中中机机器器的的使使用用，使使整整个计划期内的总产量最大。个计划期内的总产量最大。v化化工工生生产产过过程程包包含含一一系系列列的的过过程程设设备备，如如反反应应器器、蒸蒸馏馏塔塔、吸吸收收器器等等等等，前前一一设设备备的的输输出出是是后后一一设设备备的的输输入入。因因此此，应应该该如如何何控控制制生生产产过过程程中中各各个个设设备备的的输输出出和和输输入入，使使总总产产量最大。量最大。2022/12/26第6页，本讲稿共7

6、4页v某台设备，例如汽车，刚买来时故障少，耗油低，出车时间长，某台设备，例如汽车，刚买来时故障少，耗油低，出车时间长，处理价值和经济效益高。随着使用时间的增加则变为故障多，处理价值和经济效益高。随着使用时间的增加则变为故障多，耗油高，维修费用增加，经济效益差。使用时间愈长，处理价耗油高，维修费用增加，经济效益差。使用时间愈长，处理价值也愈低。另外，每次更新都要付出更新费用。因此，应当如值也愈低。另外，每次更新都要付出更新费用。因此，应当如何决定设备的使用年限，使总的效益最佳。何决定设备的使用年限，使总的效益最佳。v发射一枚火箭去击中运动中的目标。由于目标的行动是不断改变的，发射一枚火箭去击中运

7、动中的目标。由于目标的行动是不断改变的，因此应如何根据目标运动情况，不断调整火箭飞行的方向与速度，因此应如何根据目标运动情况，不断调整火箭飞行的方向与速度，使之最快地命中目标，等等。使之最快地命中目标，等等。2022/12/27第7页，本讲稿共74页什么是动态规划？什么是动态规划？n动动态态规规划划是是运运筹筹学学OROR的的一一个个分分支支，是是解解决决多多阶阶段段决决策策过过程程最最优优化化的的一一种种方方法法或或是是一一种种分分析析多多阶阶段段决决策策过过程程的的数数学学方方法法，这这种种方方法法可可根根据据人人们们所所采采取取的的措措施施，一一步步步步地地控控制制过过程的发展，以实现预

8、定的要求。程的发展，以实现预定的要求。n这这一一运运筹筹学学分分支支最最初初是是由由美美国国数数学学家家BellmanBellman等等人人根根据据一一类类多多阶阶段段决决策策问问题题的的特特性性，提提出出了了解解决决这这类类问问题题的的最最优优化化原原理理，并并研研究究了了许多实际问题而建立起来的。许多实际问题而建立起来的。n贝贝尔尔曼曼的的名名著著动动态态规规划划于于19571957年年出出版版，这这成成了了动动态态规规划划的第一本著作。的第一本著作。2022/12/28第8页，本讲稿共74页动态规划方法的特点动态规划方法的特点J 优点优点：许许多多问问题题用用动动态态规规划划研研究究求求

9、解解比比线线性性规规划划、非非线线性性规规划划更更有有效效，特特别别是是离离散散性性问问题题，解解析析数数学学无无用用武武之之地地，而而动动态态规规划划成成为为得得力力工工具；具；某某些些情情况况下下，用用动动态态规规划划处处理理不不仅仅能能作作定定性性描描述述分分析析，且且可利用计算机给出求其数值解的方法。可利用计算机给出求其数值解的方法。2022/12/29第9页，本讲稿共74页L缺点：缺点：没有统一的处理方法，求解时要根据问题的性质，结合多种数没有统一的处理方法，求解时要根据问题的性质，结合多种数学技巧。因此，实践经验及创造性思维将起重要的引导作用。学技巧。因此，实践经验及创造性思维将起

10、重要的引导作用。“维数障碍维数障碍”：当变量个数太多时，由于计算机内存和速度的限制：当变量个数太多时，由于计算机内存和速度的限制导致问题无法解决。有些问题由于涉及的函数没有理想的性质使问题导致问题无法解决。有些问题由于涉及的函数没有理想的性质使问题只能用动态规划描述，而不能用动态规划方法求解。只能用动态规划描述，而不能用动态规划方法求解。2022/12/210第10页，本讲稿共74页 应特别指出的是，动态规划是解决某一类问题的一种应特别指出的是，动态规划是解决某一类问题的一种方法，是分析问题的一种途径，而不是一种特殊算法方法，是分析问题的一种途径，而不是一种特殊算法(如线如线性规划是一种算法性

11、规划是一种算法)。因而，它不象线性规划那样有一个标。因而，它不象线性规划那样有一个标准的数学表达式和明确定义的一组规则，而必须对具体问准的数学表达式和明确定义的一组规则，而必须对具体问题进行具体分析处理。因此，在学习动态规划时，除了对题进行具体分析处理。因此，在学习动态规划时，除了对基本概念和方法正确地理解外，应以丰富的想象力去建立基本概念和方法正确地理解外，应以丰富的想象力去建立模型，用创造性的技巧去求解。正如贝尔曼本人所说：模型，用创造性的技巧去求解。正如贝尔曼本人所说：“由于动态规划的最优化原理仅仅是一种基本原理，正是它由于动态规划的最优化原理仅仅是一种基本原理，正是它的某种不确定性为你

12、提供了发挥你创造性思维的巨大空间的某种不确定性为你提供了发挥你创造性思维的巨大空间!2022/12/211第11页，本讲稿共74页10.2 动态规划原理 n阶段阶段(stage)q处理多阶段决策，需将全过程划为若干阶段，每个阶段进行一次抉处理多阶段决策，需将全过程划为若干阶段，每个阶段进行一次抉择。择。q各阶段按一定顺序联接在一起组成统一的整体。各阶段按一定顺序联接在一起组成统一的整体。q用用k表示表示阶段变量阶段变量阶段变量阶段变量。q阶段编号阶段编号n顺序编号顺序编号n逆序编号逆序编号一、动态规划的基本概念一、动态规划的基本概念 2022/12/212第12页，本讲稿共74页n状态状态(s

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

14、qsk(i)表示第表示第k阶段的第阶段的第 i 个状态。个状态。2022/12/213第13页，本讲稿共74页n决策决策(decision)q从从上上一一阶阶段段某某状状态态演演变变到到下下一一阶阶段段某某状状态态要要作作一一次次选选择择，称称为为决决策。策。q用用变变量量xk(sk)表表示示第第k阶阶段段状状态态为为sk时时的的决决策策，称称为为决决决决策策策策变变变变量量量量，简记简记xkq决决策策变变量量的的取取值值被被限限制制在在某某一一范范围围内内，此此范范围围称称为为允允许许决决策策集集合合Xk(sk)n策略策略(policy)q多多阶阶段段决决策策过过程程中中，每每一一阶阶段段均

15、均有有一一个个决决策策，依依序序组组合合成一个全过程的决策序列，称为成一个全过程的决策序列，称为全过程策略全过程策略全过程策略全过程策略。p1,n(s1)=x1(s1),x2(s2),xn(sn)，简记简记p1,n=x1,x2,xn2022/12/214第14页，本讲稿共74页q从从过过程程的的某某个个阶阶段段开开始始到到最最终终阶阶段段结结束束称称为为后后部部子子过过程。从第程。从第k阶段开始的后部子策略称为阶段开始的后部子策略称为第第第第k k子过程策略子过程策略子过程策略子过程策略。pk,n(sk)=xk(sk),xk+1(sk+1),xn(sn)简记简记 pk,n=xk,xk+1,xn

16、q每每一一阶阶段段有有若若干干状状态态,每每个个状状态态又又有有若若干干个个不不同同的的决决策策,即即有有许许多多策策略略可可供供选选择择。全全体体策策略略构构成成允允允允许许许许策策策策略略略略集集集集合合合合Pk,n(sk)。q能能使使预预期期目目标标达达到到最最优优效效果果的的策策略略称称为为最最最最优优优优策策策策略略略略P*k,n，q构成最优策略的各决策称为相应阶段的构成最优策略的各决策称为相应阶段的最优决策最优决策最优决策最优决策x*k。2022/12/215第15页，本讲稿共74页n状态转移方程状态转移方程q下下一一阶阶段段状状态态sk+1 是是本本阶阶段段状状态态变变量量sk

17、和和决决策策变变量量xk的的函函数数，即即 sk+1=T(sk,xk(sk)=T(sk,xk)q从从状状态态sk出出发发到到下下一一阶阶段段状状态态sk+1的的转转移移规规律律称称为为状状状状态态态态转转转转移移移移方程方程方程方程。n指标函数指标函数q用用来来衡衡量量每每一一阶阶段段决决策策效效果果的的优优劣劣的的数数量量指指标标，称称为为阶阶阶阶段段段段指指指指标标标标函函函函数数数数vk ，阶阶段段指指标标是是状状态态变变量量和和相相应应决决策策变变量量的的函函数数，即即vk=vk(sk,xk)。n最最短短问问题题是是运运费费或或路路程程。对对阶阶段段的的不不同同状状态态，采采取取不不同

18、同的的决决策，运费不同。策，运费不同。n指标函数也可以是利润、成本、产量等。指标函数也可以是利润、成本、产量等。2022/12/216第16页，本讲稿共74页q从从第第k阶阶段段的的状状态态sk出出发发到到最最后后阶阶段段结结束束，各各阶阶段段绩绩效效综综合合起起来来反反映映这这个个后后部部子子过过程程的的绩绩效效，称称为为过过过过程程程程指指指指标标标标函函函函数数数数，记记为为Vk,n。qVk,n的大小取决于从第的大小取决于从第k阶段到最后阶段所采取的子策略。即阶段到最后阶段所采取的子策略。即 q Vk,n=Vk,n(sk,xk,sk+1,xk+1,sn)q根据实际问题的性质，指标函数根据

19、实际问题的性质，指标函数Vk,n 为各个阶段指标的和或积。为各个阶段指标的和或积。q从从状状态态sk出出发发，选选取取最最优优策策略略所所得得的的指指标标函函数数值值称称为为最最最最优优优优指指指指标标标标函数值函数值函数值函数值。qfk(sk)=optVk,n=optvk(sk,xk)+fk+1(sk+1)qopt表示最优化，取最大表示最优化，取最大max或最小或最小min。2022/12/217第17页，本讲稿共74页n逆序算法：逆着阶段顺序的方向，由后向前推算。逆序算法：逆着阶段顺序的方向，由后向前推算。q把寻求最优策略看作连续递推过程，从最终阶段开始，逆着实把寻求最优策略看作连续递推过

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

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

22、加上上(或或乘乘以以)从从下下一一阶阶段段k+1开开始始到到过过程程结结束束采采取取最最优优策策略略取取得得的的最最优优指指标标函函数数值值fk+1(sk+1)，再再从从中中选选出出最最优优，便便是是阶阶段段k从从状状态态sk出出发发到到全过程结束的最优指标函数值。全过程结束的最优指标函数值。2022/12/219第19页，本讲稿共74页阶段阶段1阶段阶段2阶段阶段k阶段阶段k+1阶段阶段n状态状态S1决决策策x1状态状态S2v1决决策策x2状态状态S3v2决决策策xk状态状态Sk+1vk决决策策xk+1vk+1决决策策xnvn寻求最优解的方向寻求最优解的方向2022/12/220第20页，本

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

24、际问顺序递推法本质上并无新的建树，只是对某些实际问题的求解，应用起来较为简便而已。题的求解，应用起来较为简便而已。2022/12/221第21页，本讲稿共74页三、建立动态规划模型的步骤三、建立动态规划模型的步骤 1、划分阶段、划分阶段划划分分阶阶段段是是运运用用动动态态规规划划求求解解多多阶阶段段决决策策问问题题的的第第一一步步，在在确确定定多多阶阶段段特特性性后后，按按时时间间或或空空间间先先后后顺顺序序，将将过过程程划划分分为为若若干干相相互互联联系系的的阶阶段段。对于静态问题要人为地赋予对于静态问题要人为地赋予“时间时间”概念，以便划分阶段。概念，以便划分阶段。2、正确选择状态变量、正

25、确选择状态变量选选择择变变量量既既要要能能确确切切描描述述过过程程演演变变又又要要满满足足无无后后效效性性，而而且且各各阶阶段段状状态态变变量量的的取取值值能能够够确确定定。一一般般地地，状状态态变变量量的的选选择择是是从从过过程程演演变变的特点中寻找。的特点中寻找。3、确定决策变量及允许决策集合、确定决策变量及允许决策集合通通常常选选择择所所求求解解问问题题的的关关键键变变量量作作为为决决策策变变量量，同同时时要要给给出出决决策策变变量量的的取值范围，即确定允许决策集合。取值范围，即确定允许决策集合。2022/12/222第22页，本讲稿共74页 4、确定状态转移方程、确定状态转移方程 根据

26、根据k 阶段状态变量和决策变量，写出阶段状态变量和决策变量，写出k+1阶段状态变量，阶段状态变量，状态转移方程应当具有递推关系。状态转移方程应当具有递推关系。5、确定阶段指标函数和最优指标函数，建立动态规划基本方程、确定阶段指标函数和最优指标函数，建立动态规划基本方程 阶段指标函数是指第阶段指标函数是指第k 阶段的收益，最优指标函数是指从阶段的收益，最优指标函数是指从第第k 阶段状态出发到第阶段状态出发到第n 阶段末所获得收益的最优值，最后写出动阶段末所获得收益的最优值，最后写出动态规划基本方程。态规划基本方程。以上五步是建立动态规划数学模型的一般步骤。由于动态规以上五步是建立动态规划数学模型

27、的一般步骤。由于动态规划模型与线性规划模型不同，动态规划模型没有统一的模式，建划模型与线性规划模型不同，动态规划模型没有统一的模式，建模时必须根据具体问题具体分析，只有通过不断实践总结，才能模时必须根据具体问题具体分析，只有通过不断实践总结，才能较好掌握建模方法与技巧。较好掌握建模方法与技巧。2022/12/223第23页，本讲稿共74页四、动态规划模型的求解四、动态规划模型的求解例例 分配投资问题分配投资问题 某公司有资金某公司有资金 10 万元，若投资于项目万元，若投资于项目 k(k=1，2，3)的投资额的投资额为为 xk 时，其收益分别为时，其收益分别为 g1(x1)=4x1，g2(x2

28、)=9x2，g3(x3)=2x32，问应该如何分配投资数额才能使总收益最大？问应该如何分配投资数额才能使总收益最大？该问题表面上看与时间无明显关系，其静态模型：该问题表面上看与时间无明显关系，其静态模型：Max z=4x1+9x2+2x32 x1+x2+x3=10 xi 0(i=1，2，3)2022/12/224第24页，本讲稿共74页 如何应用动态规划方法求解此类静态规划问题？一般我们可以如何应用动态规划方法求解此类静态规划问题？一般我们可以人为地给它赋予人为地给它赋予“时段时段”的概念，将投资项目按任意顺序进行排的概念，将投资项目按任意顺序进行排序，如首先考虑项目序，如首先考虑项目1 的投

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

30、段的投资量(分配给第分配给第 k 个项目的资金个项目的资金数量数量)，决策集合，决策集合 Dk(sk)=xk 0 xk sk n状态转移方程状态转移方程 sk+1=sk-xk 2022/12/225第25页，本讲稿共74页n阶段指标值阶段指标值(函数函数)vk(sk，xk)=gk(xk)n定义定义fk(sk)：第：第 k 段初拥有的资金总量为段初拥有的资金总量为 sk 时，第时，第 k 至第至第 3 段按最优投资策略所获得的第段按最优投资策略所获得的第 k 至第至第 3 段的总收益。段的总收益。n建立动态规划基本方程：建立动态规划基本方程：(逆序递推方程逆序递推方程)fk(sk)=max gk

31、(xk)+fk+1(sk+1)，k=3，2，10 xk skf4(s4)=02022/12/226第26页，本讲稿共74页逆序递推求解动态规划基本方程逆序递推求解动态规划基本方程k=3k=2 f3(s3)=Max 2x32+f4(s4)=Max 2x32+0 0 x3 s30 x3 s3f3*(s3)=2s32，xk*=s3 f2(s2)=Max 9x2+f3(s3)=Max 9x2+2s32 0 x2 s2=Max 9x2+2(s2 x2)2 可以证明极大值只可能在端点取得，即：可以证明极大值只可能在端点取得，即：f2(0)=2s22 f2(s2)=9s2 s2 9/2 时，时，f2(0)f

32、2(s2)，此时，此时 x2*=0 s2 9/2 时，时，f2(0)f2(s2)，此时，此时 x2*=s2 2022/12/227第27页，本讲稿共74页k=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 同样可以证明极大值只可能在端点取得，比较两个端点：同样可以证明极大值只可能在端点取得，比较

33、两个端点：x1=0 时，时，f1(10)=200，x1=10 时，时，f1(10)=40所以所以 x1*=0 2022/12/228第28页，本讲稿共74页顺序确定顺序确定最优策略最优策略 s1=10 x1*=0s2=s1 x1*=10 9/2 x2*=0 s3=s2 x2*=10 x3*=10最优投资方案为全部资金投资于第最优投资方案为全部资金投资于第 3 3 个项目，可获最大收益个项目，可获最大收益 200 200 万元。万元。2022/12/229第29页，本讲稿共74页例、从例、从A 地到地到D 地要铺设一条煤气管道地要铺设一条煤气管道,其中需经过两级中间站，其中需经过两级中间站，两点

34、之间的连线上的数字表示距离，如图所示。问应该选择什两点之间的连线上的数字表示距离，如图所示。问应该选择什么路线，使总距离最短？么路线，使总距离最短？AB1B2C1C2C3D24333321114一、最短路径问题一、最短路径问题10.2 动态规划应用举例 2022/12/230第30页，本讲稿共74页 解：整个计算过程分三个阶段，从最后一个阶段开始。解：整个计算过程分三个阶段，从最后一个阶段开始。第一阶段第一阶段(C D)：C 有三条路线到终点有三条路线到终点D。AB1B2C1C2C3D24333321114DC1C2C3显然有显然有 f1(C1)=1 ；f1(C2)=3 ；f1(C3)=4 2

35、022/12/231第31页，本讲稿共74页 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)2022/12/232第32页，本讲稿共74页 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 =

36、3 5AB1B2C1C2C3D24333321114DC1C2C3B1B2(最短路线为最短路线为B2C1 D)2022/12/233第33页，本讲稿共74页第三阶段第三阶段(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，路长为路长为 6AB1B2C1C2C3D24333321114DC1C2C3B1B2A2022/12/234第34页，本讲稿共74页q企业一年中的产品生产往往是

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

38、使总支出最少，这是一个多阶段决策问题。这是一个多阶段决策问题。二、生产与存储问题二、生产与存储问题 2022/12/235第35页，本讲稿共74页n例，例，某工厂与用户签订了某工厂与用户签订了4个月的交货合同如表所示个月的交货合同如表所示 该厂生产能力为每月该厂生产能力为每月5万件，该厂仓库的存货能力为万件，该厂仓库的存货能力为4万件。万件。已知生产费用为已知生产费用为c=1千元千元/万件，在进行生产的月份，工厂要支万件，在进行生产的月份，工厂要支出固定费用出固定费用b=2千元，每月仓库保管费用千元，每月仓库保管费用h=0.2千元千元/万件万件/月。月。假定开始时及假定开始时及4月底交货后无存

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

40、;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 开开始始到到最最后后阶阶段段采采用用最最优优生生产产策略实现的最

41、低生产费用策略实现的最低生产费用;2022/12/237第37页，本讲稿共74页n逆序求解逆序求解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,22022/12/238第38页，本讲稿共74页qk=3x3s30.2 s3+f4(s4)v3(s3,x3)+f4(s4)=2+x3+0.

42、2 s3+f4(s4)f3(s3)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下的下的最低生产成本最低生产成本2022/12/239第39页，本讲稿共74页qk=2x2s20.2 s2+f3(s3)v2(s2,x

43、2)+f3(s3)=2+x2+0.2 s2+f3(s3)f2(s2)x2*01201234511.410.67.8210-11.411.611.811.6-10.6 10.811.010.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下的最低下的最低生产成本生产成本2022/12/

44、240第40页，本讲稿共74页nk=1x1s1v1(s1,x1)+f2(s2)=2+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，则，则

45、x1 3，生产能力限制生产能力限制 x1 5，则，则3 x1 5，x1=3,4,52022/12/241第41页，本讲稿共74页n资源分配问题：资源分配问题：q把有限的资源把有限的资源(如资金、材料、设备、人力等如资金、材料、设备、人力等)分配给若干使分配给若干使用者，而使某一指标为最优的问题即为资源分配问题。用者，而使某一指标为最优的问题即为资源分配问题。q资源可以有一种或若干种，资源可以有一种或若干种，q只有一种资源可供分配的问题称之为一维资源分配问题。只有一种资源可供分配的问题称之为一维资源分配问题。n一维资源分配问题一维资源分配问题三、资源分配问题三、资源分配问题 设备台数设备台数分厂

46、分厂0123456I0356765II04678910III0259887如何分配设备，可使获利最大？如何分配设备，可使获利最大？各分厂各分厂在不同在不同设备台设备台数下所数下所获利润获利润2022/12/242第42页，本讲稿共74页n动态规划的数学模型动态规划的数学模型q将三个分厂看作是三个阶段，即阶段变量将三个分厂看作是三个阶段，即阶段变量 k=1,2,3;q状态变量状态变量sk 表示第表示第k 阶段初可分配的设备台数阶段初可分配的设备台数,0 sk 6;q决策变量决策变量xk 表示第表示第k 阶段分配给分厂阶段分配给分厂k 的设备台数，的设备台数，允允许决策集合许决策集合Xk(sk)=

47、xk 0 xk sk;q状态转移方程为状态转移方程为 sk+1=sk-xk;q阶阶段段指指标标vk(sk,xk)表表示示第第k 阶阶段段从从sk台台设设备备中中分分配配给给k 分分厂厂xk 台设备的阶段效益台设备的阶段效益;q最最优优指指数数函函数数fk(sk)表表示示第第k阶阶段段从从sk 开开始始到到最最后后阶阶段段采采用用最最优分配策略取得的最大的效益值优分配策略取得的最大的效益值;q递推方程函数式递推方程函数式 2022/12/243第43页，本讲稿共74页n逆序求解逆序求解qK=3x3s3v3(s3,x3)f3(s3)x3*第第III分厂在不同设分厂在不同设备台数下所获利润备台数下所

48、获利润012345601234560020250259025980259880259887025999901233332022/12/244第44页，本讲稿共74页qk=2x2s2v2(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+2

49、10+02022/12/245第45页，本讲稿共74页qk=1x1s1v1(s1,x1)+f2(s2)f1(s1)x1*第第I分厂在不同设分厂在不同设备台数下所获利润备台数下所获利润0123456第第II分厂在设备台数为分厂在设备台数为s2下所下所获得的最大利润获得的最大利润60356765181,2顺序递推，得出结论顺序递推，得出结论第第I 分厂分厂1套或套或2套套第第II 分厂分厂2套或套或1套套第第III 分厂分厂3套套0+163+155+136+97+66+45+02022/12/246第46页，本讲稿共74页n有一种设备可以在高低两种不同的负荷下运行，在高负荷下生产时，有一种设备可以

50、在高低两种不同的负荷下运行，在高负荷下生产时，产品的年产量产品的年产量Q1与投入生产的设备台数与投入生产的设备台数x1的关系为：的关系为：Q1=9x1，年完好率年完好率(折损后折损后)a=0.75；在低负荷下生产时，年产量；在低负荷下生产时，年产量Q2与与投入生产的设备台数投入生产的设备台数x2的关系为的关系为:Q2=6 x2，年完好率为，年完好率为b=0.96，若开始时拥有完好机器台数为，若开始时拥有完好机器台数为100台，要求制定一个台，要求制定一个4年计划，在年计划，在每年初时应决定如何重新分配设备在高低不同的负荷下生产，使得每年初时应决定如何重新分配设备在高低不同的负荷下生产，使得4年