第9章-动态规划课件.ppt
第第9章章 动态规划动态规划RUC,Information School,Ye Xiang实用运筹学实用运筹学运用运用ExcelExcel建模和求解建模和求解第第9 9章章动态规划动态规划Dynamic ProgrammingDynamic Programming第第9章章 动态规划动态规划RUC,Information School,Ye Xiang本章内容要点本章内容要点动态规划基本概念动态规划基本概念各种动态规划问题各种动态规划问题建模与应用建模与应用第第9章章 动态规划动态规划RUC,Information School,Ye Xiang本章节内容本章节内容9.1 9.1 背包问题背包问题9.2 9.2 生产经营问题生产经营问题9.3 9.3 资金管理问题资金管理问题9.4 9.4 资源分配问题资源分配问题第第9章章 动态规划动态规划RUC,Information School,Ye Xiang本章主要内容框架图本章主要内容框架图第第9章章 动态规划动态规划RUC,Information School,Ye Xiang动态规划问题的提出动态规划问题的提出u动动态态规规划划是是解解决决多多阶阶段段决决策策过过程程最最优优化化问问题题的的一一种种方方法法。该该方方法法是是由由美美国国数数学学家家贝贝尔尔曼曼(R R BellmanBellman)等等人人在在2020世世纪纪5050年年代代初初提提出出的的。他他们们针针对对多多阶阶段段决决策策问问题题的的特特点点，提提出出了了解解决决这这类类问问题题的的“最最优优化化原原理理”，并并成成功功地地解解决决了了生生产产管管理理、工工程程技技术术等等方方面面的的许许多多实实际际问问题题，从从而而建建立立了了运运筹筹学学的的一一个个新分支，即新分支，即动态规划动态规划。第第9章章 动态规划动态规划RUC,Information School,Ye Xiang动态规划问题的提出动态规划问题的提出u在在实实际际的的决决策策过过程程中中，由由于于涉涉及及的的参参数数比比较较多多，往往往往需需要要将将问问题题分分成成若若干干个个阶阶段段，对对不不同同阶阶段段采采取取不同的决策，从而使整个决策过程达到最优不同的决策，从而使整个决策过程达到最优。u显显然然，由由于于各各个个阶阶段段选选择择的的策策略略不不同同，对对应应的的整整个过程就可以有一系列不同的策略。个过程就可以有一系列不同的策略。u动动态态规规划划是是解解决决多多阶阶段段决决策策过过程程最最优优化化的的一一种种方方法法。这这种种方方法法把把困困难难的的多多阶阶段段决决策策问问题题变变换换成成一一系系列列互互相相联联系系的的比比较较容容易易的的单单阶阶段段问问题题，解解决决了了这这一一系系列列比比较较容容易易的的单单阶阶段段问问题题，也也就就解解决决了了困困难难的的多多阶段决策问题。阶段决策问题。u有有时时阶阶段段可可以以用用时时间间表表示示，在在各各个个时时间间段段，采采用用不不同同决决策策，它它随随时时间间而而变变动动，这这就就有有“动动态态”的的含含意意第第9章章 动态规划动态规划RUC,Information School,Ye Xiang动态规划问题的提出动态规划问题的提出u动动态态规规划划是是现现代代企企业业管管理理中中的的一一个个重重要决策方法。要决策方法。u本本章章利利用用微微软软ExcelExcel软软件件在在“公公式式”和和“规规划划求求解解工工具具”两两方方面面的的强强大大功功能能，对对背背包包问问题题、生生产产经经营营问问题题、资资金金管管理理问问题题和和资资源源分分配配问问题题等等进进行行分分析析、建建模模与与求求解解，解解决决了了实实际际经经营营中中的的优优化化问问题题，迅迅速速准准确确地地得得出出决决策策结结果。果。第第9章章 动态规划动态规划RUC,Information School,Ye Xiang9.1 9.1 背包问题背包问题u背背包包问问题题可可以以抽抽象象为为这这样样一一类类问问题题：设设有有n n种种物物品品，每每种种物物品品有有其其重重量量及及价价值值。同同时时有有一一个个背背包包，最最大大装装重重为为c c，现现从从n n种种物物品品中中选选取取若若干干件件（同同一一种种物物品品可可以以选选多多件件），使使其其总总重重量量小小于于等等于于c c，而而总总价价值值最大。最大。u背背包包问问题题等等同同于于车车、船船、人人造造卫卫星星等等工工具的最优装载问题，有广泛的实际意义具的最优装载问题，有广泛的实际意义。第第9章章 动态规划动态规划RUC,Information School,Ye Xiang9.1.1 9.1.1 一维背包问题一维背包问题例例9.19.1 某某货货运运公公司司使使用用一一种种最最大大承承载载能能力力为为1010吨吨的的卡卡车车来来装装载载3 3种种货货物物，每每种种货货物物的的重重量量及及价价值值如如表表9-19-1所所示示。应应当当如如何何装载货物才能使总价值最大？装载货物才能使总价值最大？货物货物编号编号1 1 2 2 3 3单位单位重量重量(吨吨)3 3 4 4 5 5单位单位价值价值(百元百元)4 4 5 5 6 6用用ExcelExcel求解背包问题时，采用的是求解背包问题时，采用的是整数规划整数规划的方法。的方法。第第9章章 动态规划动态规划RUC,Information School,Ye Xiang9.1.2 9.1.2 多维背包问题多维背包问题u当当约约束束条条件件不不仅仅有有货货物物的的重重量量，还还有有体体积积等等限制时，构成了限制时，构成了多维背包问题多维背包问题。u例例9.29.2 现现有有一一辆辆载载重重为为5 5吨吨，装装载载体体积积8 8立立方方米米的的卡卡车车，可可装装载载三三种种货货物物，已已知知每每种种货货物物各各8 8件件，其其它它有有关关信信息息如如表表9-29-2所所示示，求求携携带带货物价值最大的装载方案。货物价值最大的装载方案。货物品种货物品种单位重量单位重量(吨吨)单位体积单位体积(立方米立方米)单位价值单位价值(千元千元)1 10.20.20.30.33 32 20.40.40.50.57.57.53 30.30.30.40.46 6第第9章章 动态规划动态规划RUC,Information School,Ye Xiang补充补充：背包问题：背包问题（容量一定的背包里装尽可能多的物品）（容量一定的背包里装尽可能多的物品）u某某人人出出国国留留学学打打点点行行李李，现现有有三三个个旅旅行行包包，容容积积大大小小分分别别为为10001000、15001500和和20002000，根根据据需需要要列列出出需需带带物物品品清清单单，其其中中一一些些物物品品是是必必带带物物品品，共共有有7 7件件，其其体体积积大大小小分分别别为为400400、300300、150150、250250、450450、760760、190190。尚尚有有1010件件可可带带可可不不带带物物品品，如如果果不不带带将将在在目目的的地地购购买买，通通过过网网络络查查询询可可以以得得知知其其在在目目的的地地的的价价格格（美美元元）。这这些些物物品品的的容容量量及及价价格格分分别别见见下下表表，试试给给出出一一个个合合理理的的安安排排方方案案，把把物物品品放放在在三三个个旅旅行行包包里。里。物品物品12345678910体积体积200350500430320120700420250100价格价格1545100705075200902030第第9章章 动态规划动态规划RUC,Information School,Ye Xiang补充补充：背包问题：背包问题（容量一定的背包里装尽可能多的物品）（容量一定的背包里装尽可能多的物品）u决决策策变变量量：对对每每个个物物品品要要确确定定是是否否带带的的同同时时，还还要要确确定定放放在在哪哪个个包包里里（如如果果增增加加一一个个虚虚拟拟包包，把把不不带带的的物物品品放放在在里里面面，则则问问题题就就转转化化为为确确定定每每个个物物品品放放在在哪哪个个包包里里。这这里里的的数数学学模型和电子表格模型没有用虚拟包模型和电子表格模型没有用虚拟包）。）。u因因此此可可设设决决策策变变量量为为第第i i个个物物品品是是否否放放在在第第j j个包中（个包中（1-1-放，放，0-0-不放）。不放）。第第9章章 动态规划动态规划RUC,Information School,Ye Xiang补充补充：背包问题：背包问题（容量一定的背包里装尽可能多的物品）（容量一定的背包里装尽可能多的物品）u约束条件约束条件包的容量限制包的容量限制必带物品限制必带物品限制选带物品限制选带物品限制0-1变量：变量：u目标函数：未带物品购买费用最小目标函数：未带物品购买费用最小 第第9章章 动态规划动态规划RUC,Information School,Ye Xiang补充补充：背包问题：背包问题（容量一定的背包里装尽可能多的物品）（容量一定的背包里装尽可能多的物品）uExcelExcel求解结果为：求解结果为：包包1 1放放3 3件件 物品物品1 物品物品3物品物品5包包2 2放放5件件 物品物品4物品物品10 物品物品13 物品物品15 物品物品17包包3 3放放4件件 物品物品2物品物品6物品物品7物品物品14没有放没有放5件件 物品物品8物品物品9物品物品11 物品物品12 物品物品16未带物品购买费用为未带物品购买费用为200美元美元第第9章章 动态规划动态规划RUC,Information School,Ye Xiang9.2 9.2 生产经营问题生产经营问题u在在生生产产和和经经营营中中，经经常常遇遇到到如如何何合合理理安安排排生生产产计计划划、采采购购计计划划以以及及库库存存计计划划和和销销售售计计划划等等问问题题，要要求求既既要要满满足足市市场场的的需需要要，又又要要尽尽量量降降低低成成本本费费用用。因因此此，正正确确制制定定生生产产（或或采采购购）策策略略，确确定定不不同同时时期期的的生生产产量量（或或采采购购量量）、销销售售量量和和库库存存量量，在在满满足足产产品品需需求求量量的的条条件件下下，使使得得总总收收益益最最大大或或总总成成本本（生生产产成成本本存存储储成成本本）最最小小，这这就就是是生生产产经经营营问问题题，包包括括生生产产与与存存储储问问题题、采采购购与与销售问题销售问题等。等。第第9章章 动态规划动态规划RUC,Information School,Ye Xiang9.2.1 9.2.1 生产与存贮问题生产与存贮问题例例9.39.3 某某皮皮鞋鞋公公司司根根据据对对去去年年的的市市场场需需求求分分析析预预测测明明年年的的需需求求：一一季季度度30003000双双，二二季季度度40004000双双，三三季季度度80008000双双、四四季季度度70007000双双。企企业业现现在在每每个个季季度度最最多多可可以以生生产产60006000双双皮皮鞋鞋。为为了了满满足足所所有有的的预预测测需需求求，前前两两个个季季度度必必须须有有一一定定的的库库存存才才能能满满足足后后两两个个季季度度的的需需求求。已已知知每每双双皮皮鞋鞋的的利利润润为为2020元元，每每个个季季度度的的库库存存成成本本8 8元元。请请确确定定该该公公司司明明年年每每个个季季度度的的生生产产计计划划，使使公公司司的的年年利利润润最大。最大。第第9章章 动态规划动态规划RUC,Information School,Ye Xiang9.2.1 9.2.1 生产与存贮问题生产与存贮问题解解：明明年年市市场场总总需需求求为为300030004000400080008000700070002200022000双双，而而最最多多可可生生产产4 4600060002400024000双，所以皮鞋公司可以满足市场总需求。双，所以皮鞋公司可以满足市场总需求。(1)(1)决策变量决策变量 本本问问题题是是要要确确定定该该公公司司明明年年每每个个季季度度的的生生产产计划，所以设计划，所以设 公公司司每每个个季季度度生生产产xi（i i1,2,3,41,2,3,4）双双皮皮鞋鞋；还还有有，设设辅辅助助决决策策变变量量：每每个个季季度度的的期期末末库库存存为为si（i i1,2,3,41,2,3,4）双皮鞋。）双皮鞋。第第9章章 动态规划动态规划RUC,Information School,Ye Xiang9.2.1 9.2.1 生产与存贮问题生产与存贮问题(2)(2)目标函数目标函数 本本问问题题的的目目标标是是公公司的年利润最大。司的年利润最大。(3)(3)约束条件约束条件满满足足每每个个季季度度的的需需求求（本本季季度度的的库库存存上上季季度度库库存存本本季季度度生生产产本季度市场需求本季度市场需求）每季度的生产力限制每季度的生产力限制非负非负第第9章章 动态规划动态规划RUC,Information School,Ye Xiang9.2.1 9.2.1 生产与存贮问题生产与存贮问题例例9.39.3的电子表格模型的电子表格模型第第9章章 动态规划动态规划RUC,Information School,Ye Xiang9.2.1 9.2.1 生产与存贮问题生产与存贮问题例例9.49.4 某某毛毛毯毯厂厂是是一一个个小小型型的的生生产产商商，致致力力于于生生产产家家用用和和办办公公用用的的毛毛毯毯。紧紧接接的的4 4个个季季度度的的生生产产能能力力、市市场场需需求求、每每平平方方米米的的生生产产成成本本以以及及库库存存成成本本如如表表9-9-3 3所所示示。毛毛毯毯厂厂需需要要确确定定在在这这4 4个个季季度度里里每每季季度度生生产产多多少毛毯，才能使总生产和库存成本最小。少毛毯，才能使总生产和库存成本最小。季度季度生产能力生产能力(平方米平方米)市场需求市场需求(平方米平方米)生产成本生产成本(元元/平方米平方米)库存成本库存成本(元元/平方米平方米)1 16006004004002 20.250.252 23003005005005 50.250.253 35005004004003 30.250.254 44004004004003 3第第9章章 动态规划动态规划RUC,Information School,Ye Xiang9.2.1 9.2.1 生产与存贮问题生产与存贮问题解解：采采用用另另外外一一种种解解法法，即即用用网网络络最最优优化化问问题题中中的的最最小小费费用用流流问问题题来来求求解解。通通过过建建立立一一个个网网络络图图来来代代表表这这个个问问题题。首首先先根根据据四四个个季季度度建建立立四四个个产产量量节节点点和和四四个个需需求求节节点点。每每个个产产量量节节点点由由一一个个流流出出弧弧连连接接对应的需求节点。对应的需求节点。33520.250.250.251季度产量2季度产量3季度产量4季度产量1季度需求2季度需求3季度需求4季度需求产量节点需求节点600300500400400500400400弧弧的的流流量量代代表表了了该该季季度度所所生生产产的的毛毛毯毯数数量量。相相对对于于每每个个需需求求节节点点，一一个个流流出出弧弧代代表表了了库库存存的的数数量量，即即供供给给下下季季度度需需求节点的数量求节点的数量第第9章章 动态规划动态规划RUC,Information School,Ye Xiang9.2.1 9.2.1 生产与存贮问题生产与存贮问题例例9.49.4数学模型数学模型（采用节点净流量）采用节点净流量）上季度库存本季度生产本季度的库存本季度市场需求上季度库存本季度生产本季度的库存本季度市场需求第第9章章 动态规划动态规划RUC,Information School,Ye Xiang9.2.1 9.2.1 生产与存贮问题生产与存贮问题例例9.49.4的电子表格模型的电子表格模型第第9章章 动态规划动态规划RUC,Information School,Ye Xiang9.2.1 9.2.1 生产与存贮问题生产与存贮问题例例9.5 9.5 某某厂厂根根据据订订货货合合同同在在今今后后四四个个季季度度对对某某产产品品的的需需求求量量如如表表9-49-4所所示示。如如果果该该季季度度生生产产，需需要要生生产产准准备备费费用用为为3 3千千元元，每每件件产产品品的的生生产产成成本本为为1 1千千元元，由由于于生生产产能能力力的的限限制制，每每季季度度最最多多不不超超过过6 6件件。又又设设每每一一件件产产品品存存贮贮一一个个季季度度的的费费用用为为0.50.5千千元元，并并且且第第一一季季度度开开始始与第四季度末均没有产品库存。与第四季度末均没有产品库存。要要求求在在上上述述条条件件下下该该厂厂应应该该如如何何安安排排各各季度的生产与库存，以使总费用季度的生产与库存，以使总费用最低？最低？季度季度1 12 23 34 4需求量需求量2 23 32 24 4第第9章章 动态规划动态规划RUC,Information School,Ye Xiang9.2.1 9.2.1 生产与存贮问题生产与存贮问题解解：根根据据题题意意，对对于于每每个个季季度度来来说说，可可知知当当生生产产x（00“5 5”，还还是是有有解解，只只是是生生产产方方案案不不同同而而已，读者可以在已，读者可以在ExcelExcel中尝试中尝试)。在在第第3 3次次及及以以后后印印刷刷的的，约约束束改改为为“”，则比较容易满足，则比较容易满足。第第9章章 动态规划动态规划RUC,Information School,Ye Xiang上机上机实验九实验九 动态规划动态规划（）实验目的：用（）实验目的：用Excel软件求解动态规划中的生产软件求解动态规划中的生产经营问题、资金管理问题等，掌握其建模和求解方法。经营问题、资金管理问题等，掌握其建模和求解方法。（二）内容和要求：求解（二）内容和要求：求解习题习题9.5、9.10、9.18、9.21、案例、案例8、案例、案例9（或案例（或案例10）。（三）操作步骤：（三）操作步骤：（1）建立电子表格模型；）建立电子表格模型；（2）使用）使用Excel规划求解工具求解动态规划问题；规划求解工具求解动态规划问题；（3）结果分析；）结果分析；（4）在）在Excel或或Word文档中写实验报告，包括动态规划数文档中写实验报告，包括动态规划数学模型（手写）、电子表格模型和结果分析等。学模型（手写）、电子表格模型和结果分析等。
