第10章 动态规划

1、1多阶段决策过程最优化问题举例2基本概念、基本方程与最优化原理3动态规划的应用(1)4动态规划的应用(2)1管理运筹学第十章动态规划例1 最短路径问题下图表示从起点A到终点E之间各点的距离。求A到E的最短路径。2CB8111664D1104737AB 2C 2E52362D128463B 3C 3751B42管理运筹学1多阶段决策过程最优化问题举例讨论：1、以上求从A到E的最短路径问题，可以转化为四个性质完全相 同，但规模较小的子问题，即分别从Di 、Ci、Bi、A到E的最短路径问题。第四阶段：两个始点D1和D2，终点只有一个；表10-1分析得知：从D1和D2到E的最短路径唯一。3管理运筹学阶

2、段4本阶段始点（状态）本阶段各终点（决策）到E的最短距离本阶段最优终点（最优决策)ED1 D210*6106E E1多阶段决策过程最优化问题举例第三阶段：有三个始点C1，C2，C3，终点有D1，D2，对始点和终点进行分析和讨论分别求C1，C2，C3到D1，D2 的最短路径问题：表10-2分析得知：如果经过C1，则最短路为C1-D2-E； 如果经过C2，则最短路为C2-D2-E； 如果经过C3，则最短路为C3-D1-E。4管理运筹学阶段3本阶段始点（状态）本阶段各终点（决策）到E的最短距离本阶段最优终点（最优决策)D1D2C1 C2 C38+10=187+10=171+10=116+6=125+

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

4、191+11=127+11=188+11=195+11=166+11=172+11=133+11=141+11=1212131412C2 C3 C3 C31多阶段决策过程最优化问题举例第一阶段：只有1个始点A，终点有B1,B2,B3,B4 。对始点和终点进行分析和讨论分别求A到B1,B2,B3,B4的最短路径问题：表10-4最后，可以得到：从A到E的最短路径为A B4 C3 D1 E6管理运筹学阶段1本阶段始点(状态)本阶段各终点（决策）到E的最短距离本阶段最优终点(最优决策)B1B2B3B4A4+12=163+13=163+14=172+12=1414B41多阶段决策过程最优化问题举例以上计

5、算过程及结果，可用图2表示，可以看到，以上方法不仅得到了从A到D的最短路径，同时，也得到了从图中任一点到E的最 短路径。B 1 2C 181664D11014A4 727 33B2C2E56D 248 312BC36375B41以上过程，仅用了22次加法，计算效率远高于穷举法。7管理运筹学1211146011131012121多阶段决策过程最优化问题举例一、基本概念：1、阶段k：表示决策顺序的离散的量，阶段可以按时间或空间划 分。2、状态sk：能确定地表示决策过程当前特征的量。状态可以是 数量，也可以是字符，数量状态可以是连续的，也可以是离散 的。3、决策xk：从某一状态向下一状态过渡时所做的

6、选择。决策是 所在状态的函数，记为xk(sk)。决策允许集合Dk(sk)：在状态sk下，允许采取决策的全体。4、策略Pk,n(sk)：从第k阶段开始到最后第n阶段的决策序列，称k子策略。P1,n(s1)即为全过程策略。5、状态转移方程 sk+1=Tk(sk,xk)：某一状态以及该状态下的决策， 与下一状态之间的函数关系。8管理运筹学2基本概念、基本方程与最优化原理6、阶段指标函数vk(sk, xk)：从状态sk出发，选择决策xk所产生的第k阶段指标。过程指标函数Vk,n(sk,xk,xk+1, xn)：从状态sk出发，选择决策xk,xk+1, , xn所产生的过程指标。动态规划要求过程指标具有

