第9章 动态规划ppt课件.ppt

《第9章 动态规划ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、实用运筹学－运用Excel建模和求解第9章动态规划本章内容要点动态规划基本概念各种动态规划问题建模与应用本章节内容9.1背包问题9.2生产经营问题9.3资金管理问题9.4资源分配问题本章主要内容框架图动态规划问题的提出动态规划是解决多阶段决策过程最优化问题的一种方法。该方法是由美国数学家贝尔曼(R.Bellman)等人在20世纪50年代初提出的。他们针对多阶段决策问题的特点，提出了解决这类问题的“最优化原理”，并成功地解决了生产管理、工程技术等方面的许多实际问题，从而建立了运筹学的一个新分支，即动态规

2、划。动态规划问题的提出在实际的决策过程中，由于涉及的参数比较多，往往需要将问题分成若干个阶段，对不同阶段采取不同的决策，从而使整个决策过程达到最优。显然，由于各个阶段选择的策略不同，对应的整个过程就可以有一系列不同的策略。动态规划是解决多阶段决策过程最优化的一种方法。这种方法把困难的多阶段决策问题变换成一系列互相联系的比较容易的单阶段问题，解决了这一系列比较容易的单阶段问题，也就解决了困难的多阶段决策问题。有时阶段可以用时间表示，在各个时间段，采用不同决策，它随时间而变动，这就有“动态”的含意。动态规划

3、问题的提出动态规划是现代企业管理中的一个重要决策方法。本章利用微软Excel软件在“公式”和“规划求解”两方面的强大功能，对背包问题、生产经营问题、资金管理问题和资源分配问题等进行分析、建模与求解，解决了实际经营中的优化问题，迅速准确地得出决策结果。9.1背包问题背包问题可以抽象为这样一类问题：设有n种物品，每种物品有其重量及价值。同时有一个背包，最大装重为c，现从n种物品中选取若干件（同一种物品可以选多件），使其总重量小于等于c，而总价值最大。背包问题等同于车、船、人造卫星等工具的最优装载问题，有广泛

4、的实际意义。9.1.1一维背包问题例9.1某货运公司使用一种最大承载能力为10吨的卡车来装载3种货物，每种货物的重量及价值如表9-1所示。应当如何装载货物才能使总价值最大？货物编号123单位重量(吨)345单位价值(百元)456用Excel求解背包问题时，采用的是整数规划的方法。9.1.2多维背包问题当约束条件不仅有货物的重量，还有体积等限制时，构成了多维背包问题。例9.2现有一辆载重为5吨，装载体积8立方米的卡车，可装载三种货物，已知每种货物各8件，其它有关信息如表9-2所示，求携带货物价值最大的装载

5、方案。货物品种单位重量(吨)单位体积(立方米)单位价值(千元)10.20.3320.40.57.530.30.469.2生产经营问题在生产和经营中，经常遇到如何合理安排生产计划、采购计划以及库存计划和销售计划等问题，要求既要满足市场的需要，又要尽量降低成本费用。因此，正确制定生产（或采购）策略，确定不同时期的生产量（或采购量）、销售量和库存量，在满足产品需求量的条件下，使得总收益最大或总成本（生产成本＋存储成本）最小，这就是生产经营问题，包括生产与存储问题、采购与销售问题等。9.2.1生产与存贮问题例9

6、.3某皮鞋公司根据对去年的市场需求分析预测明年的需求：一季度3000双，二季度4000双，三季度8000双、四季度7000双。企业现在每个季度最多可以生产6000双皮鞋。为了满足所有的预测需求，前两个季度必须有一定的库存才能满足后两个季度的需求。已知每双皮鞋的利润为20元，每个季度的库存成本8元。请确定该公司明年每个季度的生产计划，使公司的年利润最大。9.2.1生产与存贮问题解：明年市场总需求为3000＋4000＋8000＋7000＝22000双，而最多可生产4×6000＝24000双，所以皮鞋公司可以

7、满足市场总需求。(1)决策变量本问题是要确定该公司明年每个季度的生产计划，所以设公司每个季度生产xi（i＝1,2,3,4）双皮鞋；还有，设辅助决策变量：每个季度的期末库存为si（i＝1,2,3,4）。9.2.1生产与存贮问题(2)目标函数本问题的目标是公司的年利润最大。(3)约束条件①满足每个季度的需求（本季度的库存＝上季度库存＋本季度生产－本季度市场需求）②每季度的生产力限制③非负9.2.1生产与存贮问题例9.3的电子表格模型9.2.1生产与存贮问题例9.4某毛毯厂是一个小型的生产商，致力于生产家用和

8、办公用的毛毯。紧接的4个季度的生产能力、市场需求、每平方米的生产成本以及库存成本如表9-3所示。毛毯厂需要确定在这4个季度里每季度生产多少毛毯，才能使总生产和库存成本最小。季度生产能力(平方米)市场需求(平方米)生产成本(元/平方米)库存成本(元/平方米)160040020.25230050050.25350040030.25440040039.2.1生产与存贮问题解：采用另外一种解法，即用网络最优化问题中的最小费用流问题来求解。通过建立一