《第三讲动态规划高级运筹学课件.ppt》由会员分享，可在线阅读，更多相关《第三讲动态规划高级运筹学课件.ppt（52页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第三讲动态规划高级运筹学课件1第1页，此课件共52页哦4.1 4.1 动态规划的基本概念和最优化原理动态规划的基本概念和最优化原理一、引例（最短路问题）一、引例（最短路问题）假如上图是一个线路网络，两点之间连线上的数字表示两点间假如上图是一个线路网络，两点之间连线上的数字表示两点间的距离（或费用），我们的问题是要将货物从的距离（或费用），我们的问题是要将货物从A地运往地运往E地，中间地，中间通过通过B、C、D三个区域，在区域内有多条路径可走，现求一条由三个区域，在区域内有多条路径可走，现求一条由A到到E的线路，使总距离最短（或总费用最小）。的线路，使总距离最短（或总费用最小）。AB1B2B3C
2、1C2C3D1D2E243746324265346333342第2页，此课件共52页哦 将将该该问问题题划划分分为为4个个阶阶段段的的决决策策问问题题，即即第第一一阶阶段段为为从从A到到Bj（j=1，2，3），有有三三种种决决策策方方案案可可供供选选择择；第第二二阶阶段段为为从从Bj到到Cj（j=1,2,3），也也有有三三种种方方案案可可供供选选择择；第第三三阶阶段段为为从从Cj到到Dj(j=1,2)，有有两两种种方方案案可可供供选选择择；第第四四阶阶段段为为从从Dj到到E，只只有有一一种种方方案案选选择择。如如果果用用完完全全枚枚举举法法，则则可可供供选选择择的的路路线线有有3321=18（
3、条条），将其一一比较才可找出最短路线：将其一一比较才可找出最短路线：AB1C2D3E 其长度为其长度为12。显显然然，这这种种方方法法是是不不经经济济的的，特特别别是是当当阶阶段段数数很很多多，各各阶阶段段可可供供的的选选择择也也很很多多时时，这这种种解解法法甚甚至至在在计计算算机机上上完完成成也也是是不现实的。不现实的。由由于于我我们们考考虑虑的的是是从从全全局局上上解解决决求求A到到E的的最最短短路路问问题题，而而不不是是就就某某一一阶阶段段解解决决最最短短路路线线，因因此此可可考考虑虑从从最最后后一一阶阶段段开开始始计计算算，由由后后向向前逐步推至前逐步推至A点：点：3第3页，此课件共5
4、2页哦第四阶段，由第四阶段，由D1到到E只有一条路线，其长度只有一条路线，其长度f4（D1）=3，同理同理f4（D2）=4。第三阶段，由第三阶段，由Cj到到Di分别均有两种选择，即分别均有两种选择，即，决策点为D1,决策点为D1，决策点为D24第4页，此课件共52页哦第二阶段，由Bj到Cj分别均有三种选择，即：决策点为C2 决策点为C1或C2决策点为C2 5第5页，此课件共52页哦第一阶段，由A到B，有三种选择，即：决策点为B3 f1（A）=15说明从A到E的最短距离为12，最短路线的确定可按计算顺序反推而得。即AB3C2D2E 上述最短路线问题的计算过程，也可借助于图形直观的表示出来：6第6
5、页，此课件共52页哦 图图中中各各点点上上方方框框的的数数，表表示示该该点点到到E的的最最短短距距离离。图图中中红红箭箭线线表表示从示从A到到E的最短路线。的最短路线。从引例的求解过程可以得到以下启示：从引例的求解过程可以得到以下启示：对对一一个个问问题题是是否否用用上上述述方方法法求求解解，其其关关键键在在于于能能否否将将问问题题转转化化为为相互联系的决策过程相同的多个阶段决策问题。相互联系的决策过程相同的多个阶段决策问题。AB1B2B3C1C2C3D1D2E24374632426534633334346769911127第7页，此课件共52页哦 所所谓谓多多阶阶段段决决策策问问题题是是：把
6、把一一个个问问题题看看作作是是一一个个前前后后关关联联具具有有链链状状结构的多阶段过程，也称为序贯决策过程。如下图所示：结构的多阶段过程，也称为序贯决策过程。如下图所示：在在处处理理各各阶阶段段决决策策的的选选取取上上，不不仅仅只只依依赖赖于于当当前前面面临临的的状状态态，而而且且还还要要注注意意对对以以后后的的发发展展。即即是是从从全全局局考考虑虑解解决决局局部部（阶阶段段）的的问问题。题。各各阶阶段段选选取取的的决决策策，一一般般与与“时时序序”有有关关，决决策策依依赖赖于于当当前前的的状状态态，又又随随即即引引起起状状态态的的转转移移，整整个个决决策策序序列列就就是是在在变变化化的的状状
7、态态中中产产生生出出来来，故故有有“动动态态”含含义义。因因此此，把把这这种种方方法法称称为为动动态态规划方法。规划方法。决策过程是与阶段发展过程逆向而行。决策过程是与阶段发展过程逆向而行。8第8页，此课件共52页哦 二、多阶段决策问题的典型例子：二、多阶段决策问题的典型例子：v企企业业在在生生产产过过程程中中，由由于于需需求求是是随随着着时时间间变变化化的的因因素素，因因此此企企业业为为了了获获得得全全年年最最佳佳经经济济效效益益，就就要要在在整整个个生生产产过过程程中逐月或逐季的根据库存和需求决定生产计划。中逐月或逐季的根据库存和需求决定生产计划。v某某种种机机器器，可可以以在在高高、低低
8、两两种种负负荷荷下下生生产产。高高负负荷荷下下生生产产的的产产量量多多，但但每每生生产产一一个个阶阶段段后后机机器器的的完完好好率率低低；低低负负荷荷下下生生产产时时的的情情况况则则相相反反。现现在在需需要要安安排排该该种种机机器器在在多多个个阶阶段段内内的的生生产产，问问应应该该如如何何决决定定各各阶阶段段中中机机器器的的使使用用，使使整整个计划期内的总产量最大。个计划期内的总产量最大。v某台设备，例如汽车，刚买来时故障少，耗油低，出车时间某台设备，例如汽车，刚买来时故障少，耗油低，出车时间长，处理价值和经济效益高。随着使用时间的增加则变为故长，处理价值和经济效益高。随着使用时间的增加则变为
9、故障多，耗油高，维修费用增加，经济效益差。使用时间愈长，障多，耗油高，维修费用增加，经济效益差。使用时间愈长，处理价值也愈低。另外，每次更新都要付出更新费用。因此，处理价值也愈低。另外，每次更新都要付出更新费用。因此，应当如何决定设备的使用年限，使总的效益最佳。应当如何决定设备的使用年限，使总的效益最佳。9第9页，此课件共52页哦三、动态规划方法的特点三、动态规划方法的特点J 优优点点：许许多多问问题题用用动动态态规规划划研研究究求求解解比比线线性性规规划划、非非线线性性规规划划更更有有效效，特特别别是是离离散散性性问问题题，解解析析数数学学无无用用武武之之地地，而而动动态态规划成为得力工具；
10、规划成为得力工具；某某些些情情况况下下，用用动动态态规规划划处处理理不不仅仅能能作作定定性性描描述述分分析析，且且可利用计算机给出求其数值解的方法。可利用计算机给出求其数值解的方法。L 缺点：缺点：没有统一的处理方法，求解时要根据问题的性质，结没有统一的处理方法，求解时要根据问题的性质，结合多种数学技巧。因此，实践经验及创造性思维将起重要的引合多种数学技巧。因此，实践经验及创造性思维将起重要的引导作用。导作用。“维数障碍维数障碍”：当变量个数太多时，由于计算机内存：当变量个数太多时，由于计算机内存和速度的限制导致问题无法解决。有些问题由于涉及的函数和速度的限制导致问题无法解决。有些问题由于涉及
11、的函数没有理想的性质使问题只能用动态规划描述，而不能用动态没有理想的性质使问题只能用动态规划描述，而不能用动态规划方法求解。规划方法求解。10第10页，此课件共52页哦4.2 动态规划的基本概念动态规划的基本概念一、动态规划的基本要素一、动态规划的基本要素 1、阶阶段段。阶阶段段的的划划分分，一一般般根根据据时时序序和和空空间间的的自自然然特特征征来来划划分分，但但要要便便于于把把问问题题的的过过程程能能转转化化为为阶阶段段决决策策的的过过程程。描描述述阶阶段段的的变变量量称称为为阶阶段段变变量量，常常用用自自然然数数k表表示示。如如引引例例可可划划分分为为4个个阶阶段段求求解解，k=1，2，
12、3，4。2、状状态态。状状态态就就是是阶阶段段的的起起始始位位置置。它它既既是是该该阶阶段段某某支支路路的起点，又是前一阶段某支路的终点。的起点，又是前一阶段某支路的终点。（1）状状态态变变量量和和状状态态集集合合。描描述述过过程程状状态态的的变变量量称称为为状状态态变变量量。它它可可用用一一个个数数、一一组组数数或或一一向向量量（多多维维情情形形）来来描描述述，常常用用Sk表表示示第第k阶阶段段的的状状态态变变量量。通通常常一一个个阶阶段段有有若若干干个个状状态态。第第k阶阶段段的的状状态态就是该阶段所有始点的集合。如引例中就是该阶段所有始点的集合。如引例中11第11页，此课件共52页哦 （
13、2）状状态态应应具具有有无无后后效效性性（即即马马尔尔可可夫夫性性）。即即如如果果某某阶阶段段状状态态给给考考虑虑，则则在在这这阶阶段段以以后后过过程程的的发发展展不不受受这这阶阶段段以以前前各各阶阶段段状状态的影响。态的影响。3、决决策策与与决决策策变变量量。在在某某阶阶段段对对可可供供选选择择状状态态的的决决定定（或或选选择择），称称为为决决策策。描描述述的的变变量量称称为为决决策策变变量量。常常用用dk(Sk)表表示示第第k阶阶段段处处于于状状态态Sk时时的的决决策策变变量量，它它是是状状态态变变量量的的函函数数。决决策策变变量量允允许许取取值值的的范范围围，称称为为允允许许决决策策集集
14、合合，常常用用Dk(Sk)表表示示。显显然然dk（Sk）Dk(Sk)。如如在在引引例例的的第第二二阶阶段段中中，若若从从B1出出发发，D2（B1）=B1 C1,B1 C2,B1 C3如果决定选取如果决定选取B1 C2，则，则d2（B1）=B1 C2。12第12页，此课件共52页哦称可供选择策略的范围，为允许策略集，用称可供选择策略的范围，为允许策略集，用P表示。表示。动态规划方法就是要从允许策略集动态规划方法就是要从允许策略集P中找出最优策略中找出最优策略P1n*。4、策策略略与与子子策策略略。策策略略是是一一个个决决策策序序列列的的集集合合。当当k=1时时，P1n（S1）=d1(s1),d2
15、(s2),dn(sn)就就称称为为全全过过程程的的一一个个策策略略，简简称称策策略略，简简记为记为P1n(S1).称称Pk,n(Sk)=dk(sk),dk+1(sk+1),dn(sn)为由第为由第k阶段开始到最后阶段开始到最后阶段止的一个子策略，简称后部子策略。简记为阶段止的一个子策略，简称后部子策略。简记为Pk,n(Sk)5、状状态态转转移移方方程程。它它是是确确定定过过程程由由某某一一阶阶段段的的一一个个状状态态到到下下一一阶阶段段另另一一状状态态的的演演变变过过程程，用用Sk+1=Tk(Sk,dk)表表示示。该该方方程程描描述述了了由由第第k阶阶段段到到第第k+1阶阶段段的的状状态态转转
16、移移规规律律。因因此此又又称称其其为为状状态态转转移移函数。函数。13第13页，此课件共52页哦6、阶段指标、指标函数和最优指标函数、阶段指标、指标函数和最优指标函数（1）衡衡量量某某阶阶段段决决策策效效益益优优劣劣的的数数量量指指标标，称称为为阶阶段段指指标标，用用vk(Sk,dk)表示第表示第k阶段的阶段指标。阶段的阶段指标。在不同的问题中，其含义不同。它可以是距离、利润、成本等。在不同的问题中，其含义不同。它可以是距离、利润、成本等。在在引引例例中中，用用dk=vk(Sk,dk)表表示示在在第第k阶阶段段由由点点Sk到到点点Sk+1=dk(Sk)距距离。如离。如d2(B3,C1)=6。1
17、4第14页，此课件共52页哦（2）用用于于衡衡量量所所选选定定策策略略优优劣劣的的数数量量指指标标，称称为为指指标标函函数数。它它是是定定义义在在全全过过程程和和所所有有后后部部子子过过程程上上确确定定的的数数量量函函数数。记记为为Vk,n(Sk,Pk,n).Vk,n(Sk,Pk,n)=Vk,n(Sk,dk,Sk+1,Sn+1)k=1,2,n。构成动态规划模型的指标函数，应具有可分离性，并满足递推关系。构成动态规划模型的指标函数，应具有可分离性，并满足递推关系。常见的指标函数的形式有：常见的指标函数的形式有：15第15页，此课件共52页哦（3）最最优优指指标标函函数数fk(Sk),表表示示从从
18、第第k阶阶段段的的状状态态Sk开开始始采采用用最最优优子子策略策略P*k,n，到第，到第n阶段终止时所得到的指标函数值。阶段终止时所得到的指标函数值。即即fk(Sk)=Opt Vk,n(Sk,dk,Sn+1)其其中中Opt是是最最优优化化（Optimum）的的缩缩写写，可可根根据据题题意意取取max或或min。在引例中，指标函数在引例中，指标函数Vk,n表示在第表示在第k阶段由点阶段由点Sk至终点至终点E的距离。的距离。fk(sk)表示第表示第k阶段点阶段点Sk到终点到终点E的最短距离。的最短距离。f2(B1)=11表示从第表示从第2阶阶段中的点段中的点B1到点到点E的最短距离。的最短距离。1
19、6第16页，此课件共52页哦7、基本方程（递推关系式）、基本方程（递推关系式）从引例求从引例求A到到E的最短路的计算过程中可以看出，在求解的各个阶的最短路的计算过程中可以看出，在求解的各个阶段，我们利用了段，我们利用了k阶段与阶段与k+1阶段之间的递推关系阶段之间的递推关系一般地，若一般地，若 则有则有若17第17页，此课件共52页哦 1、基基本本思思想想：动动态态规规划划方方法法的的关关键键在在于于正正确确地地写写出出基基本本方方程程，因因此此首首先先必必须须将将问问题题的的过过程程划划分分为为多多个个相相互互联联系系的的多多阶阶段段决决策策过过程程，恰恰当当地地选选取取状状态态变变量量和和
20、决决策策变变量量及及定定义义最最优优指指标标函函数数，从从而而把把问问题题化化成成一一族族同同类类型型的的子子问问题题。然然后后从从边边界界条条件件开开始始，逆逆过过程程行行进进方方向向，逐逐段段递递推推寻寻优优。在在每每个个子子问问题题求求解解时时，均均利利用用它它前前面面已已求求出出的的子子问问题题的的最最优优化化结结果果依依次次进进行行，最最后后一一个个子子问问题题所所得得的的最优解，就是整个问题的最优解。最优解，就是整个问题的最优解。在在多多阶阶段段决决策策过过程程中中，动动态态规规划划方方法法是是既既把把当当前前的的一一段段和和未未来来的的各各段段分分开开，又又把把当当前前效效益益和
21、和未未来来效效益益结结合合起起来来考考虑虑的的一一种种最最优优化化方方法法。因因此此，每每阶阶段段决决策策的的选选取取是是从从全全局局来来考考虑虑，与与该该段段的的最最优优选选择择一一般般是是不不同同的。的。动动态态规规划划方方法法的的基基本本思思想想体体现现了了多多阶阶段段性性、无无后后效效性性、递递归归性性、总总体优化性。体优化性。二、动态规划的基本思想与最优化原理二、动态规划的基本思想与最优化原理18第18页，此课件共52页哦 2、最优化原理、最优化原理 动动态态规规划划方方法法基基于于RBellman等等人人提提出出的的最最优优化化原原理理：“作作为为整整个个过过程程的的最最优优策策略
22、略具具有有这这样样的的性性质质，即即无无论论过过去去的的状状态态和和决决策策如如何何，对对于于先先前前的的决决策策所所形形成成的的状状态态而而言言，余余下下的的诸诸决决策策必必须须构构成成最最优优策策略略。”简简言言之之，“一一个个最最优优策策略略的的子子策略总是最优的策略总是最优的”。但但是是，最最优优化化原原理理仅仅是是策策略略最最优优性性的的必必要要条条件件，而而基基本本方方程程是是策策略略最最优优性性的的充充要要条条件件。由由此此可可见见，基基本本方方程程是是动动态态规规划划理理论与方法的基础。论与方法的基础。4.3 4.3 动态规划模型的建立与求解动态规划模型的建立与求解一、构成动态
23、规划模型的条件一、构成动态规划模型的条件19第19页，此课件共52页哦 应用动态规划解决问题时必须首先建立动态规划模型，再应用动态规划解决问题时必须首先建立动态规划模型，再用逆序或顺序算法求解。写一个问题的动态规划模型一般包用逆序或顺序算法求解。写一个问题的动态规划模型一般包含以下含以下6个步骤：个步骤：（1）阶段划分）阶段划分 k=1,2,n （2）确定状态变量）确定状态变量sk （3）确定决策变量）确定决策变量dk （4）确定状态转移方程）确定状态转移方程sk+1=f(sk,dk)或或sk-1=f(sk,dk)（5）确定阶段指标）确定阶段指标V(sk,dk)（6）确定基本递推方程）确定基本
24、递推方程或20第20页，此课件共52页哦二、求解动态规划模型的方法二、求解动态规划模型的方法1、在已知初始状态、在已知初始状态S1下，采用逆序解法：（反向递归）下，采用逆序解法：（反向递归）按上图示意的求解方法称为逆序法。例如引例的求解，就是把按上图示意的求解方法称为逆序法。例如引例的求解，就是把A看作始端，看作始端，E为终端，规定从为终端，规定从A到到E为过程的行进方向，而寻优为过程的行进方向，而寻优则是从则是从E到到A逆过程进行，所以是采用了逆序法。逆过程进行，所以是采用了逆序法。阶段阶段1s1d1(s1)v1(s1,d1)阶段阶段2s2d2(s2)v2(s2,d2)阶段阶段kskdk(s
25、k)vk(sk,dk)阶段阶段k+1sk+1dk+1(sk+1)vk+1(sk+1,dk+1)阶段阶段nsndn(sn)vn(sn,dn)vk,nfk(sk)=optVk,n寻优方向寻优方向21第21页，此课件共52页哦2、在已知终止状态、在已知终止状态Sn下，采用顺序解法（正向递归）下，采用顺序解法（正向递归）如果我们把引例中如果我们把引例中E看作始端，看作始端，A为终端，规定从为终端，规定从E到到A过程为过程为行进方向，而寻优则是从行进方向，而寻优则是从A到到E过程进行求解的方法称为顺序法。其过程进行求解的方法称为顺序法。其示意图如下：示意图如下：逆序法与顺序法的不同仅在对始端终端看法的颠
26、倒或在规定逆序法与顺序法的不同仅在对始端终端看法的颠倒或在规定的行进方向不同。但在寻优时却都是逆行进方向，从最后一阶的行进方向不同。但在寻优时却都是逆行进方向，从最后一阶段开始，逐段逆推向前计算，找出最优结果。段开始，逐段逆推向前计算，找出最优结果。阶段阶段1s0d1(s1)v1(s1,d1)阶段阶段2s1d2(s2)v2(s2,d2)阶段阶段kdk(sk)vk(sk,dk)阶段阶段k+1sk+1dk+1(sk+1)vk+1(sk+1,dk+1)阶段阶段ndn(sn)vn(sn,dn)vk,nfk(sk)=optV1,k寻优方向寻优方向sksn22第22页，此课件共52页哦3、两种解法在建模时
27、的区别如下表所示、两种解法在建模时的区别如下表所示23第23页，此课件共52页哦案例案例1 某商店在未来四个月里，利用一个仓库经销某种商品。该仓库某商店在未来四个月里，利用一个仓库经销某种商品。该仓库的最大容量为的最大容量为1000件，每月中旬订购商品，并于下月初取到订件，每月中旬订购商品，并于下月初取到订货。据估计，今后四个月这种商品的购价和售价如下表所示。货。据估计，今后四个月这种商品的购价和售价如下表所示。假定商店在假定商店在1月初开始经销时仓库已存有该种商品月初开始经销时仓库已存有该种商品500件，每月市场件，每月市场需求不限，问应如何计划每个月的订购与销售量，使这四个月的总需求不限，
28、问应如何计划每个月的订购与销售量，使这四个月的总利润最大（不考虑仓库的存储费用）？利润最大（不考虑仓库的存储费用）？月份k购价pk售价qk110122993111341517解：首先建立动态规划模型。（1）问题划分为四个阶段K=1，2，3，4；（2）状态变量sk表示第k阶段初的库存量，且s1=50024第24页，此课件共52页哦（3）决策变量xk表示第k月的订货量，yk表示第k月的销售量；（4）状态转移方程sk+1=sk+xk-yk,（5）指标函数表示第k月的利润V(sk,xk,yk)=qkyk-pkxk（6）基本方程为其逆序计算过程见课本P10425第25页，此课件共52页哦解：当解：当K=
29、4时，根据基本递推方程时，根据基本递推方程显然，显然，y4*=s4,x4*=0为最优决策，这时，为最优决策，这时，f4(s4)=17s4当当K=3时，时，这是一个线性规划问题，解得最优解为这是一个线性规划问题，解得最优解为y3*=s3,x3*=H，f3(s3)=13s3+6H26第26页，此课件共52页哦当当K=2时，时，得最优解为得最优解为y2*=s2,x2*=H，f2(s2)=9s2+10H当当K=1时，时，得最优解为得最优解为y1*=s1,x1*=0，f1(s1)=12s1+10H将将s1=500,H=1000代入上式，并按计算顺序反推，得：代入上式，并按计算顺序反推，得：x1*=0，y
30、1*=s1=500 x2*=H=1000，y2*=s2=s1+x1*-y1*=0 x3*=H=1000，y2*=s3=s2+x2*-y2*=1000 x4*=0，y4*=s4=s3+x3*-y3*=100027第27页，此课件共52页哦案例案例2 P118练习4.4 某工厂有100台机器，拟分四期使用，在每一期都有两种生产任务。据经验，若把x1台机器投入第一种生产任务，则在本期结束时将有1/3 x1台机器损坏报废，剩下的机器全部投入第二种生产任务，则有1/10的机器在期未损坏报废。如果干第一种生产任务时每台机器可获得利润10，干第二种生产任务时每台机器可获利润7，问应怎样分配使用机器以使四期的
31、总利润最大（期未剩下的完好机器数量不限）？解：1、首先建立动态规划模型。（1）问题划分为四个阶段K=1，2，3，4；（2）状态变量sk表示第k阶段初可用于分配的机器数，且s1=100（3）决策变量xk表示第k阶段分配于干第一种任务的机器数，则干第二种任务的机器数为sk-xk28第28页，此课件共52页哦（4）状态转移方程sk+1=2/3xk+9/10（sk-xk）=9/10sk-7/30 xk,（5）阶段指标表示第k期的利润V(sk,xk)=10 xk+7（sk-xk）=3xk+7sk（6）基本方程为：2、用逆序算法求解（见习题集、用逆序算法求解（见习题集P104）当当K=4时，根据基本递推方
32、程时，根据基本递推方程最优解为最优解为x4*=s4,f4(s4)=10s429第29页，此课件共52页哦当当K=3时，时，最优解为最优解为x3*=s3,f3(s3)=50s3/3当当K=2时，时，最优解为最优解为x2*=0,f2(s2)=22s230第30页，此课件共52页哦P106案例案例3 某厂在未来3个月连续生产某种产品。每月初开始生产，月产量为x，生产成本为x2，库存费为每月每单位1元。假如3个月的需求量预测为：b1=100,b2=110,b3=120，且初始存货s0=0，第三个月的期未存货s3=0，问应如何安排生产使总成本最小？当当K=1时，时，最优解为最优解为x1*=0,f1(s1
33、)=134s1/5=2680逆顺序回推，得逆顺序回推，得x1*=0，s1=100 x2*=0，s2=9s1/10-7x1*/30=90 x3*=s3=81，s3=9s2/10-7x2*/30=81x4*=s4=54，s4=9 s3/10-7x3*/30=5431第31页，此课件共52页哦解法解法1：建立用逆序算法求解的动态规划模型建立用逆序算法求解的动态规划模型（1）阶段：）阶段：K=1，2，3（2）状态变量：）状态变量：SK表示第表示第K月初的库存，且已知月初的库存，且已知S1=0，S4=0（3）决策变量：）决策变量：XK表示第表示第K月的生产量月的生产量（4）状态转移方程：）状态转移方程：
34、Sk+1=Sk+Xk-bk，表示第，表示第K+1月初的库存等于第月初的库存等于第K月的库存加上该月的生产量再减去该月的需求量。月的库存加上该月的生产量再减去该月的需求量。（5）指标函数：）指标函数：Vk(Sk,Xk)=Xk2+Sk，表示第表示第K月的总费用（生产成月的总费用（生产成本加上库存费）本加上库存费）（6）基本递推方程：）基本递推方程：可用逆序得法进行求解。可用逆序得法进行求解。32第32页，此课件共52页哦解法解法2：建立用顺序算法求解的动态规划模型建立用顺序算法求解的动态规划模型（1）阶段：）阶段：K=1，2，3（2）状态变量：）状态变量：SK表示第表示第K月末的库存，且已知月末的
35、库存，且已知S0=0，S3=0（3）决策变量：）决策变量：XK表示第表示第K月的生产量月的生产量（4）状态转移方程：）状态转移方程：Sk-1=Sk-Xk+bk，表示第，表示第K-1月初的库存等于第月初的库存等于第K月的库存减去该月的生产量再加上该月的需求量。月的库存减去该月的生产量再加上该月的需求量。（5）指标函数：）指标函数：Vk(Sk,Xk)=Xk2+Sk，表示第表示第K月的总费用（生产成本月的总费用（生产成本加上库存费）加上库存费）（6）基本递推方程：）基本递推方程：可用顺序得法进行求解，详细求解过程见课本可用顺序得法进行求解，详细求解过程见课本P106。33第33页，此课件共52页哦当
36、K=1 时当K=2 时利用微分求极值的方法利用微分求极值的方法,得得34第34页，此课件共52页哦当K=3 时利用微分求极值的方法利用微分求极值的方法,得得按计算顺序反推按计算顺序反推,得最优解为得最优解为:35第35页，此课件共52页哦案例案例3（生产存贮问题）某工厂与购货单位签订的供货合同如下表。该厂每月最大产量为4百件，仓库的存货能力为3百件。已知每一百件货物的生产费为一万元。在生产的月份，每批产品的生产准备费为4千元，仓库保管费为每一百件货物每月一千元。假定1月初开始时及6月底交货后仓库中都无存货。问该厂应该如何安排每月的生产与库存，才能既满足交货合同的要求，又使总费用最小？月份123
37、456交货量（百件）125321解：1、建立动态规划模型（1）阶段划分：k=1，2，3，4，5，6（2）状态变量sk表示第k月初的库存量，s1=0（3）决策变量dk表示第k月的计划生产量 表示第月的合同交货量36第36页，此课件共52页哦（4）状态转移方程：（5）第k月的总费用包括生产费和库存费（6）基本递推方程2、用逆序算法求解当k=6时，s6+d6-1=s7=0,所以 s6+d6=1 f6(s6)=minv6(s6,d6)当s6=0,d6=1,f6(s6)=14 当s6=1,d6=0,f6(s6)=137第37页，此课件共52页哦当k=5时，s5+d5-2=s6,所以 请对照课本P108表
38、4.6结果。38第38页，此课件共52页哦当k=4时，s4+d4-3=s5,所以 39第39页，此课件共52页哦求解结果对照课本P108表4.7结果。余下求解结果参看课本P108，所求最优决策结果如下表：月初存货量 sk最优生产量 dk月底存货量 sk+104130214503303210140第40页，此课件共52页哦案例案例4 （背包问题）某工厂生产三种产品，各种产品重量与利润的关系下表所示。现将此三种产品运往市场出售，运输能力总重量不超过6吨，问如何安排使运输总利润最大？种类重量（吨/件）利润（元/件）12802418033130解：其实本例是一个整数规划问题，其整数规划模型如下但是由于
39、整数规划的求解需用分枝定界法求解，计算量非常大，因而在此我们选用动态规划方法来解。41第41页，此课件共52页哦1、建立动态规划模型（在此用的是逆序算法求解，与课本不同）（1）阶段划分：k=1,2,3，把装载一种产品看成一个阶段（2）状态变量sk表示第k阶段初可用于装载产品的总容量量，s1=6（3）决策变量dk表示第k阶段装载第k种货物的件数。（4）状态转移方程：其中ak表示第k种货物的单件重量（6）基本递推方程（5）指标函数：vk(sk,dk)表示装载第k种货物dk件所得的利润，即v1(s1,d1)=80d1,v2(s2,d2)=180d2,v3(s3,d3)=130d342第42页，此课件
40、共52页哦2、用逆序法求解。其结果如下表s3d3f3(s3)d3*000*01000200030101301401013015010130160120130260*243第43页，此课件共52页哦其计算结果如下表s2d2s3f3(s3)f2(s2)d2*00000010100020200030313013014014013000+130180+0*1501511301800+130180+01601622601800+260*180+0044第44页，此课件共52页哦其计算结果如下表s1d1s2f2(s2)f1(s1)d1*601236420260180000+260*80+180*160+0
41、240+001按计算次序反推，得到最优解有两个：（1）x1=0,x2=0,x3=2；（2）x1=1,x2=1,x3=0；45第45页，此课件共52页哦案例案例5（一维资源分配问题）某公司拟将3千万元资金用于改造扩建所属的3个工厂，每个工厂的利润增长额与所分配到的投资额有关。各工厂在获得不同的投资额时所能增加的利润如下表。问应如何分配这些资金，使公司总的利润增长额最大？投资工厂0102030102.541020358.530269解：这是一个静态问题，通过将对三个工厂的投资看成三个阶段化为一个多阶段的动态问题。1、建立动态规划模型（1）阶段划分：k=1,2,3，把对每个工厂的投资看成一个阶段（2
42、）状态变量sk表示第k阶段初可用于投资的投资总额，s1=346第46页，此课件共52页哦（3）决策变量dk表示第k阶段对第k个工厂的投资额。（4）状态转移方程：（5）阶段指标vk(sk,dk)表示对k第个工厂投资dk后所增加的利润，其值为表中数据。（6）基本递推方程2、用逆序算法求解。47第47页，此课件共52页哦其计算结果见下表：s30123f3(s3)0269d*3012348第48页，此课件共52页哦s2d2s3f3(s3)f2(s2)d2*00000+0010110200+2=23+0=3120122106200+6=63+2=55+0=5030123321096200+9=93+6=
43、95+2=78.5+0=8.50,1其计算结果见下表：49第49页，此课件共52页哦其计算结果见下表：s1d1s2f2(s2)f1(s1)d1*30123321096300+9=92.5+6=8.54+3=710+0=103所求最优解为d1=3，d2=0，d3=0，公司总的最大利润增长额为期10千万元。50第50页，此课件共52页哦案例案例6、设备更新问题、设备更新问题 在已知一台设备的效益函数r(i)，维修费用函数u(i)及更新费用函数C(i)条件下，在n年内，每年年初作出决策，是继续使用旧设备还是更换一台新设备，使n年总效益最大的这类问题称为设备更新问题。设rk(i)表示在第k年设备已使用
44、i年（或称役令为i年的设备），再使用1年产生的效益：uk(i)表示在第k年设备役令为i年，再使用1年的维修费用；Ck(i)表示在第k年卖掉一台役令为i的设备，买进一台新设备的更新净费用(即新设备的购买费-旧设备折旧费）。P112例题：设某企业在今后4年内需用一辆卡车，现有一辆已使用了2年的旧车，根据统计资料分析，预计卡车的年收入、年维修费（包括油料费）、一次性更新重置费及4年后的残值如下表：51第51页，此课件共52页哦（1）阶段划分：卡车使用的每一年作为一个阶段，k=1,2,3,4（2）状态变量sk：表示设备的役龄。即在第k年初，设备已使用的年限数。s1=2,s2=1,3,s3=1,2,4,s4=1,2,3,5,s5=1,2,3,4,6（3）决策变量dk：表示在第k年初对役龄为sk的设备的决策，是更新，还是继续使用，即i0123456rk(i)161411852-vk(i)122344-ck(i)-1821252934-t5(i)-15128300试确定4年中的最优更新计划，以使总利润最大？1、建立动态规划模型52第52页，此课件共52页哦