7、可分离性，即 Vk,n(sk, xk, xk+1, , xn) = vk(sk, xk)+Vk+1(sk+1, xk+1, , xn)称指标具有可加性，或Vk,n(sk, xk, xk+1, , xn) = vk(sk, xk)Vk+1(sk+1,xk+1, , xn)称指标具有可乘性。二、基本方程：最优指标函数fk(sk)：从状态sk出发，对所有的策略Pk,n，过程optxk Dk ( sk )指) =f k (skVk ,n(sk, Pk ,n)标Vk,n的最优值，即9管理运筹学2基本概念、基本方程与最优化原理对于可加性指标函数，上式可以写为optxk Dk ( sk )fk (sk )

8、=vk (sk , xk ) + fk +1 (sk +1 )k = 1,2,L, n上式中“opt”表示“max”或“min”。对于可乘性指标函数，上式可以optxk Dk ( sk )fk (sk ) =vk (sk , xk ) fk +1 (sk +1 )k = 1,2,L, n写为以上式子称为动态规划最优指标的递推方程，是动态规划的基本方程。终端条件：为了使以上的递推方程有递推的起点，必须要设定最 优指标的终端条件，一般最后一个状态n+1下最优指标fn+1(sn+1) = 0。10管理运筹学2基本概念、基本方程与最优化原理用逆序法列表求解右例k=n=5 时，f5(v10)0k=4，递

9、推方程为11管理运筹学s4D4(s4)s5v4(s4,x4)v4(s4,x4)+f5(s5)f4(s4)最优决策x4*v7v7v10v1055+0=5*5v7 v10v8v8v10v1088+08*8v8 v10v9v9v10v1044+0=4*4v9 v10f4 (s4 ) =minv4 (s4 , x4 ) + f5 (s5 )x4D4 (s4 )2基本概念、基本方程与最优化原理k=3，递推方程为表10-212管理运筹学s3D3(s3)s4v3(s3,x3)v3(s3,x3)+f4(s4)f3(s3)最优决策x3*v5v5v7 v5v8 v5v9v7 v8 v92862+5=7*8+8=1

10、66+4=107v5v7v6v6 v7 v6v8 v6v9v7 v8 v9125812+5=175+8=138+4=12*12v6v9f3 (s3 ) =minv3 (s3 , x3 ) + f4 (s4 )x3D3 (s3 )2基本概念、基本方程与最优化原理k=2，递推方程为表10-313管理运筹学s2D2(s2)s3v2(s2,x2)v2(s2,x2)+f3(s3)f2(s2)最优决策x2*v2v2 v5v2 v6v5 v6101310+7=17*13+12=2517v2 v5v3v3 v5v3 v6v5 v67107+7=14*10+12=2214v3v5v4v4 v5v4 v6v5 v

11、6131113+7=20*11+12=2320v4v5f2 (s2 ) =minv2 (s2 , x2 ) + f3 (s3 )x2D2 (s2 )2基本概念、基本方程与最优化原理k=1，递推方程为表10-4最优值是表8-4中f1(s1)的值，从v1到v10的最短路长为19。最短路 线从表8-4到表8-1回朔，查看最后一列最优决策，得到最短路径为：v1 v2 v5 v7 v1014管理运筹学s1D1(s1)s2v1(s1,x1)v1(s1,x1)+f2(s2)f1(s1)最优决策x1*v1v1v2 v1v3 v1v4v2 v3 v42852+17=19*8+14=225+20=2519v1v2

12、f1 (s1 ) =minv1 (s1 , x1 ) + f2 (s2 )x1D1 (s1 )2基本概念、基本方程与最优化原理三、最优化原理作为整个过程的最优策略具有如下性质： 不管在此最优策略上的某个状态以前的状态和决策如何，对该状态来说，以后的所有决策必定构成最优子策略。就是说，最优策略的任意子策略都是最优的。15管理运筹学2基本概念、基本方程与最优化原理一、资源分配问题例2. 某公司拟将某种设备5台，分配给所属的甲、乙、丙三个工厂。各工厂获得此设备后，预测可创造的利润如表10-5所示， 问这5台设备应如何分配给这3个工厂，使得所创造的总利润为 最大？表10-5管理运16筹学盈利工厂设备台

13、数甲厂乙 厂丙 厂0000135427106391111412111251311123动态规划的应用(1)解：将问题按工厂分为三个阶段，甲、乙、丙三个厂分 别编号为1、2、3厂。设sk= 分配给第k个厂至第3个厂的设备台数（k=1、2、3）。xk=分配给第k个设备台数。已知s1=5,并有s2 = T1 (s1, x1 ) = s1 - x1s3 = T2 (s2 , x2 ) = s2 - x2从sk 与xk 的定义，可知s3 = x3以下我们从第三阶段开始计算。17管理运筹学3动态规划的应用(1)第三阶段:显然将 s3 (s3 = 0,1,2,3,4,5)台设备都分配给第3工厂时，= x3也

14、就是s3时，第3阶段的指标值（即第3厂的盈利）为最大，即max r3 (s3 , x3 ) = r3 (s3 , s3 )x3由于第3阶段是最后的阶段，故有f3 (s3 ) = max r3 (s3 , x3 ) = r3 (s3 , s3 ).x3其中x3可取值为0,1,2,3,4,5。其数值计算见表106。18管理运筹学3动态规划的应用(1)表10619管理运筹学sx33r3 (s3 , x3 )f3 (s3 )x*30123450000144126623111134121245121253动态规划的应用(1)表示取3子过程上最优指标值f3 (s3 )时的 x3其中 x*3决策，例如在表1

15、0-6中可知当s3=4时，有 r3 (4,4) =12;有= 4此时x*3 = 4，即当s= 4 时，此时取x3f (4) =12,33（把4台设备分配给第3厂）是最优决策，此时阶段指标值（盈利）为12，最优3子过程最优指标值也为12。第二阶段：s2 (s2 = 0,1,2,3,4,5)台设备分配给第2工厂和第3工当把厂时，则对每个s2 值，有一种最优分配方案，使最大盈利即最优2子过程最优指标函数值为f2 (s2 ) = maxr2 (s2 , x2 ) + f3 (s3 )x220管理运筹学3动态规划的应用(1)= s2- x2,上式也可写成因为s3f2 (s2 ) = maxr2 (s2

16、, x2 ) + f3 (s2- x2 )x2其数值计算如表107所示。表10721管理运筹学sx22r2 (s2 , x2 ) + f3 (s2 - x2 )f2 (s2 )x*201234500 + 0001045 + 0512065410 + 010230115610 + 411014240125 +1110 + 6114110161,2501251210 +111161141102123动态规划的应用(1)= 4 的这一行里，当 x2= 1s2其中在时，r2 (s2 , x2 ) + f3 (s2 - x2 ) = r2 (4,1) + f3 (4 -1) = r2 (4,1) + f

17、3 (3) = 5 +11 =16从表105中可知，把1台设备交给乙厂所得盈这里 r2 (4,1)利数即可，知 r2 (4,1) = 5，这里f3 (4 -1) = f3 (3) 从表106查= 2 时，可知f3 (3)即可知 f3 (3) =11。同样可知当 x2r2 (s2 , x2 ) + f3 (s2 - x2 ) = r2 (4,2) + f3 (4 - 2) = r2 (4,2) + f3 (2) =10 + 6 =16;= 0 时，r2 (4,0) + f3 (4 - 0) = 0 +12 =12 ；当 x2 = 3当时，x2r2 (4,3) + f3 (4 - 3) =11+

18、4 ；当时，x2 = 4= 4 ，不可能分2厂5s2；由于r2 (4,4) + f3 (4 - 4) =11+ 0 =11时， r2 (4,5) + f3 (4 -5)台设备，故栏空着不填。从x2 = 5这些数值中取得最大即得 f2 (4)，即有f2 (4) =16。在此行中我们在取最大值的r2 (s2 , x2 ) + f3 (s2- x2 )上面加一横以示区别，也可知这时 x2的最优决策为1或2。22管理运筹学3动态规划的应用(1)第一阶段：把 s1 (s1 = 5) 台设备分配给第1，第2，第3厂时，最大盈利为 f1(5) = maxr1(5, x1) + f2 (5 - x1),其中x

19、1可取值0,1,2,3,4,5.x1数值计算见表108表10-8然后按计算表格的顺序推算，可知最优分配方案有两个：1 = 0，根据s= s- x*= 5 - 0 = 5，查表107可1.由于x*121= 2，再由s= s= 3。即分配知x*2x*= s- x*2 = 5 - 2 = 3，求得3332给甲厂0台，乙厂2台，丙厂3台。= 2，根据s= s- x*= 5 - 2 = 3 ，查表107可2.由于x*112123管理运筹学x1s1r1 (5, x1 ) + f2 (5 - x1 )f1 ( x)x*101234550 + 213167 +149+1012+513+0210,23动态规划的

20、应用(1)= s- x*2 = 3 - 2 =1,求得= s= 1 ，知= 2 ，再由sx*x*23323即分配给甲厂2台，乙厂2台，丙厂1台。这两种分配方案都能得到最高的总盈利21万元。24管理运筹学3动态规划的应用(1)二、背包问题设有n种物品，每一种物品数量无限。第i种物品每件重量为wi公斤，每件价值ci元。现有一只可装载重量为W公斤的背包，求各种物品应各取多少件放入背包， 使背包中物品的价值最高。这个问题可以用整数规划模型来描述。设xi为第i种 物品装入背包的件数（i =1, 2, , n），背包中物品的总价值为z，则Max z = c1x1+c2x2+ +cnxns.t.w1x1+w

21、2x2+wnxnW x1, x2, , xn0 且为整数。25管理运筹学3动态规划的应用(1)下面用动态规划逆序解法求解它。设阶段变量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(

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

23、问题分成四个阶段，第一阶段我们决策将 处理多少个第一种咨询项目类型中的客户，第二阶段决 策将处理多少个第二种咨询项目类型中的客户，第三阶 段、第四阶段我们也将作出类似的决策。我们设sk分配给第k种咨询项目到第四种咨询项目的所有客户的总工作日（第k阶段的状态变量）。xk=在第k种咨询项目中处理客户的数量（第k阶段的决策变量）。已知 s110 并有s2 = T1 (s1 , x1 ) = s1- x1,28管理运筹学3动态规划的应用(1)s3 = T2 (s2 , x2 ) = s2 - 3x2 ,s4 = T3 (s3 , x3 ) = s3 - 4x3.并从sk 与xk 的定义可知 s4= 7

24、x4从第四阶段开始计算：显然将s4 个工作日(s4 = 0,1,L,10)尽可能分配给第四= s4/ 7 时，第四阶段的指标值为最大，类咨询项目，即x4其中，s4 / 7 表示取不大于s/ 7的最大整数，符号为4取整符号，故有max r4 (s4 , x4 ) = r4 = (s4 ,s4 / 7).x4由于第四阶段是最后的阶段，故有f(s ) = max r (s , x*4 ) = r= (s ,s/ 7),4444444x429管理运筹学3动态规划的应用(1)因为s4 至多为10，其数值计算见表1010。表101030管理运筹学x4s4r4 (s4 , x4 )f4 (s4 )x*401

25、0000100020003000400050006000702020180202019020201100202013动态规划的应用(1)第三阶段：当把 s3 (s3 = 0,1,2,3,L,10) 个工作日分配给第四类和第三类咨询项目时，则对每个s3 值，都有一种最优分配方案，使其最大盈利即最优3子过程最优指标函数值为f3 (s3 ) = maxr3 (s3 , x3 ) + f4 (s4 ).x3s4 = s3 - 4x3f3 (s3 ) = maxr3 (s3 , x3 ) + f4 (s3 - 4x3 ).因为x3因为 s3至多为10，所以 x 的取值可为0,1,2。其数值计算3见表10

26、11。31管理运筹学3动态规划的应用(1)表101132管理运筹学sx33r3 (s3, x3 ) + f4 (s3 - 4x3 )f3 (s3 )x*301200 + 00010 + 00020 + 00030 + 00040011 + 011150011 + 011160011 + 011170 + 2011+0200802011+022 + 0222902011+022 + 02221002011+022 + 02223动态规划的应用(1)第二阶段：同样以每个s2 值都有一种最优分配方案，使其最大盈利即最优2子过程最优指标函数值为：f2 (s2 ) = maxr2 (s2 , x2 )

27、+ f3 (s2 - 3x2 ).x2-3x2，故有= s2f2 (s2 ) = maxr2 (s2 , x2 ) + f3 (s2 - 3x2 ).因为s3x2因为s 至多为10x，所以 2的取值为0,1,2,3。其数值计算2见表1012。33管理运筹学3动态规划的应用(1)表10-1234管理运筹学3动态规划的应用(1)第一阶段：s2= s1 - x，1= 10，又因为s1我们已知同样有f1(s1) = maxr1(s1, x1) + f2 (s1 - x1).x1f1(10) = maxr1(10, x1) + f2 (10 - x1).x1因为s1 = 10 ,故 x1可取值为0,1,

28、2, ,10。其数值计算见表1013。表101335管理运筹学3动态规划的应用(1)= 0 从而得sf (10) = 28 ，x*=10 - x*从表1013可知101112010，在表1012的 s= 10的这一行可知 x*2 = 1 ，由2=10 - 3 = 7，查表1011的 s3 = 7 的这一行可知s= s- 3x*23x*32= 0= 7= 7 - 0 = 7，查表10-10的 s，最后由s的这= s- x*4343一行得x*4 = 1 ，综上所述得最优解为：x*= 0, x*=1, x*= 0123=1,x*4此时最大盈利为28。现在我们不妨假设该咨询公司的工作计划有所改变，只有

29、8个工作日来处理这四类咨询项目，那么该咨询公司如何选择客户使得获利最大呢？我们不必从头开始重做这个问题，而只要在第一阶段上把s4 改成8，重新计算就可得到结果，如表10 14所示，这是动态规划的一个好处。36管理运筹学3动态规划的应用(1)表1014如上一样可从表1014,1012,1011,1010得到两组最优解= 2= 4= 0= 3 x* x1x= 1= 0= 0如下：1x*2I)II )2x*x33x4 x*4= 1它们的最优解（即最大盈利）都为22。一旦咨询的工作日不是减少而是增加，那么我们不仅要重新计算第一阶段，而且要在第二、第三、第四阶段的计算表上补上增加的工作日的新的信息，也可

