运筹(第八章动态规划)

1、2022-6-51运筹学运筹学OPERATIONS RESEARCH2022-6-52第八章第八章 动态规划动态规划n 多阶段决策最优化问题举例多阶段决策最优化问题举例n基本概念、基本方程与最优化原理基本概念、基本方程与最优化原理n离散确定性动态规划求解离散确定性动态规划求解n离散随机性动态规划求解离散随机性动态规划求解n一般数学规划模型的动态规划解法一般数学规划模型的动态规划解法2022-6-531 1多阶段决策过程最优化问题举例多阶段决策过程最优化问题举例例例1 1 最短路径问题最短路径问题下图表示从起点下图表示从起点A A到终点到终点E E之间各点的距离。求之间各点的距离。求A A到到E

2、 E的最短路径。的最短路径。BACBDBCDEC41231231232216472483867561106437512022-6-54用穷举法的计算量用穷举法的计算量: :如果从如果从A A到到E E的站点有的站点有k k个，除个，除A A、E E之外每站有之外每站有3 3个位个位置则总共有置则总共有3 3k-1k-12 2条路径；条路径；计算各路径长度总共要进行计算各路径长度总共要进行 (k+1) 3(k+1) 3k-1k-12 2次加法次加法以及以及3 3k-1k-12-12-1次比较。随着次比较。随着 k k 的值增加时，需要的值增加时，需要进行的加法和比较的次数将迅速增加；进行的加法和

3、比较的次数将迅速增加；例如例如 k=20k=20时，加法次数为时，加法次数为 4.25508339662274.255083396622710101515 次，比较次，比较 1.37260754729771.372607547297710101414 次。次。若用若用1 1亿次亿次/ /秒的计算机计算需要约秒的计算机计算需要约508508天。天。2022-6-55讨论：讨论：1 1、以上求从、以上求从A A到到E E的最短路径问题，可以转化为四个的最短路径问题，可以转化为四个 性质完全相同，但规模较小的子问题，即分别从性质完全相同，但规模较小的子问题，即分别从 D Di i 、C Ci i、B

4、 Bi i、A A到到E E的最短路径问题。的最短路径问题。 第四阶段：第四阶段：两个始点两个始点D D1 1和和D D2 2，终点只有一个；，终点只有一个； 表表-1-1分析得知：从分析得知：从D D1 1和和D D2 2到到E E的最短路径唯一。的最短路径唯一。 阶段4本阶段始点（状态）本阶段各终点（决策）到E的最短距离本阶段最优终点（最优决策) E D1 D2 10 6 10 6 E E2022-6-56 第三阶段第三阶段：有三个始点有三个始点C C1 1，C C2 2，C C3 3，终点有，终点有D D1 1，D D2 2，对始点和终点进行分析和讨论分别求对始点和终点进行分析和讨论分别

5、求C C1 1，C C2 2，C C3 3到到D D1 1，D D2 2 的最短路径问题：的最短路径问题： 表-2 分析得知：如果经过分析得知：如果经过C C1 1，则最短路为则最短路为C C1 1-D-D2 2-E-E； 如果经过如果经过C C2 2，则最短路为则最短路为C C2 2-D-D2 2-E-E； 如果经过如果经过C C3 3，则最短路为，则最短路为C C3 3-D-D1 1-E-E。 阶段3本阶段始点（状态）本阶段各终点（决策）到E的最短距离本阶段最优终点（最优决策) D1 D2 C1 C2 C3 8+10=18 7+10=17 1+10=11 6+6=12 5+6=11 6+6

6、=12 12 11 11 D2 D2 D12022-6-57第二阶段第二阶段：有有4 4个始点个始点B B1 1,B,B2 2,B,B3 3,B,B4 4，终点有，终点有C C1 1,C,C2 2,C,C3 3。对始点和终点进行分析和讨论分别求对始点和终点进行分析和讨论分别求B B1 1,B,B2 2,B,B3 3,B,B4 4到到C C1 1,C,C2 2,C,C3 3 的最短路径问题：的最短路径问题： 表-3分析得知：如果经过分析得知：如果经过B B1 1，则走，则走B B1 1-C-C2 2-D-D2 2-E-E； 如果经过如果经过B B2 2，则走，则走B B2 2-C-C3 3-D-

