第10章动态规划

1、管管 理理 运运 筹筹 学学1第十章第十章 动态规划动态规划1 多阶段决策过程最优化问题举例多阶段决策过程最优化问题举例2 基本概念、基本方程与最优化原理基本概念、基本方程与最优化原理3 动态规划的应用动态规划的应用(1)4 动态规划的应用动态规划的应用(2)管管 理理 运运 筹筹 学学21 1 多阶段决策过程最优化问题举例多阶段决策过程最优化问题举例例例1 最短路径问题最短路径问题 下图表示从起点A到终点E之间各点的距离。求A到E的最短路径。BACBDBCDEC4123123123221647248386756110643751管管 理理 运运 筹筹 学学31 1 多阶段决策过程最优化问题举

2、例多阶段决策过程最优化问题举例用穷举法的计算量用穷举法的计算量: 如果从A到E的站点有k个，除A、E之外每站有3个位置则总共有3k-12条路径； 计算各路径长度总共要进行 (k+1) 3k-12次加法以及3k-12-1次比较。随着 k 的值增加时，需要进行的加法和比较的次数将迅速增加； 例如当 k=20时，加法次数为 4.25508339662271015 次，比较 1.37260754729771014 次。若用1亿次/秒的计算机计算需要约508天。管管 理理 运运 筹筹 学学41 1 多阶段决策过程最优化问题举例多阶段决策过程最优化问题举例讨论： 1、以上求从A到E的最短路径问题，可以转化

3、为四个性质完全相同，但规模较小的子问题，即分别从Di 、Ci、Bi、A到E的最短路径问题。 第四阶段：两个始点D1和D2，终点只有一个； 表10-1分析得知：从D1和D2到E的最短路径唯一。 阶段4本阶段始点（状态）本阶段各终点（决策）到E的最短距离本阶段最优终点（最优决策) E D1 D2 10* 6 10 6 E E管管 理理 运运 筹筹 学学5 第三阶段：有三个始点C1，C2，C3，终点有D1，D2，对始点和终点进行分析和讨论分别求C1，C2，C3到D1，D2 的最短路径问题： 表10-2分析得知：如果经过C1，则最短路为C1-D2-E； 如果经过C2，则最短路为C2-D2-E； 如果经

4、过C3，则最短路为C3-D1-E。 1 1 多阶段决策过程最优化问题举例多阶段决策过程最优化问题举例 阶段3本阶段始点（状态）本阶段各终点（决策）到E的最短距离本阶段最优终点（最优决策) D1 D2 C1 C2 C3 8+10=18 7+10=17 1+10=11 6+6=12 5+6=11 6+6=12 12 11 11 D2 D2 D1管管 理理 运运 筹筹 学学6第二阶段：有4个始点B1,B2,B3,B4，终点有C1,C2,C3。对始点和终点进行分析和讨论分别求B1,B2,B3,B4到C1,C2,C3 的最短路径问题： 表10-3 分析得知：如果经过B1，则走B1-C2-D2-E； 如果

5、经过B2，则走B2-C3-D1-E； 如果经过B3，则走B3-C3-D1-E； 如果经过B4，则走B4-C3-D1-E。 1 1 多阶段决策过程最优化问题举例多阶段决策过程最优化问题举例 阶段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 C3管管 理理 运运 筹筹 学学7第一阶段：只有

6、1个始点A，终点有B1,B2,B3,B4 。对始点和终点进行分析和讨论分别求A到B1,B2,B3,B4的最短路径问题： 表10-4最后，可以得到：从A到E的最短路径为A B4 C3 D1 E1 1 多阶段决策过程最优化问题举例多阶段决策过程最优化问题举例 阶段1本阶段始点(状态) 本阶段各终点（决策）到E的最短距离本阶段最优终点(最优决策) B1 B2 B3 B4 A 4+12=16 3+13=163+14=172+12=14 12 C2管管 理理 运运 筹筹 学学8 以上计算过程及结果，可用图2表示，可以看到，以上方法不仅得到了从A到D的最短路径，同时，也得到了从图中任一点到E的最短路径。