30、得到新的结果。37管理运筹学3动态规划的应用(1)实际上，背包问题我们也可以用整数规划来求解，如果背包携带物品重量的限制为W公斤，这N种物品中第i种物品的重量为wi，价值为 ci，第i种物品的总数量的ni ，我们可以设 xi 表示携带第i种物品的数量，则其数学模型为：max f= ci xi ,i=1NS.T.N wi xi Wi=1xi ni (i = 1,2,L, N )xi 0且为整数。我们不妨用此模型去求解例3，也一定得出同样的结果。38管理运筹学3动态规划的应用(1)三、生产与存贮问题例4.某公司为主要电力公司生产大型变压器，由于电力采取预订方式购买，所以该公司可以预测未来几个月的需

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

32、设sk为第k阶段期初库存量； k=1,2,3,440管理运筹学3动态规划的应用(1)xkdk为第k阶段生产量； k=1,2,3,4为第k阶段需求量； k=1,2,3,4，这已在表10-15中告诉我们。因为下个月的库存量等于上个月的库存量加上上个月的产量减去上个月的需求量，我们就得到了如下状态转移方s2 = s1 + x1 - d1,，故有s2 =1+ x1 - d1, s3 = s2 + x2 - d2, s4 = s3 + x3 - d3,s5 = s4 + x4 - d4,程：因为 s1= 1= 0 ，故有0 = s4 + x4 - d4,因为 s541管理运筹学3动态规划的应用(1)由于

