《运筹学（第3版）》 课件 第6章 动态规划

实用运筹学

－－运用Excel建模和求解（第3版）第6章动态规划DynamicProgramming本章内容要点动态规划的基本概念生产与存储问题订购与销售问题餐巾供应问题资源分配问题本章主要内容框架图动态规划的基本概念动态规划是解决多阶段决策过程的最优化问题的一种方法。该方法是由美国数学家贝尔曼(R

Bellman)等人在20世纪50年代初提出的。他们针对多阶段决策问题的特点，提出了解决这类问题的“最优化原理”，并成功地解决了生产管理、工程技术等方面的许多实际问题，从而建立了运筹学的一个新分支，即动态规划。动态规划的基本概念在实际决策过程中，由于涉及的参数比较多，往往需要将问题分成若干个阶段，对不同阶段采取不同的决策，从而使整个决策过程达到最优。显然，由于各个阶段选择的策略不同，对应的整个过程就可以有一系列不同的策略。动态规划把困难的多阶段决策问题变换成一系列互相联系的比较容易的单阶段问题，解决了这一系列比较容易的单阶段问题，也就解决了困难的多阶段决策问题。有时阶段可以用时间表示，在各个时间段，采用不同的决策，它随时间而变化，就有了“动态”的含义。动态规划的基本概念动态规划是现代企业管理中一种重要的决策方法。本章利用微软Excel软件在“公式”和“规划求解”两方面的强大功能，对生产与存储问题、订购与销售问题、餐巾供应问题、资源分配问题等进行分析、建模和求解，解决实际经营管理中的优化问题。动态规划也适用于人生规划，它是人类智慧的体现。“千里之行，始于足下”，完成任何一项伟大的事业总是从小事做起的，小目标的达成是实现大目标的基础。6.1生产与存储问题在生产和经营管理中，经常会遇到如何合理安排生产与库存的问题，要求既要满足市场需要，又要尽量降低成本。因此，合理制订生产策略，确定不同时期的生产量和库存量，在满足产品需求量的条件下，可使得总收益最大或总成本（生产成本＋库存成本）最小。例6-1

某皮鞋公司根据去年的市场需求分析预测今年的需求：第一季度3000双、第二季度4000双、第三季度8000双、第四季度7000双。企业现在每个季度最多可以生产6000双皮鞋。为了满足所有的预测需求，前两个季度必须有一定的库存才能满足后两个季度的需求。已知每双皮鞋的销售利润为20元，每个季度的库存成本为8元。请制订该公司今年每个季度的生产计划，以使公司的年利润最大。6.1生产与存储问题【解】今年市场总需求量为3000＋4000＋8000＋7000＝22000（双），而该公司最多可生产4×6000＝24000（双），所以该公司可以满足市场总需求。（1）决策变量本问题是要制订该公司今年每个季度的生产计划，所以设公司四个季度生产的皮鞋数量分别为x1，x2，x3，x4（双）；四个季度皮鞋的期末库存量分别为s1，s2，s3，s4（双）。6.1生产与存储问题（2）目标函数

公司的年利润最大。（3）约束条件①满足每个季度的需求本季度期末库存＝上季度期末库存＋本季度生产－本季度市场需求（状态转移方程）②每季度的生产力限制③非负6.1生产与存储问题例6-1的电子表格模型6.1生产与存储问题例6-2

某毛毯厂是一个小型生产商，致力于生产家用和办公用的毛毯。四个季度的生产能力、市场需求、每平方米的生产成本以及库存成本如表6-2所示。毛毯厂需要确定每个季度生产多少毛毯，才能使总成本（生产成本和库存成本）最小。季度生产能力(平方米)市场需求(平方米)生产成本(元/平方米)库存成本(元/平方米)一60040020025二30050050025三50040030025四4004003006.1生产与存储问题【解】本问题可以用例6-1的方法来求解，即有：

本季度期末库存＝上季度期末库存＋本季度生产－本季度市场需求这里介绍另外一种解法，即用第4章介绍过的网络最优化问题中的最小费用流问题的方法来求解。通过建立一个网络模型来描述该问题。首先根据四个季度建立四个生产节点和四个需求节点。每个生产节点由一个流出弧连接对应的需求节点。弧的流量表示该季度所生产的毛毯数量。相对于每个需求节点，一个流出弧表示该季度毛毯的期末库存，即供应下一个季度需求节点的毛毯数量。300300500200252525第一季度生产第二季度生产第三季度生产第四季度生产第一季度需求第二季度需求第三季度需求第四季度需求生产节点需求节点600300500400400500400400生产能力市场需求6.1生产与存储问题例6-2的线性规划模型（需求节点的净流量）上季度期末库存＋本季度生产－本季度期末库存＝本季度市场需求6.1生产与存储问题例6-2的电子表格模型（用例6-1的方法来求解）6.1生产与存储问题例6-2的电子表格模型（用最小费用流问题的方法来求解）6.1生产与存储问题例6-3