7、以上过程，仅用了22次加法，计算效率远高于穷举法。BACBDBCDEC412312312332164724838675161060106121111121314144B1275121 1 多阶段决策过程最优化问题举例多阶段决策过程最优化问题举例管管 理理 运运 筹筹 学学9一、动态规划的基本概念一、动态规划的基本概念 1.阶段阶段 阶段阶段(stage)是对整个过程的自然划分。通常根据时间顺序或空间特征来划分阶段，以便按阶段 的 次 序 解 优 化 问 题 。 阶 段 变 量 一 般 用k=1,2,.,n表示。在例1中由A出发为k=1，由Bi(i=1,2，3,4)出发为k=2，依此下去从Di(

8、i=1,2,)出发为k=4，共n=4个阶段。2 2 基本概念、基本方程与最优化原理基本概念、基本方程与最优化原理管管 理理 运运 筹筹 学学10第一阶段第一阶段第二阶段第二阶段第三阶段第三阶段第四阶段第四阶段BACBDBCDEC4123123123221647248386756110643751管管 理理 运运 筹筹 学学112.状态状态状态(state)表示每个阶段开始时过程所处的自然状况。它应该能够描述过表示每个阶段开始时过程所处的自然状况。它应该能够描述过程的特征并且具有无后向性，即当某阶段的状态给定时，这个阶段以后过程的特征并且具有无后向性，即当某阶段的状态给定时，这个阶段以后过程的演

9、变与该阶段以前各阶段的状态无关，即每个状态都是过去历史的一程的演变与该阶段以前各阶段的状态无关，即每个状态都是过去历史的一个完整总结。通常还要求状态是直接或间接可以观测的。个完整总结。通常还要求状态是直接或间接可以观测的。描述状态的变量称状态变量描述状态的变量称状态变量(state variable)。变量允许取值的范围称允许。变量允许取值的范围称允许状态集合状态集合(set of admissible states)。用。用xk表示第表示第k阶段的状态变量，它可阶段的状态变量，它可以是一个数或一个向量。用以是一个数或一个向量。用Sk表示第表示第k阶段的允许状态集合。在例阶段的允许状态集合。在

10、例1中中S2可可取取B1，B2， B3，B4 , ,则则S2=B1,B2， B3，B4。管管 理理 运运 筹筹 学学12第一阶段第一阶段第二阶段第二阶段第三阶段第三阶段第四阶段第四阶段BACBDBCDEC4123123123221647248386756110643751S2=B1,B2, ,B3,B4管管 理理 运运 筹筹 学学13 n个阶段的决策过程有n+1个状态变量，Sn+1表示Sn演变的结果，在例1中S5取E。 根据过程演变的具体情况，状态变量可以是离散的或连续的。为了计算的方便有时将连续变量离散化；为了分析的方便有时又将离散变量视为连续的。管管 理理 运运 筹筹 学学143.决策决策

11、 当一个阶段的状态确定后，可以作出各种选择从而演变到下一阶段的某个状态，这种选择手段称为决策决策(decision)。 决策是所在状态的函数，记为决策是所在状态的函数，记为xk(sk)。例如。例如x2(B1)=C2表示第表示第2阶段处于阶段处于B1为始点的状态为始点的状态下选择了由下选择了由B1到到C2的决策。的决策。管管 理理 运运 筹筹 学学154.策略策略 决策组成的序列称为策略策略(policy)。由初始状态x1开始的全过程的策略记作p1,n(S1)，即p1,n(S1)=x1(S1),x2(S2),.，xn(Sn)。由第k阶段的状态xk开始到终止状态的后部子过程的策略记作pk,n(Sk

12、)，即pk,n(sk)=xk(sk),xk+1(sk+1),.，xn(sn)。类似地，由第k到第j阶段的子过程的策略记作pk,j(sk)=xk(sk),xk+1(sk+1),.，xj(sj)。管管 理理 运运 筹筹 学学165.指标函数 指标函数是衡量全过程策略或K子过程策略优劣的数量指标，指标函数的最优指称之为最优指标函数，记为)()(11kksfsf或11( )f s表示全过程上的最优指标函数()kkfs表示K过程上的最优指标函数表示从A点开始到到终点E的最短距离为14，从B2点开始到达终点E的最短距离为1311122( )( )14,()13f sf AfB),(jjjxsr表示在第j阶

13、段的sj的状态下做出xj决策的决策指标值，例如 表示在第2阶段以B3为始点，选择C3为终点，则从B3到C2的距离为8.232(,)8r B C管管 理理 运运 筹筹 学学176.状态转移方程状态转移方程 在确定性过程中，一旦某阶段的状态和决策为已知，下阶段的状态便完全确定。用状态转移方程状态转移方程(equation of state)表示这种演变规律，写作: sk+1=Tk(sk ,xk). 在例1中状态转移方程为：s3=C1=T2(B2,C1) 表示当第2个阶段的状态（始点）为B2，决策（终点）为C1时，则第3阶段的状态（始点）为C1 管管 理理 运运 筹筹 学学18二、基本方程二、基本方

14、程 终端条件：为了使以上的递推方程有递推的起点，必须要设定最优指标的终端条件，一般最后一个状态n+1下最优指标fn+1(sn+1) = 0。例1:1111()min(,)(),1,2,2,1()0kkkkkkknnfsrsxfskn nnfs终点条件：1121233211332123321333()min (,)( )(,)()2 12min(,)()min 1 1112(,)()6 11f Br B xf sr B Cf Cr B Cf Cr B Cf C管管 理理 运运 筹筹 学学19一般的递推关系一般的递推关系 其中opt可根据具体情况取max或min。上式的意义是，对于某个阶段k的某个

15、状态sk，从该阶段k到最终目标阶段n的最优指标函数值等于从sk出发取遍所有能策略pk所得到的最优指标值中最优的一个。)11() (,)(),1,22,1kkkkkkkkkkpPsfsoptr sxfskn nn 管管 理理 运运 筹筹 学学20三、最优化原理三、最优化原理 作为整个过程的最优策略具有如下性质： 不管在此最优策略上的某个状态以前的状态和决策如何，对该状态来说，以后的所有决策必定构成最优子策略。就是说，最优策略的任意子策略都是最优的。2 2 基本概念、基本方程与最优化原理基本概念、基本方程与最优化原理管管 理理 运运 筹筹 学学21一、资源分配问题一、资源分配问题 例2. 某公司拟