33、必须要满足需求，则有sk + xk dk , (k = 1,2,3,4),通过移项得到xk dk - sk另一方面，第k阶段的生产量xk 必不大于同期的生产能力（4台），也不大于第k阶段至第四阶段的需求之和与第k阶段期初库存量之差，否则第k阶段的生产量就要超过从第k阶段至第四阶段的总需求，故有d ) - s ,44x min(kik i=k以下我们从第四阶段开始计算：从以上的状态转移方程 0 = s4 + x4 - d4 , 可知x4 = d4 - s4 = 3 - s4 ,f4 (s4 ) = min r4 (s4 , x4 ) = r4 (s4 ,3 - s4 )x4这样就有42管理运筹学

34、3动态规划的应用(1)这里的阶段指标rn (sn , xn )可以分成两部分，即生产成本与储存费，即为rn (sn , xn ) = cn (xn ) + hn (sn , xn )由于第四阶段末要求库存为零，即有h4 (s4 , x4 ) = 1 0 = 0，f4 (s4 ) = r4 (s4 ,3 - s4 ) = c4 (3 - s4 ) + h4 (s4 ,3 - s4 ) = c4 (3 - s4 )这样可得对于每个s4的可行值，f4 (s4 ) 的值列于表1017。表101743管理运筹学3动态规划的应用(1)= 0= 3 - s4 = 3表中当s4时，可知第四阶段要生产x4台，从

35、表1016可知总成本为9，同样可以算出当s4 为1,2,3时的情况，结果已列于表1017中。第三阶段： 此时有：r3 (s3, x3 ) = c3 (x3 ) + h3 (s3, x3 ) = c3 (x3 ) +1(s3 + x3 - d3 )因为 s4 = s3 + x3 - d3, 以及 d3= 1,所以有c3 (x3 ) +1(s3 + x3 -1) + f4 (s4 )f3 (s3 ) =min1-s3 x3 min(4-s3 ,4)c3 (x3 ) +1(s3 + x3 -1) + f4 (s3 + x3 -1)=min1-s3 x3 min(4-s3 ,4)例如，当第三阶段初库存

36、量s3 = 1 时，生产量x3 为2时， 则 s3 + x3 - d3 =1+ 2 -1 = 2所以生产成本为8，第三阶段末库存为2时，储存费为12 = 2 ，而f4 (s4 ) = f4 (s3 + x3 - d3 ) = f4 (2),44管理运筹学3动态规划的应用(1)查1017表可知f4 (2) = 6 ，这样可知，r3 (1,2) + f4 (2) = 8 + 2 + 6 +16,=1, x3= 2 的栏内，其他结果如表1018所表1018填入表1018中s3示 ：第二阶段：d2 = 4, s3= s2 + x2 - d2 ,因为所以有45管理运筹学3动态规划的应用(1)r2 (s2

37、 , x2 ) + f3 (s3 )f2 (s2 ) =min4-s2 x2 min(8-s2 ,4)c2 (x2 ) + h2 (s2 , x2 ) + f3 (s3 )min4-s2 x2 min(8-s2 ,4)c2 (x2 ) +1(s2 + x2 - d2 ) + f3 (s2+ x2 - d2 )=min4-s2 x2 min(8-s2 ,4)c2 (x2 ) +1(s2+ x2 - 4)=+ x2- 4) + f3 (s2min4-s2 x2 min(8-s2 ,4)计算结果如表1019所示。表101946管理运筹学3动态规划的应用(1)第一阶段：因为d1 = 2, s1 = 1

38、, s1 + x1 - d1 = s2 , 故有f1(s1) = f1(1) = min r1(s1, x1) + f2 (s2 )1x1 4= min c1(x1) +1(1+ x1 - 2) + f2 (1+ x1 - 2)1x1 4计算结果见表1020。表102047管理运筹学3动态规划的应用(1)利用递推关系可以从表1020，表1019，表1018和表1017得到两组最优解：= 1= 4= 4= 0 x1x= 2= 4= 0= 3 x1xI)II )22xx33x4x4这时有最低总成本29。48管理运筹学3动态规划的应用(1)四、系统可靠性问题例5.某科研项目组由三个小组用不同的手段分

