文档介绍：动态规划
1
一、多阶段决策问题
(Multi-Stage decision process)
多阶段决策过程特点:
状态
x1
阶段1
T1
决策u1
状态
x2
决策u2
阶段2
T2
状态
x3
...
状态
xk
决策uk
阶段k
Tk
状态
xk+1
...
状态
xn
决策un
阶段n
Tn
状态
xn+1
多阶段决策过程的最优化
2
多阶段决策过程的最优化
动态规划方法与“时间”关系很密切,随着时间过程的发展而决定各时段的决策,产生一个决策序列,这就是“动态”的意思。然而它也可以处理与时间无关的静态问题,只要在问题中人为地引入“时段”因素,就可以将其转化为一个多阶段决策问题。在本章中将介绍这种处理方法。
3
多阶段决策过程的最优化
二、多阶段决策问题举例
属于多阶段决策类的问题很多,例如:
1)工厂生产过程:由于市场需求是一随着时间而变化的因素,因此,为了取得全年最佳经济效益,就要在全年的生产过程中,逐月或者逐季度地根据库存和需求情况决定生产计划安排。
4
2)设备更新问题:一般企业用于生产活动的设备,刚买来时故障少,经济效益高,即使进行转让,处理价值也高,随着使用年限的增加,就会逐渐变为故障多,维修费用增加,可正常使用的工时减少,加工质量下降,经济效益差,并且,使用的年限越长、处理价值也越低,自然,如果卖去旧的买新的,,使总的经济效益最好。
5
3)连续生产过程的控制问题:一般化工生产过程中,常包含一系列完成生产过程的设备,前一工序设备的输出则是后一工序设备的输入,因此,应该如何根据各工序的运行工况,控制生产过程中各设备的输入和输出,以使总产量最大。
6
许多问题的发展过程都与时间因素有关。在这类多阶段决策问题中,阶段的划分常取时间区段来表示,并且各个阶段上的决策往往也与时间因素有关。这就使它具有了“动态”的含义,所以把处理这类动态问题的方法称为动态规划方法。
实际中尚有许多不包含时间因素的一类“静态”决策问题,就其本质而言是一次决策问题,是非动态决策问题,但是也可以人为地引入阶段的概念当作多阶段决策问题,应用动态规划方法加以解决。
7
4)资源分配问题:资源分配问题便属于这类静态问题。如:某工业部门或公司,拟对其所属企业进行稀缺资源分配,为此需要制定出收益最大的资源分配方案。这种问题原本要求一次确定出对各企业的资源分配量,它与时间因素无关,不属动态决策,但是,我们可以人为地规定一个资源分配的阶段和顺序,从而使其变成一个多阶段决策问题(后面我们将详细讨论这个问题)。
8
多阶段决策过程的最优化
5)运输网络问题:如图5-1所示的运输网络,点间连线上的数字表示两地距离(也可是运费、时间等),要求从fk(sk)至v10的最短路线。
这种运输网络问题也是静态决策问题。但是,按照网络中点的分布,可以把它分为4个阶段,而作为多阶段决策问题来研究。
9
多阶段决策过程的最优化
三、动态规划求解的多阶段决策问题的特点
通常多阶段决策过程的发展是通过状态的一系列变换来实现的。
一般情况下,系统在某个阶段的状态转移除与本阶段的状态和决策有关外,还可能与系统过去经历的状态和决策有关。
适合于用动态规划方法求解的只是一类特殊的多阶段决策问题,即具有“无后效性”的多阶段决策过程。
10