16、将某种设备5台，分配给所属的甲、乙、丙三个工厂。各工厂获得此设备后，预测可创造的利润如表10-5所示，问这5台设备应如何分配给这3个工厂，使得所创造的总利润为最大？ 表10-5 盈利 工厂设备台数 甲 厂 乙 厂 丙 厂 0 0 0 0 1 3 5 4 2 7 10 6 3 9 11 11 4 12 11 12 5 13 11 123 3 动态规划的应用动态规划的应用(1)(1)管管 理理 运运 筹筹 学学22解：将问题按工厂分为三个阶段，甲、乙、丙三个厂分别编号为1、2、3厂。设 sk= 分配给第k个厂至第3个厂的设备台数（k=1、2、3）。 xk=分配给第k个工厂的设备台数。 已知s1=5

17、, 并有 从与的定义，可知以下我们从第三阶段开始计算。222223),(xsxsTskskx33xs 3 3 动态规划的应用动态规划的应用(1)111112),(xsxsTs管管 理理 运运 筹筹 学学23 第三阶段: 显然将台设备都分配给第3工厂时，也就是时，第3阶段的指标值（即第3厂的盈利）为最大，即 由于第3阶段是最后的阶段，故有 其中可取值为0,1,2,3,4,5。其数值计算见表106。 )5 , 4 , 3 , 2 , 1 , 0(33ss).,(),(max)(333333333ssrxsrsfx3x),(),(max3333333ssrxsrx3 3 动态规划的应用动态规划的应用

18、(1)33xs 管管 理理 运运 筹筹 学学24 表表106 012345000014 4126623111134121245121253x3s),(333xsr)(33sf3*x3 3 动态规划的应用动态规划的应用(1)管管 理理 运运 筹筹 学学25 其中表示取3子过程上最优指标值时的决策，例如在表10-6中可知当=4时，有有此时，即当时，此时取（把4台设备分配给第3厂）是最优决策，此时阶段指标值（盈利）为12，最优3子过程最优指标值也为12。 第二阶段： 当把台设备分配给第2工厂和第3工厂时，则对每个值，有一种最优分配方案，使最大盈利即最优2子过程最优指标函数值为 3*x)(33sf3x

19、3s;12)4 , 4(3r,12)4(3f43*x43s43x)5 , 4 , 3 , 2 , 1 , 0(22ss2s)(),(max)(33222222sfxsrsfx3 3 动态规划的应用动态规划的应用(1)管管 理理 运运 筹筹 学学26因为上式也可写成其数值计算如表107所示。表107 , 223xss0123450 00104 51206 54 1023011 56 110 1424012 114110 161,25012 512 116114 1102122x2s)(),(233222xsfxsr)(22sf2*x00050104101156101110)(),(max)(22

20、3222222xsfxsrsfx3 3 动态规划的应用动态规划的应用(1)管管 理理 运运 筹筹 学学27 其中在的这一行里，当时，这里从表105中可知，把1台设备交给乙厂所得盈利数即可，知，这里从表106查即可知=11。同样可知当时，可知 ;当时，；当时，；当时， ；由于，不可能分2厂5台设备，故时，栏空着不填。从这些数值中取得最大即得，即有=16。在此行中我们在取最大值的 上面加一横以示区别，也可知这时的最优决策为1或2。42s12x16115)3() 1 , 4() 14() 1 , 4()(),(3232223222frfrxsfxsr) 1 , 4(2r5) 1 , 4(2r)3()