39、别研究， 它们失败的概率各为0.40，0.60，0.80。为了减少三个小组都失败的可能性，现决定给三个小组中增派两名高级科学家，到各小组后，各小组科研项目失败概率如下表：问如何分派科学家才能使三个小组都失败的概率（即科研项目最终失败的概率）最小？49管理运筹学高级科学家小组12300.400.600.8010.200.400.5020.150.200.303动态规划的应用(1)解：用逆序算法。设阶段：每个研究小组为一个阶段，且决策变量 xn ：分配给第 n 小组的高级科学家数目，相应的失败概率为 Pn( xn )； 状态变量 sn ：在阶段 n 时可分配于阶段 n，n-1，1 的高级科学家人数

40、。递推关系：Minx3 s3Minxn sn*sPfx3 (3 )=3 (3 )f *fsPxsxn (n )=n (n )n+1 (n -n ) n=1,250管理运筹学阶段123小组1233动态规划的应用(1)计算当n=3时，当n=2时，51管理运筹学x2s2f2(s2,x2)=P2(x2) f 3*(s2-x2)f2*(s2)x2*012004804801030032030020180200160162s3f3*(s3)x3*0080010501203023动态规划的应用(1)当n=1时，最优解为 x1*=1，x2*=0，x3*=1；科研项目最终失败的概率为0.060。52管理运筹学x1

