文档介绍：动态规划
动态规划是贝尔曼(Bellman)在五十年代为解决多级决策过程而提出来的。它可以解决很多领域中的问题,如生产过程的决策,收益和投资问题,有多级反应器的化工装置的设计,多级轧钢机的最速轧制问题,资源分配、机器负荷分配、生产计划编制,特别是控制工程问题。
它和极小值原理一样,可解决控制变量受约束的最优控制问题,而且在这两种方法之间存在某种内在的联系。动态规划的中心思想是利用所谓“最优性原理”,把一个级决策过程化为个单级决策过程,从而使问题简单。
多级决策的例子——最短时间问题
设有人要从点开车到站,中间要经过任意三个中间站,站名在图中圆圈内表示。站与站之间称为段,每段路程所需时间(小时)标在段上。现要问,这人应如何选择路线才能最快到达目的地?
为了便于理解动态规划的思想,我们来研究图6-1所示的最短时间问题。
图6-1 按最短时间的路径选择
(一)穷举法
从走到一共有六条路线,每条路线由四段组成。这六条路线和对应的行车时间如下
路线行车时间(小时)
13
11
14
13
12
9
显然最优路线是,它所花时间为9小时。
这里每条路线由四段组成,也可以说是四级决策。
为了计算每条路线所花时间,要做三次加法运算,为了计算六条路线所花的时间要作3×6=18次运算。这种方法称为“穷举法”。
显然当段数很多时,计算量是很大的。这种方法的特点是从起点站往前进行,而且把这四级决策一起考虑。应注意从到下一站所花的时间为1,而到所花时间为3,但最优路线却不经过。
这说明只看下一步的“眼前利益”来作决策是没有意义的。
(二)动态规划法
为将问题表达得清楚,引进下面的术语。
令表示由某点到终点的段数(如到为2段)。
令表示当前所处点的位置(如),称为状态变量。
令为决策(控制)变量,它表示当处在位置而还有段要走时,所要选取的下一点。
例如,从出发,下一点为时,则表示为
。
令表示在位置,向终点还有段要走时,由到终点的最短时间。
例如,从C2到E的最短时间为4,可表示为
T2(C2)=4。