21、14(33ff)3(3f) 3(3f22x16610)2()2 , 4()24()2 , 4()(),(3232223222frfrxsfxsr02x12120)04()0 , 4(32 fr32x411)34()3 , 4(32 fr42x11011)44()4 , 4(32 fr42s52x)54()5 , 4(32 fr)4(2f)4(2f)(),(223222xsfxsr2x3 3 动态规划的应用动态规划的应用(1)管管 理理 运运 筹筹 学学28第一阶段：把台设备分配给第1，第2，第3厂时，最大盈利为其中可取值0,1,2,3,4,5.数值计算见表108 表10-8 然后按计算表格的顺

22、序推算，可知最优分配方案有两个： 1.由于，根据，查表107可知，再由 ，求得。即分配给甲厂0台，乙厂2台，丙厂3台。 2.由于，根据 ，查表107可 )5(11ss),5(), 5(max)5(111111xfxrfx1x0123455 316 9+10 12+5 13+0 21 0,21x1s)5(), 5(1211xfxr210147)(1xf1*x01*x5051*12xss02*x3252*23xss333* sx21*x3251*12xss3 3 动态规划的应用动态规划的应用(1)管管 理理 运运 筹筹 学学29知，再由 ,求得，即分配给甲厂2台，乙厂2台，丙厂1台。这两种分配方案

23、都能得到最高的总盈利21万元。 22*x1232*23xss133* sx3 3 动态规划的应用动态规划的应用(1)管管 理理 运运 筹筹 学学30二、背包问题二、背包问题 设有n种物品，每一种物品数量无限。第i种物品每件重量为wi公斤，每件价值ci元。现有一只可装载重量为W公斤的背包，求各种物品应各取多少件放入背包，使背包中物品的价值最高。 这个问题可以用整数规划模型来描述。设xi为第i种物品装入背包的件数（i =1, 2, , n），背包中物品的总价值为z，则 Max z = c1x1+c2x2+ +cnxn s.t. w1x1+w2x2+wnxnW x1, x2, , xn0 且为整数。

24、3 3 动态规划的应用动态规划的应用(1)管管 理理 运运 筹筹 学学31 下面用动态规划逆序解法求解它。设阶段变量k：第k次装载第k种物品（k=1, 2, , n）状态变量sk：第k次装载时背包还可以装载的重量；决策变量uk = xk：第k次装载第k种物品的件数；决策允许集合：Dk(sk) = xk | 0 xksk/wk，xk为整数；状态转移方程： sk+1 = sk wkxk；阶段指标： vk = ckxk；最优过程指标函数fk(sk)：第k到n阶段容许装入物品的最大使用价值；递推方程： fk(sk) = max ckxk+fk+1(sk+1) = max ckxk+fk+1(sk wk

25、xk)； xDk(sk) 终端条件： fn+1(sn+1) = 0。3 3 动态规划的应用动态规划的应用(1)管管 理理 运运 筹筹 学学32例3.某咨询公司有10个工作日可以去处理四种类型的咨询项目，每种类型的咨询项目中待处理的客户数量、处理每个客户所需工作日数以及所获得的利润如表109所示。显然该公司在10天内不能处理完所有的客户，它可以自己挑选一些客户，其余的请其他咨询公司去做，应如何选择客户使得在这10个工作日中获利最大？ 表109 咨询项目类型待处理客户数处理每个客户所需工作日数处理每个客户所获利润1234432213472811203 3 动态规划的应用动态规划的应用(1)管管 理

26、理 运运 筹筹 学学33解：用动态规划来求解此题。我们把此问题分成四个阶段，第一阶段我们决策将处理多少个第一种咨询项目类型中的客户，第二阶段决策将处理多少个第二种咨询项目类型中的客户，第三阶段、第四阶段我们也将作出类似的决策。我们设分配给第k种咨询项目到第四种咨询项目的所有客户的总工作日（第k阶段的状态变量）。 =在第k种咨询项目中处理客户的数量（第k阶段的决策变量）。已知10并有 kx1s,),(111112xsxsTsks3 3 动态规划的应用动态规划的应用(1)管管 理理 运运 筹筹 学学34 并从与的定义可知从第四阶段开始计算：显然将个工作日尽可能分配给第四类咨询项目，即时，第四阶段的

27、指标值为最大，其中，表示取不大于的最大整数，符号为取整符号，故有由于第四阶段是最后的阶段，故有,3),(222223xsxsTs.4),(333334xsxsTskskx447xs 4s)10, 1 , 0(4s7/44sx 7/4s7/4s ).7/,(),(max4444444ssrxsrx),7/,(),(max)(4444*44444ssrxsrsfx3 3 动态规划的应用动态规划的应用(1)管管 理理 运运 筹筹 学学35因为至多为10，其数值计算见表1010。 表表10104s01000100200300400500600702018020190201100114x4s),(444

28、xsr)(44sf4*x0000000202020203 3 动态规划的应用动态规划的应用(1)管管 理理 运运 筹筹 学学36第三阶段：当把个工作日分配给第四类和第三类咨询项目时，则对每个值，都有一种最优分配方案，使其最大盈利即最优3子过程最优指标函数值为 因为因为至多为10，所以的取值可为0,1,2。其数值计算见表1011。)10, 3 , 2 , 1 , 0(33ss3s. )(),(max)(33222222sfxsrsfx2233xss. )4(),(max)(334333333xsfxsrsfx3s3x3 3 动态规划的应用动态规划的应用(1)管管 理理 运运 筹筹 学学37 表表

29、1011 0 1 2000 1 00 200 300 40011 1 50011 1 60011 1 7 11+0 20 0 8020 11+0 22 2 9020 11+0 22 2 10020 11+0 22 23x3s)4(),(334333xsfxsr)(33sf3*x000000200011011011022022022003 3 动态规划的应用动态规划的应用(1)管管 理理 运运 筹筹 学学38 第二阶段： 同样以每个值都有一种最优分配方案，使其最大盈利即最优2子过程最优指标函数值为：因为，故有因为至多为10，所以的取值为0,1,2,3。其数值计算见表1012。. )3(),(ma

30、x)(223222222xsfxsrsfx2233xss. )3(),(max)(223222222xsfxsrsfx2s2x2s3 3 动态规划的应用动态规划的应用(1)管管 理理 运运 筹筹 学学393 3 动态规划的应用动态规划的应用(1) 表表10-12管管 理理 运运 筹筹 学学40 第一阶段： 我们已知，又因为 ，同样有 因为 ,故可取值为0,1,2, ,10。其数值计算见表1013。 表1013101s. )(),(max)(112111111xsfxsrsfx112xss.)10(),10(max)10(121111xfxrfx101s1x3 3 动态规划的应用动态规划的应用(

31、1) 管管 理理 运运 筹筹 学学41 从表1013可知，从而得10010，在表1012的的这一行可知，由，查表1011的的这一行可知，最后由，查表10-10的的这一行得，综上所述得最优解为：此时最大盈利为28。现在我们不妨假设该咨询公司的工作计划有所改变，只有8个工作日来处理这四类咨询项目，那么该咨询公司如何选择客户使得获利最大呢？我们不必从头开始重做这个问题，而只要在第一阶段上把改成8，重新计算就可得到结果，如表1014所示，这是动态规划的一个好处。28)10(1f01*x1*210 xs102s12*x731032*23xss73s03*x7073*34xss74s14*x0, 1, 0

32、3*2*1*xxx, 14*x4s3 3 动态规划的应用动态规划的应用(1) 管管 理理 运运 筹筹 学学42表1014如上一样可从表1014,1012,1011,1010得到两组最优解如下：它们的最优解（即最大盈利）都为22。一旦咨询的工作日不是减少而是增加，那么我们不仅要重新计算第一阶段，而且要在第二、第三、第四阶段的计算表上补上增加的工作日的新的信息，也可得到新的结果。3042)4321xxxx1001)4*3*2*1*xxxx3 3 动态规划的应用动态规划的应用(1) 管管 理理 运运 筹筹 学学43 实际上，背包问题我们也可以用整数规划来求解，如果背包携带物品重量的限制为W公斤，这N

