高等教育运筹学课程动态规划

1、动态规划（2）应用举例1、建立动态规划模型的一般步骤1 划分阶段。即按时间和空间的先后顺序适当地划分为满足递推关系的若干个阶段。2 正确选择状态变量。（可知性和无后效性）3 根据状态变量和决策变量的含义，正确写出状态转移方程 Sk+1=Tk(sk,uk)4 明确指标函数Vk.n、最优指标函数fk(sk)及k阶段指标Vk(sk,us)的含义。5 正确列出最优指标函数的递推关系及边界条件。2、资源分配问题资源分配问题 所谓分配问题，就是将数量一定的一种或若干种资源（例如原材料，资金，机器设备，劳力，食品等等），恰当地分配给若干个使用者，使效益函数为最优。资源分配离散连续(1)资源离散分配问题资源离

2、散分配问题 多元投资分配问题 设有某种原料，总数量为a，用于生产n种产品。若分配数量xi用于生产第i种产品，其收益为gi(xi),问应如何分配，才能使生产n种产品的总收入最大？nixaxxxtsxgxgxgMaxZinnn,2, 10.212211静态规划建立动态规划模型1、决策变量dk表示分配给生产第k种产品的原料数量，dk=xk；2、设状态变量sk表示为分配给用于生产第k种产品至第n种产品的原料数量；3、状态转移方程： sk+1=sk-uk=sk-xk4、决策集合：Dk(sk)=uk|0uk=xksk5、最优值函数fk(sk)表示以数量为sk的原料分配给第k种产品至第n种产品所得到的最大总

