《运筹学》讲义 第二部分 动态规划（Dymamic Programming）

第二部分动态规划( 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 阶段的终止时所得到的指标函数值