4.1动态规划.ppt

第四章
动态规划






动态规划是解决多阶段决策过程最优化的一种方法。1951年美国数学家贝尔曼(R·Bellman)等人针对多阶段决策问题的特征,提出了解决这类问题的"最优化原理",并研究了许多实际问题,从而创立了解决最优化问题的一种新方法--动态规划。动态规划的方法在工程技术、企业管理、工农业生产及军事部门中都有广泛的应用并且获得了显著的效果。在企业管理方面,动态规划可以用来解决最优路径问题、资源分配问题、生产调度问题、库存问题、装载问题、排序问题、设备更新问题、生产过程最优控制问题等等,所以它是现代企业管理中的一种重要的决策方法。许多问题用动态规划的方法处理,常常比线性规划或非线性规划更有效。特别是对于离散性的问题,由于解析数学无法施展,而动态规划的方法就成为非常有用的工具。应当指出,动态规划是求解某类问题的一种方法,是观察问题的一种途径,而不是一种特殊的算法(如线性规划是一种算法)。因而,它不象线性规划那样有一个标准的数学表达式和明确的一组规划,而必须对具体的问题进行具体的分析和处理。
根据多阶段决策过程的时间参量是离散还是连续的变量,以及决策过程的演变是确定性的还是随机性的特点,动态规划模型可分为离散确定型、离散随机型、连续确定型、连续随机型四种决策过程模型。本章主要研究离散型决策过程,介绍动态规划的基本概念、理论和方法,并通过几个典型的问题说明它的应用,这些都是动态规划的基本内容。
多阶段决策问题的概念和主要应用
多阶段决策问题,是指可将过程划分为若干个互相联系的阶段,在它的每一个阶段都需要作出决策,并且一个阶段的决策确定以后,常影响下一阶段的决策,从而影响整个过程的活动。各个阶段所确定的决策就构成一个决策序列,通常称为策略。由于每一个阶段可供选择的决策往往不只一个,因而就有许多策略可供选择。多阶段的决策问题,就是要在允许选择的那些策略中,选择一个最优策略,使在预定的标准下达到最好的效果。
在这类问题中,阶段往往可以用时段来表示。在各个时间阶段,采用不同的决策是随时间而变动的,这就有"动态"的含义。它是在时间的推移过程中要在每一段选择最恰当的决策,以期整体上达到最优。应该指出的是,动态规划在一定条件下也可以解决一些与时间无关的问题,只要人为地引进“阶段”因素以后,这些问题就可变为一个多阶段决策问题。
因此,许多性质不同的问题,都可以归结为多阶段决策问题。下面举几个实例加以说明。
。如图4-1,有A地到D地要铺设一条煤气管道,其中需经过两级中间站。第一级中间站分别为B1和B2,第二级中间站分别为C1、C2、C3。如果两站之间有连线,就表示可以铺设管道。连线之间的数值表示两点间铺设管道的长度。要确定一条从A到D的铺设管道的路线,使得总的管道长度最小。
图4-1
这是一个典型而直观的多阶段决策问题。从A到D分为3个阶段。A点只作起点,B1,B2;C1,C2,C3既可能是上一阶段的终点,又可能是下一阶段的起点,D点只作终点。从图4-1可以看出,在某一阶段选择一条距离最短的路线,不一定使得A