某厂根据订货合同进行生产，已知今后四个季度对某产品的需求量如表6-3所示。如果某个季度生产，则需要生产准备费用3万元，每件产品的生产成本为1万元。由于生产能力的限制，每个季度的产量最多不超过6件。每件产品一个季度的存储费用为5000元，并且第一季度开始时与第四季度结束时均没有产品库存。在上述条件下该厂应该如何安排各季度的生产与库存，可使总费用最少？季度一二三四需求量（件）23246.1生产与存储问题【解】本问题是一个有固定成本（生产准备费用）的生产与存储问题。（1）决策变量四个季度生产的产品数量分别为x1，x2，x3，x4。

四个季度产品的期末库存量分别为s1，s2，s3，s4。

引入隐性0-1变量：yi为第i季度是否生产（1表示生产，0表示不生产）。6.1生产与存储问题（2）目标函数总费用最少。（3）约束条件①对于每个季度来说，本季度期末库存＝上季度期末库存＋本季度生产－本季度需求②生产能力限制③第四季度结束时没有产品库存④非负⑤隐性0-1变量6.1生产与存储问题例6-3的电子表格模型6.2订购与销售问题例6-4

某商店在未来的4个月里，准备利用它的一个仓库来专门经销某种商品，仓库最多能储存这种商品1000单位。假定该商品每月只能卖仓库现有的货。当商店在某月订货时，下月初才能到货。该商品未来4个月预测的买卖价格如表6-5所示，假定商店在1月开始经销时，仓库储存有该商品500单位。试问若不计库存费用，该商店如何制订1-4月的订购与销售计划，可使预期获利最大？月份订购单价（元）销售单价（元）1月10122月983月11134月15176.2订购与销售问题【解】（1）决策变量本问题需要制订1-4月的订购与销售计划，所以设1-4月的销售量分别为x1，x2，xi，x4，1-4月的订货量分别为y1，y2，y3，y4。

还需设辅助变量：1-4月月初仓库中的存货量（月初库存）分别为s1，s2，s3，s4。（2）目标函数因为不考虑库存费用，所以要使预期获利最大，只要考虑每月的销售收入与订货成本即可。6.2订购与销售问题（3）约束条件①因为当月订货，下月初才能到货，所以该商店每月可销售的货是上月的月末库存和上月的订货，而“上月的月末库存＝上月的月初库存－上月的销售”。也就是说，本月的月初库存＝上月的月初库存－上月的销售＋上月的订货（本月到货）②仓库的容量限制③非负6.2订购与销售问题例6-4的电子表格模型6.2订购与销售问题需要说明的是：在用Excel求解有库存（或剩余量）的问题时，辅助变量“库存si”经常不用可变单元格（填充颜色为“黄底”）表示，而用输出单元格（公式，无填充颜色）来替代，但此时要求在“约束条件”中加入“库存≥0或某个值”的约束。如在图6-6中，没有“月初库存”可变单元格，而用“月初库存”输出单元格来替代。6.3餐巾供应问题例6-5

某饭店宴席部预计一周内每天接待的客人数如表6-8所示。规定每位客人每天用餐巾一条。所用餐巾可购买新的，每条成本6元，或者用已经洗净的餐巾。附近有两家洗衣店：甲店洗净一条餐巾收费3元，隔一天送回；乙店洗净一条餐巾收费2元，隔两天送回。假定每周开始时没有旧餐巾。问饭店后勤部应如何安排每天餐巾的供应，才能使总成本（费用）最小？星期一二三四五六日客人数1001201401601401802006.3餐巾供应问题例6-5的线性规划模型P195-1966.3餐巾供应问题例6-5的电子表格模型6.4资源分配问题资源分配问题是将数量一定的若干种资源（例如原材料、资金、机器设备、劳动力等），合理地分配给若干使用者，使总收益最大。资源的多元分配问题资源的多段分配问题6.4.1资源的多元分配问题例6-6

某公司拟将500万元资金投放给下属的A、B、C三个企业，各企业获得资金后的收益如表6-11所示。求总收益最大的投资分配方案。投资收益企业A企业B企业C120122123323434453756.4.1资源的多元分配问题【解】用类似于指派问题（分派问题）的求解方法。决策变量为：6.4.1资源的多元分配问题例6-6的线性规划模型为：6.4.1资源的多元分配问题例6-6的电子表格模型6.4.2资源的多段分配问题例6-7

某厂现有100台机床，能够加工2种零件，要安排1-4月的任务，根据以往的经验，这些机床用来加工第1种零件，1个月后损坏率为1/3。而用来加工第2种零件时，1个月后损坏率为1/10。又知道，每台机床加工第1种零件时每个月的收益为10万元，加工第2种零件时每个月的收益为7万元。试问：怎样分配机床，才能使总收益最大？6.4.2资源的多段分配问题例6-7的线性规划模型6.4.2资源的多段分配问题例6-7的电子表格模型本章上机实验1．实验目的