33、种物品中第i种物品的重量为，价值为，第i种物品的总数量的，我们可以设表示携带第i种物品的数量，则其数学模型为：S.T. 且为整数。 我们不妨用此模型去求解例3，也一定得出同样的结果。iwicinix,max1Niiixcf0), 2 , 1(1iiiNiiixNinxWxw3 3 动态规划的应用动态规划的应用(1) 管管 理理 运运 筹筹 学学44三、生产与存贮问题 例4.某公司为主要电力公司生产大型变压器，由于电力采取预订方式购买，所以该公司可以预测未来几个月的需求量。为确保需求，该公司为新的一年前四个月制定一项生产计划，这四个月的需求如表1015所示。生产成本随着生产数量而变化。调试费为4

34、，除了调度费用外，每月生产的头两台各花费为2，后两台花费为1。最大生产能力每月为4台，生产成本如表1016所示。表10153 3 动态规划的应用动态规划的应用(1) 管管 理理 运运 筹筹 学学45 表表1016每台变压器在仓库中由这个月存到下个月的储存费为1，仓库的最大储存能力为3台，另外，知道在1月1日时仓库里存有一台变压器，要求在4月30日仓库的库存量为零。试问该公司应如何制定生产计划，使得四个月的生产成本和储存总费用最少？解：我们按月份来划分阶段，第i个月为第i阶段：（i=1,2,3,4). 设 为第k阶段期初库存量； k=1,2,3,4 ks3 3 动态规划的应用动态规划的应用(1)

