1、第第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 背包问题背包
2、问题9.2 9.2 生产经营问题生产经营问题9.3 9.3 资金管理问题资金管理问题9.4 9.4 资源分配问题资源分配问题第第9章章 动态规划动态规划RUC,Information School,Ye Xiang本章主要内容框架图本章主要内容框架图阶 段 与 阶 段 变 量基 本 概 念状 态 转 移 方 程求 出 最 优 策 略（最 优 决 策 序 列）求 解 要 求求 出 最 优 目 标 函 数 值数 学 模 型模 型 与 求 解电 子 表 格 的 建 模 与 求 解一 维 背 包 问 题背 包 问 题多 维 背 包 问 题动 态 规 划生 产 与 存 储 问 题生 产 经 营 问 题采
3、 购 与 销 售 问 题流 动 资 金 问 题应 用贷 款 问 题资 金 管 理 问 题购 买 债 券 问 题连 续 投 资 问 题资 源 的 多 元 分 配资 源 分 配 问 题资 源 的 多 段 分 配第第9章章 动态规划动态规划RUC,Information School,Ye Xiang动态规划问题的提出动态规划问题的提出u动态规划是解决多阶段决策过程最动态规划是解决多阶段决策过程最优化问题的一种方法优化问题的一种方法。该方法是由美。该方法是由美国数学家国数学家贝尔曼贝尔曼(R(R BellmanBellman)等人在等人在2020世纪世纪5050年代初提出的。他们针对年代初提出的。他
4、们针对多阶多阶段决策问题段决策问题的特点，提出了解决这类的特点，提出了解决这类问题的问题的“最优化原理最优化原理”，并成功地解，并成功地解决了生产管理、工程技术等方面的许决了生产管理、工程技术等方面的许多实际问题，从而建立了运筹学的一多实际问题，从而建立了运筹学的一个新分支，即个新分支，即动态规划动态规划。第第9章章 动态规划动态规划RUC,Information School,Ye Xiang动态规划问题的提出动态规划问题的提出u在实际的决策过程中，由于涉及的参数比较多，在实际的决策过程中，由于涉及的参数比较多，往往需要往往需要将问题分成若干个阶段，对不同阶段采取将问题分成若干个阶段，对不同
5、阶段采取不同的决策，从而使整个决策过程达到最优不同的决策，从而使整个决策过程达到最优。u显然，由于各个阶段选择的策略不同，对应的整显然，由于各个阶段选择的策略不同，对应的整个过程就可以有一系列不同的策略。个过程就可以有一系列不同的策略。u动态规划是解决多阶段决策过程最优化的一种方动态规划是解决多阶段决策过程最优化的一种方法。这种方法把法。这种方法把困难的多阶段决策问题困难的多阶段决策问题变换成变换成一系一系列互相联系的比较容易的单阶段问题列互相联系的比较容易的单阶段问题，解决了这一，解决了这一系列比较容易的单阶段问题，也就解决了困难的多系列比较容易的单阶段问题，也就解决了困难的多阶段决策问题。
6、阶段决策问题。u有时阶段可以用时间表示，在各个时间段，采用有时阶段可以用时间表示，在各个时间段，采用不同决策，不同决策，它随时间而变动它随时间而变动，这就有，这就有“动态动态”的含的含意意第第9章章 动态规划动态规划RUC,Information School,Ye Xiang动态规划问题的提出动态规划问题的提出u动态规划是现代企业管理中的一个动态规划是现代企业管理中的一个重要决策方法。重要决策方法。u本章利用微软本章利用微软ExcelExcel软件在软件在“公式公式”和和“规划求解工具规划求解工具”两方面的强大功两方面的强大功能，对能，对背包问题背包问题、生产经营问题生产经营问题、资资金管理
7、问题金管理问题和和资源分配问题资源分配问题等进行分等进行分析、建模与求解，解决了实际经营中析、建模与求解，解决了实际经营中的优化问题，迅速准确地得出决策结的优化问题，迅速准确地得出决策结果。果。第第9章章 动态规划动态规划RUC,Information School,Ye Xiang9.1 9.1 背包问题背包问题u背包问题可以抽象为这样一类问题：设背包问题可以抽象为这样一类问题：设有有n n种物品，每种物品有其重量及价值。种物品，每种物品有其重量及价值。同时有一个背包，最大装重为同时有一个背包，最大装重为c c，现从，现从n n种种物品中选取若干件（同一种物品可以选多物品中选取若干件（同一种
8、物品可以选多件），使其总重量小于等于件），使其总重量小于等于c c，而总价值，而总价值最大。最大。u背包问题等同于车、船、人造卫星等工背包问题等同于车、船、人造卫星等工具的最优装载问题，有广泛的实际意义具的最优装载问题，有广泛的实际意义。第第9章章 动态规划动态规划RUC,Information School,Ye Xiang9.1.1 9.1.1 一维背包问题一维背包问题例例9.19.1 某货运公司使用一种最大承载能某货运公司使用一种最大承载能力为力为1010吨的卡车来装载吨的卡车来装载3 3种货物，每种货种货物，每种货物的重量及价值如表物的重量及价值如表9-19-1所示。应当如何所示。应当
9、如何装载货物才能使总价值最大？装载货物才能使总价值最大？货物编号货物编号1 12 23 3单位重量单位重量(吨吨)3 34 45 5单位价值单位价值(百元百元)4 45 56 6用用ExcelExcel求解背包问题时，采用的是求解背包问题时，采用的是整数规划整数规划的方法。的方法。第第9章章 动态规划动态规划RUC,Information School,Ye Xiang9.1.2 9.1.2 多维背包问题多维背包问题u当约束条件不仅有货物的当约束条件不仅有货物的重量重量，还有，还有体积体积等限制时，构成了等限制时，构成了多维背包问题多维背包问题。u例例9.29.2 现有一辆载重为现有一辆载重为
10、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补充补充：背包问题：背包问题（容量一定的背
11、包里装尽可能多的物品）（容量一定的背包里装尽可能多的物品）u某人出国留学打点行李，现有三个旅行包，容积某人出国留学打点行李，现有三个旅行包，容积大小分别为大小分别为10001000、15001500和和20002000，根据需要列出需带，根据需要列出需带物品清单，其中一些物品是必带物品，共有物品清单，其中一些物品是必带物品，共有7 7件，其件，其体积大小分别为体积大小分别为400400、300300、150150、250250、450450、760760、190190。尚有。尚有1010件可带可不带物品，如果不带将在目的件可带可不带物品，如果不带将在目的地购买，通过网络查询可以得知其在目的地的
12、价格地购买，通过网络查询可以得知其在目的地的价格（美元）。这些物品的容量及价格分别见下表，试（美元）。这些物品的容量及价格分别见下表，试给出一个合理的安排方案，把物品放在三个旅行包给出一个合理的安排方案，把物品放在三个旅行包里。里。物品物品12345678910体积体积200350500430320120700420250100价格价格1545100705075200902030第第9章章 动态规划动态规划RUC,Information School,Ye Xiang补充补充：背包问题：背包问题（容量一定的背包里装尽可能多的物品）（容量一定的背包里装尽可能多的物品）u决策变量：对每个物品要确定
13、是否带的同决策变量：对每个物品要确定是否带的同时，还要确定放在哪个包里（时，还要确定放在哪个包里（如果增加一个如果增加一个虚拟包虚拟包，把不带的物品放在里面，则问题就，把不带的物品放在里面，则问题就转化为确定每个物品放在哪个包里。转化为确定每个物品放在哪个包里。这里的这里的数学模型和电子表格模型没有用虚拟包数学模型和电子表格模型没有用虚拟包）。）。u因此可设决策变量为第因此可设决策变量为第i i个物品是否放在第个物品是否放在第j j个包中（个包中（1-1-放，放，0-0-不放）。不放）。1,0 (1,2,17;1,2,3)ijxij第第9章章 动态规划动态规划RUC,Information S
14、chool,Ye Xiang补充补充：背包问题：背包问题（容量一定的背包里装尽可能多的物品）（容量一定的背包里装尽可能多的物品）u 约束条件约束条件 包的容量限制包的容量限制 必带物品限制必带物品限制 选带物品限制选带物品限制 0-1变量：变量：u 目标函数：未带物品购买费用最小目标函数：未带物品购买费用最小 )3,2,1(171jrxcjijii311 (1,2,7)ijjxi311 (8,9,17)ijjxi1,0 (1,2,17;1,2,3)ijxij311(8,9,17)ijjxi)1(31178jijiixpzMin第第9章章 动态规划动态规划RUC,Information Scho
15、ol,Ye Xiang补充补充：背包问题：背包问题（容量一定的背包里装尽可能多的物品）（容量一定的背包里装尽可能多的物品）u ExcelExcel求解结果为：求解结果为：包包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
16、.2 9.2 生产经营问题生产经营问题u在生产和经营中，经常遇到如何合理安排在生产和经营中，经常遇到如何合理安排生产计划、采购计划以及库存计划和销售计生产计划、采购计划以及库存计划和销售计划等问题，要求既要满足市场的需要，又要划等问题，要求既要满足市场的需要，又要尽量降低成本费用。因此，正确制定生产（尽量降低成本费用。因此，正确制定生产（或采购）策略，或采购）策略，确定确定不同时期不同时期的生产量（或的生产量（或采购量）、销售量和库存量采购量）、销售量和库存量，在满足产品需，在满足产品需求量的条件下，使得总收益最大或总成本（求量的条件下，使得总收益最大或总成本（生产成本存储成本）最小，这就是生
17、产经生产成本存储成本）最小，这就是生产经营问题，包括营问题，包括生产与存储问题生产与存储问题、采购与销售采购与销售问题问题等。等。第第9章章 动态规划动态规划RUC,Information School,Ye Xiang9.2.1 9.2.1 生产与存贮问题生产与存贮问题例例9.39.3 某皮鞋公司根据对去年的市场需求某皮鞋公司根据对去年的市场需求分析预测明年的需求：一季度分析预测明年的需求：一季度30003000双，二双，二季度季度40004000双，三季度双，三季度80008000双、四季度双、四季度70007000双。企业现在每个季度最多可以生产双。企业现在每个季度最多可以生产60006
18、000双皮鞋。为了满足所有的预测需求，前两双皮鞋。为了满足所有的预测需求，前两个季度必须有一定的库存才能满足后两个个季度必须有一定的库存才能满足后两个季度的需求。已知每双皮鞋的利润为季度的需求。已知每双皮鞋的利润为2020元元，每个季度的库存成本，每个季度的库存成本8 8元。请确定该公司元。请确定该公司明年每个季度的明年每个季度的生产计划生产计划，使公司的年利，使公司的年利润最大。润最大。第第9章章 动态规划动态规划RUC,Information School,Ye Xiang9.2.1 9.2.1 生产与存贮问题生产与存贮问题解：解：明年市场总需求为明年市场总需求为3000300040004
19、00080008000700070002200022000双，而最多可生产双，而最多可生产4 4600060002400024000双，所以皮鞋公司可以满足市场总需求。双，所以皮鞋公司可以满足市场总需求。(1)(1)决策变量决策变量 本问题是要确定该公司明年每个季度的生产本问题是要确定该公司明年每个季度的生产计划，所以设计划，所以设 公司每个季度生产公司每个季度生产xi（i i1,2,3,41,2,3,4）双皮鞋）双皮鞋；还有，设辅助决策变量：每个季度的；还有，设辅助决策变量：每个季度的期末库期末库存存为为si（i i1,2,3,41,2,3,4）双皮鞋。）双皮鞋。第第9章章 动态规划动态规划
20、RUC,Information School,Ye Xiang9.2.1 9.2.1 生产与存贮问题生产与存贮问题(2)(2)目标函数目标函数 本问题的目标是公本问题的目标是公司的年利润最大。司的年利润最大。(3)(3)约束条件约束条件满足每个季度的需求满足每个季度的需求（本季度的库存上季本季度的库存上季度库存本季度生产度库存本季度生产本季度市场需求本季度市场需求）每季度的生产力限制每季度的生产力限制非负非负123411212323434Max z 20(3000 4000 8000 7000)8()300040008000s.t.70006000(1,2,3,4)0(1,2,3,4)iiss
21、sssxssxssxssxxisi 0第第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个季度的生产能力、个季度的生产能力、市场需求、每平方米的生产成本以及库存成本如表市
22、场需求、每平方米的生产成本以及库存成本如表9-9-3 3所示。毛毯厂需要确定在这所示。毛毯厂需要确定在这4 4个季度里每季度生产多个季度里每季度生产多少毛毯，才能使总生产和库存成本最小。少毛毯，才能使总生产和库存成本最小。季度季度生产能力生产能力(平方米平方米)市场需求市场需求(平方米平方米)生产成本生产成本(元元/平方米平方米)库存成本库存成本(元元/平方米平方米)1 16006004004002 20.250.252 23003005005005 50.250.253 35005004004003 30.250.254 44004004004003 3第第9章章 动态规划动态规划RUC,I
23、nformation School,Ye Xiang9.2.1 9.2.1 生产与存贮问题生产与存贮问题解：解：采用采用另外一种解法另外一种解法，即用，即用网络最优化问题网络最优化问题中的中的最小费用流问题最小费用流问题来求解。通过建立一个网络图来代来求解。通过建立一个网络图来代表这个问题。首先根据四个季度建立四个产量节点表这个问题。首先根据四个季度建立四个产量节点和四个需求节点。每个产量节点由一个流出弧连接和四个需求节点。每个产量节点由一个流出弧连接对应的需求节点。对应的需求节点。33520.250.250.251季度产量2季度产量3季度产量4季度产量1季度需求2季度需求3季度需求4季度需求
24、产量节点需求节点600300500400400500400400弧的流量代表了弧的流量代表了该季度所生产的该季度所生产的毛毯数量。相对毛毯数量。相对于每个需求节点于每个需求节点，一个流出弧代，一个流出弧代表了库存的数量表了库存的数量，即供给下季度，即供给下季度需求节点的数量需求节点的数量第第9章章 动态规划动态规划RUC,Information School,Ye Xiang9.2.1 9.2.1 生产与存贮问题生产与存贮问题例例9.49.4数学模型数学模型（采用节点净流量）（采用节点净流量）上季度库存本季度生产本季度的库存本季度市场需求上季度库存本季度生产本季度的库存本季度市场需求12341
25、2311122233341234Min z25330.25400500400s.t.400600,300,500,4000(1,2,3,4),0(1,2,3)iixxxxsssxssxssxssxxxxxxisi第第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 某厂根据订货合同在今后四个季度对某厂根据
26、订货合同在今后四个季度对某产品的需求量如表某产品的需求量如表9-49-4所示。所示。如果该季度生如果该季度生产，需要生产产，需要生产准备费用为准备费用为3 3千元千元，每件产品的，每件产品的生产成本为生产成本为1 1千元，由于生产能力的限制，每千元，由于生产能力的限制，每季度最多季度最多不超过不超过6 6件。又设每一件产品存贮一件。又设每一件产品存贮一个季度的费用为个季度的费用为0.50.5千元，并且第一季度开始千元，并且第一季度开始与第四季度末均没有产品库存。与第四季度末均没有产品库存。要求要求在上述条件下该厂应该如何安排各在上述条件下该厂应该如何安排各季度的生产与库存，以使总费用季度的生产
27、与库存，以使总费用最低？最低？季度季度1 12 23 34 4需求量需求量2 23 32 24 4第第9章章 动态规划动态规划RUC,Information School,Ye Xiang9.2.1 9.2.1 生产与存贮问题生产与存贮问题解：解：根据题意，对于每个季度来说，可知当生根据题意，对于每个季度来说，可知当生产产x（00 x66）件产品时，产品的费用为）件产品时，产品的费用为3+13+1x；当不生产（当不生产（x=0=0）时，费用为）时，费用为0 0。这是一个。这是一个有启有启动成本动成本（生产准备费用）（生产准备费用）的生产与存储问题的生产与存储问题。(1)(1)决策变量决策变量
28、设设xi为第为第i i个季度的个季度的生产量生产量，si为第为第i i个季度个季度的的期末库存量期末库存量（i i1,2,3,4);1,2,3,4);引入辅助引入辅助0-10-1变量：变量：yi为第为第i i个季度个季度是否组织是否组织生产生产（0 0表示不生产，表示不生产，1 1表示生产）。表示生产）。第第9章章 动态规划动态规划RUC,Information School,Ye Xiang9.2.1 9.2.1 生产与存贮问题生产与存贮问题(2)(2)目标函数目标函数 本问题的目标是总费本问题的目标是总费用最低。用最低。(3)(3)约束条件约束条件 对于每个季度来说，对于每个季度来说，本季
29、库存上季库存本本季库存上季库存本季生产本季需求季生产本季需求 生产能力限制生产能力限制 根据要求，第四季度末根据要求，第四季度末没有库存没有库存 非负非负 辅助辅助0-10-1变量变量123412341234112123234344Min z3 0.5232s.t.406(1,2,3,4)00(1,2,3,4)0,1(1,2,3,4)iiiiyyyyxxxxsssssxssxssxssxxyissiyi且第第9章章 动态规划动态规划RUC,Information School,Ye Xiang9.2.1 9.2.1 生产与存贮问题生产与存贮问题例例9.59.5的电子表格模型的电子表格模型第第9
30、章章 动态规划动态规划RUC,Information School,Ye Xiang9.2.2 9.2.2 采购与销售问题采购与销售问题例例9.69.6 某商店在未来的某商店在未来的4 4个月里，准备利用它的一个个月里，准备利用它的一个仓库来专门经销某种商品，仓库最大容量能储存这种仓库来专门经销某种商品，仓库最大容量能储存这种商品商品10001000单位。假定该商品每月只能卖出仓库现有的单位。假定该商品每月只能卖出仓库现有的货。当商店在某月订货时，货。当商店在某月订货时，下月初才能到货下月初才能到货。预测该。预测该商品未来商品未来4 4个月的买卖价格如表个月的买卖价格如表9-59-5所示，假定
31、商店在所示，假定商店在1 1月开始经销时，仓库储有该商品月开始经销时，仓库储有该商品500500单位。试问若不单位。试问若不计库存费用，该商店应如何制定计库存费用，该商店应如何制定1 1月至月至4 4月的订购与销月的订购与销售计划，使预期获利最大。售计划，使预期获利最大。月份月份购买单价购买单价销售单价销售单价1 1101012122 29 98 83 3111113134 415151717第第9章章 动态规划动态规划RUC,Information School,Ye Xiang9.2.2 9.2.2 采购与销售问题采购与销售问题解：解：(1)(1)决策变量决策变量 本问题需要制定本问题需要
32、制定1 1月至月至4 4月的订购与销售计划，月的订购与销售计划，所以设：每月的所以设：每月的销售量销售量为为xi(i(i=1,2,3,4)=1,2,3,4)，每月的，每月的订订购量购量为为yi(i(i=1,2,3,4)=1,2,3,4)；还有设辅助决策变量：每；还有设辅助决策变量：每月月初初仓库中的仓库中的存货量存货量为为si(i(i=1,2,3,4)=1,2,3,4)。(2)(2)目标函数目标函数 因为不考虑库存的费用，所以要使预期获利最因为不考虑库存的费用，所以要使预期获利最大，只要建立每个月订货成本与销售收入之间的关大，只要建立每个月订货成本与销售收入之间的关系即可。系即可。112233
33、44max12108913111715zxyxyxyxy第第9章章 动态规划动态规划RUC,Information School,Ye Xiang9.2.2 9.2.2 采购与销售问题采购与销售问题(3)(3)约束条件约束条件因为当月的订货，下个月才因为当月的订货，下个月才能到，所以该商场每月可销售能到，所以该商场每月可销售的是上月剩余库存和上个月的的是上月剩余库存和上个月的订货，而上月剩余库存上月订货，而上月剩余库存上月初的库存上月销售，也就是初的库存上月销售，也就是说，说，每月初的库存上月初的每月初的库存上月初的库存上月销售上月进货库存上月销售上月进货仓库的容量限制仓库的容量限制每月销售量
34、不超过月初库存每月销售量不超过月初库存非负非负112233441211132224333Max z121089 13111715500s.t.1000(1,2,3,4)(1,2,3,4),0(1,2,3,4)iiiiiixyxyxyxysssxyssxyssxysixs ix y si第第9章章 动态规划动态规划RUC,Information School,Ye Xiang9.2.2 9.2.2 采购与销售问题采购与销售问题例例9.69.6的电子表格模型的电子表格模型第第9章章 动态规划动态规划RUC,Information School,Ye Xiang9.2.2 9.2.2 采购与销售问题
35、采购与销售问题u需要说明的是：在用需要说明的是：在用ExcelExcel求解有库存（或剩求解有库存（或剩余量）问题时，辅助决策变量余量）问题时，辅助决策变量“库存库存si”经常不经常不用可变单元格（黄底）表示用可变单元格（黄底）表示，而，而用输出单元格用输出单元格（公式，没有填充颜色）公式，没有填充颜色）来代替来代替，但此时要求在，但此时要求在“约束约束”中加入中加入“库存库存00或某个值或某个值”的约束。的约束。u如在图如在图9-59-5的例的例9.69.6电子表格模型中，没有电子表格模型中，没有“月月初库存初库存”可变单元格，而用输出单元格可变单元格，而用输出单元格“月初库月初库存存”来代
36、替，还有在图来代替，还有在图9-69-6的例的例9.79.7电子表格模型电子表格模型和图和图9-79-7的例的例9.89.8电子表格模型中，没有电子表格模型中，没有“期末余期末余额额”可变单元格，而用输出单元格可变单元格，而用输出单元格“期末余额期末余额”来代替来代替第第9章章 动态规划动态规划RUC,Information School,Ye Xiang9.3 9.3 资金管理问题资金管理问题资金管理问题研究如何选择投资对象，资金管理问题研究如何选择投资对象，例如，如何例如，如何选择不同的贷款和债券选择不同的贷款和债券，在，在满足某些要求的前提下使得利润最大或满足某些要求的前提下使得利润最大
37、或风险最小。因此，其决策变量是对各种风险最小。因此，其决策变量是对各种可能的投资对象的投资组合，其目标函可能的投资对象的投资组合，其目标函数通常是期望回报最大化或者风险最小数通常是期望回报最大化或者风险最小化，而约束条件则可包括总投资、公司化，而约束条件则可包括总投资、公司政策、法律法规等约束。政策、法律法规等约束。资金管理问题资金管理问题通常被运用在公司的财务计划或个人的通常被运用在公司的财务计划或个人的理财计划理财计划。第第9章章 动态规划动态规划RUC,Information School,Ye Xiang9.3.1 9.3.1 流动资金问题流动资金问题例例9.79.7 某企业打算利用流
38、动资金进行短某企业打算利用流动资金进行短期理财投资，在保证每月现金余额不少期理财投资，在保证每月现金余额不少于于1010万元的前提下，进行三种期限的投万元的前提下，进行三种期限的投资（见资（见P304P304的表的表9-79-7）。已知该企业现有）。已知该企业现有现金现金4040万元以及预计的每月现金支出额万元以及预计的每月现金支出额，求半年后资金最大的优化计划。，求半年后资金最大的优化计划。月份月份1 12 23 34 45 56 6现金支出现金支出（元）（元）+75000+75000-10000-10000-20000-20000+80000+80000+50000+50000-15000
39、-15000第第9章章 动态规划动态规划RUC,Information School,Ye Xiang9.3.1 9.3.1 流动资金问题流动资金问题解：解：(1)(1)决策变量决策变量 设设xij为第为第i i个月存期为个月存期为j j个月的存款额（万元），由于目个月的存款额（万元），由于目标是半年后资金最大的优化计划，因此有如表标是半年后资金最大的优化计划，因此有如表9-99-9的决策变的决策变量。为了求解方便，引入辅助决策变量：量。为了求解方便，引入辅助决策变量：每月现金余额每月现金余额si万万元元（i=1,2,3,4,5,6)i=1,2,3,4,5,6)。(2)(2)目标函数目标函数
40、每月的支出是一定的，因此要使半年后的资金最大，每月的支出是一定的，因此要使半年后的资金最大，就是要使存款的总利息最大。就是要使存款的总利息最大。目标函数也可以是半年后的资金最大。目标函数也可以是半年后的资金最大。1121314151611323334316Max z0.15%3 0.18%6 0.20%xxxxxxxxxxx 6614316Max z(1 0.15%)(1 3 0.18%)(1 6 0.20%)sxxx 第第9章章 动态规划动态规划RUC,Information School,Ye Xiang9.3.1 9.3.1 流动资金问题流动资金问题(3)(3)约束条件约束条件每月的现金
41、余每月的现金余额上月现金余额上月现金余额本月本利收额本月本利收益本月投资益本月投资本月现金支出本月现金支出每月现金余额每月现金余额不少于不少于1010万元万元非负非负112131415161132333431611113162111212332213133433113414354Max z0.15%3 0.18%6 0.20%407.51.001511.001521.0015(1 3 0.0018)8s.t.xxxxxxxxxxxsxxxssxxxssxxxssxxxxss 4123516551336111213141516113233343161.0015(1 3 0.0018)51.001
42、5(1 3 0.0018)1.510(1,2,3,4,5,6),0ixxxssxxxsixxxxxxxxxxx 第第9章章 动态规划动态规划RUC,Information School,Ye Xiang9.3.1 9.3.1 流动资金问题流动资金问题例例9.69.6的电子表格模型的电子表格模型第第9章章 动态规划动态规划RUC,Information School,Ye Xiang9.3.2 9.3.2 贷款问题贷款问题例例9.89.8 某建筑公司为了盘活市场，打算向银行贷款某建筑公司为了盘活市场，打算向银行贷款来开展更多的业务。现有来开展更多的业务。现有两种两种不同的不同的贷款方式贷款方式：
43、第：第一种是一种是1010年年长期贷款长期贷款，年利率，年利率7%7%，只能在，只能在20062006年初年初贷贷1 1次，以后每年还息（次，以后每年还息（1010次），第次），第1010年后还本；第年后还本；第二种是二种是1 1年年短期贷款短期贷款，年利率，年利率10%10%，可以在，可以在2006200620152015年初贷，可贷年初贷，可贷1010次，下一年还本付息。请问：次，下一年还本付息。请问：如何贷款（贷款组合），使得公司在如何贷款（贷款组合），使得公司在1010年内可以正年内可以正常运转。目前公司只有常运转。目前公司只有100100万元，每年的现金储备最万元，每年的现金储备最少
44、少5050万元，已知公司未来万元，已知公司未来1010年的年的每年年初每年年初净净现金流现金流（预测）。希望在（预测）。希望在20162016年年初的现金余额最多。年年初的现金余额最多。年份年份20062006200720072008200820092009201020102011201120122012201320132014201420152015净现金流净现金流（万元）（万元）-800-800-200-200-400-400300300600600300300-400-400700700-200-20010001000第第9章章 动态规划动态规划RUC,Information Schoo
45、l,Ye Xiang9.3.2 9.3.2 贷款问题贷款问题解：解：(1)(1)决策变量决策变量x为为20062006年初贷的年初贷的1010年长期贷款额年长期贷款额(万元万元)；y1,y2,y10为为2006200620152015年初贷的年初贷的1 1年期贷年期贷款额（万元）；款额（万元）；辅助决策变量：辅助决策变量：s1,s2,s11表示表示2006200620162016年初的现金余额（万元）。年初的现金余额（万元）。(2)(2)目标函数目标函数使使20162016年年初的现金余额最大年年初的现金余额最大:11Max z=s第第9章章 动态规划动态规划RUC,Information S
46、chool,Ye Xiang9.3.2 9.3.2 贷款问题贷款问题(3)(3)约束条件约束条件每年的现金余额每年的现金余额=上年的现金余额上年的现金余额现金流贷款（长现金流贷款（长期、短期）还款期、短期）还款（长期、短期的利（长期、短期的利息和本金）息和本金）每年的现金储备每年的现金储备最少最少5050万元万元贷款额非负贷款额非负1111212132324343545465657676878M ax z1008002007%(110%)4007%(110%)3007%(110%)6007%(110%)3007%(110%)s.t.4007%(110%)7007%ssxyssyxyssyxys
47、syxyssyxyssyxyssyxyssy79898109109111010(110%)2007%(110%)10007%(110%)(17%)(110%)50 (1,2,11)0,0(1,2,10)iixyssyxyssyxyssxysixyiLL第第9章章 动态规划动态规划RUC,Information School,Ye Xiang9.3.2 9.3.2 贷款问题贷款问题例例9.89.8的的电电子子表表格格模模型型第第9章章 动态规划动态规划RUC,Information School,Ye Xiang9.3.3 9.3.3 购买债券问题购买债券问题例例9.99.9 有个好爸爸，他打算
48、为他正在读有个好爸爸，他打算为他正在读高三的儿子准备一笔教育基金，以保证高三的儿子准备一笔教育基金，以保证儿子四年大学和三年硕士的学习费用。儿子四年大学和三年硕士的学习费用。据估计，四年大学和三年硕士的学习和据估计，四年大学和三年硕士的学习和生活费用生活费用如表如表9-119-11所示。所示。年份年份1 12 23 34 45 56 67 7费用费用(万元万元)1.31.3 1.11.1 1.21.2 1.31.3 1.51.5 1.61.62 2第第9章章 动态规划动态规划RUC,Information School,Ye Xiang9.3.3 9.3.3 购买债券问题购买债券问题经多方调查
49、，爸爸发现有三种债券值得购买（且经多方调查，爸爸发现有三种债券值得购买（且只能在第一年年初购买）。这三种债券的面值均只能在第一年年初购买）。这三种债券的面值均为为10001000元，但由于它们的回报率不同，所以它们元，但由于它们的回报率不同，所以它们的购买价格不同。同时，爸爸也考虑在每年的年的购买价格不同。同时，爸爸也考虑在每年的年初将现金存入银行，在下一年初再全部取出（即初将现金存入银行，在下一年初再全部取出（即一年期存款），这时可得利息一年期存款），这时可得利息2%2%（假设扣除利息（假设扣除利息税后）。爸爸希望能设计一个理财计划，使得在税后）。爸爸希望能设计一个理财计划，使得在保证儿子保
50、证儿子7 7年学习费用的前提下，所需投入的教育年学习费用的前提下，所需投入的教育基金最少。基金最少。债券债券购买价格购买价格(千元千元)每年每年回报率回报率到期年限到期年限1 11.051.055%5%4 42 21 13%3%5 53 31.151.157%7%6 6第第9章章 动态规划动态规划RUC,Information School,Ye Xiang9.3.3 9.3.3 购买债券问题购买债券问题解：解：(1)(1)决策变量决策变量 爸爸面临的决策包括：第一年投入的教育爸爸面临的决策包括：第一年投入的教育基金和购买债券的数量，以及前基金和购买债券的数量，以及前6 6年每年年初存年每年年
