第6章动态规划 当我们视线性规划是一种解决单一阶段单目标规划决策问题的定量分析方法时,则 可认为动态规划( Dynamic Programming)是可以解决更复杂的多阶段单目标决策的定量 分析方法。做决策时,有一种情况是将决策问题涉及的所有变量一次性处理,寻求最优 决策,称为单一阶段决策问题。还有一种情况是将决策问题从时间上或空间上划分为前 后几个相互联系的阶段(或部分),按顺序对每一个阶段做出决策,并考虑每一阶段的决 策将对以后各阶段的决策产生的影响,使整个活动过程所取得的效果最优。这样的决策 问题称为多阶段决策问题。解决这类问题时显然不能运用线性规划及非线性规划的方 法,但用动态规划方法则可以求解。所谓“动态”就是指某问题需逐个阶段处理(即时 间或空间的转移)这一特点 6.1动态规划的基本原理 6.1.1多阶段决策问题的解法 在企业管理的决策活动中,有一类重要问题,对这类问题进行决策将产生广泛、持 续性影响。这类问题作决策时,有时需要从时间上划分阶段,按顺序对各个阶段作决策。 例如产品生产计划的逐月(季、年)安排这个决策活动,确定了某个月的生产计划,则这 个月的生产计划将直接影响到后面各月的计划安排;有时需要从空间上划分为若干部 分。对各部分逐个作决策。例如在对一些工程项目进行投资分配的决策中,确定了其中 任何一个项目去的投资额,都影响到其他所有项目投资分配额的确定。这两个典型的关 于时间和空间的实际问题都具有“动态”的特性。我们进行决策的最终目标将是在一定 的资源条件下,使所安排的逐个时期的生产计划或工程项目的投资分配计划,从整体上 能达到最优的效果。上述的两个问题都属于多阶段决策问题。 解决这类具有“动态”特性的决策问题时,可以按照下面的基本思想进行工作。首 先,把较为复杂的决策问题视为多阶段决策问题,按问题的时间或空间关系将问题分解 为几个相互联系的阶段,从而使每一阶段上的决策问题都是一个较易求解的“子问题”, 在实际决策时从初始状态开始按顺序逐段进行直到终止状态为止;然后,按“动态”的 特点,有顺序地(逐次地)做出每一阶段上的最优决策,具体求解时通常按逆序进行,即 从最后一个阶段开始到最初阶段为止。需要强调的是,做这种最优决策时必须同时考虑 并保证这一阶段以前的各阶段上对“子问题”所做出的决策,从整体来说是最优决策 这样依次地做完每个阶段的最优决策后,它们便构成了整个问题的最优决策。这种方法 可用于求解很多运筹学的问题,甚至对复杂的多变量的线性规划问题及非线性规划问
第 6 章 动态规划 当我们视线性规划是一种解决单一阶段单目标规划决策问题的定量分析方法时，则 可认为动态规划(Dynamic Programming)是可以解决更复杂的多阶段单目标决策的定量 分析方法。做决策时，有一种情况是将决策问题涉及的所有变量一次性处理，寻求最优 决策，称为单一阶段决策问题。还有一种情况是将决策问题从时间上或空间上划分为前 后几个相互联系的阶段(或部分)，按顺序对每一个阶段做出决策，并考虑每一阶段的决 策将对以后各阶段的决策产生的影响，使整个活动过程所取得的效果最优。这样的决策 问题称为多阶段决策问题。解决这类问题时显然不能运用线性规划及非线性规划的方 法，但用动态规划方法则可以求解。所谓“动态”就是指某问题需逐个阶段处理(即时 间或空间的转移)这一特点。 6.1 动态规划的基本原理 6.1.l 多阶段决策问题的解法 在企业管理的决策活动中，有一类重要问题，对这类问题进行决策将产生广泛、持 续性影响。这类问题作决策时，有时需要从时间上划分阶段，按顺序对各个阶段作决策。 例如产品生产计划的逐月(季、年)安排这个决策活动，确定了某个月的生产计划，则这 个月的生产计划将直接影响到后面各月的计划安排；有时需要从空间上划分为若干部 分。对各部分逐个作决策。例如在对一些工程项目进行投资分配的决策中，确定了其中 任何一个项目去的投资额，都影响到其他所有项目投资分配额的确定。这两个典型的关 于时间和空间的实际问题都具有“动态”的特性。我们进行决策的最终目标将是在一定 的资源条件下，使所安排的逐个时期的生产计划或工程项目的投资分配计划，从整体上 能达到最优的效果。上述的两个问题都属于多阶段决策问题。 解决这类具有“动态”特性的决策问题时，可以按照下面的基本思想进行工作。首 先，把较为复杂的决策问题视为多阶段决策问题，按问题的时间或空间关系将问题分解 为几个相互联系的阶段，从而使每一阶段上的决策问题都是一个较易求解的“子问题”， 在实际决策时从初始状态开始按顺序逐段进行直到终止状态为止；然后，按“动态”的 特点，有顺序地(逐次地)做出每一阶段上的最优决策，具体求解时通常按逆序进行，即 从最后一个阶段开始到最初阶段为止。需要强调的是，做这种最优决策时必须同时考虑 并保证这一阶段以前的各阶段上对“子问题”所做出的决策，从整体来说是最优决策。 这样依次地做完每个阶段的最优决策后，它们便构成了整个问题的最优决策。这种方法 可用于求解很多运筹学的问题，甚至对复杂的多变量的线性规划问题及非线性规划问
题,也可按动态规划的思想和步骤用动态规划的方法将该问题分解为每次只考虑一个变 量的一系列子问题。 动态规划是美国数学家贝尔曼(R→ Bellman)于1957年首先提出的。贝尔曼在其《动 态规划》一书中指出了应用动态规划求优时的最优化原则就是:“作为整个过程的最优 策略具有这样的性质:即无论初始状态和决策如何,对前面的决策所形成的状态而言, 余下的所有决策必须构成一个最优策略。”这个原则便作为我们建立动态规划数学模型 的理论基础。下面举例来说明这个最优化原则 某地拟铺设从地点A到地点F的地下水管道, 有两条路线可供选择,其一是经地点B及C1到F; 另一是经地点B2及C2到达F,见图6-1。 施工中每段路线所需时间如图所示。问题是寻8 找一条由A到F的施工时间最短的路线。这是一个 多阶段决策问题。此问题可划分为三个阶段(图1-2-13 6-1)。第一阶段的决策指的就是由A到B1或由A到 B2这两条可能走的路线的选择。一旦选定了其中的 图6-1 某条路线,就直接影响到下一阶段的决策是由B到C1或由B2到C2。这就是说对每一阶 段都应做出恰当的决策。由图6-1可知由A到B需6个时间单位,而由A到B,需8个 时间单位,前者所需时间比后者要少,对本阶段来说似乎应选择由A到B1的路线作为第 阶段的最优决策。此阶段决策一经做出,则后面各段决策应接B到C1,C1到F的路 线来施工,所需总时间为23个单位。但若选择由A到B2,再经C2到F的路线则所需总 时间为19个单位。显然,本应选择后一个路线才能使总时间数为最小,而第一阶段所 选的由A到B的决策不能保证整个问题为最优决策。这就说明当某阶段决策选定时,它 还直接影响到后面各阶段的决策和整个问题的决策。为了使整个问题的决策为优,按照 贝尔曼的最优化原则意味着对某阶段作的决策对该阶段本身来说,从表面上看未必是 个最好的选择,甚至需要做出让步。如本例中第一阶段选择由A到B2的路线对于本阶段 来说表面上看不是最优决策,但是对于从第一阶段的决策由A到B2得到的状态B2而言 从B2开始,余下的第二阶段决策由B2到C2及第三阶段的决策由C2到F所构成的路线应 该在时间上少于由B1经C1到F所需的时间。这就是贝尔曼所指的“……余下的所有决 策必须构成一个最优策略。”这样再综合第一阶段由A到B,的时间,从整体上来看反而 为最优路线。相反,对前面阶段虽然选择了一个最优路线如例中的由A到B线路,但并 不能保证由此产生的最后结论从整体上看为最优决策。这便是动态规划方法的理论基 础。所以按动态规划方法求解时应按逆序逐段从终点向始点方向决策。对于本例,应该 是先求第三阶段的最优决策为C2→F,再求第二阶段的最优决策为B2→C2,最后求 得第一阶段的最优决策为A>B2,则整个问题的最优决策为A→B2→C2→F
题，也可按动态规划的思想和步骤用动态规划的方法将该问题分解为每次只考虑一个变 量的一系列子问题。 动态规划是美国数学家贝尔曼(R·Bellman)于 1957 年首先提出的。贝尔曼在其《动 态规划》一书中指出了应用动态规划求优时的最优化原则就是：“作为整个过程的最优 策略具有这样的性质：即无论初始状态和决策如何，对前面的决策所形成的状态而言， 余下的所有决策必须构成一个最优策略。”这个原则便作为我们建立动态规划数学模型 的理论基础。下面举例来说明这个最优化原则。 某地拟铺设从地点 到地点 的地下水管道， 有两条路线可供选择，其一是经地点 A F B1及 到 ； 另一是经地点 C1 F B2 及C2 到达 F ，见图 6-1。 施工中每段路线所需时间如图所示。问题是寻 找一条由 到 的施工时间最短的路线。这是一个 多阶段决策问题。此问题可划分为三个阶段(图 6-1)。第一阶段的决策指的就是由 到 A F A B1或由 A到 B2 这两条可能走的路线的选择。一旦选定了其中的 某条路线，就直接影响到下一阶段的决策是由 B1到C1或由 B2 到C 。这就是说对每一阶 段都应做出恰当的决策。由图 6-l 可知由 到 2 A B1需 6 个时间单位，而由 A到 B2 需 8 个 时间单位，前者所需时间比后者要少，对本阶段来说似乎应选择由 A到 B1的路线作为第 一阶段的最优决策。此阶段决策一经做出，则后面各段决策应接 B1到 ， 到 的路 线来施工，所需总时间为 23 个单位。但若选择由 到 ，再经 到 的路线则所需总 时间为 19 个单位。显然，本应选择后一个路线才能使总时间数为最小，而第一阶段所 选的由 到 的决策不能保证整个问题为最优决策。这就说明当某阶段决策选定时，它 还直接影响到后面各阶段的决策和整个问题的决策。为了使整个问题的决策为优，按照 贝尔曼的最优化原则意味着对某阶段作的决策对该阶段本身来说，从表面上看未必是一 个最好的选择，甚至需要做出让步。如本例中第一阶段选择由 到 的路线对于本阶段 来说表面上看不是最优决策，但是对于从第一阶段的决策由 到 得到的状态 而言， 从 开始，余下的第二阶段决策由 到C 及第三阶段的决策由C 到 所构成的路线应 该在时间上少于由 经C 到 所需的时间。这就是贝尔曼所指的“……余下的所有决 策必须构成一个最优策略。”这样再综合第一阶段由 到 的时间，从整体上来看反而 为最优路线。相反，对前面阶段虽然选择了一个最优路线如例中的由 到 线路，但并 不能保证由此产生的最后结论从整体上看为最优决策。这便是动态规划方法的理论基 础。所以按动态规划方法求解时应按逆序逐段从终点向始点方向决策。对于本例，应该 是先求第三阶段的最优决策为C ，再求第二阶段的最优决策为 ，最后求 得第一阶段的最优决策为 ，则整个问题的最优决策为 。 C1 2 1 B 2 F C 1 C → F 2 A B2 C2 B2 2 → F F A B → A B1 A A B2 B2 A 2 B2 B2 → F 2 B1 1 A F → B A B B → C2 2 2 1 2 3 7 B C2 2 F 6 B1 8 4 8 A C1 9 图 6-1
6.1.2最短路线问题 最短路线问题就是说给定了初始点及终点以及由始点到终点的各种可能途径,要求 寻找一条由始点到终点的最短路线。对于不同的实际问题也就是求距离(或时间、运输 费用)的最小值。 例6.1图6-2是一个示意图,表示由始点A到终点E的网络路线。图中A,B1, B2…表示各个地点,线段表示各个地点之间的交通路线,线段上的数字表示各个地点 之间的距离(或时间、费用)。要求选择一条从A到E距离最短的路线(或时间、费用 最少)。这是一个多阶段决策问题 求解这个问题可采用穷举法。就是列出 从A点到E点的所有路线,然后计算每 SC 条路线的距离(或时间、费用),再进行 比较,找出距离最短(或时间,费用最 少)的路线,则最优解便找到了。此法 称为枚举法或穷举法。本例从A点到E 1中23-|4-|点共有11条不同路线,比较它们的长 图6-2 度,最短路线为 A→B,→>C 其距离为14。但这样的计算相当冗繁,特别是网络路线比较复杂时,用穷举法计算 甚至无法实现。下面采用动态规划方法求解此例。该法是求解这类最短路线(或最长路 线)的最有效的方法之 用动态规划方法求解时,根据最优化原则导致最短路线问题应具有这种特性,就是: 如果最短路线通过点P,则这条最短路线从P点到终点的部分,对于从P点到终点的所 有路线(称为P的后部路线)而言,必然也是最短的线路(P的最短后部路线)。例如本例 中最短路线通过B2,C2,D2,则路线C2→D2→E就是C2到终点E所有路线中最短 的一条。最短路线所具有的这个特性不难理解,用反证法,若从P点至终点还有另一条 更短的路线存在,把这条更短的路线与原最短路线从起始点到P点的那部分路线连接起 来,就会形成一条比原来由始点到终点的最短路线还要短的路线,这是不可能的 现在我们利用这种特性把整个问题按空间关系,即把从A到E的网络路线划分为几 个阶段,然后接逆序从最后一段开始向最初阶段递推,做出各阶段中各点的最优决策即 寻找某阶段各点到终点E的最短路线上,在下一阶段应经过的点O则各点到终点E的最 短(后部)路线可同时确定,最后便得到起点A到终点E的最短路线。因此,动态规划方 法就是从终点逐段向始点方向寻找最短路线的方法。解题步骤如下:
6.1.2 最短路线问题 最短路线问题就是说给定了初始点及终点以及由始点到终点的各种可能途径，要求 寻找一条由始点到终点的最短路线。对于不同的实际问题也就是求距离（或时间、运输 费用）的最小值。 例 6.1 图 6-2 是一个示意图，表示由始点 A到终点 E 的网络路线。图中 ， ， ……表示各个地点，线段表示各个地点之间的交通路线，线段上的数字表示各个地点 之间的距离（或时间、费用）。要求选择一条从 到 A B1 B2 A E 距离最短的路线（或时间、费用 最少）。这是一个多阶段决策问题。 6 3 C1 A 4 2 6 6 7 5 8 9 1 3 2 5 1 3 B1 D1 E B2 C2 D2 C3 1 2 3 4 图 6-2 求解这个问题可采用穷举法。就是列出 从 A点到 E 点的所有路线，然后计算每 条路线的距离(或时间、费用)，再进行 比较，找出距离最短(或时间，费用最 少)的路线，则最优解便找到了。此法 称为枚举法或穷举法。本例从 A点到 E 点共有 11 条不同路线，比较它们的长 度，最短路线为： A → B2 → C2 → D2 → E 其距离为 14。但这样的计算相当冗繁，特别是网络路线比较复杂时，用穷举法计算 甚至无法实现。下面采用动态规划方法求解此例。该法是求解这类最短路线(或最长路 线)的最有效的方法之一。 用动态规划方法求解时，根据最优化原则导致最短路线问题应具有这种特性，就是： 如果最短路线通过点 P ，则这条最短路线从 P 点到终点的部分，对于从 P 点到终点的所 有路线(称为 P 的后部路线)而言，必然也是最短的线路( P 的最短后部路线)。例如本例 中最短路线通过 B2，C2 ， D2 ，则路线C2 → D2 → E 就是C2 到终点 E 所有路线中最短 的一条。最短路线所具有的这个特性不难理解，用反证法，若从 P 点至终点还有另一条 更短的路线存在，把这条更短的路线与原最短路线从起始点到 P 点的那部分路线连接起 来，就会形成一条比原来由始点到终点的最短路线还要短的路线，这是不可能的。 现在我们利用这种特性把整个问题按空间关系，即把从 A到 E 的网络路线划分为几 个阶段，然后接逆序从最后一段开始向最初阶段递推，做出各阶段中各点的最优决策即 寻找某阶段各点到终点 E 的最短路线上，在下一阶段应经过的点O则各点到终点 E 的最 短(后部)路线可同时确定，最后便得到起点 A到终点 E 的最短路线。因此，动态规划方 法就是从终点逐段向始点方向寻找最短路线的方法。解题步骤如下：
1.把问题划分为几个阶段。本例可把网络按各点位置划分为四个阶段。第一阶段由 A到B1及B2的路线构成,……,第四阶段由D,D2到E的路线构成,如图6-2所示 2.按阶段顺序首先考虑最后阶段即第四阶段的最优决策,也就是走哪条路线最短 先考虑D1,D1到终点E只有一条路线,故D1的最短后都路线就是D→E,最短距离 为8;同样,从D2到E的最短后部路线就是D2→E,最短距离为9。 3.按阶段顺序依次考虑第三、第二,第一阶段的最优决策,为此只需确定每一阶段 上各初始点的最优决策即可。在第三阶段中分别考虑三个点C1,C2和C3的最优决策。 点C后部路线的第一段路线有两种选择.即C1→D和C1→>D2。为了确定C1的最优决 策即确定出对第四阶段的D1,D2的某个选择,应比较由C1分别经过D、D2到E所用 的时间,即比较C,→D的长度与D的最短后部路线长度之和,以及C1→>D,的长度与 D,的最短后部路线的长度之和。前者为3+8=11,后者为6+9=15,取其中较小者为C的 最短后部路线的长度。所以C1的最优决策是下一阶段到达点D,C1的最短后部路线是 C1→D1→E,最短距离为11。用同样的方法求C2的最优决策。由于C2后部路线的第 阶段有两种选择,即C2→>D1,C2→>D2。所以比较C2→>D1的长度与D1的最短后部 路线D1→E的长度之和,以及C2→D2的长度与D2的最短后部路线D2→>E的长度之 和,前者为6+8=14,后者为2+9=11,取其中较小者为11,对应的C2的最优决策是到达 D2,C2的最短后部路线为C2→D2→E,其距离为11。对于C3比较4+8=12及3+9=12 因为二者相等,所以C3的最优决策是到达D及D2均可,C3的最短后部路线可以取其中 任一条,C3→D1→E或C3→D2→E距离都是12 在第二阶段中讨论点B1及B2的最优决策。点B1的后部路线在第一段上有三条,即 B1→C1,B1→C2,B1→C3。而C1,C2,C3各点到终点E的最优决策在第三阶段的 讨论中已确定了。所以比较6+11=17,5+11=16及7+12=19,知三条路线中长度最短者为 16,则B1的最优决策就是由点B1到点C2,点B1的最短后部路线为B1→C2→D2→E, 最短距离为16。点B2的后部路线第一阶段上有三条。比较B2→C1→D1→E B2→C2→D2→E及B2→C3→D1→E(或B2→C3→D2→E)这三条后部路线 的长短,由5+11=16,1+11=12,1+12=13得点B2的最优决策是到点C2,点B2的最短后 部路线为B2→C2→>D2→E,其距离为12。 最后考虑第一阶段,也就是求始点A的最优决策。点可能的决策方案有两个,即到 达B1或B2,而B1及B2两点到终点E的最优决策已在第二阶段确定了,并找到了该两点 之间的最短后部路线,因此我们只需在A→B1→C2→D2→E和 A→B2→C2→D2→E这两条路线中选择点B2,点A的最短后部路线为 A→B2→丶C2→E。至此解题过程结束,整个网络最短路线的决策问题得到解决。从A 到E的最短路线为A→B2→C2→D2→E,最短距离为14。 通过此例的求解过程,可以看到用动态规划方法逐段求解时,每个阶段上的求优方
1.把问题划分为几个阶段。本例可把网络按各点位置划分为四个阶段。第一阶段由 A到 B1及 B2的路线构成，……，第四阶段由 D1， D2 到 E 的路线构成，如图 6-2 所示。 2.按阶段顺序首先考虑最后阶段即第四阶段的最优决策，也就是走哪条路线最短。 先考虑 D1， D1到终点 E 只有一条路线，故 的最短后都路线就是 ，最短距离 为 8；同样，从 到 D1 D1 → E D2 E 的最短后部路线就是 D2 → E ，最短距离为 9。 3.按阶段顺序依次考虑第三、第二，第一阶段的最优决策，为此只需确定每一阶段 上各初始点的最优决策即可。在第三阶段中分别考虑三个点C ，C 和C 的最优决策。 点 后部路线的第一段路线有两种选择．即C 和C 。为了确定C 的最优决 策即确定出对第四阶段的 ， 的某个选择，应比较由C 分别经过 、 到 1 D2 2 3 D1 C1 1 → D1 1 → 1 1 D1 D2 D2 E 所用 的时间，即比较 的长度与 的最短后部路线长度之和，以及C 的长度与 的最短后部路线的长度之和。前者为 3+8=11，后者为 6+9=15，取其中较小者为C 的 最短后部路线的长度。所以 的最优决策是下一阶段到达点 ， 的最短后部路线是 ，最短距离为 11。用同样的方法求C 的最优决策。由于C 后部路线的第 一阶段有两种选择，即C ，C 。所以比较C 的长度与 的最短后部 路线 的长度之和，以及C 的长度与 的最短后部路线 的长度之 和，前者为 6+8=14，后者为 2+9=11，取其中较小者为 11，对应的C 的最优决策是到达 ，C 的最短后部路线为C ，其距离为 11。对于C 比较 4+8=12 及 3+9=12， 因为二者相等，所以 的最优决策是到达 及 均可，C 的最短后部路线可以取其中 任一条， 或 距离都是 12。 C1 → D1 C3 D1 → E D1 2 → 2 → → D2 1 E 1 → 2 D2 2 1 → 2 D C D 1 1 D → C → 2 C3 D1 D1 3 C1 2 D1 → E D1 → E 2 C3 → 2 D2 1 D2 1 2 → D D2 2 → D2 D2 E D E 2 → 3 D → 在第二阶段中讨论点 及 的最优决策。点 的后部路线在第一段上有三条，即 ， ， 。而 ， ，C 各点到终点 B1 → C B2 B1 B1 → C1 B1 → C2 B1 3 C1 C2 3 E 的最优决策在第三阶段的 讨论中已确定了。所以比较 6+11=17，5+11=16 及 7+12=19，知三条路线中长度最短者为 16，则 的最优决策就是由点 到点C ，点 的最短后部路线为 ， 最短距离为 16。点 的后部路线第一阶段上有三条。比较 ， 及 （或 ）这三条后部路线 的长短，由 5+11=16，1+11=12，1+12=13 得点 的最优决策是到点 ，点 的最短后 部路线为 ，其距离为 12。 B1 B2 → C2 B1 3 → 2 E B1 B2 B1 → C2 → D2 → E B2 → C1 → D1 → E E C2 B2 B2 B C D2 → D2 → E 2 → C2 → 2 → D1 → → E B2 → C3 → D2 → B 最后考虑第一阶段，也就是求始点 的最优决策。点可能的决策方案有两个，即到 达 或 ，而 及 两点到终点 A B1 B2 B1 B2 E 的最优决策已在第二阶段确定了，并找到了该两点 之间的最短后部路线，因此我们只需在 和 这两条路线中选择点 ， 点 的最短后部路线为 。至此解题过程结束，整个网络最短路线的决策问题得到解决。从 到 A → B1 → C2 → D2 → E A B C2 D2 E A A B C2 → → → E 2 → 2 → → → B2 A E 的最短路线为 A → B2 → C2 → D2 → E ，最短距离为 14。 通过此例的求解过程，可以看到用动态规划方法逐段求解时，每个阶段上的求优方
法基本相同,而且比较简单,所以在后面进一步学习这种方法时,虽然会遇到较多的数 学符号,但对这些符号还是易于理解的。另外,动态规划方法明显优于枚举法(穷举法), 在本例中,每一阶段的计算都要利用上一阶段的计算结果,因而减少了很多计算量。阶 段数愈多,这种效果愈明显 6.2动态规划的数学模型 6.2.1动态规划的基本概念 为讨论问题方便起见,先介绍动态规划的基本概念和符号 1.阶段 用动态规划方法解题,原问题必须能划分为若干阶段。阶段是按问题的时间或空间 特征来划分的。通常用k表示阶段的变量;阶段的编号在本书中按从左到右的顺序编号。 例如前例(最短路线问题)中将整个问题按空间划分为四个阶段,当k=1,2,34时,分 别表示问题处于第一、二、三、四阶段。第一阶段(k=1)包括两条支路A→B1和A→丶B2 第二阶段(k=2)包括6条支路B1→C1、B1→C2、B1→C3、B2→C1、B2→C2 B2→>C3。依次类推。用动态规划方法求解时,通常按相反方向逐段决策,即从最后 阶段开始,按逆序到最初阶段为止。 2.状态和状态变量 状态可理解为事物的某种特征。状态的改变意味着事物发生变化。在动态规划问题 中,状态是划分阶段的依据,状态的变化就意味着阶段的推移,因此解题时首先应明确 每一阶段开始时的一切可能状态。在最短路线问题中,用状态表示某阶段的出发位置, 它既是该阶段的初始点也是前一阶段的终止点,通常一个阶段包含若干个状态。如前例 的最短路线问题中,第一阶段只有一个状态时点A;第二阶段有两个状态点B1和B2, 等等。为了将实际问题转化为数学模型之后便于计算,通常可将状态用数量表示,则状 态可视为变量,并称为状态变量S,记S为第k阶段(有时记S为第阶段)的状态变 量,用S={S4}表示k阶段上所有状态的集合。例如前例中,当k=2时,有两个状态B 和B2,则第二阶段状态为S2=B1和S2=B2,状态集合S2}={B,B2}(或记为 S2=B1,B2),若用数量表示,令点B1=1,点B2=2(每阶段状态都可记为1,2,3…n), 则{S2}=2}(S2=1.2)。对于有些实际问题状态本身就是数量。例如投资分配问题 第k阶段的状态即该段最初的投资数额,仍可将实际数额转换数i并记为 S=i(=12,…n) 3.决策和决策变量 对实际问题进行多阶段决策时是从第一阶段的初始状态开始,逐段向后发展,直到 最后一个阶段为止。在每一阶段中只达到一个可能的状态,从该状态演变到下一阶段进 入哪个状态,取决于这一阶段做出的决策。这就是说,决策就是各阶段对状态演变各种
法基本相同，而且比较简单，所以在后面进一步学习这种方法时，虽然会遇到较多的数 学符号，但对这些符号还是易于理解的。另外，动态规划方法明显优于枚举法（穷举法）， 在本例中，每一阶段的计算都要利用上一阶段的计算结果，因而减少了很多计算量。阶 段数愈多，这种效果愈明显。 6.2 动态规划的数学模型 6.2.1 动态规划的基本概念 为讨论问题方便起见，先介绍动态规划的基本概念和符号。 1. 阶段 用动态规划方法解题，原问题必须能划分为若干阶段。阶段是按问题的时间或空间 特征来划分的。通常用 表示阶段的变量；阶段的编号在本书中按从左到右的顺序编号。 例如前例（最短路线问题）中将整个问题按空间划分为四个阶段，当 时，分 别表示问题处于第一、二、三、四阶段。第一阶段（ k k = 1,2,3,4 k = 1 → C2 ）包括两条支路 和 ， 第二阶段（ ）包括 6 条支路 、 、 、 、 、 。依次类推。用动态规划方法求解时，通常按相反方向逐段决策，即从最后一 个阶段开始，按逆序到最初阶段为止。 → B1 A → C1 B2 A 2 → B2 → C2 k = 2 B1 → C1 B1 B1 → C3 B B2 → C3 2. 状态和状态变量 状态可理解为事物的某种特征。状态的改变意味着事物发生变化。在动态规划问题 中，状态是划分阶段的依据，状态的变化就意味着阶段的推移，因此解题时首先应明确 每一阶段开始时的一切可能状态。在最短路线问题中，用状态表示某阶段的出发位置， 它既是该阶段的初始点也是前一阶段的终止点，通常一个阶段包含若干个状态。如前例 的最短路线问题中，第一阶段只有一个状态时点 ；第二阶段有两个状态点 和 ， 等等。为了将实际问题转化为数学模型之后便于计算，通常可将状态用数量表示，则状 态可视为变量，并称为状态变量 ，记 为第 阶段（有时记 为第 阶段）的状态变 量，用 表示 阶段上所有状态的集合。例如前例中，当 A B1 B2 S Sk k Si i { } Sk = Sk k k = 2 时，有两个状态 和 ，则第二阶段状态为 和 B1 B2 B1 S2 = 2 B2 S = ，状态集合 {S2 } { = B1 , B2 } （或记为 S2 = B1 , B2 ），若用数量表示，令点 1 B1 = ，点 2 B2 = （每阶段状态都可记为1 ）， 则 （ ）。对于有些实际问题状态本身就是数量。例如投资分配问题， 第 阶段的状态即该段最初的投资数额 ，仍可将实际数额转换数 i 并记为 。 ,2,3,""n {}{ = 1,2} S = =i 1, 2," 2 S k S i 1,2 2 = ( ) n k 3. 决策和决策变量 对实际问题进行多阶段决策时是从第一阶段的初始状态开始，逐段向后发展，直到 最后一个阶段为止。在每一阶段中只达到一个可能的状态，从该状态演变到下一阶段进 入哪个状态，取决于这一阶段做出的决策。这就是说，决策就是各阶段对状态演变各种