7、D1 1-E-E； 如果经过如果经过B B3 3，则走，则走B B3 3-C-C3 3-D-D1 1-E-E； 如果经过如果经过B B4 4，则走，则走B B4 4-C-C3 3-D-D1 1-E-E。 阶段2本阶段始点（状态） 本阶段各终点（决策）到E的最短距离本阶段最优终点（最优决策) C1 C2 C3 B1 B2 B3 B4 2+12=14 4+12=16 4+12=16 7+12=19 1+11=12 7+11=18 8+11=19 5+11=16 6+11=17 2+11=13 3+11=14 1+11=12 12 13 14 12 C2 C3 C3 C32022-6-58第一阶段：

8、第一阶段：只有只有1 1个始点个始点A A，终点有，终点有B B1 1,B,B2 2,B,B3 3,B,B4 4 。对。对始点和终点进行分析和讨论分别求始点和终点进行分析和讨论分别求A A到到B B1 1,B,B2 2,B,B3 3,B,B4 4的的最短路径问题：最短路径问题： 表10-4最后，可以得到：最后，可以得到：从从A A到到E E的最短路径为的最短路径为A A B B4 4 C C3 3 D D1 1 E E 阶段1本阶段始点(状态) 本阶段各终点（决策）到E的最短距离本阶段最优终点(最优决策) B1 B2 B3 B4 A4+12=16 3+13=163+14=172+12=14 1

9、2 B42022-6-59 以上计算过程及结果，可用图以上计算过程及结果，可用图2 2表示，可以看到，以表示，可以看到，以上方法不仅得到了从上方法不仅得到了从A A到到D D的最短路径，同时，也得的最短路径，同时，也得到了从图中任一点到到了从图中任一点到E E的最短路径。的最短路径。 以上过程，仅用了以上过程，仅用了2222次加法，计算效率远高于穷举次加法，计算效率远高于穷举法。法。BACBDBCDEC412312312332164724838675161060106121111121314144B1275122022-6-510例例2 2 资源分配问题资源分配问题设有某种机器数台，用于完成两

10、类工作设有某种机器数台，用于完成两类工作A A，B B。由于。由于机器使用后有一定的损坏率，所以每年初的机器数机器使用后有一定的损坏率，所以每年初的机器数量是变化的；量是变化的；A A、B B两项工作产生的收益也不同。如两项工作产生的收益也不同。如何合理的分配机器的使用，可使得三年的总收益最何合理的分配机器的使用，可使得三年的总收益最大大? ? 假设第假设第k k年年初完好机器数是年年初完好机器数是S SK K，用于用于A A生产的生产的机器数是机器数是X XK K，则用于则用于B B生产的机器数是（生产的机器数是（S SK K- X- XK K）；）； 用于用于A A工作的设备的完好率是：工

11、作的设备的完好率是：a%a%，用于，用于B B工作工作的设备的完好率是：的设备的完好率是：b%b%。则下一年初的完好机器数。则下一年初的完好机器数是是 S SK+1K+1= a% X= a% XK K+ b% + b% （S SK K- X- XK K）第第k k年的收益：年的收益： h(X h(XK K)+ g(S)+ g(SK K- X- XK K) )2022-6-511例例3 3 背包问题背包问题设有设有n n种物品，每一种物品数量无限。第种物品，每一种物品数量无限。第i i种物品每种物品每件重量为件重量为w wi i公斤，每件价值公斤，每件价值c ci i元。现有一只可装载重元。现有

12、一只可装载重量为量为W W公斤的背包，求各种物品应各取多少件放入背公斤的背包，求各种物品应各取多少件放入背包，使背包中物品的价值最高。包，使背包中物品的价值最高。 这个问题可以用整数规划模型来描述。设这个问题可以用整数规划模型来描述。设x xi i为第为第I I种物品装入背包的件数（种物品装入背包的件数（i i =1, 2, , =1, 2, , n n），背包），背包中物品的总价值为中物品的总价值为z z，则，则 Max z = cMax z = c1 1x x1 1+c+c2 2x x2 2+ +c+ +cn nx xn n s.t. w s.t. w1 1x x1 1+w+w2 2x x

