第六章 动态规划.doc

第六章动态规划
第六章动态规划
动态规划是运筹学的一个分支,它是解决多阶段决策过程最优化的一种数学方法。大约产生于50年代。1951年美国数学家贝尔曼(R3>.Bellman)等人,根据一类多阶段决策问题的特点,把多阶段决策问题变换为一系列互相联系单阶段问题,然后逐个加以解决。与此同时,他提出了解决这类问题的“最优性原理”,研究了许多实际问题,从而创建了解决最优化问题的一种新的方法——动态规划。他的名著“动态规划”于1957年出版,该书是动态规划的第一本著作。
动态规划的方法,在工程技术、企业管理、工农业生产及军事等部门中都有广泛的应用,并且获得了显著的效果。在企业管理方面,动态规划可以用来解决最优路径问题、资源分配问题、生产调度问题、库存问题、装载问题、排序问题、设备更新问题、生产过程最优控制问题等等,所以它是现代企业管理中的一种重要的决策方法。许多问题用动态规划的方法去处理,常比线性规划或非线性规划更有成效。特别对于离散性的问题,由于解析数学无法施展其术,而动态规划的方法就成为非常有用的工具。应指出,动态规划是求解某类问题的一种方法,是考察问题的一种途径,而不是一种特殊算法(如线性规划是一种算法)。因而,它不象线性规划那样有一个标准的数学表达式和明确定义的一组规则,而必须对具体问题进行具体分析处理。因此,读者在学习时,除了要对基本概念和方法正确理解外,应以丰富的想象力去建立模型,用创造性的技巧去求解。
动态规划模型的分类,根据多阶段决策过程的时间参量是离散的还是连续的变量,过程分为离散决策过程和连续决策过程。根据决策过程的演变是确定性的还是随机性的,过程又可分为确定性决策过程和随机性决策过程。组合起来就有离散确定性、离散随机性、连续确定性、连续随机性四种决策过程模型。
本部分主要研究离散决策过程,介绍动态规划的基本概念、理论和方法,并通过几个典型的问题来说明它的应用,这些都是整个动态规划的基本内容。
第一节动态规划的基本原理
一、引例——最短路问题
例1 ,各路段的长度如图中所示,某人欲从A到J,试为他选择一条最短线。
为解决这一问题,显然可用直接枚举法,即列出从A到J(沿图中箭头方向前进)的所有路线,分别计算出这些路线的长度,经比较选出其中最短者。
,可知共有8条路线。为清楚起见,。
,A—B—E—H—J为最短路,其长度等于9。
由于每条路线均由4段组成,故计算一条路线的长度要做3次加法运算,8条路线共需24次加法运算。此外,为决定最短路长还要进行7次比较。
为减少计算工作量,我们考虑另一种算法。用表示从起点A到终点J的
最短路长,类似地,用表示从某一节点K到J的最短路长,并用表示节点K到某节点Y的路段长度。由于各路段长度已给,故知取决于和,取决于和,取决于和,……,、和则仅取决于,而J为终点,可令=0。如此,可按以下顺序逐步进行计算。
=+=3+0=3
=5+0=5
=6+0=6
=2+3=5
算出的最短路线长度等于9,与枚举法结果相同。由=9知B在最短路上线,由知E在最短路线上,如此追踪可找出最短路径(在有关数据下加有横线)为A—B—E—H—J。该算法仅需14次加法,5次比较,比枚举法计算量少;问题规模越大,计算量的节约越显著。可以认为,随问题规模的增加,枚举法的计算量按指数增加,而该方法则按线性增加。
上述第二种算法采用了由后向前逐阶段递推的方法,它包含了动态规划的基本思想。
二、动态规划的主要术语
为便于下面讨论,先解释动态规划的主要术语,并说明一些有关概念。
(stage)
多阶段决策过程包含若干个组成阶段,整个过程是由各个阶段按一定顺序联系起来的统一整体,它由开始阶段出发,按过程进行的方向,由前向后一个阶段一个阶段地推移,直至最后一个阶段结束为止。
若决策者在某一阶段作出了一个决策,则系统此后的发展就要受到这一决策的影响,这个决策的好坏,将影响到此后的决策序列及其效果。因此,在作阶段决策时不能不考虑到对后面各阶段的影响而将它单独“最优化”。由于最后一个阶段对其它阶段不产生影响,因而可以把它看作是整个系统的一个子问题,而将它子最优化,从而得出这一阶段的相应决策。然后,把最后两个阶段看成第二个子问题,利用已得前一子问题子最优化的结果,对其进行子最优化,并得出倒数第二个阶段的相应决策。如此继续,直至第一阶段,即可求出全过程的最优决策序列。用上述方法,通过由后向前逐阶段求解由后部各阶段(或称后部子过程)构成的子问题,就把求解原来的n阶段问题,简化成了求解n个单阶段子问题。,并且虚线框代