Pyth基础及其求解 3

实用运筹学

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

Bellman)等人在20世纪50年代初提出的。他们针对多阶段决策问题的特点，提出了解决这类问题的“最优化原理”，并成功地解决了生产管理、工程技术等方面的许多实际问题，从而建立了运筹学的一个新分支，即动态规划。动态规划的基本概念在实际决策过程中，由于涉及的参数比较多，往往需要将问题分成若干个阶段，对不同阶段采取不同的决策，从而使整个决策过程达到最优。显然，由于各个阶段选择的策略不同，整个过程就可以有一系列不同的策略。动态规划把困难的多阶段决策问题变换成一系列互相联系的比较容易的单阶段问题，解决了这一系列比较容易的单阶段问题，也就解决了困难的多阶段决策问题。有时阶段可以用时间表示，在各个时间段，采用不同的决策，它随时间而变化，就有了“动态”的含义。动态规划的基本概念动态规划是现代企业管理中一种重要的决策方法。本章利用Python的pulp库，对生产与存储问题、订购与销售问题、餐巾供应问题、资源分配问题等进行分析、建模和求解，解决实际经营管理中的优化问题。动态规划也适用于人生规划，它是人类智慧的体现。“千里之行，始于足下”，完成任何一项伟大的事业总是从小事做起的，小目标的达成是实现大目标的基础。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生产与存储问题利用Python求解例6-1利用pulp库求解代码框6-1例6-1.ipynb最优解（最优生产与存储方案）：四个季度生产皮鞋数量：4000600060006000四个季度的期末库存量：1000300010000最优目标值（总利润最大）：400000

其中，销售总利润：440000

库存总成本：400006.1生产与存储问题例6-2

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

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

其中，生产总成本：510000

库存总成本：50006.1生产与存储问题例6-3

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

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

引入隐性0-1变量：yi为第i季度是否生产。6.1生产与存储问题（2）目标函数总费用最小。（3）约束条件①对于每个季度来说，本季度期末库存＝上季度期末库存＋本季度生产－本季度需求②生产能力限制③第四季度结束时没有产品库存④非负⑤隐性0-1变量6.1生产与存储问题利用Python求解例6-3利用pulp库求解代码框6-3例6-3.ipynb最优解（最优生产与存储方案）： 是否生产产量期末库存量一季度153二季度000三季度164四季度000最优目标值（总成本最小）：20.5其中，总准备费用：6

总生产成本：11

总存贮费用：3.56.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订购与销售问题利用Python求解例6-4利用pulp库求解代码框6-4例6-4.ipynb最优解（最优策略）：1－4月月初库存：5000100010001－4月的销售量：5000100010001－4月的订货量：0100010000最优目标值（总获利最大）：16000

其中，总销售收入：36000

总订货成本：200006.3餐巾供应问题例6-5

某饭店宴席部预计一周内每天接待的客人数如表6-8所示。规定每位客人每天用餐巾一条。所用餐巾可购买新的，每条成本6元，或者用已经洗净的餐巾。附近有两家洗衣店：甲店洗净一条餐巾收费3元，隔一天送回；乙店洗净一条餐巾收费2元，隔两天送回。假定每周开始时没有旧餐巾。问饭店后勤部应如何安排每天餐巾的供应，才能使总成本（费用）最小？星期一二三四五六日客人数1001201401601401802006.3餐巾供应问题例6-5的线性规划模型P219-2206.3餐巾供应问题利用Python求解例6-5利用pulp库求解代码框6-5例6-5.ipynb最优供应方案（一周各天餐巾的供应情况）：

星期一：新购、送去甲店、送去乙店、未送：10001000

星期二：新购、送去甲店、送去乙店、未送：12001200

星期三：新购、送去甲店、送去乙店、未送：140201200

星期四：新购、送去甲店、送去乙店、未送：60601000

星期五：新购、送去甲店、未送：010040

星期六：新购、未送：0220

星期日：新购、未送：0420

新购买的餐巾数（合计）：420

甲店送回餐巾数（合计）：180

乙店送回餐巾数（合计）：440最优目标值（总费用最小）：39406.4资源分配问题资源分配问题是将数量一定的若干种资源（例如原材料、资金、机器设备、劳动力等）合理地分配给若干使用者，使总收益最大。资源的多元分配问题资源的多段分配问题6.4.1资源的多元分配问题例6-6

某公司拟将500万元资金投放给下属的A、B、C三个企业，各企业获得资金后的收益如表6-11所示。求总收益最大的投资分配方案。投资收益企业A企业B企业C120122123323434453756.4.1资源的多元分配问题【解】用类似于指派问题（分派问题）的求解方法。决策变量为：决策变量6.4.1资源的多元分配问题例6-6的0-1规划模型6.4.1资源的多元分配问题利用Python求解例6-6利用pulp库求解代码框6-6例6-6.ipynb最优解（最优投资分配方案）： 向企业A投资：0

向企业B投资：5

向企业C投资：0最优目标值（总收益最大）：76.4.2资源的多段分配问题例6-7

某厂现有100台机床，能够加工2种零件，要安排1-4月的任务，根据以往的经验，这些机床用来加工第1种零件时，1个月后损坏率为1/3。而用来加工第2种零件时，1个月后损坏率为1/10。又知道，每台机床加工