第二部分动态规划( Dymamic Programming) 第三章动态规划 动态规划是解决一类多阶段决策问题的优化方法,也是考察问题的一种途 径,而不是一种算法(如LP单纯形法)。因此它不象LP那样有一个标准的数 学表达式和明确定义的一组规则,而必须对具体问题进行具体分析处理。 动态规划方法是现代企业管理中的一种重要决策方法。如果一个问题可将 其过程划分为若干个相互联系的阶段问题,且它的每一阶段都需进行决策,则 这类问题均可用动态规划方法进行求解。 根据多阶段决策过程的时序和决策过程的演变,动态规划方法有以下四种 类型:离散确定性、离散随机性、连续确定性和连续随机性。 §1动态规划的基本概念和最优化原理 、引例(最短路线问题) E C 上图是一个线路网络,两点之间连线上的数字表示两点间的距离(或费 用),试求一条由A到E的铺管线路,使总距离最短(或总费用最小)。 将该问题划分为4个阶段的决策问题,即第一阶段为从A到B(j=1,2, 3),有三种决策方案可供选择;第二阶段为从B1到C(j=1,2,3),也有三种方 案可供选择;第三阶段为从G到D(=1,2),有两种方案可供选择;第四阶段 为从D到E,只有一种方案选择。如果用完全枚举法,则可供选择的路线有3
1 第二部分 动态规划（Dymamic Programming） 第三章 动态规划 动态规划是解决一类多阶段决策问题的优化方法，也是考察问题的一种途 径，而不是一种算法（如 LP 单纯形法）。因此它不象 LP 那样有一个标准的数 学表达式和明确定义的一组规则，而必须对具体问题进行具体分析处理。 动态规划方法是现代企业管理中的一种重要决策方法。如果一个问题可将 其过程划分为若干个相互联系的阶段问题，且它的每一阶段都需进行决策，则 这类问题均可用动态规划方法进行求解。 根据多阶段决策过程的时序和决策过程的演变，动态规划方法有以下四种 类型：离散确定性、离散随机性、连续确定性和连续随机性。 §1 动态规划的基本概念和最优化原理 一、引例（最短路线问题） B1 1 C1 5 6 8 6 A 3 B2 C2 3 D1 5 6 E B3 6 C3 5 D2 A 1 B 2 C 3 D 4 E 上图是一个线路网络，两点之间连线上的数字表示两点间的距离（或费 用），试求一条由 A 到 E 的铺管线路，使总距离最短（或总费用最小）。 将该问题划分为 4 个阶段的决策问题，即第一阶段为从 A 到 Bj（j=1，2， 3），有三种决策方案可供选择；第二阶段为从 Bj 到 Cj（j=1,2,3），也有三种方 案可供选择；第三阶段为从 Cj 到 Dj(j=1,2)，有两种方案可供选择；第四阶段 为从 Dj 到 E，只有一种方案选择。如果用完全枚举法，则可供选择的路线有 3 3 2 4 3 8 7 4 5 8 3
×3×2×1=18(条),将其一一比较才可找出最短路线: A→B1→C2→D3→E 其长度为15。 显然,这种方法是不经济的,特别是当阶段数很多,各阶段可供的选择也 很多时,这种解法甚至在计算机上完成也是不现实的。 由于我们考虑的是从全局上解决求A到E的最短路问题,而不是就某 阶段解决最短路线,因此可考虑从最后一阶段开始计算,由后向前逐步推至A 点 第四阶段,由D1到E只有一条路线,其长度f4①D1)=4,同理f4(D2)=3 第三阶段,由C到D分别均有两种选择,即 C D,+D) 6+4 f C=m CD2+f,(D=m08+3/=10,决策点为D f(C2) C2D,+A(D) 3+4 mll C2D2+/)L5+3/=7,决策点为D S(C)=min,D,+AD) 8+4 min C,D,+D 5+3 8,决策点为D2 第二阶段,由B到G分别均有三种选择,即: BCI+f(C 1+10 f1(B)=mnBC2+/2)=m3+7|=10,决策点为C2 B,C3+f3(C, 6+8 B,C2+fi(c 8+10 (B)=mnBC2+f(2)=m17+71=14,决策点为C2或C3 B,C3+f(C3) 6+8 BC+f(Cu f2(B3)=mBC2+f(C2)=mn4+7=11,决策点为C2 LB, C3+f,(3) 6+8 第一阶段,由A到B,有三种选择,即
2 ×3×2×1=18（条），将其一一比较才可找出最短路线： A→B1→C2→D3→E 其长度为 15。 显然，这种方法是不经济的，特别是当阶段数很多，各阶段可供的选择也 很多时，这种解法甚至在计算机上完成也是不现实的。 由于我们考虑的是从全局上解决求 A 到 E 的最短路问题，而不是就某一 阶段解决最短路线，因此可考虑从最后一阶段开始计算，由后向前逐步推至 A 点： 第四阶段，由D1到E 只有一条路线，其长度f4（D1）=4，同理f4（D2）=3。 第三阶段，由 Cj 到 Di 分别均有两种选择，即 ( ) ( ) ( ) 10 8 3 6 4 min min 1 2 4 2 1 1 4 1 3 1 = + + = + + = C D f D C D f D f C ，决策点为 D1 ( ) ( ) ( ) 7 5 3 3 4* min min 2 2 4 2 2 1 4 1 3 2 = + + = + + = C D f D C D f D f C ,决策点为 D1 ( ) ( ) ( ) 8 5 3 8 4 min min 3 2 4 2 3 1 4 1 3 3 = + + = + + = C D f D C D f D f C ，决策点为 D2 第二阶段，由 Bj 到 Cj 分别均有三种选择，即： ( ) ( ) ( ) ( ) 10 6 8 3 7 1 10 min min * 3 3 3 3 2 2 3 2 1 1 3 1 2 1 = + + + = + + + = B C f C B C f C B C f C f B ，决策点为 C2 ( ) ( ) ( ) ( ) 14 6 8 7 7 8 10 min min * 3 3 3 3 2 2 3 2 2 2 3 1 2 2 = + + + = + + + = B C f C B C f C B C f C f B ，决策点为 C2 或 C3 ( ) ( ) ( ) ( ) 11 6 8 4 7 2 10 min min * 3 3 3 3 3 2 3 2 3 1 3 1 2 3 = + + + = + + + = B C f C B C f C B C f C f B ，决策点为 C2 第一阶段，由 A 到 B，有三种选择，即：
AB,+52 B, 5+10 f(-=mAB2+f(B)=mn3+14|=15,决策点为B AB3+f2(B3) 5+11 fA=15)说明从A到E的最短铺管线长为1,最短路线的确定可按计算顺 序反推而得。即 A→B1→C2→D1→E 上述最短路线问题的计算过程,也可借助于图形直观的表示出来 D B 图中各点上方框的数,表示该点到E的最短距离。图中双箭线表示从A 到E的最短路线。 从引例的求解过程可以得到以下启示: ①对一个问题是否用上述方法求解,其关键在于能否将问题转化为相互联 系的多个阶段的决策问题 所谓多阶段决策问题是:把一个问题看作是一个前后关联具有链状结构的 多阶段过程,也称为序贯决策过程。如下图所示: 决策 决策 决策 状态 状态 状态 状态 状态 ②在处理各阶段决策的选取上,不仅只依赖于当前面临的状态,而且还要
3 ( ) ( ) ( ) ( ) 15 5 11 3 14 5 10 min min 5 2 5 2 2 2 1 2 2 1 = + + + = + + + = AB f B AB f B AB f B f A ，决策点为 B1 f1(A=15)说明从 A 到 E 的最短铺管线长为 1，最短路线的确定可按计算顺 序反推而得。即 A→B1→C2→D1→E 上述最短路线问题的计算过程，也可借助于图形直观的表示出来： 10 10 B1 C1 4 5 3 D1 15 14 7 3 0 A B2 C2 E D2 11 8 B3 C3 图中各点上方框的数，表示该点到 E 的最短距离。图中双箭线表示从 A 到 E 的最短路线。 从引例的求解过程可以得到以下启示： ①对一个问题是否用上述方法求解，其关键在于能否将问题转化为相互联 系的多个阶段的决策问题。 所谓多阶段决策问题是：把一个问题看作是一个前后关联具有链状结构的 多阶段过程，也称为序贯决策过程。如下图所示： 决策 决策 决策 状态 状态 状态 状态 状态 1 2 n ②在处理各阶段决策的选取上，不仅只依赖于当前面临的状态，而且还要 4 3
注意对以后的发展。即是从全局考虑解决局部(阶段)的问题 ③各阶段选取的决策,一般与“时序”有关,决策依赖于当前的状态,又 随即引起状态的转移,整个决策序列就是在变化的状态中产生出来,故有“动 态”含义。因此,把这种方法称为动态规划方法。 ④决策过程是与阶段发展过程逆向而行 、动态规划的基本概念 阶段。阶段的划分,一般根据时序和空间的自然特征来划分,但要便 于把问题的过程能转化为阶段决策的过程。描述阶段的变量称为阶段变量,常 用自然数k表示。如引例可划分为4个阶段求解,k=1,2,3,4。 2、状态。状态就是阶段的起始位置。它既是该阶段某支路的起点,又是 前一阶段某支路的终点 (1)状态变量和状态集合。描述过程状态的变量称为状态变量。它可用 一个数、一组数或一向量(多维情形)来描述,常用Sk表示第k阶段的状态 变量。通常一个阶段有若干个状态。第k阶段的状态就是该阶段所有始点的集 合。如引例中 S1={4,S2={B,B2B},S3=C1C2C3},S4={D,D} (2)状态应具有无后效性(即马尔可夫性)。即如果某阶段状态给考虑, 则在这阶段以后过程的发展不受这阶段以前各阶段状态的影响。 在构造决策过程的动态规划模型时,不能仅由描述过程的具体特征这点去 规定状态变量,而要充分注意是否满足无后效性要求。 3、决策与决策变量。在某阶段对可供选择状态的决定(或选择),称为决 策。描述的变量称为决策变量。常用dk(Sk)表示第k阶段处于状态S时的决策 变量,它是状态变量的函数。决策变量允许取值的范围,称为允许决策集合, 常用D(Sk)表示。显然dk(Sk)∈D(Sk) 如在引例的第一阶段中,若从B1出发,D2(B1)=1C2C3},如果决定 选取C2,则d2(B1)=C2
4 注意对以后的发展。即是从全局考虑解决局部（阶段）的问题。 ③各阶段选取的决策，一般与“时序”有关，决策依赖于当前的状态，又 随即引起状态的转移，整个决策序列就是在变化的状态中产生出来，故有“动 态”含义。因此，把这种方法称为动态规划方法。 ④决策过程是与阶段发展过程逆向而行。 二、动态规划的基本概念 1、阶段。阶段的划分，一般根据时序和空间的自然特征来划分，但要便 于把问题的过程能转化为阶段决策的过程。描述阶段的变量称为阶段变量，常 用自然数 k 表示。如引例可划分为 4 个阶段求解，k=1，2，3，4。 2、状态。状态就是阶段的起始位置。它既是该阶段某支路的起点，又是 前一阶段某支路的终点。 （1）状态变量和状态集合。描述过程状态的变量称为状态变量。它可用 一个数、一组数或一向量（多维情形）来描述，常用 Sk 表示第 k 阶段的状态 变量。通常一个阶段有若干个状态。第 k 阶段的状态就是该阶段所有始点的集 合。如引例中 S1 = A， S2 = B1 ,B2 ,B3， S3 = C1 ,C2 ,C3，S4 = D1 ,D2 （2）状态应具有无后效性（即马尔可夫性）。即如果某阶段状态给考虑， 则在这阶段以后过程的发展不受这阶段以前各阶段状态的影响。 在构造决策过程的动态规划模型时，不能仅由描述过程的具体特征这点去 规定状态变量，而要充分注意是否满足无后效性要求。 3、决策与决策变量。在某阶段对可供选择状态的决定（或选择），称为决 策。描述的变量称为决策变量。常用 dk(Sk)表示第 k 阶段处于状态 Sk 时的决策 变量，它是状态变量的函数。决策变量允许取值的范围，称为允许决策集合， 常用 Dk(Sk)表示。显然 dk（Sk）∈Dk(Sk)。 如在引例的第一阶段中，若从 B1 出发，D2（B1）=C1 ,C2 ,C3 ，如果决定 选取 C2，则 d2（B1）=C2
4、策略与子策略。策略是一个决策序列的集合。当k=1时,Pn(S1 a(S)d(S3)…d、Sn}就称为全过程的一个策略,简称策略,简记为Pn(Sn) 称Pkn(S={d4(SA)d212(S1)…dn(Sn)为由第k阶段开始到最后阶段止 的一个子策略,简称后部子策略。简记为Pkn(Sk) 称可供选择策略的范围,为允许策略集,用P表示。 动态规划方法就是要从允许策略集P中找出最优策略Pn*。 状态转移方程。它是确定过程由某一阶段的一个状态到下一阶段另 状态的演变过程,用Sk+1=Ik(Skdk)表示。该方程描述了由第k阶段到第k+1 阶段的状态转移规律。因此又称其为状态转移函数。 6、阶段指标、指标函数和最优指标函数 (1)衡量某阶段决策效益优劣的数量指标,称为阶段指标,用w(Sk,dk) 表示第k阶段的阶段指标 在不同的问题中,其含义不同。它可以是距离、利润、成本等。 在引例中,用dk=Uk(Skdk)表示在第k阶段由点Sk到点Sk+=dk(Sk)距离。 如d2(B3,C1)=2。 (2)用于衡量所选定策略优劣的数量指标,称为指标函数。它是定义在 全过程和所有后部子过程上确定的数量函数。记为Vkn(Sk,Pkn) Vk,n(Sk, Pk,nVkn(Sk, dk, Sk+1, Sn+1)k=1, 2, ...,no 构成动态规划模型的指标函数,应具有可分离性,并满足递推关系。 常见的指标函数的形式有 ①H(,u25S1…,Sm)=∑(s,d)=(S,d1)+1(sn,Pn) vk (SK, uk, Sm.,Sm)=Iu, (S, u,)=v2( u dx )v( (3)最优指标函数f(Sk),表示从第k阶段的状态Sk开始采用最优子策略 *kn,到第n阶段的终止时所得到的指标函数值
5 4、策略与子策略。策略是一个决策序列的集合。当 k=1 时，Pin（S1） =d1 (S1 ),d2 (S2 ), dn (Sn ) 就称为全过程的一个策略，简称策略，简记为 Pin(S1). 称 Pk,n(Sk)= dk (Sk1 ),dk +12(Sk +1 ), dn (Sn ) 为由第 k 阶段开始到最后阶段止 的一个子策略，简称后部子策略。简记为 Pk,n(Sk) 称可供选择策略的范围，为允许策略集，用 P 表示。 动态规划方法就是要从允许策略集 P 中找出最优策略 Pin*。 5、状态转移方程。它是确定过程由某一阶段的一个状态到下一阶段另一 状态的演变过程，用 Sk+1=Tk(Sk,dk)表示。该方程描述了由第 k 阶段到第 k+1 阶段的状态转移规律。因此又称其为状态转移函数。 6、阶段指标、指标函数和最优指标函数 （1）衡量某阶段决策效益优劣的数量指标，称为阶段指标，用 vk(Sk,dk) 表示第 k 阶段的阶段指标。 在不同的问题中，其含义不同。它可以是距离、利润、成本等。 在引例中，用 dk=Uk(Sk,dk)表示在第 k 阶段由点 Sk 到点 Sk+1=dk(Sk)距离。 如 d2(B3,C1)=2。 （2）用于衡量所选定策略优劣的数量指标，称为指标函数。它是定义在 全过程和所有后部子过程上确定的数量函数。记为 Vk,n(Sk,Pk,n). Vk,n(Sk,Pk,n)=Vk,n(Sk,dk,Sk+1,…Sn+1) k=1,2,…,n。 构成动态规划模型的指标函数，应具有可分离性，并满足递推关系。 常见的指标函数的形式有： ① ( ) ( ) ( ) ( ) k ku k k k k k n n j k Vk,n Sk uk Sk 1 Sn 1 v j S j d j v S d V 1, S 1 P , , , , , , , + + = + + = = + ② ( ) ( ) ( ) ( ) , 1 1 1 1 1 1 , , , , , + + + + = + + = = k ku k k k k n n j k Vk n Sk uk Sk Sn ui S ju j v S d V S d S （3）最优指标函数 fk(Sk),表示从第 k 阶段的状态 Sk 开始采用最优子策略 P*k,n，到第 n 阶段的终止时所得到的指标函数值
即f(Sk)= OPtIk(Sk,uk,…Sn+l) 其中OPt是最优化( OPtimisation)的缩写,可根据题意取max或min 在引例中,指标函数Vkn表示在第k阶段由点Sk至终点E的距离。f(sk) 表示第k阶段点Sk到终E的最短距离。f2(B1)=10表示从第2阶段中的点B1 到点E的最短距离。 7、基本方程(递推关系式) 从引例求A到E的最短路的计算过程中可以看出,在求解的各个阶段, 我们利用了k阶段与k+1阶段之间的递推关系 f(s)=min U, (s,, dk)+f2 SK+) d4()∈D4(SA)(k=4,32.1) f(s3)=0 般地, 若Vn=∑,,d则有 IK(sk)=OPIUK (Sk, dk )+/2+(Sk+), dk∈D(Sk)k=n,n-1,…1 fn(Sn)=0(边界条件) 若Vn=∏U(s,d)则有 f(s)=0p{(,d4)f1(3) d4(S)∈D(Sk),(k=n,n-1,…1) fn(Sn)=l(边界条件) 以上递推关系式称为动态规划的基本方程。 、动态规划方法的基本思想与最优化原理 1、基本思想:动态规划方法的关键在于正确地写出基本方程,因此首先 必须将问题的过程划分为多个相互联系的多阶段决策过程,恰当地选取状态变 量和决策变量及定义最优指标函数,从而把问题化成一族冋类型的子问题。然 后从边界条件开始,逆过程行进方向,逐段递推寻优。在每个子问题求解时
6 即 fk(Sk)=0PtVk,n(Sk,uk,…Sn+1) 其中 0Pt 是最优化（0Ptimiyation）的缩写，可根据题意取 max 或 min。 在引例中，指标函数 Vk,n 表示在第 k 阶段由点 Sk 至终点 E 的距离。fk(sk) 表示第 k 阶段点 Sk 到终 E 的最短距离。f2(B1)=10 表示从第 2 阶段中的点 B1 到点 E 的最短距离。 7、基本方程（递推关系式） 从引例求 A 到 E 的最短路的计算过程中可以看出，在求解的各个阶段， 我们利用了 k 阶段与 k+1 阶段之间的递推关系； ( ) ( ) ( ) ( ) ( ) ( ) ( ) = = = + + + 0 , 4,3,2,1 min , 5 5 1 1 f s d s D S k f s U s d f s k k k k k k k k k k k 一般地， 若 ( ) = = n j k Vk n U j S j d j , , , 则有 = = − = + + + + + ( ) 0( ) ( ) , 1, 1 ( ) 0 ( , ) ( ) , 1 1 1 1 n n 边界条件 k k k k k k k k k k f s d D s k n n f s Pt U s d f s 若 = = n j k k n j j d j V , U (s , ),则有 = = − = + + + + ( ) 1( ) ( ) ( ),( , 1, 1) ( ) 0 ( , ) ( ) 1 1 1 1 n n 边界条件 k k k k k k k k k k k f s d s D s k n n f s pt U s d f s 以上递推关系式称为动态规划的基本方程。 三、动态规划方法的基本思想与最优化原理 1、基本思想：动态规划方法的关键在于正确地写出基本方程，因此首先 必须将问题的过程划分为多个相互联系的多阶段决策过程，恰当地选取状态变 量和决策变量及定义最优指标函数，从而把问题化成一族同类型的子问题。然 后从边界条件开始，逆过程行进方向，逐段递推寻优。在每个子问题求解时
均利用它前面己求出的子问题的最优化结果依次进行,最后一个子问题所得的 最优解,就是整个问题的最优解。 在多阶段决策过程中,动态规划方法是既把当前的一段和未来的各段分 开,又把当前效益和未来效益结合起来考虑的一种最优化方法。因此,每阶段 决策的选取是从全局来考虑,与该段的最优选择一般是不同的。 动态规划方法的基本思想体现了多阶段性、无后效性、递归性、总体优化 最优化原理 动态规划方法基于R· Bellman等人提出的最优化原理:“作为整个过程 的最优策略具有这样的性质,即无论过去的状态和决策如何,对于先前的决策 所形成的状态而言,余下的诸决策必须构成最优策略。”简言之,“一个最优策 略的子策略总是最优的”。 但是,最优化原理仅是策略最优性的必要条件,而基本方程是策略最优性 的充要条件。由此可见,基本方程是动态规划理论与方法的基础。 §2、动态规划模型的建立与求解 一、构成动态规划模型的条件 建立动态规划模型,就是分析问题并建立问题的动态规划基本方程。为此, 必须满足以下条件 1、将问题的过程划分成恰当的阶段; 2、正确选择状态变量S,使它既能描述过程的演变,又要满足无后效性; 3、确定决策变量dk及每阶段的允许决策集合D(Sk) 4、正确写出状态转移方程 5、正确写出指标函数Vkn的关系式,它应具有以下三个性质 (1)是定义全过程和所有后部子过程上的数量函数;
7 均利用它前面已求出的子问题的最优化结果依次进行，最后一个子问题所得的 最优解，就是整个问题的最优解。 在多阶段决策过程中，动态规划方法是既把当前的一段和未来的各段分 开，又把当前效益和未来效益结合起来考虑的一种最优化方法。因此，每阶段 决策的选取是从全局来考虑，与该段的最优选择一般是不同的。 动态规划方法的基本思想体现了多阶段性、无后效性、递归性、总体优化 性。 2、最优化原理 动态规划方法基于 R·Bellman 等人提出的最优化原理：“作为整个过程 的最优策略具有这样的性质，即无论过去的状态和决策如何，对于先前的决策 所形成的状态而言，余下的诸决策必须构成最优策略。”简言之，“一个最优策 略的子策略总是最优的”。 但是，最优化原理仅是策略最优性的必要条件，而基本方程是策略最优性 的充要条件。由此可见，基本方程是动态规划理论与方法的基础。 §2、动态规划模型的建立与求解 一、构成动态规划模型的条件 建立动态规划模型，就是分析问题并建立问题的动态规划基本方程。为此， 必须满足以下条件： 1、将问题的过程划分成恰当的阶段； 2、正确选择状态变量Sk，使它既能描述过程的演变，又要满足无后效性； 3、确定决策变量 dk 及每阶段的允许决策集合 Dk(Sk)； 4、正确写出状态转移方程； 5、正确写出指标函数 Vk,n 的关系式，它应具有以下三个性质； （1）是定义全过程和所有后部子过程上的数量函数；
(2)具有可分离性,并满足递推关系,即 Vk, n(Sk, dk, " Sn+1)=c(Sk, dk, vk+1, n) (3)函数e(Skdk,Vk+ln)对于Vk+1n要求严格单调 以上五点是正确写出动态规划基本方程的要素。 、求解动态规划模型的方法 1、在已知初始状态S1下,采用逆序解法:(反向递归) dI(sn) d2( 2) dk+I(Sk+1) dn(sn) v2(S2,V2) V2(SK, Vu) Viti(Sk+1, vk+1) V(So,vn) fi(StOPt Vkn 寻优方向 按上图示意的求解方法称为逆序法。例如引例的求解,就是把A看作始 端,E为终端,规定从A到E为过程的行进方向,而寻优则是从E到A逆过 程进行,所以是采用了逆序法。 2、在已知终止状态Sn下,采用顺序解法(正向递归) 如果我们把引例中E看作始端,A为终端,规定从E到A过程为行进方 向,而寻优则是从A到E过程进行求解的方法称为顺序法。其示意图如下 d(s1) d2(S2) d k+I(Sk+1) d,(sn) 阶段1 阶段2-匚阶段k 阶段k+1 阶段n vI(SI, du) 2(S2,da) Sk, d) Vk+1(Sk+1,dk+1) Vn(Sn, dn) 寻优方向 逆序法与顺序法的不同仅在对始端终端看法的颠倒或在规定的行进方向 不同。但在寻优时却都是逆行进方向,从最后一阶段开始,逐段逆推向前计算
8 （2）具有可分离性，并满足递推关系，即 Vk,n(Sk,dk,…Sn+1)=¢ (Sk,dk,Vk+1,n) （3）函数¢（Sk,dk,Vk+1,n）对于 Vk+1,n要求严格单调。 以上五点是正确写出动态规划基本方程的要素。 二、求解动态规划模型的方法 1、在已知初始状态 S1 下，采用逆序解法：（反向递归） d1(s1) d2(S2) dk(Sk) dk+1(Sk+1) dn(Sn) S1 S2 Sk Sk+1 Sn Sn+1 阶段 1 阶段 2 阶段 k 阶段 k+1 阶段 n v1(S1,v1) v2(S2,v2) v2(Sk,vk) vk+1(Sk+1,vk+1) vn(Sn,vn) Vkn fk(Sk)=0ptVk,n 寻优方向 按上图示意的求解方法称为逆序法。例如引例的求解，就是把 A 看作始 端，E 为终端，规定从 A 到 E 为过程的行进方向，而寻优则是从 E 到 A 逆过 程进行，所以是采用了逆序法。 2、在已知终止状态 Sn 下，采用顺序解法（正向递归） 如果我们把引例中 E 看作始端，A 为终端，规定从 E 到 A 过程为行进方 向，而寻优则是从 A 到 E 过程进行求解的方法称为顺序法。其示意图如下： d1(s1) d2(S2) dk(Sk) dk+1(Sk+1) dn(Sn) S S1 S2 Sk Sk+1 Sn 阶段 1 阶段 2 阶段 k 阶段 k+1 阶段 n v1(S1,d1) v2(S2,d2) vk(Sk,dk) vk+1(Sk+1,dk+1) vn(Sn,dn) V1,k fk,(Sk)=0ptV1,k 寻优方向 逆序法与顺序法的不同仅在对始端终端看法的颠倒或在规定的行进方向 不同。但在寻优时却都是逆行进方向，从最后一阶段开始，逐段逆推向前计算
找出最优结果。 3、两种解法在建模时的区别如下表所示 逆序法 状态转移方程Sx+=IkSk,dk) Sk-1=Tk(Sk, dk) W∑v(S,d) v=∑v(S,d) 指标函数定义 fi(SkF-OPt Vk,n或wm∏1u(S,d) (s,d) AS)=Os4)+s,1|c=0.4)+A dk∈D.(k=n,n-1,…1) dk∈D(k=12,…n) fn+(Sn1)=0 基本方程形式 f(Sk=OPt(V, (Sk, dk).R()) f(s)=0P{(s2d4)·f-(-) dk∈D(k=n,n-1,…1) dk∈D(k Mm (SnD=I f(S0) §3、建模训练与求解 维资源分配问题 例1某工业部门根据国家计划的安排,拟将某种高效率的设备五台,分配 给所属的甲、乙、丙三个工厂,各工厂获得这种设备,可以提供的期望盈利如 下表所示。问如何分配这五台设备给各厂,才能使国家得到的期望盈利最大? 盈利 甲 设备台数 0 0 3 5 2 04612 解:设x(j=1,2,3)分别表示分配给甲、乙、丙三个厂的设备台数,则此
9 找出最优结果。 3、两种解法在建模时的区别如下表所示 逆 序 法 顺 序 法 状态转移方程 Sk+1=Tk(Sk,dk) Sk-1=Tk(Sk,dk) 指标函数定义 Vk,n== n j k j S j d j v ( , ) fk(Sk)=0Pt Vk,n 或 Vk,n= = n j k u j S j d j ( , ) V1,k== k j j S j d j v 1 ( , ) fk(Sk)=0Pt V1,k 或 V1k== k j j j d j v s 1 ( , ) 基本方程形式 = = − = + + + + + ( ) 0 ( , 1, 1) ( ) { ( , ) ( )} 1 1 1 1 n n k k k k k k k k k f S d D k n n f S OPt v S d f S = = − = + + + + ( ) 1 ( , 1, 1) ( ) { ( , ) ( )} 1 1 1 1 n n k k k k k k k k k f S d D k n n f S OPt v S d f S = = = + − − ( ) 0 ( 1,2, ) ( ) 0 ( , ) ( 0 0 1 1) f s d D k n f S Pt V S d f s k k k k k k k k k = = = − − ( ) 1 ( 1,2, ) ( ) 0 ( , ) ( ) 0 0 1 1 f s d D k n f s Pt U s d f s k k k k k k k k k §3、建模训练与求解 一、维资源分配问题 例 1 某工业部门根据国家计划的安排，拟将某种高效率的设备五台，分配 给所属的甲、乙、丙三个工厂，各工厂获得这种设备，可以提供的期望盈利如 下表所示。问如何分配这五台设备给各厂，才能使国家得到的期望盈利最大？ 工厂 盈利 设备台数 甲 乙 丙 0 1 2 3 4 5 0 3 7 9 12 13 0 5 10 11 11 11 0 4 6 11 12 12 解：设 xj（j=1,2,3）分别表示分配给甲、乙、丙三个厂的设备台数，则此
问题可写成以下数学模型:max=gi(x1)+g2(x2)+g3(x3) x1x2x3≥0,且皆为整数 其中g(x1)g2(x2)gx3)分别对应表中甲、乙、丙厂的期望盈利数 先考虑构成动态规划模型的条件 1、按工厂将问题划分为三个阶段,并将工厂编号为k=1,2,3 2、设状态变量Sk表示为分配给第k个工厂至第3个工厂的设备台数。(显 然S1=5,所以可考虑用逆序法。) 3、决策变量ⅹk,表示为分配给第k个工厂的设备数。0≤Xk≤Sk 状态转移方程为Sk+1=Sk-Xk 5、阶段指标g(skxk)表示Xk设备分配到第k个工厂所得的期望盈利值。 因此基本方程为 f()=mx{g(s,x4)+f1(S4-x)} 0≤xk≤Sk(k=32,1) f4(S4)=0 下面用逆序法采用表格形式进行求解 k=3, 0≤X3≤S3 S4=S3-X3 S X3(S3 g(S3,X3)+f4(S4) f3(S3) X3*(S3) 0 0 0 4+0* 4 6+0* 12+0* 12 12+0* k=2 0≤X2≤S2 S3=S2-X
10 问题可写成以下数学模型：max=g1(x1)+g2(x2)+g3(x3) + + = 0,且皆为整数 5 1. 2. 3 1 2 3 x x x x x x 其中 g1(x1),g2(x2),g3(x3)分别对应表中甲、乙、丙厂的期望盈利数。 先考虑构成动态规划模型的条件： 1、按工厂将问题划分为三个阶段，并将工厂编号为 k=1,2,3。 2、设状态变量 Sk 表示为分配给第 k 个工厂至第 3 个工厂的设备台数。（显 然 S1=5，所以可考虑用逆序法。） 3、决策变量 Xk，表示为分配给第 k 个工厂的设备数。0≤Xk≤Sk。 4、状态转移方程为 Sk+1=Sk-Xk 5、阶段指标 gk(sk,xk)表示 Xk 设备分配到第 k 个工厂所得的期望盈利值。 因此基本方程为： = = = + + − ( ) 0 0 ( 3,2,1) ( ) max ( , ) ( ) 4 4 1 f s x s k f s g s x f s x k k k k k k k k k k 下面用逆序法采用表格形式进行求解 k=3, 0≤X3≤S3 S4=S3-X3 S3 X3(S3) g3(S3，X3)+f4(S4) f3(S3) X3*(S3) 0 0 0+0 0 0 1 1 4+0* 4 1 2 2 6+0* 6 2 3 3 11+0* 11 3 4 4 12+0* 12 4 5 5 12+0* 12 5 k=2 0≤X2≤S2 S3=S2－X2