第6章动态规划 当我们视线性规划是一种解决单一阶段单目标规划决策问题的定量分析方法时,则 可认为动态规划( Dynamic Programming)是可以解决更复杂的多阶段单目标决策的定量 分析方法。做决策时,有一种情况是将决策问题涉及的所有变量一次性处理,寻求最优 决策,称为单一阶段决策问题。还有一种情况是将决策问题从时间上或空间上划分为前 后几个相互联系的阶段(或部分),按顺序对每一个阶段做出决策,并考虑每一阶段的决 策将对以后各阶段的决策产生的影响,使整个活动过程所取得的效果最优。这样的决策 问题称为多阶段决策问题。解决这类问题时显然不能运用线性规划及非线性规划的方 法,但用动态规划方法则可以求解。所谓“动态”就是指某问题需逐个阶段处理(即时 间或空间的转移)这一特点 6.1动态规划的基本原理 6.1.1多阶段决策问题的解法 在企业管理的决策活动中,有一类重要问题,对这类问题进行决策将产生广泛、持 续性影响。这类问题作决策时,有时需要从时间上划分阶段,按顺序对各个阶段作决策。 例如产品生产计划的逐月(季、年)安排这个决策活动,确定了某个月的生产计划,则这 个月的生产计划将直接影响到后面各月的计划安排;有时需要从空间上划分为若干部 分。对各部分逐个作决策。例如在对一些工程项目进行投资分配的决策中,确定了其中 任何一个项目去的投资额,都影响到其他所有项目投资分配额的确定。这两个典型的关 于时间和空间的实际问题都具有“动态”的特性。我们进行决策的最终目标将是在一定 的资源条件下,使所安排的逐个时期的生产计划或工程项目的投资分配计划,从整体上 能达到最优的效果。上述的两个问题都属于多阶段决策问题。 解决这类具有“动态”特性的决策问题时,可以按照下面的基本思想进行工作。首 先,把较为复杂的决策问题视为多阶段决策问题,按问题的时间或空间关系将问题分解 为几个相互联系的阶段,从而使每一阶段上的决策问题都是一个较易求解的“子问题”, 在实际决策时从初始状态开始按顺序逐段进行直到终止状态为止;然后,按“动态”的 特点,有顺序地(逐次地)做出每一阶段上的最优决策,具体求解时通常按逆序进行,即 从最后一个阶段开始到最初阶段为止。需要强调的是,做这种最优决策时必须同时考虑 并保证这一阶段以前的各阶段上对“子问题”所做出的决策,从整体来说是最优决策 这样依次地做完每个阶段的最优决策后,它们便构成了整个问题的最优决策。这种方法 可用于求解很多运筹学的问题,甚至对复杂的多变量的线性规划问题及非线性规划问第 6 章 动态规划 当我们视线性规划是一种解决单一阶段单目标规划决策问题的定量分析方法时，则 可认为动态规划(Dynamic Programming)是可以解决更复杂的多阶段单目标决策的定量 分析方法。做决策时，有一种情况是将决策问题涉及的所有变量一次性处理，寻求最优 决策，称为单一阶段决策问题。还有一种情况是将决策问题从时间上或空间上划分为前 后几个相互联系的阶段(或部分)，按顺序对每一个阶段做出决策，并考虑每一阶段的决 策将对以后各阶段的决策产生的影响，使整个活动过程所取得的效果最优。这样的决策 问题称为多阶段决策问题。解决这类问题时显然不能运用线性规划及非线性规划的方 法，但用动态规划方法则可以求解。所谓“动态”就是指某问题需逐个阶段处理(即时 间或空间的转移)这一特点。 6.1 动态规划的基本原理 6.1.l 多阶段决策问题的解法 在企业管理的决策活动中，有一类重要问题，对这类问题进行决策将产生广泛、持 续性影响。这类问题作决策时，有时需要从时间上划分阶段，按顺序对各个阶段作决策。 例如产品生产计划的逐月(季、年)安排这个决策活动，确定了某个月的生产计划，则这 个月的生产计划将直接影响到后面各月的计划安排；有时需要从空间上划分为若干部 分。对各部分逐个作决策。例如在对一些工程项目进行投资分配的决策中，确定了其中 任何一个项目去的投资额，都影响到其他所有项目投资分配额的确定。这两个典型的关 于时间和空间的实际问题都具有“动态”的特性。我们进行决策的最终目标将是在一定 的资源条件下，使所安排的逐个时期的生产计划或工程项目的投资分配计划，从整体上 能达到最优的效果。上述的两个问题都属于多阶段决策问题。 解决这类具有“动态”特性的决策问题时，可以按照下面的基本思想进行工作。首 先，把较为复杂的决策问题视为多阶段决策问题，按问题的时间或空间关系将问题分解 为几个相互联系的阶段，从而使每一阶段上的决策问题都是一个较易求解的“子问题”， 在实际决策时从初始状态开始按顺序逐段进行直到终止状态为止；然后，按“动态”的 特点，有顺序地(逐次地)做出每一阶段上的最优决策，具体求解时通常按逆序进行，即 从最后一个阶段开始到最初阶段为止。需要强调的是，做这种最优决策时必须同时考虑 并保证这一阶段以前的各阶段上对“子问题”所做出的决策，从整体来说是最优决策。 这样依次地做完每个阶段的最优决策后，它们便构成了整个问题的最优决策。这种方法 可用于求解很多运筹学的问题，甚至对复杂的多变量的线性规划问题及非线性规划问