35、 管管 理理 运运 筹筹 学学46为第k阶段生产量； k=1,2,3,4为第k阶段需求量； k=1,2,3,4，这已在表10-15中告诉我们。因为下个月的库存量等于上个月的库存量加上上个月的产量减去上个月的需求量，我们就得到了如下状态转移方程：因为，故有因为，故有kxkd, 1112dxss11s, 1121dxs, 2223dxss, 3334dxss, 4445dxss05s, 4440dxs3 3 动态规划的应用动态规划的应用(1) 管管 理理 运运 筹筹 学学47由于必须要满足需求，则有通过移项得到 另一方面，第k阶段的生产量必不大于同期的生产能力（4台），也不大于第k阶段至第四阶段的

36、需求之和与第k阶段期初库存量之差，否则第k阶段的生产量就要超过从第k阶段至第四阶段的总需求，故有以下我们从第四阶段开始计算：从以上的状态转移方程可知这样就有),4, 3 ,2, 1(,kdxskkkkkksdxkx44 ,)(minkikiksdx,0444dxs,34444ssdx)3 ,(),(min)(444444444ssrxsrsfx3 3 动态规划的应用动态规划的应用(1) 管管 理理 运运 筹筹 学学48 这里的阶段指标可以分成两部分，即生产成本与储存费，即为 由于第四阶段末要求库存为零，即有，这样可得 对于每个的可行值，的值列于表1017。 表1017),(nnnxsr),()

37、(),(nnnnnnnnxshxcxsr001),(444xsh)3()3 ,()3()3 ,()(444444444444scsshscssrsf4s)(44sf3 3 动态规划的应用动态规划的应用(1) 管管 理理 运运 筹筹 学学49表中当时，可知第四阶段要生产台，从表1016可知总成本为9，同样可以算出当为1,2,3时的情况，结果已列于表1017中。第三阶段：此时有：因为以及所以有例如，当第三阶段初库存量时，生产量为2时，则所以生产成本为8，第三阶段末库存为2时，储存费为，而04s3344sx4s)(1)(),()(),(3333333333333dxsxcxshxcxsr,3334d

38、xss, 13d)() 1(1)(min)(443333)4,4min(133333sfxsxcsfsxs) 1() 1(1)(min3343333)4,4min(1333xsfxsxcsxs13s3x2121333dxs221),2()()(4333444fdxsfsf3 3 动态规划的应用动态规划的应用(1) 管管 理理 运运 筹筹 学学50查1017表可知，这样可知，填入表1018中的栏内，其他结果如表1018所示 ： 表1018 第二阶段：因为所以有6) 2 (4f,16628)2()2 , 1 (43 fr2, 133xs, 422232dxssd3 3 动态规划的应用动态规划的应用

39、(1) 管管 理理 运运 筹筹 学学51 计算结果如表1019所示。 表1019 )(),(min)(33222)4,8min(422222sfxsrsfsxs)(),()(min3322222)4,8min(4222sfxshxcsxs)()(1)(min222322222)4,8min(4222dxsfdxsxcsxs)4()4(1)(min2232222)4,8min(4222xsfxsxcsxs3 3 动态规划的应用动态规划的应用(1) 管管 理理 运运 筹筹 学学52第一阶段：因为故有计算结果见表1020。 表1020, 1, 2211111sdxssd)(),(min) 1 ()(

40、22111411111sfxsrfsfx)21 ()21 (1)(min12111411xfxxcx3 3 动态规划的应用动态规划的应用(1) 管管 理理 运运 筹筹 学学53利用递推关系可以从表1020，表1019，表1018和表1017得到两组最优解： 这时有最低总成本29。0441)4321xxxx3042)4321xxxx3 3 动态规划的应用动态规划的应用(1) 管管 理理 运运 筹筹 学学543 3 动态规划的应用动态规划的应用(1) 四、系统可靠性问题 例例5.某科研项目组由三个小组用不同的手段分别研究，它们失败的概率各为0.40，0.60，0.80。为了减少三个小组都失败的可能

