补充：动态规划
RUC Information School,Ye Xiang,2007
Data,Model and Decisions
数据、模型与决策补充动态规划补充：动态规划
RUC Information School,Ye Xiang,2007
本章内容
动态规划问题概述
动态规划在经济管理中的应用本章的具体内容可以参见胡运权主编,运筹学教程,（
第二版）清华大学出版社,2004.2 第七章 动态规划
，但它不是用 Excel求解，而是用动态规划方法 手工求解 。这里想告诉大家，用 Excel求解动态规划问题非常简单（如第三章 P65案例：大沼泽地金色年代公司的现金流问题）。
也就是说，本章介绍的是用 Excel来求解动态规划问题
,但并没有介绍动态规划方法,有兴趣的同学可以参考国内运筹学书籍中的,动态规划,章节。
补充：动态规划
RUC Information School,Ye Xiang,2007
动态规划问题概述
动态规划 是解决多阶段决策过程最优化问题的一种方法。该方法是由美国数学家贝尔曼 (R Bellman)等人在 20世纪 50年代初提出的。
他们针对多阶段决策问题的特点，提出了解决这类问题的最优化原理，并成功地解决了生产管理、工程技术等方面的许多实际问题，
从而建立了运筹学的一个新分枝，即动态规划。
动态规划是 现代企业管理 中的一个重要决策方法，可用于解决最优路径问题、资源分配问题、生产计划与库存、投资、装载、排序等问题及生产过程的最优控制等。由于它有独特的解题思路，在处理某些优化问题时，比线性规划或非线性规划方法更有效。
多阶段决策过程,是指这样一类特殊的活动过程，它们可以按时间顺序分解成若干互相联系的阶段，称为,时段,,在每一个时段都要做出决策，全部过程的决策是一个决策序列，所以多阶段决策问题属序惯决策问题。
多阶段决策过程最优化的 目标是要达到整个活动过程的总体效果最优 。由于各阶段决策间有机地联系着，本段决策的执行将影响到下一段的决策，以至于影响总体效果，所以决策者在每段决策时不仅考虑本阶段最优，还应考虑对最终目标的影响，从而做出对全局来讲是最优的决策。
补充：动态规划
RUC Information School,Ye Xiang,2007
动态规划在经济管理中的应用
动态规划在经济管理中的应用
最短路线问题（例 1和扩展）－工程线路问题
背包问题（例 2和扩展）
生产经营问题（例 3～例 6）
营业资金管理（例 7～例 10）
资源分配问题（例 11～例 12）
补充：动态规划
RUC Information School,Ye Xiang,2007
动态规划在经济管理中的应用－ 最短路线问题
例 1：最短路线问题－工程线路问题
给定一个线路网络图，要从 A地向 F地铺设一条输油管道，各点间连线上的数字表示距离，问应选择什么路线，可使总距离最短?
在 Excel中的解法：用第七章网络最优化问题的 7.4节最短路问题（ P257,A节点为源,F节点为目的地）
最短路线问题的扩展,货郎担问题和中国邮路问题（我们已经讲过）
5
A
B1
B2
C2
C3
C1
C4
D2
D3
D1 E1
E2
F
7
5
2
3
6
8
4
7
8
4
5
3
4
8
4
3
5
6
2
1
3
4
3
补充：动态规划
RUC Information School,Ye Xiang,2007
动态规划在经济管理中的应用－ 背包问题
例 2：背包问题
一位旅行者携带背包去登山，已知他所能承受的背包重量限度为 a千克，现有 n种物品可供他选择装入背包，第 i种物品的单件重量为 ai千克，其价值（可以是表明本物品对登山的重要性的数量指标）是携带数量 xi的函数 cixi（ i=1,2,…,n），问旅行者应该如何选择携带各种物品的件数，以使总价值最大？ (背包问题等同于车、船、人造卫星等工具的最优装载等，有广泛的实际意义 )
代数模型（一维背包问题）：
设 xi为第 i种物品装入的件数，则整数规划模型：
目标 (总价值最大 ),Max P=?cixi
总重量约束,?aixi? a
非负约束,xi? 0 且为整数（ i=1,2,…,n）
在 Excel中的解法：用本书 9.1节的一般整数规划
背包问题的扩展
当 xi仅表示装入 (取 1)和不装 (取 0)第 i种物品，则本模型就是 0-1背包问题。
多维背包问题：当约束条件不止一个时，如多总体积的限制等。
补充：动态规划
RUC Information School,Ye Xiang,2007
动态规划在经济管理中的应用－ 0-1背包问题
背包问题的扩展,0-1背包问题某人准备外出旅游，行装中有 A,B,C,D,E共 5件备选物品，其重量和价值如表所示，假定行李总重不得超过 13Kg，求总价值最大的行李构成方案。
物品 A B C D E
重量 /Kg 7 5 4 3 1
价值 /百元 9 4 3 2 0.5
数学模型：
设 xi为第 i种物品是否装入（ 1-是,0-
否），则 0-1整数规划模型：
目标 (总价值最大 )：
Max P=9x1+4x2+3x3+2x4+0.5x5
重量约束,7x1+5x2+4x3 +3x4+x5?13
0-1约束,xi为 0或 1（ i=1,2,3,4,5）
补充：动态规划
RUC Information School,Ye Xiang,2007
动态规划在经济管理中的应用－ 多维背包问题
背包问题的扩展,多维背包问题现有一辆载重 w=5t，最大装载体积 v=8m3卡车作为运输工具，可装载三种货物，已知每种货物各 8件，其他有关信息如表所示，求携带货物价值最大的装载方案。
货物品种 k
单件货物重量
wk/t
单件货物体积
vk/m3
单件货物价值
pk/万元
1 1 2 30
2 3 4 75
3 2 3 60
数学模型：
设 xk为第 k种物品装入的件数，则整数规划模型：
目标 (总价值最大 )：
Max P=30x1+75x2+60x3
重量约束,x1+3x2+2x3? 5
体积约束,2x1+4x2+3x3? 8
货物件数,xk? 8 (k=1,2,3)
非负约束,xk? 0 且为整数 (k=1,2,3)
补充：动态规划
RUC Information School,Ye Xiang,2007
动态规划在经济管理中的应用－ 生产经营问题
在生产和经营中，经常遇到如何合理安排生产计划、采购计划以及仓库的存货计划和销售计划，使总效益最大的问题。以下是几个例子
例 3,P206 生产进度安排（动态规划方法）
例 4：生产与库存问题（动态规划的另外一种写法：网络最优化中的最小费用流问题）
例 5,P87 习题 3.3（多种解法）
例 6：采购与销售问题补充：动态规划
RUC Information School,Ye Xiang,2007
动态规划在经济管理中的应用
－ 生产经营问题（续）
例 3,P206 生产进度安排（动态规划方法）
在 Excel中的解法，主要利用：
本月剩余量 Ri=上月剩余量 Ri -1＋
本月生产量（ xi+yi）－
本月计划安装量 Ni
具体见本章的,补充－动态规划问题,的
Excel文件。
补充：动态规划
RUC Information School,Ye Xiang,2007
动态规划在经济管理中的应用
－ 生产经营问题（续）
例 4 生产与库存问题康托斯毛毯厂是一个小型的生产商，致力于生产家用和办公用的毛毯。紧接的 4个季度的生产能力、市场需求、每平方米的生产成本以及库存成本如下表所示。特别需要注意的是生产能力、市场需求、每平方米的生产成本每个季度都会产生变化。关键是库存成本从一个季度到下一个季度持续在每平方米 0.25美元。康托斯毛毯厂要决定在这 4个季度里每季度生产多少平方米的毛毯，
能使总生产和库存成本最小。
季度 生产能力(平方米 ) 市场需求(平方米 ) 生产成本(美元 /平方米 ) 库存成本(美元 /平方米 )
1 600 400 2 0.25
2 300 500 5 0.25
3 500 400 3 0.25
4 400 400 3 0.25
补充：动态规划
RUC Information School,Ye Xiang,2007
例 4 生产与库存问题 (续 )
网络流中需求节点的流入和流出量导致这个模型成为一个转运模型（ 网络最优化问题中的最小费用流问题 ）
我们通过建立一个流图来代表这个问题。首先根据 4个季节建立 4个产量节点和 4个需求节点。每个产量节点由一个流出弧连接对应的需求节点。弧的流量代表了这时期所生产的毛毯。相对于每个需求节点，一个流出弧代表了库存的数量，即供给下季度需求节点的数量。下图显示了这个网络模型。
1季度产量
3季度产量
2季度产量
4季度产量生产节点
1季度需求
3季度需求
2季度需求
4季度需求需求节点
600
300
500
400
400
500
400
400
2
5
3
3
0.25
0.25
0.25
决策变量,（图中弧的流量）
4个季度的生产量 xi(i=1,2,3,4)，
前 3个季度库存量 Ri (i=1,2,3)
目标,Min C=2x1+5x2+3x3＋ 3x4＋
0.25(R1+R2+R3)
约束条件：
生产能力,x1? 600,x2?300，
x3? 500,x4?400
第一季度需求,x1 － R1 ＝ 400
第二季度需求,x2 ＋ R1 － R2 ＝ 500
第三季度需求,x3 ＋ R2 － R3 ＝ 400
第四季度需求,x4 ＋ R3 ＝ 400
非负,xi?0(i=1,2,3,4),Ri? 0(i=1,2,3)
补充：动态规划
RUC Information School,Ye Xiang,2007
生产与库存问题补充练习题
设有一生产部门，生产计划周期分为 3个阶段，已知最初库存为 1,3个阶段的产量需求分别为 3,4,3，生产的固定成本为 8，单位产品的费用为 2，单位产品的阶段库存费用为 2，库存容量为 4，阶段生产能力为 6，问应如何安排各阶段的生产，使计划期内的费用总和最小？请写数学模型，并用 Excel求解。
提示：比较难，有固定成本，是一个综合题
结果：（ 2,4,3),Min C=42
补充：动态规划
RUC Information School,Ye Xiang,2007
（解法 1：书上的解法，动态规划，利用剩余 Rt）
决策变量,4个季度靴子的生产数量 x1,x2,x3,x4；
4个季度靴子的库存量 R1,R2,R3,R4
目标 利润最大 Max P=20（ 3000＋ 4000＋ 8000＋ 7000） － 8（ R1+R2+R3+R4）
约束条件,用,本月库存量＝上月库存＋本月生产－本月需求,
一季度,R1＝ 1000+x1-3000
二季度,R2＝ R1+x2-4000
三季度,R3＝ R2+x3-8000
四季度,R4＝ R3+x4-7000
最大生产量,xi? 6000（ i＝ 1,2,3,4）
非负,xi?0（ i＝ 1,2,3,4）,Ri?0（ i＝ 1,2,3,4）
例 5,P87 习题 3.3
补充：动态规划
RUC Information School,Ye Xiang,2007
（解法 2：网络最优化中的流量，也利用剩余 Rt）
决策变量,x1,x2,x3,x4：每季度靴子的生产数量
R1,R2,R3：每季度靴子的库存量目标 利润最大 Max P=20（ 3000＋ 4000＋ 8000＋ 7000） － 8（ R1+R2+R3）
约束条件,用,上月库存＋本月生产－本月库存量＝本月需求,
一季度,1000+x1－ R1＝ 3000
二季度,R1+x2－ R2 ＝ 4000
三季度,R2+x3－ R3 ＝ 8000
四季度,R3+x4 ＝ 7000
最大生产量,xi? 6000（ i＝ 1,2,3,4）
非负,xi?0（ i＝ 1,2,3,4）,Ri?0（ i＝ 1,2,3）
例 5,P87 习题 3.3（续）
补充：动态规划
RUC Information School,Ye Xiang,2007
（解法 3：没有利用剩余 Rt，而是直接代入 ）
决策变量,设 x1,x2,x3,x4：每季度靴子的生产数量目标 利润最大 Max P=20（ 1000+x1+x2+x3+x4） － 8（ 1000+x1-3000）
－ 8（ 1000+x1-3000＋ x2-4000）
－ 8（ 1000+x1-3000＋ x2-4000+x3-8000）
约束条件,用,上月剩余＋本月生产? 需求量,
一季度,1000+x1? 3000
二季度,1000+x1-3000+x2? 4000
三季度,1000+x1-3000+x2-4000+x3? 8000
四季度,1000+x1-3000+x2-4000+x3-8000+x4 ＝ 7000
最大生产量,xi? 6000（ i＝ 1,2,3,4）
非负,xi? 0（ i＝ 1,2,3,4）
例 5,P87 习题 3.3（续）
补充：动态规划
RUC Information School,Ye Xiang,2007
（解法 4：没有利用剩余 Rt，而是直接代入 ）
决策变量,设 x1,x2,x3,x4：每季度靴子的生产数量目标 利润最大 Max P=20（ 1000+x1+x2+x3+x4） － 8（ 1000+x1-3000）
－ 8（ 1000+x1＋ x2-3000-4000）
－ 8（ 1000+x1＋ x2+x3-3000-4000-8000）
约束条件,用,累计生产量? 累计需求量,
一季度,1000+x1? 3000
二季度,1000+x1+x2? 3000+4000
三季度,1000+x1+x2+x3? 3000+4000+8000
四季度,1000+x1+x2+x3+x4 = 3000+4000+8000+7000
最大生产量,xi? 6000（ i＝ 1,2,3,4）
非负,xi? 0（ i＝ 1,2,3,4）
例 5,P87 习题 3.3（续）
补充：动态规划
RUC Information School,Ye Xiang,2007
动态规划在经济管理中的应用
－ 生产经营问题（续）
例 6：采购与销售问题某商店在未来的 4个月里，准备利用它的一个仓库来专门经销某种商品，仓库的最大容量能储存这种商品 1000单位。
假定该商品每月只能出卖仓库现有的货。当商店在某月购货时，下月初才能到货。预测该商品未来四个月的买卖价格如下表所示，假定商店在一月开始经销时，仓库储有该商品 500单位。试问若不计库存费用，该商店应如何制定 1
月至 4月的订购与销售计划，使预期获利最大。
在 Excel中的解法，主要利用：
月初库存 Sk＝上月库存 Sk－ 1－
上月卖出 Xk－ 1 ＋
上月订货 Yk－ 1,
具体见本章的,补充－动态规划问题,的 Excel文件
。
补充：动态规划
RUC Information School,Ye Xiang,2007
动态规划在经济管理中的应用－ 资金管理
资金管理例 7：流动资金管理（ 将多余的现金存入银行,以获取利息 ）
例 8：贷款问题（ P65的 3.1案例研究,
大沼泽地金色年代公司的现金流问题）
例 9：购买债券问题（ P89 案例 3.1 养老金的谨慎供应）
例 10：连续投资问题（ P136习题 4.17）
补充：动态规划
RUC Information School,Ye Xiang,2007
动态规划在经济管理中的应用－ 资金管理
例 7,流动资金管理：如何进行计划管理
在保证流动资金的情况下（每月现金余额不少于
10万），将多余的现金存入银行（有 1个月,3个月,6个月定存）以获取利息
目标：半年的资金优化计划（半年后，存入银行的钱全部到期。注意是每月初存入银行），使总利息收益最大化
已知：刚开始有 40万（ 400000）现金和每月的现金支出额
在 Excel中的解法：利用到期定存本金和到期定存利息与 1个月,3个月,6个月定存间的关系（
存几个月后取出），具体见本章的,补充－动态规划问题,的 Excel文件。
补充：动态规划
RUC Information School,Ye Xiang,2007
第 3章 电子表格建模的艺术
（ 动态规划－利用每个阶段的剩余量 Ri）
3.1 案例研究,大沼泽地金色年代公司的现金流问题
有两种不同的贷款：
10年长期贷款，年利率 7%，只能在 2003年初贷 1次，以后每年还息（ 10次），第 10年后还本
1年短期贷款，年利率 10%，可以在 2003－ 2012年初贷，可贷 10次，下一年还本付息
问题：如何贷款（贷款组合），使得公司在 10年内可以正常运转。目前公司只有 100万美元，每年的现金储备最少 50万美元，已知公司未来 10年的净现金流（预测），并希望在
2013年年初的现金余额最多（目标）。
例 8：贷款问题补充：动态规划
RUC Information School,Ye Xiang,2007
3.1 案例研究,大沼泽地金色年代公司的现金流问题的线性规划模型
1、决策变量（单位：百万美元）
x,2003年初贷的 10年长期贷款额,y1,…,y 10,2003－ 2012年初贷的 1年期贷款额，
R1,…,R 11,2003－ 2013年初的现金余额
2、目标：最大化 2013年年初的现金余额 Max R11
3、约束条件（每年的现金余额＝上年的现金余额＋现金流＋贷款（长期、短期）－还款（长期、短期的利息和本金，非负，每年的现金储备最少 50万美元）
2003,R1＝ 1 － 8 ＋ x＋ y1
2004,R2＝ R1 － 2 ＋ y2－ 0.07x－ 1.1y1
2005,R3＝ R2 － 4 ＋ y3－ 0.07x－ 1.1y2
2006,R4＝ R3 ＋ 3 ＋ y4－ 0.07x－ 1.1y3
2007,R5＝ R4 ＋ 6 ＋ y5－ 0.07x－ 1.1y4
2008,R6＝ R5 ＋ 3 ＋ y6－ 0.07x－ 1.1y5
2009,R7＝ R6 － 4 ＋ y7－ 0.07x－ 1.1y6
2010,R8＝ R7 ＋ 7 ＋ y8－ 0.07x－ 1.1y7
2011,R9＝ R8 － 2 ＋ y9－ 0.07x－ 1.1y8
2012,R10＝ R9 ＋ 10 ＋ y10－ 0.07x－ 1.1y9
2013,R11＝ R10 － 1.07x－ 1.1y10
非负,x? 0,yi?0 （ i=1,2,…,10 ）
每年的现金储备 Ri?0.5 （ i=1,2,…,11 ）
例 8：贷款问题（续）
补充：动态规划
RUC Information School,Ye Xiang,2007
P89 案例 3.1 养老金的谨慎供应的线性规划模型（解法 1）
1、决策变量（单位：百万美元）
xi：债券 i的投资数量 （ i=1,2,3,4） (千份 )
R1,…,R 10,2003－ 2012年各年的余额（年度资本市场基金的存款）
2、目标函数：最小化 2003.1.1总投入 min C=0.98x1+0.92x2+0.75x3+0.8x4+8+R1
3、约束条件（各年的余额 =上一年的余额（上年资本市场基金）的本金利息＋债券的本金利息－养老金支付，非负）
2004,R2=1.05R1+1.04x1+0.02x2+0.03x4-12
2005,R3=1.05R2+0.02x2+0.03x4-13
2006,R4=1.05R3+1.02x2+0.03x4-14
2007,R5=1.05R4+0.03x4-16
2008,R6=1.05R5+x3+0.03x4-17
2009,R7=1.05R6+0.03x4-20
2010,R8 =1.05R7+0.03x4-21
2011,R9 =1.05R8+1.03x4-22
2012,R10=1.05R9-24
非负,x1,x2,x3,x4,R1,…,R 10? 0
例 9：购买债券问题补充：动态规划
RUC Information School,Ye Xiang,2007
P89 案例 3.1 养老金的谨慎供应的线性规划模型（解法 2）
1、决策变量（单位：百万美元）
x,2003.1.1 的投资额
xi：债券 i的投资数量 （ i=1,2,3,4） (千份 )
R1,…,R 10,2003－ 2012年各年的余额（年度资本市场基金的存款）
2、目标函数,最小化 2003.1.1投资额 min x
3、约束条件（各年的余额 =上一年的余额（上年资本市场基金）的本金利息＋债券的本金利息－养老金支付，非负）
2003,R1=x-0.98x1-0.92x2-0.75x3-0.8x4-8
2004,R2=1.05R1+1.04x1+0.02x2+0.03x4-12
2005,R3=1.05R2+0.02x2+0.03x4-13
2006,R4=1.05R3+1.02x2+0.03x4-14
2007,R5=1.05R4+0.03x4-16
2008,R6=1.05R5+x3+0.03x4-17
2009,R7=1.05R6+0.03x4-20
2010,R8 =1.05R7+0.03x4-21
2011,R9 =1.05R8+1.03x4-22
2012,R10=1.05R9-24
非负,x,x1,x2,x3,x4,R1,…,R 10? 0
例 9：购买债券问题（续）
补充：动态规划
RUC Information School,Ye Xiang,2007
P89 案例 3.1 养老金的谨慎供应的线性规划模型（解法 3）
1、决策变量（单位：百万美元）
x,2003.1.1 的投资额
xi：债券 i的投资数量 （ i=1,2,3,4） (千份 )
R1,…,R10,2003－ 2012年各年的余额（年度资本市场基金的存款）
2、目标函数：最小化 2003.1.1 投资额 min x
3、约束条件（ 上一年的余额（上年资本市场基金）的本金利息 +债券的本金利息 -各年的余额 =养老金支付,非负）
2003,x-0.98x1-0.92x2-0.75x3-0.8x4-R1=8
2004,1.05R1+1.04x1+0.02x2+0.03x4 -R2=12
2005,1.05R2+0.02x2+0.03x4-R3=13
2006,1.05R3+1.02x2+0.03x4-R4=14
2007,1.05R4+0.03x4-R5 = 16
2008,1.05R5+x3+0.03x4-R6=17
2009,1.05R6+0.03x4-R7= 20
2010,1.05R7+0.03x4-R8 = 21
2011,1.05R8+1.03x4-R9 = 22
2012,1.05R9-R10 =24
非负,x,x1,x2,x3,x4,R1,…,R 10? 0
例 9：购买债券问题（续）
补充：动态规划
RUC Information School,Ye Xiang,2007
例 10：连续投资问题
P136的习题 4.17 （解法 1：书上的解法）
决策变量,At,Bt,Ct,Dt分别表示在 t年的年初可购买得的并且在第 5年年底前投资将收回的各种类型的投资所投入的数量（实际的决策变量为 A1,A2,A3,A4,B1,B2,B3,C2,D5）。同样，用 Rt表示 t年所拥有的但未投出的钱（可以在接下来的年份中投资）（实际是
R1,R2,R3,R4,R5），这样，在 t年年初的投资加上 Rt一定等于那时可以获得的投资的数量（ 连续投资问题 ）。
目标,第 6年年初拥有最多的累积的钱,即 最大化
Max P=R5+1.4A4+1.7B3+1.9C2+1.3D5
约束条件,每年年初的投资额＋未投出的钱 Rt=可用的资金,非负第 1年,A1+B1+R1=60000
第 2年,A2+B2+C2+R2=R1
第 3年,A3+B3+R3=R2+1.4A1
第 4年,A4+R4=R3+1.4A2+1.7B1
第 5年,D5+R5=R4+1.4A3+1.7B2
且 非负,A1,A2,A3,A4,B1,B2,B3,C2,D5,R1,R2,R3,R4,R5? 0
投资项目 第 1年年初 第 2年年初 第 3年年初 第 4年年初 第 5年年初
A(2年期 ) A1 A2 A3 A4
B(3年期 ) B1 B2 B3
C(4年期 ) C2
D(1年期 ) D5
补充：动态规划
RUC Information School,Ye Xiang,2007
P136的习题 4.17 （解法 2：动态规划，利用剩余 Rt）
决策变量,At,Bt,Ct,Dt分别表示在 t年的年初可购买得的并且在第 5年年底前投资将收回的各种类型的投资所投入的数量（实际的决策变量为
A1,A2,A3,A4,B1,B2,B3,C2,D5）。同样，用 Rt表示 t年所拥有的但未投出的钱（可以在接下来的年份中投资）（实际是 R1,R2,R3,R4,R5），这样,在
t年年初的 Rt一定等于可以获得的投资额－投资额。
目标,第 6年年初拥有最多的累积的钱,即 最大化
Max P=R5+1.4A4+1.7B3+1.9C2+1.3D5
约束条件,每年年初未投出的钱 Rt=可用的资金－投资额,非负第 1年,R1=60000－ （ A1+B1）
第 2年,R2=R1－ （ A2+B2+C2）
第 3年,R3=R2+1.4A1－ （ A3+B3）
第 4年,R4=R3+1.4A2+1.7B1－ A4
第 5年,R5=R4+1.4A3+1.7B2 － D5
且 非负,A1,A2,A3,A4,B1,B2,B3,C2,D5,R1,R2,R3,R4,R5?0
例 10：连续投资问题（续）
补充：动态规划
RUC Information School,Ye Xiang,2007
连续投资问题补充练习题
某企业现有资金 200万元，计划在今后 5年内给 A,B,C,D 4
个项目投资。根据有关情况的分析得知：
项目 A：从第一年到第五年每年年初都可进行投资，当年末就能收回本利 110%；
项目 B：从第一年到第四年每年年初都可进行投资，次年末能收回本利 125%，但是要求每年最大投资额不能超过 30万元；
项目 C：若投资则需在第三年年初投资，到第五年末能收回本利
140%，但是限制最大投资额不能超过 80万元；
项目 D：若投资则需在第二年年初投资，到第五年末能收回本利
155%，但是规定最大投资额不能超过 100万元。
问题：应如何确定这些项目的每年投资额，使得第五年年末拥有资金的本利金额为最大？请写数学模型，并用
Excel求解。
补充：动态规划
RUC Information School,Ye Xiang,2007
动态规划在经济管理中的应用－ 资源分配问题
资源分配问题例 11：资源的多元分配例 12：资源的多段分配补充：动态规划
RUC Information School,Ye Xiang,2007
动态规划在经济管理中的应用－ 资源的多元分配
例 11：资源的多元分配某种资源总量为 M，用于进行 n种生产活动，已知用于活动 k的资源量为 uk时收益为 gk(uk),
gk(uk)为 uk的非线性函数，问如何分配资源，
才能使 n种生产活动的总收益最大？
例：某公司拟将 5万元资金投放下属 A,B,C三个企业，各企业在获得资金后的收益如下表所示。求总收益最大的投资分配方案（投资数取整数）
Excel解法：
与 P374的例 2类似投放资金 0 1 2 3 4 5
A 0 2 2 3 3 3
B 0 0 1 2 4 7
C 0 1 2 3 4 5
补充：动态规划
RUC Information School,Ye Xiang,2007
动态规划在经济管理中的应用－ 资源的多段分配
例 12：资源的多段分配资源的多段分配是有消耗的资源多阶段地在两种不同的生产活动中投放的问题。
问题的一般提法是：假设拥有某种总量为 M的资源，计划在 A,B两个部门（或两种生产过程）中连续使用 n个阶段，已知在两个部门中分别投入资源 ua,ub后可分别获得阶段效益为 g(ua),h(ub)，同时知道每生产一个阶段后资源完好率分别为 a和 b（ 0<a<1,0<b<1 ），求 n个阶段间总收益最大的资源分配计划？
例：今有 1000台机床，要投放到 A,B两个生产部门，计划连续使用 3年。已知对 A部门投入 ua台机床时的年收益是 g(ua)=ua2,机器完好率为 a=0.8；相应地，部门为
h(ub)=2ub2,b=0.4。试建立 3年间总收益最大的年度机器分配方案。
结果,ua1＝ 1000,ub2＝ 800,ub3＝ 320,P=2484800
RUC Information School,Ye Xiang,2007
Data,Model and Decisions
数据、模型与决策补充动态规划补充：动态规划
RUC Information School,Ye Xiang,2007
本章内容
动态规划问题概述
动态规划在经济管理中的应用本章的具体内容可以参见胡运权主编,运筹学教程,（
第二版）清华大学出版社,2004.2 第七章 动态规划
，但它不是用 Excel求解，而是用动态规划方法 手工求解 。这里想告诉大家，用 Excel求解动态规划问题非常简单（如第三章 P65案例：大沼泽地金色年代公司的现金流问题）。
也就是说，本章介绍的是用 Excel来求解动态规划问题
,但并没有介绍动态规划方法,有兴趣的同学可以参考国内运筹学书籍中的,动态规划,章节。
补充：动态规划
RUC Information School,Ye Xiang,2007
动态规划问题概述
动态规划 是解决多阶段决策过程最优化问题的一种方法。该方法是由美国数学家贝尔曼 (R Bellman)等人在 20世纪 50年代初提出的。
他们针对多阶段决策问题的特点，提出了解决这类问题的最优化原理，并成功地解决了生产管理、工程技术等方面的许多实际问题，
从而建立了运筹学的一个新分枝，即动态规划。
动态规划是 现代企业管理 中的一个重要决策方法，可用于解决最优路径问题、资源分配问题、生产计划与库存、投资、装载、排序等问题及生产过程的最优控制等。由于它有独特的解题思路，在处理某些优化问题时，比线性规划或非线性规划方法更有效。
多阶段决策过程,是指这样一类特殊的活动过程，它们可以按时间顺序分解成若干互相联系的阶段，称为,时段,,在每一个时段都要做出决策，全部过程的决策是一个决策序列，所以多阶段决策问题属序惯决策问题。
多阶段决策过程最优化的 目标是要达到整个活动过程的总体效果最优 。由于各阶段决策间有机地联系着，本段决策的执行将影响到下一段的决策，以至于影响总体效果，所以决策者在每段决策时不仅考虑本阶段最优，还应考虑对最终目标的影响，从而做出对全局来讲是最优的决策。
补充：动态规划
RUC Information School,Ye Xiang,2007
动态规划在经济管理中的应用
动态规划在经济管理中的应用
最短路线问题（例 1和扩展）－工程线路问题
背包问题（例 2和扩展）
生产经营问题（例 3～例 6）
营业资金管理（例 7～例 10）
资源分配问题（例 11～例 12）
补充：动态规划
RUC Information School,Ye Xiang,2007
动态规划在经济管理中的应用－ 最短路线问题
例 1：最短路线问题－工程线路问题
给定一个线路网络图，要从 A地向 F地铺设一条输油管道，各点间连线上的数字表示距离，问应选择什么路线，可使总距离最短?
在 Excel中的解法：用第七章网络最优化问题的 7.4节最短路问题（ P257,A节点为源,F节点为目的地）
最短路线问题的扩展,货郎担问题和中国邮路问题（我们已经讲过）
5
A
B1
B2
C2
C3
C1
C4
D2
D3
D1 E1
E2
F
7
5
2
3
6
8
4
7
8
4
5
3
4
8
4
3
5
6
2
1
3
4
3
补充：动态规划
RUC Information School,Ye Xiang,2007
动态规划在经济管理中的应用－ 背包问题
例 2：背包问题
一位旅行者携带背包去登山，已知他所能承受的背包重量限度为 a千克，现有 n种物品可供他选择装入背包，第 i种物品的单件重量为 ai千克，其价值（可以是表明本物品对登山的重要性的数量指标）是携带数量 xi的函数 cixi（ i=1,2,…,n），问旅行者应该如何选择携带各种物品的件数，以使总价值最大？ (背包问题等同于车、船、人造卫星等工具的最优装载等，有广泛的实际意义 )
代数模型（一维背包问题）：
设 xi为第 i种物品装入的件数，则整数规划模型：
目标 (总价值最大 ),Max P=?cixi
总重量约束,?aixi? a
非负约束,xi? 0 且为整数（ i=1,2,…,n）
在 Excel中的解法：用本书 9.1节的一般整数规划
背包问题的扩展
当 xi仅表示装入 (取 1)和不装 (取 0)第 i种物品，则本模型就是 0-1背包问题。
多维背包问题：当约束条件不止一个时，如多总体积的限制等。
补充：动态规划
RUC Information School,Ye Xiang,2007
动态规划在经济管理中的应用－ 0-1背包问题
背包问题的扩展,0-1背包问题某人准备外出旅游，行装中有 A,B,C,D,E共 5件备选物品，其重量和价值如表所示，假定行李总重不得超过 13Kg，求总价值最大的行李构成方案。
物品 A B C D E
重量 /Kg 7 5 4 3 1
价值 /百元 9 4 3 2 0.5
数学模型：
设 xi为第 i种物品是否装入（ 1-是,0-
否），则 0-1整数规划模型：
目标 (总价值最大 )：
Max P=9x1+4x2+3x3+2x4+0.5x5
重量约束,7x1+5x2+4x3 +3x4+x5?13
0-1约束,xi为 0或 1（ i=1,2,3,4,5）
补充：动态规划
RUC Information School,Ye Xiang,2007
动态规划在经济管理中的应用－ 多维背包问题
背包问题的扩展,多维背包问题现有一辆载重 w=5t，最大装载体积 v=8m3卡车作为运输工具，可装载三种货物，已知每种货物各 8件，其他有关信息如表所示，求携带货物价值最大的装载方案。
货物品种 k
单件货物重量
wk/t
单件货物体积
vk/m3
单件货物价值
pk/万元
1 1 2 30
2 3 4 75
3 2 3 60
数学模型：
设 xk为第 k种物品装入的件数，则整数规划模型：
目标 (总价值最大 )：
Max P=30x1+75x2+60x3
重量约束,x1+3x2+2x3? 5
体积约束,2x1+4x2+3x3? 8
货物件数,xk? 8 (k=1,2,3)
非负约束,xk? 0 且为整数 (k=1,2,3)
补充：动态规划
RUC Information School,Ye Xiang,2007
动态规划在经济管理中的应用－ 生产经营问题
在生产和经营中，经常遇到如何合理安排生产计划、采购计划以及仓库的存货计划和销售计划，使总效益最大的问题。以下是几个例子
例 3,P206 生产进度安排（动态规划方法）
例 4：生产与库存问题（动态规划的另外一种写法：网络最优化中的最小费用流问题）
例 5,P87 习题 3.3（多种解法）
例 6：采购与销售问题补充：动态规划
RUC Information School,Ye Xiang,2007
动态规划在经济管理中的应用
－ 生产经营问题（续）
例 3,P206 生产进度安排（动态规划方法）
在 Excel中的解法，主要利用：
本月剩余量 Ri=上月剩余量 Ri -1＋
本月生产量（ xi+yi）－
本月计划安装量 Ni
具体见本章的,补充－动态规划问题,的
Excel文件。
补充：动态规划
RUC Information School,Ye Xiang,2007
动态规划在经济管理中的应用
－ 生产经营问题（续）
例 4 生产与库存问题康托斯毛毯厂是一个小型的生产商，致力于生产家用和办公用的毛毯。紧接的 4个季度的生产能力、市场需求、每平方米的生产成本以及库存成本如下表所示。特别需要注意的是生产能力、市场需求、每平方米的生产成本每个季度都会产生变化。关键是库存成本从一个季度到下一个季度持续在每平方米 0.25美元。康托斯毛毯厂要决定在这 4个季度里每季度生产多少平方米的毛毯，
能使总生产和库存成本最小。
季度 生产能力(平方米 ) 市场需求(平方米 ) 生产成本(美元 /平方米 ) 库存成本(美元 /平方米 )
1 600 400 2 0.25
2 300 500 5 0.25
3 500 400 3 0.25
4 400 400 3 0.25
补充：动态规划
RUC Information School,Ye Xiang,2007
例 4 生产与库存问题 (续 )
网络流中需求节点的流入和流出量导致这个模型成为一个转运模型（ 网络最优化问题中的最小费用流问题 ）
我们通过建立一个流图来代表这个问题。首先根据 4个季节建立 4个产量节点和 4个需求节点。每个产量节点由一个流出弧连接对应的需求节点。弧的流量代表了这时期所生产的毛毯。相对于每个需求节点，一个流出弧代表了库存的数量，即供给下季度需求节点的数量。下图显示了这个网络模型。
1季度产量
3季度产量
2季度产量
4季度产量生产节点
1季度需求
3季度需求
2季度需求
4季度需求需求节点
600
300
500
400
400
500
400
400
2
5
3
3
0.25
0.25
0.25
决策变量,（图中弧的流量）
4个季度的生产量 xi(i=1,2,3,4)，
前 3个季度库存量 Ri (i=1,2,3)
目标,Min C=2x1+5x2+3x3＋ 3x4＋
0.25(R1+R2+R3)
约束条件：
生产能力,x1? 600,x2?300，
x3? 500,x4?400
第一季度需求,x1 － R1 ＝ 400
第二季度需求,x2 ＋ R1 － R2 ＝ 500
第三季度需求,x3 ＋ R2 － R3 ＝ 400
第四季度需求,x4 ＋ R3 ＝ 400
非负,xi?0(i=1,2,3,4),Ri? 0(i=1,2,3)
补充：动态规划
RUC Information School,Ye Xiang,2007
生产与库存问题补充练习题
设有一生产部门，生产计划周期分为 3个阶段，已知最初库存为 1,3个阶段的产量需求分别为 3,4,3，生产的固定成本为 8，单位产品的费用为 2，单位产品的阶段库存费用为 2，库存容量为 4，阶段生产能力为 6，问应如何安排各阶段的生产，使计划期内的费用总和最小？请写数学模型，并用 Excel求解。
提示：比较难，有固定成本，是一个综合题
结果：（ 2,4,3),Min C=42
补充：动态规划
RUC Information School,Ye Xiang,2007
（解法 1：书上的解法，动态规划，利用剩余 Rt）
决策变量,4个季度靴子的生产数量 x1,x2,x3,x4；
4个季度靴子的库存量 R1,R2,R3,R4
目标 利润最大 Max P=20（ 3000＋ 4000＋ 8000＋ 7000） － 8（ R1+R2+R3+R4）
约束条件,用,本月库存量＝上月库存＋本月生产－本月需求,
一季度,R1＝ 1000+x1-3000
二季度,R2＝ R1+x2-4000
三季度,R3＝ R2+x3-8000
四季度,R4＝ R3+x4-7000
最大生产量,xi? 6000（ i＝ 1,2,3,4）
非负,xi?0（ i＝ 1,2,3,4）,Ri?0（ i＝ 1,2,3,4）
例 5,P87 习题 3.3
补充：动态规划
RUC Information School,Ye Xiang,2007
（解法 2：网络最优化中的流量，也利用剩余 Rt）
决策变量,x1,x2,x3,x4：每季度靴子的生产数量
R1,R2,R3：每季度靴子的库存量目标 利润最大 Max P=20（ 3000＋ 4000＋ 8000＋ 7000） － 8（ R1+R2+R3）
约束条件,用,上月库存＋本月生产－本月库存量＝本月需求,
一季度,1000+x1－ R1＝ 3000
二季度,R1+x2－ R2 ＝ 4000
三季度,R2+x3－ R3 ＝ 8000
四季度,R3+x4 ＝ 7000
最大生产量,xi? 6000（ i＝ 1,2,3,4）
非负,xi?0（ i＝ 1,2,3,4）,Ri?0（ i＝ 1,2,3）
例 5,P87 习题 3.3（续）
补充：动态规划
RUC Information School,Ye Xiang,2007
（解法 3：没有利用剩余 Rt，而是直接代入 ）
决策变量,设 x1,x2,x3,x4：每季度靴子的生产数量目标 利润最大 Max P=20（ 1000+x1+x2+x3+x4） － 8（ 1000+x1-3000）
－ 8（ 1000+x1-3000＋ x2-4000）
－ 8（ 1000+x1-3000＋ x2-4000+x3-8000）
约束条件,用,上月剩余＋本月生产? 需求量,
一季度,1000+x1? 3000
二季度,1000+x1-3000+x2? 4000
三季度,1000+x1-3000+x2-4000+x3? 8000
四季度,1000+x1-3000+x2-4000+x3-8000+x4 ＝ 7000
最大生产量,xi? 6000（ i＝ 1,2,3,4）
非负,xi? 0（ i＝ 1,2,3,4）
例 5,P87 习题 3.3（续）
补充：动态规划
RUC Information School,Ye Xiang,2007
（解法 4：没有利用剩余 Rt，而是直接代入 ）
决策变量,设 x1,x2,x3,x4：每季度靴子的生产数量目标 利润最大 Max P=20（ 1000+x1+x2+x3+x4） － 8（ 1000+x1-3000）
－ 8（ 1000+x1＋ x2-3000-4000）
－ 8（ 1000+x1＋ x2+x3-3000-4000-8000）
约束条件,用,累计生产量? 累计需求量,
一季度,1000+x1? 3000
二季度,1000+x1+x2? 3000+4000
三季度,1000+x1+x2+x3? 3000+4000+8000
四季度,1000+x1+x2+x3+x4 = 3000+4000+8000+7000
最大生产量,xi? 6000（ i＝ 1,2,3,4）
非负,xi? 0（ i＝ 1,2,3,4）
例 5,P87 习题 3.3（续）
补充：动态规划
RUC Information School,Ye Xiang,2007
动态规划在经济管理中的应用
－ 生产经营问题（续）
例 6：采购与销售问题某商店在未来的 4个月里，准备利用它的一个仓库来专门经销某种商品，仓库的最大容量能储存这种商品 1000单位。
假定该商品每月只能出卖仓库现有的货。当商店在某月购货时，下月初才能到货。预测该商品未来四个月的买卖价格如下表所示，假定商店在一月开始经销时，仓库储有该商品 500单位。试问若不计库存费用，该商店应如何制定 1
月至 4月的订购与销售计划，使预期获利最大。
在 Excel中的解法，主要利用：
月初库存 Sk＝上月库存 Sk－ 1－
上月卖出 Xk－ 1 ＋
上月订货 Yk－ 1,
具体见本章的,补充－动态规划问题,的 Excel文件
。
补充：动态规划
RUC Information School,Ye Xiang,2007
动态规划在经济管理中的应用－ 资金管理
资金管理例 7：流动资金管理（ 将多余的现金存入银行,以获取利息 ）
例 8：贷款问题（ P65的 3.1案例研究,
大沼泽地金色年代公司的现金流问题）
例 9：购买债券问题（ P89 案例 3.1 养老金的谨慎供应）
例 10：连续投资问题（ P136习题 4.17）
补充：动态规划
RUC Information School,Ye Xiang,2007
动态规划在经济管理中的应用－ 资金管理
例 7,流动资金管理：如何进行计划管理
在保证流动资金的情况下（每月现金余额不少于
10万），将多余的现金存入银行（有 1个月,3个月,6个月定存）以获取利息
目标：半年的资金优化计划（半年后，存入银行的钱全部到期。注意是每月初存入银行），使总利息收益最大化
已知：刚开始有 40万（ 400000）现金和每月的现金支出额
在 Excel中的解法：利用到期定存本金和到期定存利息与 1个月,3个月,6个月定存间的关系（
存几个月后取出），具体见本章的,补充－动态规划问题,的 Excel文件。
补充：动态规划
RUC Information School,Ye Xiang,2007
第 3章 电子表格建模的艺术
（ 动态规划－利用每个阶段的剩余量 Ri）
3.1 案例研究,大沼泽地金色年代公司的现金流问题
有两种不同的贷款：
10年长期贷款，年利率 7%，只能在 2003年初贷 1次，以后每年还息（ 10次），第 10年后还本
1年短期贷款，年利率 10%，可以在 2003－ 2012年初贷，可贷 10次，下一年还本付息
问题：如何贷款（贷款组合），使得公司在 10年内可以正常运转。目前公司只有 100万美元，每年的现金储备最少 50万美元，已知公司未来 10年的净现金流（预测），并希望在
2013年年初的现金余额最多（目标）。
例 8：贷款问题补充：动态规划
RUC Information School,Ye Xiang,2007
3.1 案例研究,大沼泽地金色年代公司的现金流问题的线性规划模型
1、决策变量（单位：百万美元）
x,2003年初贷的 10年长期贷款额,y1,…,y 10,2003－ 2012年初贷的 1年期贷款额，
R1,…,R 11,2003－ 2013年初的现金余额
2、目标：最大化 2013年年初的现金余额 Max R11
3、约束条件（每年的现金余额＝上年的现金余额＋现金流＋贷款（长期、短期）－还款（长期、短期的利息和本金，非负，每年的现金储备最少 50万美元）
2003,R1＝ 1 － 8 ＋ x＋ y1
2004,R2＝ R1 － 2 ＋ y2－ 0.07x－ 1.1y1
2005,R3＝ R2 － 4 ＋ y3－ 0.07x－ 1.1y2
2006,R4＝ R3 ＋ 3 ＋ y4－ 0.07x－ 1.1y3
2007,R5＝ R4 ＋ 6 ＋ y5－ 0.07x－ 1.1y4
2008,R6＝ R5 ＋ 3 ＋ y6－ 0.07x－ 1.1y5
2009,R7＝ R6 － 4 ＋ y7－ 0.07x－ 1.1y6
2010,R8＝ R7 ＋ 7 ＋ y8－ 0.07x－ 1.1y7
2011,R9＝ R8 － 2 ＋ y9－ 0.07x－ 1.1y8
2012,R10＝ R9 ＋ 10 ＋ y10－ 0.07x－ 1.1y9
2013,R11＝ R10 － 1.07x－ 1.1y10
非负,x? 0,yi?0 （ i=1,2,…,10 ）
每年的现金储备 Ri?0.5 （ i=1,2,…,11 ）
例 8：贷款问题（续）
补充：动态规划
RUC Information School,Ye Xiang,2007
P89 案例 3.1 养老金的谨慎供应的线性规划模型（解法 1）
1、决策变量（单位：百万美元）
xi：债券 i的投资数量 （ i=1,2,3,4） (千份 )
R1,…,R 10,2003－ 2012年各年的余额（年度资本市场基金的存款）
2、目标函数：最小化 2003.1.1总投入 min C=0.98x1+0.92x2+0.75x3+0.8x4+8+R1
3、约束条件（各年的余额 =上一年的余额（上年资本市场基金）的本金利息＋债券的本金利息－养老金支付，非负）
2004,R2=1.05R1+1.04x1+0.02x2+0.03x4-12
2005,R3=1.05R2+0.02x2+0.03x4-13
2006,R4=1.05R3+1.02x2+0.03x4-14
2007,R5=1.05R4+0.03x4-16
2008,R6=1.05R5+x3+0.03x4-17
2009,R7=1.05R6+0.03x4-20
2010,R8 =1.05R7+0.03x4-21
2011,R9 =1.05R8+1.03x4-22
2012,R10=1.05R9-24
非负,x1,x2,x3,x4,R1,…,R 10? 0
例 9：购买债券问题补充：动态规划
RUC Information School,Ye Xiang,2007
P89 案例 3.1 养老金的谨慎供应的线性规划模型（解法 2）
1、决策变量（单位：百万美元）
x,2003.1.1 的投资额
xi：债券 i的投资数量 （ i=1,2,3,4） (千份 )
R1,…,R 10,2003－ 2012年各年的余额（年度资本市场基金的存款）
2、目标函数,最小化 2003.1.1投资额 min x
3、约束条件（各年的余额 =上一年的余额（上年资本市场基金）的本金利息＋债券的本金利息－养老金支付，非负）
2003,R1=x-0.98x1-0.92x2-0.75x3-0.8x4-8
2004,R2=1.05R1+1.04x1+0.02x2+0.03x4-12
2005,R3=1.05R2+0.02x2+0.03x4-13
2006,R4=1.05R3+1.02x2+0.03x4-14
2007,R5=1.05R4+0.03x4-16
2008,R6=1.05R5+x3+0.03x4-17
2009,R7=1.05R6+0.03x4-20
2010,R8 =1.05R7+0.03x4-21
2011,R9 =1.05R8+1.03x4-22
2012,R10=1.05R9-24
非负,x,x1,x2,x3,x4,R1,…,R 10? 0
例 9：购买债券问题（续）
补充：动态规划
RUC Information School,Ye Xiang,2007
P89 案例 3.1 养老金的谨慎供应的线性规划模型（解法 3）
1、决策变量（单位：百万美元）
x,2003.1.1 的投资额
xi：债券 i的投资数量 （ i=1,2,3,4） (千份 )
R1,…,R10,2003－ 2012年各年的余额（年度资本市场基金的存款）
2、目标函数：最小化 2003.1.1 投资额 min x
3、约束条件（ 上一年的余额（上年资本市场基金）的本金利息 +债券的本金利息 -各年的余额 =养老金支付,非负）
2003,x-0.98x1-0.92x2-0.75x3-0.8x4-R1=8
2004,1.05R1+1.04x1+0.02x2+0.03x4 -R2=12
2005,1.05R2+0.02x2+0.03x4-R3=13
2006,1.05R3+1.02x2+0.03x4-R4=14
2007,1.05R4+0.03x4-R5 = 16
2008,1.05R5+x3+0.03x4-R6=17
2009,1.05R6+0.03x4-R7= 20
2010,1.05R7+0.03x4-R8 = 21
2011,1.05R8+1.03x4-R9 = 22
2012,1.05R9-R10 =24
非负,x,x1,x2,x3,x4,R1,…,R 10? 0
例 9：购买债券问题（续）
补充：动态规划
RUC Information School,Ye Xiang,2007
例 10：连续投资问题
P136的习题 4.17 （解法 1：书上的解法）
决策变量,At,Bt,Ct,Dt分别表示在 t年的年初可购买得的并且在第 5年年底前投资将收回的各种类型的投资所投入的数量（实际的决策变量为 A1,A2,A3,A4,B1,B2,B3,C2,D5）。同样，用 Rt表示 t年所拥有的但未投出的钱（可以在接下来的年份中投资）（实际是
R1,R2,R3,R4,R5），这样，在 t年年初的投资加上 Rt一定等于那时可以获得的投资的数量（ 连续投资问题 ）。
目标,第 6年年初拥有最多的累积的钱,即 最大化
Max P=R5+1.4A4+1.7B3+1.9C2+1.3D5
约束条件,每年年初的投资额＋未投出的钱 Rt=可用的资金,非负第 1年,A1+B1+R1=60000
第 2年,A2+B2+C2+R2=R1
第 3年,A3+B3+R3=R2+1.4A1
第 4年,A4+R4=R3+1.4A2+1.7B1
第 5年,D5+R5=R4+1.4A3+1.7B2
且 非负,A1,A2,A3,A4,B1,B2,B3,C2,D5,R1,R2,R3,R4,R5? 0
投资项目 第 1年年初 第 2年年初 第 3年年初 第 4年年初 第 5年年初
A(2年期 ) A1 A2 A3 A4
B(3年期 ) B1 B2 B3
C(4年期 ) C2
D(1年期 ) D5
补充：动态规划
RUC Information School,Ye Xiang,2007
P136的习题 4.17 （解法 2：动态规划，利用剩余 Rt）
决策变量,At,Bt,Ct,Dt分别表示在 t年的年初可购买得的并且在第 5年年底前投资将收回的各种类型的投资所投入的数量（实际的决策变量为
A1,A2,A3,A4,B1,B2,B3,C2,D5）。同样，用 Rt表示 t年所拥有的但未投出的钱（可以在接下来的年份中投资）（实际是 R1,R2,R3,R4,R5），这样,在
t年年初的 Rt一定等于可以获得的投资额－投资额。
目标,第 6年年初拥有最多的累积的钱,即 最大化
Max P=R5+1.4A4+1.7B3+1.9C2+1.3D5
约束条件,每年年初未投出的钱 Rt=可用的资金－投资额,非负第 1年,R1=60000－ （ A1+B1）
第 2年,R2=R1－ （ A2+B2+C2）
第 3年,R3=R2+1.4A1－ （ A3+B3）
第 4年,R4=R3+1.4A2+1.7B1－ A4
第 5年,R5=R4+1.4A3+1.7B2 － D5
且 非负,A1,A2,A3,A4,B1,B2,B3,C2,D5,R1,R2,R3,R4,R5?0
例 10：连续投资问题（续）
补充：动态规划
RUC Information School,Ye Xiang,2007
连续投资问题补充练习题
某企业现有资金 200万元，计划在今后 5年内给 A,B,C,D 4
个项目投资。根据有关情况的分析得知：
项目 A：从第一年到第五年每年年初都可进行投资，当年末就能收回本利 110%；
项目 B：从第一年到第四年每年年初都可进行投资，次年末能收回本利 125%，但是要求每年最大投资额不能超过 30万元；
项目 C：若投资则需在第三年年初投资，到第五年末能收回本利
140%，但是限制最大投资额不能超过 80万元；
项目 D：若投资则需在第二年年初投资，到第五年末能收回本利
155%，但是规定最大投资额不能超过 100万元。
问题：应如何确定这些项目的每年投资额，使得第五年年末拥有资金的本利金额为最大？请写数学模型，并用
Excel求解。
补充：动态规划
RUC Information School,Ye Xiang,2007
动态规划在经济管理中的应用－ 资源分配问题
资源分配问题例 11：资源的多元分配例 12：资源的多段分配补充：动态规划
RUC Information School,Ye Xiang,2007
动态规划在经济管理中的应用－ 资源的多元分配
例 11：资源的多元分配某种资源总量为 M，用于进行 n种生产活动，已知用于活动 k的资源量为 uk时收益为 gk(uk),
gk(uk)为 uk的非线性函数，问如何分配资源，
才能使 n种生产活动的总收益最大？
例：某公司拟将 5万元资金投放下属 A,B,C三个企业，各企业在获得资金后的收益如下表所示。求总收益最大的投资分配方案（投资数取整数）
Excel解法：
与 P374的例 2类似投放资金 0 1 2 3 4 5
A 0 2 2 3 3 3
B 0 0 1 2 4 7
C 0 1 2 3 4 5
补充：动态规划
RUC Information School,Ye Xiang,2007
动态规划在经济管理中的应用－ 资源的多段分配
例 12：资源的多段分配资源的多段分配是有消耗的资源多阶段地在两种不同的生产活动中投放的问题。
问题的一般提法是：假设拥有某种总量为 M的资源，计划在 A,B两个部门（或两种生产过程）中连续使用 n个阶段，已知在两个部门中分别投入资源 ua,ub后可分别获得阶段效益为 g(ua),h(ub)，同时知道每生产一个阶段后资源完好率分别为 a和 b（ 0<a<1,0<b<1 ），求 n个阶段间总收益最大的资源分配计划？
例：今有 1000台机床，要投放到 A,B两个生产部门，计划连续使用 3年。已知对 A部门投入 ua台机床时的年收益是 g(ua)=ua2,机器完好率为 a=0.8；相应地，部门为
h(ub)=2ub2,b=0.4。试建立 3年间总收益最大的年度机器分配方案。
结果,ua1＝ 1000,ub2＝ 800,ub3＝ 320,P=2484800