3、收益，动态规划的递推关系为：)(max)(1 , 1)()(max)(10nnsxnnkkkkksxkkxgsfnkxsfxgsfnnkk 例1：某公司有资金10万元，若投资于项目i（i=1，2，3）的投资额为xi时，其效益分别为 23332221112)(,9)(,4)(xxgxxgxxg问如何分配投资数额才能使总效益最大解：可列出静态规划问题的模型如下)3,2,1(,010.294max3212321ixxxxtsxxxZi应用动态规划求解： 1、分阶段：考虑效益函数的形式，分为三个阶段，即k=1，2，3。2、确定决策变量dk：通常可以取静态规划中的变量为决策变量，即决 定给第 k个项目投

4、资的资金数。 确定状态变量S k：状态变量与决策变量有密切关系，状态变量一般为累计量或随递推过程变化的量。既第k阶段可以投资于第k项到第3项目的资金数量。应用动态规划求解： 1、分阶段：考虑效益函数的形式，分为三个阶段，k=1，2，32、确定决策变量dk：通常可以取静态规划中的变量为决策变量，即决定给第 k个项目投资的资金数。3、 确定状态变量sk：状态变量与决策变量有密切关系，状态变量一般为累计量或随递推过程变化的量。既第k阶段可以投资于第k项到最后项（第3项目）的资金数量。4、状态转移方程：Sk+1=sk-xk33221122311210,0,0,10sxsxsxxssxsss5、 指标函

5、数33,)(kiiikxgV6、最优指标函数fk(sk)：当可投资金额为sk时，投资第k项到第3项所得的最大收益数。基本方程为：0)(1 , 2 , 3)()(max)(44110sfksfxgsfkkkksxkkkk解算：1、当阶段k=3时，有23333*3230332)(,2max)(33ssfsxxsfsx最优决策为：最优目标函数：当阶段k=2时，有)(29max29max)(9max)(222202320332022222222xsxsxsfxsfsxsxsx是凹函数，最大值点只能在0，s2端点上取得，即2*22222*222222222222222)()0(290),()0(29)(

6、)0(299)(;2)0(sxsffsxsffssffsssfsf当当当时，时，时，此时此时2阶导数大于0当阶段k=1时，有)(4max)(22101111sfxsfsx2910, 0959max994max)10(112*1111100111100111xssxsxsxsxfxx040)10(10200)10(0)(24max)10(*11111211110011xfxfxxsxfx2229)(ssf22222)(ssf当当时时矛盾，舍去。是凹函数，故比较0,10的端点（最优决策）2阶导数0S29/21010,029103*3*223*2*112sxxssxxss因为所以最优投资方案是全部资

7、金投于第3个项目，可得最大收益200万元。 例2 某大型公司拟将某种高效率的设备5台分配给所属的甲、乙、丙三个工厂，各工厂若获得这种设备之后，可以为公司提供的盈利如表。问这五台设备如何分配给各工厂，才能使公司得到的盈利最大。 工 厂 盈 利设 备 台 数甲 乙丙 0 1 2 3 4 5037912130510111111046111212解：将问题按工厂分为三个阶段，甲、乙、丙分别编号为1，2，3。用k表示，即阶段变量决策变量dk表示分配给第k个工厂的设备台数，即dk=xk；设状态变量sk表示为分配给第k个工厂至第3工厂的设备台数；状态转移方程： sk+1=sk-uk=sk-xk决策集合：Dk

8、(sk)=dk|0dk=xksk最优值函数fk(sk)表示以数量为sk的设备台数分配给第k个工厂至第n个工厂所得到的最大总收益，动态规划的递推关系为：0)(1 , 2 , 3)()(max)(4410sfkxsfxgsfkkkkksxkkkk当阶段k=3时，0s35， 0 x3s3，有0)(4433033max33sfxgsfsx0) 0(0) 0()()(max) 0(0*33443303333xgsfxgfssx1) 1 (4) 1 ()0(max)()(max) 1 (1*3331 ,04433033333xggsfxgfsxsxx3(s3)2)2(6)2() 1 ()0(max)()(

9、max)2(2*33332, 1 ,04433033333xgggsfxgfsxsx3)3(11)3()2() 1 ()0(max)()(max)3(3*333333 ,2, 1 ,04433033333xggggsfxgfsxsx4)4(12)4()3()2() 1 ()0(max)()(max)4(4*3333334, 3 ,2, 1 ,04433033333xgggggsfxgfsxsx5)5(12)5()4()3()2() 1 ()0(max)()(max)5(5*33333335 ,4, 3 ,2, 1 ,04433033333xggggggsfxgfsxsxg3(x3) x3s30

10、12345f3(s3)x*3012345046111212046111212012345结果列于下表：当阶段k=2时， s3=s2-x2， 0s25， 0 x2s2，有0) 0(0) 0()()(max) 0(0*22332202222xgsfxgfssx1) 1 (50540max)0() 1 () 1 ()0(max)()(max) 1 (1*21 ,032321 ,033220222222xfgfgsfxgfsxxsx2)2(100104560max)0()2() 1 () 1 ()2()0(max)()(max)2(2*22 , 1 , 03232322 , 1 , 033220222

11、222xfgfgfgsfxgfsxxsx2)3(1401141065110max)0()3() 1 ()2()2() 1 ()3()0(max)()(max)3(3*23 , 2, 1 , 0323232323 , 2, 1 , 033220222222xfgfgfgfgsfxgfsxxsx2 , 1)4(16011411610115120max)0()4() 1 ()3()2()2()3() 1 ()4()0(max)()(max)4(4*24, 3 , 2, 1 , 032323232324, 3 , 2, 1 , 033220222222xfgfgfgfgfgsfxgfsxxsx2)5(

12、210114116111110125120max) 1 ()4() 1 ()4()2()3()3()2()4() 1 ()5()0(max)()(max)5(5*25 ,4, 3 ,2, 1 ,03232323232325 ,4, 3 ,2, 1 ,033220222222xfgfgfgfgfgfgsfxgfsxxsxg2(x2)+f3(s2-x2) x2s2012345f2(s2) x*201234500+40+60+110+120+125+05+45+65+115+1210+010+410+610+1111+011+411+611+011+4 11+0051014162101221,22结

13、果列于下表：当阶段k=1时， s2=s1-x1， s1=5， 0 x1s1，有2 , 0)5(,21013512109147163210max)0()5() 1 ()4()2()3()3()2()4() 1 ()5()0(max)()(max)()(max)(5*1212121212121112115 ,4, 3 ,2, 1 ,0,22110111111xfgfgfgfgfgfgxsfxgsfxgsfsxsxg1(x1)+f2(s1-x1) x1s1012345f1(s1) x*150+213+167+149+1012+5 13+0210,2结果可写成表格的形式 然后按计算表格的顺序反推，可知

14、最优分配方案有两个： 由于x1*=0，根据s2=s1-x1*=5-0=5，查表知x2*=2，由s3=s2-x2*=5-2=3，故x3*=s3=3。即得甲工厂分配0台，乙工厂分配2台，丙工厂分配3台。 由于x1*=2，根据s2=s1-x1*=5-2=3，查表知x2*=2，由s3=s2-x2*=3-2=1，故x3*=s3=1。即得甲工厂分配2台，乙工厂分配2台，丙工厂分配1台。 以上两个分配方案所得到的总盈利均为21万元。问题：如果原设备台数是4台，求最优分配方案？ 如果原设备台数是3台，求最优分配方案？（2）资源连续分配问题一般问题的提法是：资源数量s1 A种生产数量u1投入收益g(u1)年终资

15、源回收率a B种生产数量s1-u1收益h(s1-u1)年终资源回收率b第一年资源数量s2=au1+b(s1-u1)第二年 A种生产数量u2投入;收益g(u2);年终资源回收率a B种生产数量s2-u2;收益h(s2-u2);年终资源回收率b到n年如此进行n年，如何确定投入A的资源量u1、un，使总收入最大？此问题的静态规划问题模型为：nisuusbaususbaususbaustsushugZiinnnnniiii,2, 1,0)()()(.)()(max1222311121。 设sk为状态变量，它表示在第k阶段（第k年）可投入A、B两种生产的资源量；uk为决策变量，它表示在第k阶段（第k年）

16、用于A生产的资源量，则sk-uk表示用于B生产的资源量；状态转移方程为：sk+1=auk+b(sk-uk)最优值函数fk(sk)表示有资源量sk从第 k阶段至第n阶段采取最优分配方案进行生产后所得到的最大总收入。动态规划的逆推关系方程为：1 , 2 , 1)()()(max)()()(max)(100nkusbaufushugsfushugsfkkkkkkksukknnnsunnnnnn最后求得的f1(s1)即为所求问题的最大收入例3 机器负荷分配问题 某种机器可在高低两种不同负荷下进行生产，设机器在高负荷情况下的产量函数为g=8u1，其中u1是投入生产的机器数量，年完好率为 a=0.7，在低

17、负荷情况下的产量函数为h=5y，其中y是投入生产的机器数量，年完好率为b=0.9。假定开始生产时完好机器的数量为1000台，试问每年如何安排机器在高低两种负荷下的生产，可使5年内生产的产品总产量最高。 5 , 2 , 1),( 9 . 07 . 0)(1kusuusbauskkkkkkk 允许决策集合0uksk解： 设阶段阶段数k表示年度。 状态变量状态变量sk为第k年度初拥有的完好机器台数。 决策变量决策变量uk为第k年度中分配高负荷下生产的机器台数。故低负荷下生产的机器台数是sk-uk。 状态转移方程状态转移方程 第k年度产量为)(58),(kkkkkkusuusv 指标函数为515 ,

18、1),(kkkkusvV 递推方程为1 , 2 , 5)( 9 . 07 . 0()( 58max)(0)(1066kusufususfsfkkkkkkksukkkk5555*5550665550558)(,)53max)()(58max)(55555ssfsususfususfksusu当时4444*4440444044454440446 .13)(,2 .124 . 1max)(2 .126 .13max)(9 . 07 . 0()( 58max)(4444444ssfsusuusuusufususfksususu当时依次类推可得，111*1222*23333*37 .23)(08 .20

19、)(05 .17)(ssfussfussfsu相应的相应的相应的 因为S1=1000，所以f1(s1)=23700因此最优策略为5*54*43*3*2*1, 0, 0sususuuu即前两年应在年初把全部完好的机器投入低负荷生产，后三年应在年初把全部完好的机器投入高负荷生产。最高产量为23700（台）。每年年初的机器状态：S1=1000S2=0.7u1+0.9(s1-u1)=0.9s1=900S3= 0.7u2+0.9(s2-u2)=0.9s2=810S4= 0.7u3+0.9(s3-u3)=0.7s3=567S5= 0.7u4+0.9(s4-u4)=0.7s4=397S6= 0.7u5+0.

20、9(s5-u5)=0.7s5=278练习：每年年初的完好机器数。作业：如规定在第五年结束时完好机器数为500台，该如何安排生产？3、生产与存贮问题、生产与存贮问题 所谓生产与库存问题就是一个生产部门，如何在已知生产成本、库存费用和各阶段市场需求条件下，决定各阶段产量，使计划内的费用总和为最小的问题。很多问题可以化成此类问题来解决。 生产与库存问题本身就是一个多阶段决策过程。设某一生产部门，生产周期分为n个阶段，已知最初库存量为x1，阶段市场的需求为dk，生产的固定成本为K，单位产品的消耗费用为L，单位产品的阶段库存费用为h，仓库容量为M，阶段最大生产能力为B。问如何安排各阶段产量，使计划周期内

21、的费用总和最小。状态变量xk选为阶段k的初始库存量，x1已知，xn+1=0。 阶段k的库存量即不能超过库存容量M，也不能超过阶段k至阶段n的需求总量(因为n+1阶段的库存量为0），即nkdddMxnkkk, 2 , 1,min01 决策变量uk选为阶段k的产量。阶段产量必须不超过生产能力和第k阶段到第n阶段的总需求减去第k阶段初的库存量，同时要大于该阶段的需求和库存量之差，即,min1knkkkkkxdddBuxd 状态转移方程为kkkkduxx1 阶段效益为阶段生产费用和库存费用之和，即)(),(kkkkkkkduxhLuKuxg阶段k的生产费用k阶段末的库存费用 动态规划基本方程)()(m

22、in)(11)(kkkkkkxDukkxfduxhLuKxfkkk 例 已知n=3，K=8，L=2，h=2，x1=1，M=4，x4=0（计划周期末期的库存量为0），B=6，d1=3，d2=4，d3=3，求解生产与库存问题。 解：利用上述的递推方程得0) 3 (, 8) 3 (31) 2(,10) 2(22) 1 (,12) 1 (13) 0(,14) 0(03,min,min0214)3 ( 2828min)(3*333*333*333*33333333 , 6min33333ufxufxufxufxdMdMxxxuxfknkiikxuxk若若若若则则则则当时x4=x3+u3-d3=0 u3

23、x30123f3(x3)u*3(x3)01414311212221010138807 , 6min,min44,min022232223222223xxddBuxMddMxduxxk当时3) 1 (288620104181221614014min)3()3(228min) 1 (14)0(30104201221814016min)4()4(228min)0(047 ,min,min0)4()4(228min)()(228min)(*223226, 5 ,4, 322*223226, 5 ,4223222232227,6min43322227,6min42222222222uufuufxuufu

24、ufxMdMxuxfuxuxfduxuxfuuiixuxxux若若则则1) 3(248616104141221214010min)1() 1(228min) 3(32)2(268618104161221414012min)2()2(228min)2(2*223224 , 3 , 2 , 122*223225 , 4 , 3 , 22222uufuufxuufuufxuu0) 4(22861410412122101408min)(2)28(min) 4(4*223223 , 2 , 1 , 0222uufuufxu u2 x20123456f2(x2) u*2(x2)016+0+14 18+2+

25、12 20+4+10304114+0+14 16+2+12 18+4+10 20+6+8283212+0+14 14+2+12 16+4+10 18+6+8262310+0+14 12+2+12 14+4+10 16+6+824148+0+14 10+2+12 12+4+10 14+6+8220结果见下表：2) 1 (422282024618264162821430012min)2()2(228min)()(228min) 1 (62, 211*112116 , 5 , 4 , 3 , 22211116 , 5 , 4 , 3 , 21112111uufuuxfduxufuuxxkuu时是唯一

26、确定的，因此 u1 x123456f1(x1) u*1(x1)112+0+30 14+2+28 16+4+26 18+6+24 20+8+22422最优决策为最优路线为 1，0，0，0最优目标函数值为42。3)0(, 4)0(, 2) 1 (*3*2*1uuux2=u1-2=0 x3=x2+u2-d2=0+4-4=04、设备更新问题设备更新问题 个人、单位等随时均有设备更新问题。自行车、彩电、设备随着使用年限的增加而设备陈旧，处理价格愈低，因此需要维修和更新的费用增加。处于各种阶段的设备总是面临保留还是更新问题。保留还是更新，应该从整个计划期间的总回收额来考虑，而不能从局部的某个阶段的回收额来

27、考虑，是一个多阶段的决策问题。设备更新问题提法如下（以一台机器为例）： n为计划设备使用年数。 Ik(t) 为第k年（阶段）已经使用过t年的机器再使用一年所得的收入。 Ok(t) 为第k年已经使用过t年的机器再使用一年的维修费用 。 Ck(t) 为第k年卖掉一台已经使用过t年的机器，买进一台新设备的更新净费用。为折扣因子，表示一年以后收入是上一年的单位。要求在n年内的每年年初作出决策，是继续使用旧设备还是更换一台新的，使n年内总效益最大？建立动态规划模型如下：阶段k（k=1，2，n）表示计划使用该设备的年限数。状态变量sk：第k年初，设备已使用过的年数。决策变量xk：是第k年初更新（Repla

28、cement），还是保留使用（Keep）旧设备，分别用K，R表示。状态转移方程为： RxKxsskkkk111 阶段效益为：RxKxscOIsOsIxsvkkkjjjkjkjkkj)() 0() 0()()(),(最优指标函数fk(sk)：表示第k年初，使用一台已用了sk年的设备，到第n年末的最大收益，动态规划的基本方程为0)()(),(max)(1111nnkkkkjRorKxkksfsfxsvsfk实际上RxKxfscOIsfsOsIsfkkkkkkkkkkkkkkk) 1 ()() 0 () 0 () 1()()(max)(11 役龄项目012345效益 Ik(t)54.543.7532

29、.5运行费Ok(t)0.511.522.53更新费ck(t)0.51.52.22.533.5（单位：万元）例：设某台新设备的年效益及年均维修费用、更新净费用如下表，试确定今后五年内的更新策略，使总效益最大。（设=1）解：n=5RxKxscOIsOsIsfk555555555555)() 0() 0()()(max)(5状态变量s5可取1，2，3，4KxRxKxcOIOIf) 1 (5 . 35 . 15 . 0515 . 4max) 1 () 0() 0() 1 () 1 (max) 1 (555555555KxRxKxcOIOIf) 2(5 . 22 . 25 . 055 . 10 . 4m

30、ax) 2() 0() 0() 2() 2(max) 2(555555555RxRxKxcOIOIf) 3(25 . 25 . 05275. 3max) 3()0()0() 3() 3(max) 3(555555555卖掉役龄2年的设备，买入新设备的更新费用RxRxKxcOIOIf)4(5 . 135 . 055 . 23max)4()0()0()4()4(max)4(555555555RxKxfscOIsfsOsIsfk445444445444444) 1 ()() 0() 0() 1()()(max)(4状态变量s4可取1，2，3RxRxKxfscOIsfsOsIfs) 1 (5 . 65

31、 . 35 . 15 . 055 . 215 . 4max) 1 ()() 0() 0() 1()()(max) 1 (44454444454444144RxRxKxfscOIsfsOsIfs) 2(8 . 55 . 32 . 25 . 0525 . 14max) 1 ()() 0() 0() 1()()(max) 2(44454444454444244RxRxKxfscOIsfsOsIfs) 3 (5 . 55 . 35 . 25 . 055 . 1275. 3max) 1 ()() 0() 0() 1()()(max) 3 (44454444454444344RxKxfscOIsfsOsI

32、sfk334333334333333) 1 ()() 0() 0() 1()()(max)(3此时s3可取1或2RxRxKxfscOIsfsOsIfs) 1 (5 . 95 . 65 . 15 . 058 . 515 . 4max) 1 ()() 0() 0() 1()()(max) 1 (33343333343333133RxRxKxfscOIsfsOsIfs) 2(8 . 85 . 62 . 25 . 055 . 55 . 14max) 1 ()() 0() 0() 1()()(max) 2(33343333343333233RxKxfscOIsfsOsIsfk22322222322222

33、2) 1 ()() 0() 0() 1()()(max)(2由于状态s2只能取1，所以有RxRxKxfscOIsfsOsIfs) 1 (5 .125 . 95 . 15 . 058 . 815 . 4max) 1 ()() 0() 0() 1()()(max) 1 (22232222232222122RxKxfscOIsfsOsIsfk112111112111111) 1 ()() 0() 0() 1()()(max)(1由于状态s1只能取0，所以有KxRxKxfscOIsfsOsIfs) 0(175 .125 . 05 . 055 .125 . 05max) 1 ()() 0() 0() 1

34、()()(max) 0(11121111121111011上述过程递推回去，当x*1(0)=K，由状态转移方程本例的最优策略是K，R，R，R，K，即第一年初购买的设备到第二、三、四年初各更换一次，用到第五年年末，总效益为17万元。RxKxss111211s2=1，查f2(1)得x*2=Rs3=1，查f3(1)得x*3=Rs4=1，查f4(1)得x*4=Rs5=1，查f5(1)得x*5=KRxKxss222311 5、动态规划总结 一、动态规划基本概念： 1 阶段：将所给问题的过程，按时间或空间特征分 解成若干互相联系的阶段，用k表示， 2 状态：各阶段开始时的客观条件。 状态变量用sk表示。

35、状态变量集合用Sk表示。 状态性质：当某阶段状态给定以后，在这阶段以 后的过成的发展不受这段以前各状态 的影响。3 决策：当各阶段的状态确定以后，可以作出不同的选择，从 而确定下一阶段的状态。这个选择称为决策。 决策变量:dk(sk) 允许决策集合：决策变量的取值范围，用DK(SK)表示4 策略：各阶段决策确定后，整个问题的决策序列就构成一 个策略。P1.nd1(s1),d2(s2),dn(sn). 允许策略集合：可供选择的策略范围。P1.n5 状态转移方程：由k阶段到k+1段的状态转移规律。 Sk+1=Tk(sk,uk) 6 指标函数：用于衡量所选定策略优劣的数量指标。 V1.n(s1,p1

36、.n)表示初始状态为S1，采用策略p1.n 时原过程的指标函数值。7 最优指标函数：从第k阶段状态Sk，采用最优策略pk.n 到过 程终止时的最佳效益值。 fk(sk)=Vk.n(sk,pk.n ) =opt Vk.n(sk,pk.n ) 二、动态规划基本原理Bellmen 最优化原理：一个过程的最优策略具有这样的性质：无论初始状态及初始决策如何，对于先前决策所形成的状态而言，其以后的所有决策应构成最优决策，三、动态规划的基本思想 （1）划分阶段，选取变量，定义最优指标函数。 （2）从边界条件开始，逆过成行进方向逐段递推寻优。 （3）把当前效益和未来各段分开，又把当前效益与未来效 益结合起来考

37、虑。 四、动态规划的 基本解法 1 逆序解法：适用于初始状态给定的情况。 2 顺序解法：适用于终止状态给定的情况。五、动态规划基本方程0)(1 , 2, 1,)(),()(1111nnkkkkkkksfnnksfsvoptsf六、动态规划模型的建立要点1 划分满足递推关系的若干阶段2 正确选择状态变量、决策变量（可知性和无后效性）3 正确写出状态转移方程 Sk+1=Tk(sk,uk)4 确定指标函数Vk n,5 列出基本方程最优指标函数fk(sk)，确定边界条件。 七、几个典型示例动态规划模型的建立最短路问题阶段k：整体路线上的段数状态变量sk：每一段上的中转站决策变量uk：从某一段上某一状态

38、到下一阶段各中转站的决定状态转移方程：Sk+1=uk(sk)指标函数：V k.n是第k阶段到终点的距离基本方程： 0)() 1 , 2 , 1,)(),(min)(1111nnkkkkkkksfnnksfusdsf资源分配问题阶段k：投资项目数状态变量sk：第k段可以投资于第k项到第n个项目的资金数决策变量xk：决定给第k个项目投资的资金数状态转移方程：sk+1=sk-xk指标函数：最优值函数fk(sk):表示以数量为sk的原料分配给第k种产品至第n种产品所得到的最大总收益。基本方程： )(max)(1 , 1)()(max)(10nnsxnnkkkkksxkkxgsfnkxsfxgsfnnkk)(nkiiinkxgV生产与存储问题阶段k：每个月为一个阶段状态变量xk：第k个月初的库存量决策变量uk：第k个月的生产量状态转移方程：阶段效益为阶段生产费用和库存费用之和，即 kkkkduxx1)(),(kkkkkkkduxhLuKuxg基本方程：)()(min)(11)(kkkkkk