41、s1f1(s1,x1)=P1(x1) f 2*(s1-x1)f2*(s2)x1*0122006400600072006013动态规划的应用(1)8.5.1求解线性规划模型【例】用动态规划方法求解下列线性规划【解】首先将问题转化为动态规划模型阶段数为3，决策变量为xk，状态变量为第k阶段初各约束条件 右端常数的剩余值，用s1k和s2k表示，状态转移方程为f4 (s14 , s24 ) = 0终端条件53管理运筹学s1,k+1=s1ka1kxk，s2,k+1=s2ka2kxkmax Z = 6x1 + 5x2 + 8x33x1 + 2x2 20x + 4x+ 4x 14123x , x , x 0

42、 1233动态规划的应用(2)k=3时,决策变量x3的允许集合k=2时,决策变量x2的允许集合54管理运筹学D (s) = x| 0 x min s12 , s22 2i 22224D (s) = x| 0 x min s12 , s22 , a= 2, a= 42i 222 aa12221222 f (s, s) =maxc x =max8x = 2sx* = s4313230x3 s23 4330x3 s23 4323323D (s) = x| 0 x s23 3i3334 D (s) = x| 0 x min s13 , s23 , a= 0, a= 43i333 aa13231323 3动态规划的应用(2)= s12 - 2x2 , s23 = s22- 4x2s13状态转移方程为c2 x2 + f3 (s1