可能性的选择描述决策的变量,称为决策变量,用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 有