41、性，现决定给三个小组中增派两名高级科学家，到各小组后，各小组科研项目失败概率如下表： 问如何分派科学家才能使三个小组都失败的概率（即科研项目最终失败的概率）最小？ 高级科学家小组12300.400.600.8010.200.400.5020.150.200.30管管 理理 运运 筹筹 学学553 3 动态规划的应用动态规划的应用(1) 解：用逆序算法。设 阶段：每个研究小组为一个阶段，且阶段123小组123管管 理理 运运 筹筹 学学563 3 动态规划的应用动态规划的应用(1) 计算当n=3时，当n=2时， s3 f3*(s3) x3*008001050120302 x2s2f2(s2,x2

42、)=P2(x2) f3*(s2-x2) f2*(s2) x2*012004804801030032030020180200160162管管 理理 运运 筹筹 学学573 3 动态规划的应用动态规划的应用(1) 当n=1时， 最优解为 x1*=1，x2*=0，x3*=1；科研项目最终失败的概率为0.060。 x1s1f1(s1,x1)=P1(x1) f2*(s1-x1)f2*(s2)x2*01220064 0060 0072 0060 1管管 理理 运运 筹筹 学学584 4 动态规划的应用动态规划的应用(2)(2)* *一、一、连续连续确定性动态规划确定性动态规划 对于状态变量和决策变量只取连

43、续值，过程的演变方式为确定性时，这种动态规划问题就称为连续确定性动态规划问题。管管 理理 运运 筹筹 学学594 4 动态规划的应用动态规划的应用(2)(2)* *机器负荷分配问题机器负荷分配问题 例例1 一种机器能在高低两种不同的负荷状态下工作。设机器在高负荷下生产时，产量函数为P1=8u1，其中u1为在高负荷状态下生产的机器数目，年完好率为a=0.7，即到年底有70的机器保持完好。在低负荷下生产时，产量函数为P2=5u2，其中u2为在低负荷状态下生产的机器数目，年完好率为b=0.9。设开始生产时共有1000台完好的机器，请问每年应该如何把完好机器分配给高、低两种负荷下生产，才能使得5年内生

