E2
6 6
F1
1 3
F1
1 3
G1 G2
4
G1
3
4 B 3
A 5 4
E1
6 6 F2
B B B B B B B
16 16 17 14
2 4
G1 G2
4 3
F1 4 5 F2
1 3
G1 G2
4 3
2 4
S1 k =1 S2 k =2
S3 k=3
S4 k =4 S5
G1 G2
4 3
16 17
第6 第 6页 页
资源分配问题
假设有一种资源其数量为a，现将它分配给n 个使用者。若分配给第i个使用者的数量为xi（i=1，…，n） ，产生的相应收益为gi（xi），问如何分配使总收益最大？
第 12 第 12页 页
《决策理论与方法》
（生产—库存问题）：某工厂要对一种产品制定今后四个时期的
生产计划，据估计在今后四个时期内，市场对该产品的需求量分 别为 2 ， 3 ， 2 ， 4 单位，假设每批产品固定成本为 3 千元，若不生 产为0，每单位产品成本为1千元，每个时期最大生产能力不超过 6个单位，每期期末未出售产品，每单位需付存贮费0.5千元，假 定第 1期初和第 4期末库存量均为 0，问该厂如何安排生产与库存 ，可在满足市场需求的前提下总成本最小。
决策理论与方法 （Decision Making Theory and Methods）
经济管理学院 靳晨霞
《决策理论与方法》
第四章
动态决策分析
第2 第 2页 页
学习目的

《决策理论与方法》
了解多阶段决策、序贯决策的概念及特点； 掌握动态规划与决策树方法及其在多阶段决策、 序贯决策中的应用。
第 13 第 13页 页
《决策理论与方法》
背包问题
有人携带背包上山，其可携带物品的重量限度为 a公斤，现有 n种物品可供选择，设第 i种物品的单件重量为 ai公斤，其在上山过程中的价值是携带数量xi的函数ci（xi） ，问应如何安排携带各种物品的数量，使总价值最大。
第 14 第 14页 页
r a, E2 f E2
《决策理论与方法》
r a, E2 f E2
图4-1-3 最优性原理示意图
第 10 第 10页 页
《决策理论与方法》
动态规划的基本思想：
1、 将多阶段决策问题按照空间或时间顺序划分成相互联
系的阶段，即把一个大问题分解成一族同类型的子问题， 选取恰当的状态变量和决策变量，写出状态转移方程，定 义最优指标函数，写出递推关系式和边界条件。
4.1 动态决策的基本原理
4.1.2 决策树
《决策理论与方法》
决策树(decision tree)就是将决策过程各个阶段 之间的结构绘制成一张箭线图，每个决策或事件（即 自然状态）都可能引出两个或多个事件，导致不同的 结果。 决策树的构成有四个要素：1)决策结点；2)方案 枝；3)状态结点；4)概率枝。
第 11 第 11页 页
《决策理论与方法》
动态规划问题的典型例子： 机有两种生产任务。据经验，把机器x1台投入第 一种生产任务，则在一个生产周期中将有 1/3 x 1 台机器报废 ；余下的机器全部投入第二种生产任务，则有1/10的机器报 废，如果干第一种生产任务每台机器可以收益 10 ，干第二 种生产任务每台机器可以收益 7，问怎样分配机器使总收益 最大？
（库存—销售问题） 设某公司计划在1至4月份从事某种商品经营
。已知仓库最多可存储 600 件这种商品，已知 1月初存货 200 件， 根据预测知1至4月份各月的单位购货成本及销售价格，每月只能 销售本月初的库存，当月进货供以后各月销售，问如何安排进货 量和销售量，使该公司四个月获得利润最大（假设四月底库存为 零）
《决策理论与方法》
第7 第 7页 页
《决策理论与方法》
第8 第 8页 页
《决策理论与方法》
第9 第 9页 页
r a, E2 f E2
4.1 动态决策的基本原理
4.1.1 动态规划 最 优 性 原 理 （ t h e principle of optimality）也 称为Bellman原理，是R. Bellman提出的DP的基本原 理，其表述为：“一个过程 的最优策略具有这样的性质 ，即无论初始状态和初始决 策如何，对于由前面的决策 所形成的状态来说，其后各 阶段的决策序列必定构成相 应子过程的最优策略”。
第5 第 5页 页
4.1 动态决策的基本原理
4.1.1 动态规划
《决策理论与方法》
例4-1-1 最优线路问题。由水源地A向城市B的输水线路需 通过3个控制点，每个控制点均有两个可选方案，每段线路的输 水费用如下图所示。选出一条输水线路，使得总输水费用最小 。 B 费用：
E1 4 A 5 E2 4 5 F2 2 4 G2
第3 第 3页 页
本讲内容
4.1 动态决策的基本原理 4.2 多阶段决策 4.3 序贯决策
《决策理论与方法》
第4 第 4页 页
4.1 动态决策的基本原理
4.1.1 动态规划
《决策理论与方法》
动态规划（dynamic Programming，DP）是解决多阶 段决策过程最优化的一种方法，是考察问题的一种途径， 而不是一种算法，不像LP那样有一个标准的数学表达式 和明确定义的一组规则，必须具体问题具体分析。其基本 思路是将多阶段决策过程转化为一系列相互关联的单阶段 问题，并依次求解。DP的适用范围比较广，对目标函数 和约束条件没有严格的要求。 DP是离散系统最优化的一种有效工具，目前动态规划 已广泛用于工业、农业、工程技术、资源、环境、经济、 社会等领域。 DP也有一定的局限性。没有标准的模型和 算法，必须根据具体的问题来确定其求解方法；当系统状 态变量个数太大时，受计算机存储量和计算速度的限制可 能无法求解。
2、 从边界条件开始，由后向前逐段递推寻找最优，在每
一个阶段的计算中都要用到前一阶段的最优结果，依次进 行，求得最后一个子问题的最优解就是整个问题的最优解 。
3、 在多阶段决策过程中，确定阶段k的最优决策时，不是
只考虑本阶段最优，而是要考虑本阶段及其所有后部子过 程的整体最优，也就是说，它是把当前效益和未来效益结 合起来考虑的一种方法。