第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. 决策和决策变量 对实际问题进行多阶段决策时是从第一阶段的初始状态开始，逐段向后发展，直到 最后一个阶段为止。在每一阶段中只达到一个可能的状态，从该状态演变到下一阶段进 入哪个状态，取决于这一阶段做出的决策。这就是说，决策就是各阶段对状态演变各种
可能性的选择描述决策的变量,称为决策变量,用x(S)表示第k阶段处于S时的决策 变量。用决策集合D4={x(s表示x(S)的取值范围。例如图6-2示意的最短路线问 题中,当k=2时,状态集合{S2}={B1,B2},则状态B1的决策变量x2(B)的取值 x2(B)=C1,x2(B1)=C2,或x2(B)=C3,则为x(B1}=C1C2C3},表示从状态B1出 发到终点E时,进入到下一阶段所选择的状态,可以是C1,C2或C3,换句话说{x2(B1)表 示从B1点出发到达下一阶段的路线可有三条,所以在第二阶段对于B点的决策方案有 三个,即有B1→C1,B1→C2或B→C3。状态B1的最优决策指的是为达到最优目标, 对C1C2C3的某个选择,使得由A到E的最短路线经过该点。对状态B2的决策变量 x2(B2)的取值也有三个,就是{x2(B2)}={C2,C}。由此可见,决策变量x(SA)是状 态变量的函数,为了计算的方便,既然状态变量S的取值可人为地规定为数,我们也可 将决策变量x(S)的取值人为地规定为数。例如上面的{x2(B2}={C1C2,C3},若令 C1=i、(=12,3),则{x2(B2)}={2,3} 4.策略 多阶段决策问题中,把每个阶段做出的决策x4(S4k=12,…n)组成的序列称作是策 略。把解决问题时产生的效果最优的策略称为最优策略。因此,求解多阶段决策问题便 是去寻找该问题的最优策略,而动态规划方法就是用来求得这个最优策略的方法。 设整个问题分化为n个阶段(n=1,2,…,k,…,n),第k阶段状态S4开始至最终阶段到 n的终点为止的过程称为第k阶段状态S4的后部过程,相应的第k阶段以后的各阶段的 决策所构成的决策序列称为状态S的后部策略(前面提到的点P的后部路线便是由状态 尸的后部策略产生的)。从前面的例题可知,动态规划方法的每一个阶段都需找出该阶 段每一状态的最优后部策略,即最短后部路线。 5.阶段损益函数(或称阶段效应) 用动态规划方法求解问题时,把用以衡量策略优劣的数量指标称为损益函数,其取 值称为损益值。阶段损益函数是某一阶段、某一状态本身在决策选择时所能获得的损失 (或效益)值的表达式,通常表示为d4(s4,x)。S4表示第k阶段所处的状态,xk表示状 态为S时的决策,也就是该阶段所选择的决策方案。对于不同的决策问题损益函数的损 益值有不同的实际含义。例如,效益值可能是效率、产值、利润,而损失值可能是成本 费用等。又如例2的最短路线问题中,可视阶段损益值为网络路线中第k阶段上某路线 的距离,如第三阶段点C1的损益值可记为d3(C1x3(C1),具体就是d3(C,D1)=3以及 d3(C1,D2)=6,表示第三阶段由状态C1到D和到D2的距离分为3及6 6.最优损益函数 最优损益函数是用以表示某阶段、某状态的最优后部策略的数量指标。它综合考虑 了这一阶段本身的阶段损益值以及相应的下一阶段到终点为止的最优损益值两个方面 的情况。记最优损益函数为f(s)(k=12,…,n)k表示所处的阶段,Sk表示第k阶段
可能性的选择描述决策的变量，称为决策变量，用 ( ) k Sk x 表示第 阶段处于 时的决策 变量。用决策集合 表示 k Sk { } ( ) k k k D = x s ( ) k Sk x 的取值范围。例如图 6-2 示意的最短路线问 题中，当 k = 2 时，状态集合 { } S2 = {B1 , B2 } ，则状态 B1 的决策变量 的取值 ， (B1 ) 2 x ( ) x2 B1 = C1 2 x ( ) B1 = C2 ，或 ( ) 2 B1 C3 x = ，则为{x2 (B1 )} = {C1 ,C2 ,C3 }，表示从状态 出 发到终点 B1 E 时，进入到下一阶段所选择的状态，可以是C ，换句话说{ }表 示从 点出发到达下一阶段的路线可有三条，所以在第二阶段对于 点的决策方案有 三个，即有 ， 或 。状态 的最优决策指的是为达到最优目标， 对 的某个选择，使得由 到 2或C3 B 1 1 ,C (B ) 2 1 x B1 1 2 C ,C ,C B1 B1 → C1 B1 → C2 3 B1 → C3 A E 的最短路线经过该点。对状态 的决策变量 的取值也有三个，就是 B2 { ( ) 2 B2 x } { } x2 (B2 ) = {C1 ,C2 ,C3 }。由此可见，决策变量 是状 态变量的函数，为了计算的方便，既然状态变量 的取值可人为地规定为数，我们也可 将决策变量 的取值人为地规定为数。例如上面的 ( k ) k x S Sk ( k ) xk S {x2 (B2 )} { = C1 ,C2 ,C3 }，若令 Ci = i,( ) i = 1,2,3 ，则{ ( )} {1 x2 B2 = ,2,3}。 4. 策略 多阶段决策问题中，把每个阶段做出的决策 x (s )(k n) k k = 1,2,", 组成的序列称作是策 略。把解决问题时产生的效果最优的策略称为最优策略。因此，求解多阶段决策问题便 是去寻找该问题的最优策略，而动态规划方法就是用来求得这个最优策略的方法。 设整个问题分化为 n 个阶段( ) n = 1,2,", k,", n ,第 阶段状态 开始至最终阶段到 的终点为止的过程称为第k 阶段状态 的后部过程，相应的第 阶段以后的各阶段的 决策所构成的决策序列称为状态 的后部策略（前面提到的点 k Sk n k Sk Sk P 的后部路线便是由状态 P 的后部策略产生的）。从前面的例题可知，动态规划方法的每一个阶段都需找出该阶 段每一状态的最优后部策略，即最短后部路线。 5. 阶段损益函数(或称阶段效应) 用动态规划方法求解问题时，把用以衡量策略优劣的数量指标称为损益函数，其取 值称为损益值。阶段损益函数是某一阶段、某一状态本身在决策选择时所能获得的损失 (或效益)值的表达式，通常表示为 ( ) k k k d s , x 。 表示第 阶段所处的状态， 表示状 态为 时的决策，也就是该阶段所选择的决策方案。对于不同的决策问题损益函数的损 益值有不同的实际含义。例如，效益值可能是效率、产值、利润，而损失值可能是成本、 费用等。又如例 2 的最短路线问题中，可视阶段损益值为网络路线中第 阶段上某路线 的距离，如第三阶段点C 的损益值可记为 Sk k k x Sk k 1 ( ( )) 3 3 C1 x D2 1 d C , ，具体就是 以及 ，表示第三阶段由状态 到 和到 的距离分为 3 及 6。 d3 (C1 , D1 ) = 3 ( , d3 C1 D2 ) = 6 C1 D1 6. 最优损益函数 最优损益函数是用以表示某阶段、某状态的最优后部策略的数量指标。它综合考虑 了这一阶段本身的阶段损益值以及相应的下一阶段到终点为止的最优损益值两个方面 的情况。记最优损益函数为 f ( ) s (k 1,2, ,n) k k = "" k 表示所处的阶段， Sk 表示第k 阶段
中所处的状态。例如,在例2中,f2(B1)=5+11=16,表示在第二阶段时,状态B1到终 点E的最优损益函数值即点B到终点E的最短后部路线长度)为16,同理,f(B1)=12 有了上述的基本概念,我们便可将实际问题用下面介绍的动态规划模型来表示。 6.22动态规划的数学模型建立方法 现在我们结合网络最短路线来介绍动态规划方法中所使用的数学模型将如何建立 例6.2建立例1的最短路线问题的数学模型,见示意图6-2。 动态规划的数学模型包括目标函数和约束条件两部分。对于该最短路线问题求的是 从始点A到终点E的距离为最短。又因为这是多阶段决策问题,所以相应的动态规划方 法应将问题首先划分为若干个阶段。然后再按上面所述的基本思想,从终点E逐段向始 点方向寻找每阶段的最优决策。这是一个逆向递推的过程,用动态规划的术语表示出对 目标函数的要求就是求得每个阶段的最优损益函数(最短后部路线的长度)。下面的工作 就是具体建立这种按阶段表达的数学模型。 动态规划的约束条件可由实际问题决定。例如例1中最短路线问题,在网络路线图 上用带有箭头的线段表示可行的通路,箭头的方向表示行进的方向。这种方向通常都是 单向的,不能反向行进 具体表达这种具有“递推”特性的数学模型如下:首先将问题划分为四个阶段,分 别记为k=i(=1,2,3,4),其次,按逆向建模。 k=4时目标函数的优值为 f s)=mind,(S4, XA) (6-1) 其中∫4(s4)——例1中网络路线上第四阶段中状态变量S4取为D、D2两点时,由 此两点分别到达终点E的最短距离 d4(s4,x4)——第四阶段本身的损益函数。实例中即从D1、D2两点到终点E的实际 距离。它取决于该段中状态变量S4(取D1,D2)和相应的决策变量x4(S4),在本例 中x4(D1)及x4(D2)均为终点E。 min{d4(s4,x4)}-—由实际问题决定。因为各状态终点的可行路线可能不止一条, 于是就取该阶段中各状态到终点E的路线中最短者。所以本例中取min。如果需要目标 函数的取值以大者为优(求最长路线问题),则应改min为max。 具体来看,当k=4时,因状态变量可取两个点:S4=D,S4=D2,又因D1,D2 两点到终点E的路线分别只有唯一的一条路线D1→E及D2→E,所以∫4(D)即 f(S4=D)=min{、(D1,E)},f:(D2)即f(S4=D2)=min{d、(D2,E)} 分别是D1,D2到终点E的最短距离。 k=3时,有动态规划的最优决策原则,目标函数优值f(s3)应综合考虑第三阶段本 身和第四阶段两者结合为整体的最优。所以目标函数优值(反应了第三阶段状态S3的最 优后部策略)也就是在前面基本概念中提出的最优损益函数
中所处的状态。例如，在例 2 中， ( ) 5 11 16 f 2 B1 = + = ，表示在第二阶段时，状态 到终 点 B1 E 的最优损益函数值(即点 B1到终点 E 的最短后部路线长度)为 16，同理， ( ) 1 12 f 2 B = 。 E f 4 ( ) 4 = min{d4 (s4 , x4 )} 2 E 4 D1 D2 4 S 4 x E D1 D2 D1 ( ) D2 ( 4 D1 f ) S } f ( ) 4 4 D2 f S = = S3 有了上述的基本概念，我们便可将实际问题用下面介绍的动态规划模型来表示。 6.2.2 动态规划的数学模型建立方法 现在我们结合网络最短路线来介绍动态规划方法中所使用的数学模型将如何建立。 例 6.2 建立例 1 的最短路线问题的数学模型，见示意图 6-2。 动态规划的数学模型包括目标函数和约束条件两部分。对于该最短路线问题求的是 从始点 A到终点 E 的距离为最短。又因为这是多阶段决策问题，所以相应的动态规划方 法应将问题首先划分为若干个阶段。然后再按上面所述的基本思想，从终点 逐段向始 点方向寻找每阶段的最优决策。这是一个逆向递推的过程，用动态规划的术语表示出对 目标函数的要求就是求得每个阶段的最优损益函数(最短后部路线的长度)。下面的工作 就是具体建立这种按阶段表达的数学模型。 动态规划的约束条件可由实际问题决定。例如例 1 中最短路线问题，在网络路线图 上用带有箭头的线段表示可行的通路，箭头的方向表示行进的方向。这种方向通常都是 单向的，不能反向行进。 具体表达这种具有“递推”特性的数学模型如下：首先将问题划分为四个阶段，分 别记为k = i(i = 1,2,3,4) ，其次，按逆向建模。 k = 4 时目标函数的优值为 s （6-1） 其中 ——例 1 中网络路线上第四阶段中状态变量 取为 、 两点时，由 此两点分别到达终点 ( ) 4 4 f s 4 S D1 D E 的最短距离。 ( , ) 4 4 4 d s x ——第四阶段本身的损益函数。实例中即从 D1、D2 两点到终点 的实际 距离。它取决于该段中状态变量 （取 ， )和相应的决策变量 （ )，在本例 中 （ )及 均为终点 S 4 x D1 x ( 4 D2 ) 。 min{ ( , ) 4 4 4 d s x }——由实际问题决定。因为各状态终点的可行路线可能不止一条， 于是就取该阶段中各状态到终点 E 的路线中最短者。所以本例中取 min。如果需要目标 函数的取值以大者为优（求最长路线问题），则应改 min 为 max。 具体来看，当k = 4 时，因状态变量可取两个点： 4 D1 S = ，S4 = D2 ，又因 ， 两点到终点 E 的路线分别只有唯一的一条路线 及 ，所以 即 ， 即 → E D2 → E ( ) min ) f 4 4 = D1 = {d4 (D1 , E 4 min{d4 (D2 , E)} 分别是 D1， D2 到终点 E 的最短距离。 k = 3时，有动态规划的最优决策原则，目标函数优值 ( ) 3 3 f s 应综合考虑第三阶段本 身和第四阶段两者结合为整体的最优。所以目标函数优值（反应了第三阶段状态 的最 优后部策略）也就是在前面基本概念中提出的最优损益函数
所以令x()=5:时 f,(s,)=mind, (s3, x, )+(s4) (6-2) f(s3)——第三阶段目标函数的最优值 d(s3x3)-—第三阶段的阶段损益函数 在本例中即点C1,C2,C3分别到D和D2两点的实际距离。 因此,k=3时,状态变量S取值为三点即C1,C2,C3,相应的目标函数优值有三 个 f()Ep5(s,=C)=min d, (C1, D)+(D), d,(C, D2 )+A4(D) f(c2)即f(s3=C2)=min{43(C2,D1)+f(D)d(C2,D2)+f(D2), f(c3)即f(s3=C3)=min{a2(C3,D1)+(D)d3(C3,D2)+f(D2) k=2时,最优损益函数f2(s2)应综合考虑该阶段损益D2(s2,x2)及其在第三阶段受 到影响的状态设为s3=x2(2)到终点E的最短距离f(s3)整体为优。 所以,第二阶段的递推关系式为 f(s2)=min{a2(2x2)+f(s3) (6-3) 具体看,k=2时,状态变量s2取值为两点即B1及B2,相应的目标函数优值有两个 f2(B)即 f(s2=B1)=min2(B1,C1)+f(C1)d2(B1,C2)+f(C2)d2(B,C3)+f(C3) f2(B2)=min{a2(B2C1)+f(C1)d2(B2,C2)+f(C2)d2(B2C3)+f(C3) k=1时,由始点A到终点E要经点B或B2’选择经哪个点才能保证A经四个阶段 后到达E所走的距离最短?这就应综合考虑第一阶段的阶段效益d(s12x1)以及由x(1) 影响到的第二阶段的状态(设为s2)的最优损益函数/(s2),才能得到点A的最优后部 策略的数量表示f(4),也就是始点A到终点E的最优损益值。 所以,k=1时,目标函数最优值的一般表达式为 f(s1)=min{d1(s1,x1)+f(2) (6-4) 由于第一阶段上状态S1只取终点A,即S1=A,因而只能列出一个最优损益值 f1(4)即f(1=A)=min{1(,B1)+f2(B1)d1(4,B2)+f(B2) 通过上面的讨论,可知求f(4)的全过程是倒过来(由k=4开始向前计算),逐段 递推的过程。换句话说,想求得第一阶段的f(s),必须先计算第二阶段的∫2(s2),而 想求f(2),应先求第三阶段的f(3),而f(s3)的求解必须先求得第四阶段的f(s4) 为此我们可以把这种逆推方法推广到阶段数为任意正整数k的问题(k=1,2
所以令 时 ( ) 3 3 4 x s = s f 3 ( ) s3 = min{d3 (s3 , x3 ) + f 4 (s4 )} （6-2） ( ) 3 3 f s ——第三阶段目标函数的最优值 ( , ) 3 3 3 d s x ——第三阶段的阶段损益函数 在本例中即点C1，C2 ，C3分别到 D1和 D2 两点的实际距离。 因此， 时，状态变量 取值为三点即C ，C ，C ，相应的目标函数优值有三 个： k = 3 S3 1 2 3 ( ) 3 1 f c 即 f s 3 3 ( ) = = C1 min{d3 (C1, D1 ) + f4 (D1 ),d3 (C1, D2 ) + f4 (D2 )}， ( 3 2 f c )即 ( ) { } ( ) ( ) ( ) ( ) 3 3 2 3 2 1 4 1 3 2 2 4 2 f s = C = min d C , D + f D ,d C , D + f D ， ( ) 3 3 f c 即 ( ) { } ( ) ( ) ( ) ( ) 3 3 3 3 3 1 4 1 3 3 2 4 2 f s = C = min d C , D + f D ,d C , D + f D ， k = 2 时，最优损益函数 f 2 (s2 )应综合考虑该阶段损益 ( ) 2 2 2 D s , x 及其在第三阶段受 到影响的状态设为 ( 3 2 2 s = x s )到终点 E 的最短距离 ( ) 3 3 f s 整体为优。 所以，第二阶段的递推关系式为 f 2 ( ) s2 = min{d2 (s2 , x2 ) + f 3 (s3 )} （6-3） 具体看，k = 2 时，状态变量s2 取值为两点即 B1及 B2，相应的目标函数优值有两个： ( ) 2 B1 f 即 f 2 ( ) s2 = B1 = min{d2 (B1 ,C1 ) + f 3 (C1 ),d2 (B1 ,C2 ) + f3 (C2 ),d2 (B1 ,C3 ) ( + f 3 C3 )} ( ) { } ( ) ( ) ( ) ( ) ( ) ( 2 2 2 2 1 3 1 2 2 2 3 2 2 2 3 3 3 f B = min d B ,C + f C ,d B ,C + f C ,d B ,C + f C ) k = 1时，由始点 A到终点 E 要经点 或 ，选择经哪个点才能保证 经四个阶段 后到达 B1 B2 A E 所走的距离最短？这就应综合考虑第一阶段的阶段效益d1 (s1 , x1 )以及由 ( ) 1 1 x s 影响到的第二阶段的状态（设为s2 ）的最优损益函数 ( ) 2 2 f s ，才能得到点 的最优后部 策略的数量表示 ，也就是始点 到终点 A f1 (A) A E 的最优损益值。 所以，k = 1时，目标函数最优值的一般表达式为： f1 ( ) s1 = min{d1 (s1 , x1 ) + f 2 (s2 )} （6-4） 由于第一阶段上状态 只取终点 ，即S S1 A 1 = A ，因而只能列出一个最优损益值 f (A) 1 即 f1 ( ) s1 = A = min{d1 (A, B1 ) + f 2 (B1 ), d1 (A, B2 ) ( + f B2 )} 通过上面的讨论，可知求 f1 (A)的全过程是倒过来（由k = 4 开始向前计算），逐段 递推的过程。换句话说，想求得第一阶段的 ( ) 1 1 f s ，必须先计算第二阶段的 ，而 想求 ，应先求第三阶段的 ( ) 2 2 f s ( ) 2 2 f s ( ) 3 3 f s ，而 ( ) 3 3 f s 的求解必须先求得第四阶段的 ( ) 4 s 4 f "",n 。 为此我们可以把这种逆推方法推广到阶段数为任意正整数k 的问题（k = 1,2, ）中
去。得到第k阶段的动态规划数学模型中目标函数优值的表达式为: f:(s)=min(d, (sk, xx)+f& ( skD) (6-5) 公式(6-5)中令x(s)=S4,特别是(6-5)中当k=n时,(最后一个阶段),因 为f(sn)=0,所以规定: x f (s,)=mind, (s,,x (6-6) 上面这个利用了第k阶段与k+1阶段之间递推关系的数学模型(6-5)称为动态规划 的递推公式或函数基本方程 6.3动态规划的求解方法 6.3.1动态规划递推公式的迭代解法 这个解法就是利用递推公式(6-5)直接求解,举例说明如下: 例6.3试用公式(6-5)求解§6.1例1种网络最短路线问题(图6-2) 解:先按建立模型的要求,确定阶段、状态、决策。将问题划分为四个阶段,状态 变量即为各阶段的始点。第一阶段的状态为A;第二阶段的状态为B1,B2;第三阶段 的状态为C1,C2;第四阶段的状态为D,D2。则所有状态均具有无后效性且能列举出 来。每阶段的决策允许集合与§6.2中建立公式(6-5)时所述一致,在此从略。反映第 k阶段与第k+1阶段的状态转移方程sA=84(s4,x4)可由示意图中点的推移过程反映 出这种函数关系,不一定非要表达成数学形式。最后,用于计算的递推公式便是(6-5) 迭代过程如下: k=4时,考虑点D1,D2分别到终点E的最短距离(s4),此时各有一条路D1→E 及D,→E,又因为k=4为最后一个阶段,所以由公式(6-6) S(D)=mind(D, E))=min 8)=8 f(D2)=mn{4(D2E)}=min9}=9 则D1到E的最短路线是8,路线为D1→E,对D2,也有x4(D2)=E k=3时,考虑从点C1,C2,C3到终点E的最短距离f(S),对点C1到E可经过D1 或D2两点,由公式(6-5) f3C)=min(4(C1,D1)+D)d3(C1,D2)+f4(D2)}=min{3+86+9}=11 即点C1到E的最短距离为11,最短路线为C1→D1→E,C1的决策为x3(C1)=D1。 同理,对点C2有
去。得到第k 阶段的动态规划数学模型中目标函数优值的表达式为： = 1 k E ) C1 1 f k ( ) sk = min{dk (sk , xk ) + f k+1 (sk+1 )} （6-5） k = 1,2,"",n 公式（6-5）中令 xk ( ) sk = sk+1 ，特别是（6-5）中当k = n 时，（最后一个阶段），因 为 f n+1 ( ) sn+1 0，所以规定： f n (sn ) = min{dn (sn , xn )} （6-6） 上面这个利用了第 阶段与 阶段之间递推关系的数学模型（6-5）称为动态规划 的递推公式或函数基本方程。 k k +1 6.3 动态规划的求解方法 6.3.1 动态规划递推公式的迭代解法 这个解法就是利用递推公式（6-5）直接求解，举例说明如下： 例 6.3 试用公式（6-5）求解§6.1 例 1 种网络最短路线问题（图 6-2）。 解：先按建立模型的要求，确定阶段、状态、决策。将问题划分为四个阶段，状态 变量即为各阶段的始点。第一阶段的状态为 ；第二阶段的状态为 ， ；第三阶段 的状态为 ，C ；第四阶段的状态为 ，D 。则所有状态均具有无后效性且能列举出 来。每阶段的决策允许集合与§6.2 中建立公式（6-5）时所述一致，在此从略。反映第 阶段与第 阶段的状态转移方程 A 2 ( gk B1 B2 C 2 +1 D1 k k s , ) 1 k k = s x + 可由示意图中点的推移过程反映 出这种函数关系，不一定非要表达成数学形式。最后，用于计算的递推公式便是（6-5）。 迭代过程如下： k = 4 时,考虑点 D1，D2 分别到终点 E 的最短距离 ，此时各有一条路 及 ，又因为 为最后一个阶段，所以由公式（6-6） ( ) 4 4 f s D1 → E D2 → E k = 4 ( ) min{ ( , )} min{8} 8 f 4 D1 = d4 D1 E = = ( ) min{ ( , )} min{9} 9 f 4 D2 = d4 D2 E = = 则 D1到 的最短路线是 8，路线为 D1 → E ，对 D2 ，也有 x4 (D2 ) = E 。 k = 3时，考虑从点C1，C2 ，C3到终点 E 的最短距离 f 3 (s3 ) ，对点C1到 E 可经过 或 两点，由公式（6-5） D1 D2 f3 ( = min{d3 ( ) C1 , D1 + f 4 (D1 ),d3 (C1 , D2 ) + f 4 (D2 )} = min{3 + 8,6 + 9} = 11 即点C 到 E 的最短距离为 11，最短路线为C1 → D1 → E ，C1的决策为 3 1 1 x (C ) = D 。 同理，对点C2 有
f(C2)=min{3(C2,D1)+f(D)d3(C2,D2)+/(D2)=min6+82+9=11 其最短距离是1,其路线是C2→D2→>E 决策为x3(C2)=D 对点C3有 f(C3)=min{3(C3,D)+f4(D1)d2(C3,D2)+f(D2)=mn4+8,3+9}=12 点C3到E的最短距离是12,其路线可有两条:C3→>D1→>E,C3→>D2→E,决 策为x3(C3)=D1或x3(C3)=D2均可 k=2时,考虑两点B1,B2到终点的最短距离/2(s2),对点B1有 f2(B1)=min{a2(B,C1)+f(C1)d2(B1,C2)+f3(C2)d3(B1,C3)+f(C3) =min6+115+117+12}=16 则最短路线为B1→C2→D1→E,且x2(B1)=C2 从点B2出发,有 f2(B2)=min{a2(B2,C1)+f(C1)d2(B2,C2)+f3(C2)d(B2,C)+f(c3) =min5+11112}=12 则最短路线为B2→C2→D1→E,x2(B2)=C2 k=1时,考虑始点E的最短距离f(s1),有 f(A)=min(4(A,B)+f2(B)d1(A,B2)+f2(B2)}=min3+162+12}=14 所以,始点A决策为x1(4)=B2,最短距离为14,其路线为A→B2→C2→D2→>E。 整个迭代过程至此结束。 最后,可按计算顺序反推,得最优的决策序列x1(4)=B2,x2(B2)=C2,x3(C2)=D1, x:(C1)=E构成了本问题的最优策略 用数学模型(6-5)直接求解,由于数学公式中符号抽象,所以容易出错。下面再 介绍两种较为形象、直观和简捷的计算方法,成为标号法和表格求解法。这两种方法都 是根据动态规划的求优原则由递推公式 (6-5)演化而来 6.3.2动态规划的网络标号法 网络标号法就是直接在网络图上进行 计算的方法,现在仍通过求解例1种网络 最短路线来阐述 例6.4设有一个网络线路(图6-2), 试用标号法求出由A到E的最短路线。 图6-5
f3 (C2 ) = min{ } d3 ( ) C2 , D1 + f 4 (D1 ),d3 (C2 , D2 ) + f 4 (D2 ) = min{6 + 8,2 + 9} = 11 其最短距离是 11，其路线是C2 → D2 → E ， 决策为 3 2 1 x (C ) = D 对点C3有 f3 (C3 ) = min{ } d3 ( ) C3 , D1 + f 4 (D1 ),d3 (C3 , D2 )+ f 4 (D2 ) = min{4 + 8,3 + 9}= 12 点C3到 E 的最短距离是 12，其路线可有两条：C ，C ，决 策为 或 均可。 3 → D1 → E 3 → D2 → E 3 1 x ) 3 (C = D 3 3 2 x (C ) = D k = 2 时，考虑两点 B1， B2到终点的最短距离 f 2 (s2 ) ，对点 B1有 { ( ) ( ) ( ) ( ) ( ) ( )} min{ } 6 11,5 11,7 12 16 ( ) min , , , , , 2 1 2 1 1 3 1 2 1 2 3 2 3 1 3 3 3 = + + + = f B = d B C + f C d B C + f C d B C + f C 则最短路线为 B1 → C2 → D1 → E ，且 2 1 2 x (B ) = C 从点 B2出发，有 { ( ) ( ) ( ) ( ) ( ) ( )} min{ } 5 11,1 11,1 12 12 ( ) min , , , , , 2 2 2 2 1 3 1 2 2 2 3 2 3 2 3 3 3 = + + + = f B = d B C + f C d B C + f C d B C + f C 则最短路线为 B2 → C2 → D1 → E ， 2 2 2 x (B ) = C k = 1时，考虑始点 E 的最短距离 f1 (s1 )，有 ( ) min{ } ( ) , ( ), ( , ) ( ) min{3 16,2 12} 14 f1 A = d1 A B1 + f 2 B1 d1 A B2 + f 2 B2 = + + = 所以，始点 决策为 ，最短距离为 14，其路线为 。 整个迭代过程至此结束。 A 1 2 x (A) = B A → B2 → C2 → D2 → E 最后，可按计算顺序反推，得最优的决策序列 1 2 x (A) = B ，x ，x 2 2 2 (B ) = C 3 2 1 (C ) = D ， x4 (C1 ) = E 构成了本问题的最优策略。 用数学模型（6-5）直接求解，由于数学公式中符号抽象，所以容易出错。下面再 介绍两种较为形象、直观和简捷的计算方法，成为标号法和表格求解法。这两种方法都 是根据动态规划的求优原则由递推公式 （6-5）演化而来。 图 6-5 C3 D2 C2 B2 E D1 3 B1 1 5 2 1 3 9 8 5 7 6 6 2 4 A C1 3 6 6.3.2 动态规划的网络标号法 网络标号法就是直接在网络图上进行 计算的方法，现在仍通过求解例 1 种网络 最短路线来阐述。 例 6.4 设有一个网络线路（图 6-2）， 试用标号法求出由 A到 E 的最短路线