44、产的产品总产量最高。管管 理理 运运 筹筹 学学604 4 动态规划的应用动态规划的应用(2)(2)* *解 建立动态规划模型： 分为5个阶段，每个阶段为1年。设状态变量sk表示在第k阶段初拥有的完好机器数目；k=1,2,3,4,5。 决策变量xk表示第k阶段中分配给高负荷状态下生产的机器数目；k=1,2,3,4,5。显然sk-xk为分配给低负荷状态下生产的机器数目。 状态转移方程为 sk+1=0.7xk+0.9(sk-xk) 阶段指标 rk(sk,xk)=8xk+5(sk-xk) 最优指标函数 ，其中k=1,2,3,4,5。 f6(s6)=0。)()58max)(11kkkkkkksfxsx

45、sf（kksx 0管管 理理 运运 筹筹 学学614 4 动态规划的应用动态规划的应用(2)(2)* *第5阶段： 因为f5(s5)是x5的线性单调增函数，故有x5* =s5，于是有f5(s5)=8s5。第4阶段： )(2 .126 .13max)(9 . 07 . 0 8)(58max8)(58max)()(58max)(44404444440544405544404444444444xsxxsxxsxsxsxsfxsxsfsxsxsxsx 管管 理理 运运 筹筹 学学624 4 动态规划的应用动态规划的应用(2)(2)* * 同样的，f4(s4)是x4的线性单调增函数，有x4*=s4 ，f

46、4(s4)=13.6s4。 对前几个阶段依次类推，可得 f3(s3)=17.5s3， f2(s2)=20.75s2， f1(s1)=23.72s1。 因为期初共有完好机器1000台，故s1=1000。有f1(s1)=23.72s123720，即5年最大的产量为23720台。得最优解为 ， ， ， 。 这意味着前两年应把年初完好机器完全投入低负荷生产，后三年应把年初完好机器完全投入高负荷生产。0*1x0*2x3*3sx 4*4sx 5*5sx 管管 理理 运运 筹筹 学学634 4 动态规划的应用动态规划的应用(2)(2)* * 下一步工作是确定每年初的状态，按照从前向后的顺序依次计算出每年年初

47、完好的机器数目。已知s1=1000,根据状态转移方程，有:9009 . 0)(9 . 07 . 01*11*12sxsxs8109 . 0)(9 . 07 . 02*22*23sxsxs5677 . 0)(9 . 07 . 03*33*34sxsxs3977 . 0)(9 . 07 . 04*44*45sxsxs管管 理理 运运 筹筹 学学644 4 动态规划的应用动态规划的应用(2)(2)* * 上面所讨论的最优策略过程，初始端状态s1=1000台是固定的，终点状态s6没有要求。这种情况下得到最优决策称为初始端固定终点自由的最优策略。 如果终点附加一定的条件，则问题就称为“终端固定问题”。例

48、如，规定在第5年度结束时仍要保持500台机器完好（而不是278台），应如何安排生产才能使得总产量最大？ 下面来分析： 根据终点条件有 可得500)(9 . 07 . 05556xsxs25005 . 455sx管管 理理 运运 筹筹 学学654 4 动态规划的应用动态规划的应用(2)(2)* * 显然，由于固定了终点的状态，x5的取值受到了约束。因此有 类似的， 容易解得 ，f4(s4)=21.7s4-7500。75005 .18)25005 . 4(5)25005 . 4(8max)(555555sssssf75007 . 07 .21max75005 .18)(58max)()(58max

49、)(4405444055444044444444xssxsxsfxsxsfsxsxsx0*4x管管 理理 运运 筹筹 学学664 4 动态规划的应用动态规划的应用(2)(2)* * 依次类推，得 f3(s3)=24.5s3-7500 f2(s2)=27.1s2-7500 f1(s1)=29.4s1-7500 再采用顺序方法递推计算各年的状态，有 s1=1000， 0*1*2*3xxx9009 . 0)(9 . 07 . 01*11*12sxsxs8109 . 0)(9 . 07 . 02*22*23sxsxs7297 . 0)(9 . 07 . 03*33*34sxsxs6567 . 0)(9

50、 . 07 . 04*44*45sxsxs管管 理理 运运 筹筹 学学674 4 动态规划的应用动态规划的应用(2)(2)* * 可见，为了使终点完好的机器数量增加到500台，需要安排前四年中全部完好机器都要投入低负荷生产，且在第5年，也只能全部投入高负荷。 相应的最优指标为 f1(s1)=29.4s1-750021900。 可以看到，因为增加了附加条件，总产量f1(s1)要比终点自由情况下的产量要低。管管 理理 运运 筹筹 学学68二、离散随机性动态规划二、离散随机性动态规划 随机型的动态规划是指状态的转移律是不确定的，即对给定的状态和决策，下一阶段的到达状态是具有确定概率分布的随机变量，这

51、个概率分布由本阶段的状态和决策完全确定。随机型动态规划的基本结构如下图： 4 4 动态规划的应用动态规划的应用(2)(2)* * sk状态 xk决策概率k阶段的收益p1p2pN.k+1阶段的状态sk+1c1c2cN 1 2N管管 理理 运运 筹筹 学学694 4 动态规划的应用动态规划的应用(2)(2)* * 图中N表示第k+1阶段可能的状态数，p1、p2、pN为给定状态sk和决策xk的前提下，可能达到下一个状态的概率。ci为从k阶段状态sk转移到k+1 阶段状态为i时的指标函数值。 在随机性的动态规划问题中，由于下一阶段到达的状态和阶段的效益值不确定，只能根据各阶段的期望效益值进行优化。管管

52、 理理 运运 筹筹 学学70离散随机性动态规划离散随机性动态规划 例例2 2 某公司承担一种新产品研制任务，合同要求三个月内交出一件合格的样品，否则将索赔2000元。根据有经验的技术人员估计，试制品合格的概率为0.4，每次试制一批的装配费为200元，每件产品的制造成本为100元。每次试制的周期为1个月。问该如何安排试制，每次生产多少件，才能使得期望费用最小？ 管管 理理 运运 筹筹 学学71离散随机性动态规划离散随机性动态规划 解：解：把三次试制当作三个阶段（k=1,2,3）,决策变量xk表示第k次生产的产品的件数；状态变量sk表示第k次试制前是否已经生产出合格品，如果有合格品，则sk=0；如

53、果没有合格品，记sk=1。最优函数fk(sk)表示从状态sk、决策xk出发的第k阶段以后的最小期望费用。故有fk(0)0。 生产出一件合格品的概率为0.4，所以生产xk件产品都不合格的概率为 ，至少有一件合格品的概率为1- ，故有状态转移方程为 kx6 . 0kkxkxkspsp6 . 01)0(6 . 0) 1(11kx6 . 0管管 理理 运运 筹筹 学学72离散随机性动态规划离散随机性动态规划 用C(xk)表示第k阶段的费用，第k阶段的费用包括制造成本和装配费用，故有 根据状态转移方程以及C(xk)，可得到 0002)(kkkkxxxxC)1 (6 . 0)0()6 . 01 ()(mi

54、n) 1 (11kxkxkxkffxcfkkk)1 (6 . 0)(min1kxkxfxckk管管 理理 运运 筹筹 学学73离散随机性动态规划离散随机性动态规划 如果3个月后没有试制出一件合格品，则要承担2000元的罚金，因此有f4(1)=20。 当k=3时，计算如下表： x3 s3 C(x3)+20f3(s3) x3* 0 1 2 3 4 5 6 0 0 0 0 1 20 1511.2 9.32 8.59 8.56 8.93 8.56 5 0.63x管管 理理 运运 筹筹 学学74离散随机性动态规划离散随机性动态规划当k=2时，计算如下表： x2 s2 C(x2)+8.56f2(s2) x2* 0 1 2 3 4 0 0 0 0 18.5