13、2 2+w+wn nx xn nW W x x1 1, x, x2 2, , x, , xn n 0 0 且为整数。且为整数。2022-6-512动态规划动态规划是用来解决是用来解决多阶段决策多阶段决策过程最优化的一种过程最优化的一种方法。方法。多阶段决策：多阶段决策：是动态决策问题的一种特殊形式；是动态决策问题的一种特殊形式； 系统的动态过程可以按照时间等进程分为状态系统的动态过程可以按照时间等进程分为状态相互联系相互联系 而又相互区别的各个阶段；而又相互区别的各个阶段； 每个阶段都要进行决策每个阶段都要进行决策, ,目的是使整个过程的目的是使整个过程的决策达到最优效果决策达到最优效果多阶段

14、决策求解思路：多阶段决策求解思路：将多阶段决策问题（将多阶段决策问题（n n阶段）分解成阶段）分解成n n个具有递推关个具有递推关系的单阶段决策问题，进行正推或逆推计算。系的单阶段决策问题，进行正推或逆推计算。2022-6-5132.1 2.1 基本概念基本概念 1 1、阶段、阶段k k：表示决策顺序的离散的量，阶段可以按表示决策顺序的离散的量，阶段可以按时间或空间划分。时间或空间划分。( (顺序编号法、逆序编号法）顺序编号法、逆序编号法） 2 2、状态、状态s sk k：反应前一阶段决策的结果，又是本阶段反应前一阶段决策的结果，又是本阶段作决策的依据和出发点（能确定地表示决策过程作决策的依据

15、和出发点（能确定地表示决策过程当前特征的量）。状态可以是数量，也可以是字当前特征的量）。状态可以是数量，也可以是字符，数量状态可以是连续的，也可以是离散的。符，数量状态可以是连续的，也可以是离散的。 2 2基本概念、基本方程与最优化原理基本概念、基本方程与最优化原理2022-6-5143 3、决策、决策x xk k：从某一状态向下一状态过渡时所做的选从某一状态向下一状态过渡时所做的选择。决策是所在状态的函数，记为择。决策是所在状态的函数，记为x xk k(s(sk k) )。 决策允许集合决策允许集合D Dk k(s(sk k) )：在状态在状态s sk k下，允许采取决策下，允许采取决策的全

16、体的全体4 4、策略、策略Pk,n(sk)Pk,n(sk)：从第从第k k阶段开始到最后第阶段开始到最后第n n阶段的阶段的决策序列，称决策序列，称k k子策略。子策略。P1,n(s1)P1,n(s1)即为全过程策略。即为全过程策略。2022-6-5155 5、状态转移方程、状态转移方程: : S Sk+1k+1=T=Tk k(S(Sk k, X, Xk k) )：某一状态以及：某一状态以及该状态下的决策，与下一状态之间的函数关系。该状态下的决策，与下一状态之间的函数关系。6 6、阶段指标函数、阶段指标函数V Vk k(S(Sk k, X, Xk k) )：从状态从状态S Sk k出发，选择决

17、出发，选择决策策X Xk k所产生的第所产生的第k k阶段指标。阶段指标。 过程指标函数过程指标函数V Vk,nk,n(S(Sk k；X Xk k, X, Xk+1k+1, X, Xn n) )：从状态从状态S Sk k出发，选择决策出发，选择决策X Xk k, X, Xk+1k+1, , Xn, , Xn所产生的过程指所产生的过程指标。标。2022-6-516动态规划要求过程指标具有可分离性动态规划要求过程指标具有可分离性，即即 V Vk,nk,n(s(sk k, x, xk k, x, xk+1k+1, , x, , xn n) = V) = Vk k(s(sk k, x, xk k)+V

18、)+Vk+1k+1(s(sk+1k+1, x, xk+1k+1, , x, , xn n) )称指标具有称指标具有可加性可加性，或或 V Vk,nk,n(s(sk k, x, xk k, x, xk+1k+1, , x, , xn n) = v) = vk k(s(sk k, x, xk k) )V Vk+1k+1(s(sk+1k+1, x, xk+1k+1, , x, , xn n) )称指标具有称指标具有可乘性可乘性。2.2 2.2 基本方程基本方程最优指标函数最优指标函数f fk k(s(sk k) )：从状态从状态s sk k出发，对所有的策略出发，对所有的策略P Pk,nk,n，过程

19、指标，过程指标V Vk,nk,n的最优值，即的最优值，即 ),()(,)(nkknksDxkkPsVsfoptkkk2022-6-517对于可加性指标函数，上式可以写为对于可加性指标函数，上式可以写为 上式中上式中“opt”opt”表示表示“max”max”或或“min”min”。对于可乘性指标函数，上式可以写为对于可乘性指标函数，上式可以写为 以上式子称为动态规划最优指标的递推方程，是动以上式子称为动态规划最优指标的递推方程，是动态规划的态规划的基本方程基本方程。终端条件终端条件：为了使以上的递推方程有递推的起点，：为了使以上的递推方程有递推的起点，必须要设定最优指标的终端条件，一般最后一个

20、状必须要设定最优指标的终端条件，一般最后一个状态态n+1n+1下最优指标下最优指标f fn+1n+1(s(sn+1n+1) = 0) = 0。n, 2 , 1k)s (f)x,s (v)s (f1k1kkkk)s (Dxkkoptkkkn, 2 , 1k)s (f)x,s (v)s (f1k1kkkk)s (Dxkkoptkkk2022-6-5182.3 2.3 最优化原理最优化原理 作为整个过程的最优策略具有如下性质：作为整个过程的最优策略具有如下性质： 不管在此最优策略上的某个状态以前的状不管在此最优策略上的某个状态以前的状态和决策如何，对该状态来说，以后的所有决态和决策如何，对该状态来说

21、，以后的所有决策必定构成最优子策略。就是说策必定构成最优子策略。就是说，最优策略的最优策略的任意子策略都是最优的。任意子策略都是最优的。2022-6-519例例1 某警卫部门共有某警卫部门共有9支巡逻队，负责三个要害部位支巡逻队，负责三个要害部位A、B、C的警卫巡逻。每个部位分别可派出的警卫巡逻。每个部位分别可派出24支巡逻队，并且支巡逻队，并且由于派出的队伍数量不同，各部位预期的损失有差别，由于派出的队伍数量不同，各部位预期的损失有差别，详见下表。各部位应各分派多少支巡逻队可是预期的总详见下表。各部位应各分派多少支巡逻队可是预期的总损失最小。请用动态规划方法求解。损失最小。请用动态规划方法求

22、解。3 3离散确定性动态规划模型求解离散确定性动态规划模型求解部位巡逻队数 预期损失ABC2183824314352241031212022-6-520解：解：设将向三个部位设将向三个部位A A，B B，C C派巡逻队作为三个阶段，派巡逻队作为三个阶段，K=1K=1， 2 2，3 3。 决策变量决策变量 表示向第表示向第K K个部位派遣的巡逻队数。个部位派遣的巡逻队数。 状态变量状态变量 表示第表示第K K个阶段时可供派遣的巡逻队数量。个阶段时可供派遣的巡逻队数量。 状态转移方程：状态转移方程： 阶段指标函数：阶段指标函数： 派遣派遣 支巡逻队时第支巡逻队时第K K阶段产阶段产生的预期损失；生

23、的预期损失； 过程指标函数：过程指标函数： 第第K K阶段到第阶段到第3 3阶段的预期损失。阶段的预期损失。 最优指标函数：最优指标函数： kxkskkkxss1)(kkxpkx3 , 13 ,)(kkkkVxpV)()(min)(11)(kkKKSDxkksfXPsfKk2022-6-521逆序解法：逆序解法：边界条件边界条件 当当K=3K=3时，给时，给C C派巡逻队，派巡逻队， ， 0)(44sf5 , 4 , 3 , 2)(3sD4 , 3 , 23x 2342 24 -2423 24 22 -2234 24 22 212145 24 22 212143x3s)(33sf3*x)()(

24、min)(443333sfxpsf)x,s (v3332022-6-522当当K=2K=2时，给时，给B B派巡逻队，派巡逻队， 23 4538+22 35+24 -593638+21 35+22 31+24554738+21 35+21 31+22534)()(min)(2232222xsfxpsf7 , 6 , 5)(2sD4 , 3 , 22x2x2s)(22sf2*x)()(22322xsfxp2022-6-523当当K=1K=1时，给时，给A A派巡逻队，派巡逻队， )()(min)(1121111xsfxpsf 9)(1sD4 , 3 , 21x 23 4918+53 14+55

25、10+59693，41x1s)(11sf1*x)()(11211xsfxp最优方案最优方案： A A派派3 3支巡逻队，支巡逻队，B B派派4 4支巡逻队，支巡逻队，C C派派2 2支巡逻队；支巡逻队；或：或：A A派派4 4支巡逻队，支巡逻队，B B派派3 3支巡逻队，支巡逻队，C C派派2 2支巡逻队支巡逻队 2022-6-524解解2 2：顺序解法：顺序解法 设将向三个部位设将向三个部位A A，B B，C C派巡逻队作派巡逻队作为三个阶段，为三个阶段，K=1K=1，2 2，3 3。 决策变量决策变量 表示向第表示向第K K个部位派遣的巡逻队数。个部位派遣的巡逻队数。 状态变量状态变量 表

26、示前表示前K-1K-1个阶段可派遣的巡逻队数个阶段可派遣的巡逻队数量。量。 状态转移方程：状态转移方程： ， 阶段指标函数：阶段指标函数： 派遣派遣 支巡逻队时第支巡逻队时第K K阶段产生的预期损失；阶段产生的预期损失； 最优指标函数：前最优指标函数：前K K个阶段的最优目标个阶段的最优目标 kxkskkkxss1)(kkxpkx)()(min)(1)(1kkKKSDxkksfXPsfKk)(1kkkxss2022-6-525顺序解法：顺序解法： 边界条件边界条件 当当K=1K=1时，给时，给A A派巡逻队，派巡逻队， ，0)(10sf5 , 4 , 3 , 2)(2sD4 , 3 , 21x

27、 234218182318 14143418 14 10104518 14 101041x2s)(21sf1*x)()(1011sfxp2022-6-526当当K=2K=2时，给时，给B B派巡逻队，派巡逻队，7 , 6 , 5)(3sD4 , 3 , 22x 23 4538+14 35+18522638+10 35+14 31+18482738+10 35+10 31+14533，42x3s)(32sf2*x)()(23111xsfxp)()(min)(212232sfxpsf2022-6-527当当K=3K=3时，给时，给C C派巡逻队，派巡逻队，)()(min)(2223343xsfxp

28、sf 9)(4sD4 , 3 , 23x 23 4924+45 22+48 21+526923x4s)(43sf3*x)()(3233sfxp最优方案最优方案： A A派派3 3支巡逻队，支巡逻队，B B派派4 4支巡逻队，支巡逻队，C C派派2 2支巡逻队；支巡逻队；或：或：A A派派4 4支巡逻队，支巡逻队，B B派派3 3支巡逻队，支巡逻队，C C派派2 2支巡逻队支巡逻队 2022-6-528例例2 2 资源分配问题资源分配问题 (P208(P208例例5 5）假设第假设第k k年年初完好机器数是年年初完好机器数是S SK K，用于用于A A生产的机器生产的机器数是数是X XK K，则

29、用于则用于B B生产的机器数是（生产的机器数是（S SK K - X- XK K）；）；用于用于A A工作的设备的完好率是：工作的设备的完好率是： ，用于，用于B B工作的工作的设备的完好率是：设备的完好率是：0.90.9。则下一年初的完好机器数。则下一年初的完好机器数是是 S SK+1K+1= X= XK K+0.9+0.9（S SK K- X- XK K）第第k k年的收益：年的收益： 10X10XK K+ 7(S+ 7(SK K- X- XK K) )32a32,7)(10)(xxhxxg0)(44sf边界条件：边界条件：)()(710max)(110kkkkksxkksfxsxsfkk

30、2022-6-5290)(44sf逆序解法：逆序解法：边界条件边界条件 当当K=3K=3时时，第三年初分配机器，第三年初分配机器 台生产台生产A A， 台生台生产产B B ， 3x33xs 3334433303310)()(710max)(33sxssfxsxsfsx当当K=2K=2时时，第二年初分配机器，第二年初分配机器 台生产台生产A A， 台台生产生产B B，2x22xs 22222sx0222222sx033222sx022sxs3216s16x32max)xs (109x3210)xs (7x10max)s (f)xs (7x10max)s (f2222222022-6-530当当K

31、=1K=1时时，第，第1 1年初分配机器年初分配机器 台生产台生产A A， 台台生产生产B B ，1x11xs 022009 . 02200max)(1093210)(710max)()(710max)(11100011111102211101111111xxxsxxsxsfxsxsfxsxsx1001s最优方案最优方案：第一年所有机器第一年所有机器100100台用于生产台用于生产B B， 第二年初完好机器第二年初完好机器9090台；台；第二年所有机器第二年所有机器9090台用于生产台用于生产A A， 第三年初完好机器第三年初完好机器6060台；台；第三年所有机器第三年所有机器6060台用于生

32、产台用于生产A A， 第四年初完好机器第四年初完好机器4040台。台。2022-6-5314 4离散随机动态规划模型求解离散随机动态规划模型求解随机动态规划：随机动态规划：状态转移规律不定，在给定的状态状态转移规律不定，在给定的状态和决策下，下一阶段到达的状态是具有确定概率分和决策下，下一阶段到达的状态是具有确定概率分布的随机变量。布的随机变量。第第k+1阶段阶段可能状态可能状态SkXkn21第第k阶段状态阶段状态决策决策P1，C1P2，C2Pn，CnP Pi i：在决策：在决策X Xk k下出现状态下出现状态i i的概率的概率C Ci i：在决策：在决策X Xk k下出现状态下出现状态i i

33、时的指时的指标函数标函数2022-6-532随机动态规划中，对指标函数进行优化时，要根据随机动态规划中，对指标函数进行优化时，要根据各阶段的各阶段的期望效益期望效益进行优化。进行优化。基本方程改写为：基本方程改写为：)(),()(11)(kkkkSDxkksfxsvEoptsfKk例：例：P210P210，例，例6 6 解：解：阶段变量阶段变量K K， 每月投产一批作为一个阶段，每月投产一批作为一个阶段，K=1K=1，2 2，3 3。 状态变状态变量量 ：表示第：表示第K K阶段所拥有的合格样品数，有两阶段所拥有的合格样品数，有两种可能状态。种可能状态。 表示有一台以上的合格品；表示有一台以上

34、的合格品； 表示没有一台合格品。表示没有一台合格品。ks0ks1ks2022-6-533决策变量决策变量 ：表示第：表示第K K个阶段决定投产的数量个阶段决定投产的数量。kx状态转移律状态转移律：kkxkxkspsp321)0(32) 1(11阶段指标函数：阶段指标函数：0, 01,100250),(kkkkkssxxsc最优指标函数最优指标函数 ：表示第表示第K K阶段在阶段在 状态下，状态下，做决策做决策 时，到最后一个阶段的最小期望费用。时，到最后一个阶段的最小期望费用。 )(kksfkskx2022-6-534Sk=1Xk第第k阶段状态阶段状态决策决策Sk=0Sk+1=1Sk+1=0K

35、X32KX321第第k+1阶段状态阶段状态)(),()(11)(kkkkSDxkksfxscEoptsfKk易知：易知：4 , 3 , 2, 0)0(ksfkk)0(321 ) 1(32),(min) 1(1111)(kkxkkxkkSDxkksfsfxscsfkkKk2022-6-535逆序解法：逆序解法：边界条件边界条件 当当K=3K=3时，第三阶段之后的最小期望费用时，第三阶段之后的最小期望费用 0)0(33sf) 1(32),(min) 1(4433)(33333sfxscsfxSDx1500) 1(44sf 0 1 2 3 4 500 0011500 1350 1117 994 94

36、6 94894643x3s)(33sf3*x) 1(32),(44333sfxscx150032100250) 1(32),(3334433xxxsfxsc1500) 1(44sf2022-6-536当当K=2K=2时，第二阶段之后的最小期望费用时，第二阶段之后的最小期望费用0)0(22sf) 1(32),(min) 1(3322)(22222sfxscsfxSDx 0 1 2 3 4 500 001946 981 870 830 837 83032x2s)(22sf2*x) 1(32),(33222sfxscx946) 1(33sf94632100250) 1(32),(2223322xxxsfxsc2022-6-537当当K=1K=1时，第一阶段之后的最小期望费用时，第一阶段之后的最小期望费用) 1(32),(min) 1(2211)(11111sfxscsfxSDx 0 1 2 3 4 51830 903 819 796 81479631x1s)(11sf1*x) 1(32),(22111sfxscx830) 1(22sf最优方案最优方案：第