理学第八章动态规划PPT学习教案

1、会计学1 理学第八章动态规划理学第八章动态规划 2 6 AB2 B1 B3 C1 C2 C3 D1 D2 E 2 4 3 7 4 3 2 4 1 5 4 3 3 3 3 4 原问题为求从原问题为求从A A到到E E走哪条途径使保险单（走哪条途径使保险单（policypolicy，策略，策略）的总费用达到最小？）的总费用达到最小？ 6 4 第1页/共84页 2 6 AB2 B1 B3 C1 C2 C3 D1 D2 E 2 4 3 7 4 3 2 4 1 5 4 3 3 3 3 4 4 6 1 1 8 7 4 0 第2页/共84页 2 6 AB2 B1 B3 C1 C2 C3 D1 D2 E 2

2、4 3 7 4 3 2 4 1 5 4 3 3 3 3 4 6 4 第3页/共84页 EDuDf)(,3)( 1414 EDuDf)(,4)( 2424 113 24 14 13 5 )(4 )(2 min)(DCu Df Df Cf ）（， 223 24 14 23 7 )(3 )(6 min)(DCu Df Df Cf ）（， 133 24 14 33 6 )(3 )(3 min)(DCu Df Df Cf ）（， )(3 )(4 )(2 min)( 32 22 12 1 Bf Bf Bf Af 2 6 AB2 B1 B3 C1 C2 C3 D1 D2 E 2 4 3 7 4 3 2 4

3、1 5 4 3 3 3 3 4 4 6 3 4 0 5 7 6 第4页/共84页 212 33 23 13 12 11 66 74 57 min )(6 )(4 )(7 minCBu Cf Cf Cf Bf ）（，）（ 122 33 23 13 22 8 )(4 )(2 )(3 min)(CBu Cf Cf Cf Bf ）（， 232 33 23 13 32 8 )(5 )(1 )(4 min)(CBu Cf Cf Cf Bf ）（， 2 6 AB2 B1 B3 C1 C2 C3 D1 D2 E 2 4 3 7 4 3 2 4 1 5 4 3 3 3 3 4 6 4 0 3 4 5 7 6 1

4、 1 8 8 第5页/共84页 2 6 AB2 B1 B3 C1 C2 C3 D1 D2 E 2 4 3 7 4 3 2 4 1 5 4 3 3 3 3 4 6 4 0 3 4 5 7 6 1 1 8 8 31 32 22 12 1 11 83 84 112 min )(3 )(4 )(2 minBAu Bf Bf Bf Af ）（，）（ 1 1 u u2 2（B B3 3）=C=C2 2 u u3 3（C C2 2）=D=D2 2 u u4 4（D D2 2）=E=E 最安全道路为最安全道路为ABAB3 3CC2 2DD2 2EE，最小费用为，最小费用为1111。 第6页/共84页 第7页/

5、共84页 第8页/共84页 状态状态 sn 状态状态 sn+1 决策决策un 效果效果 vn n 第9页/共84页 第10页/共84页 第11页/共84页 第12页/共84页 nknkkk usVus, 1,1 n kj jjj usv),( ),(),( 11, 1,nnkknkkkknk ususVusvV 常用的指标函数常用的指标函数： 1 1 全过程和它的任一后部子过程的指标函数等于各阶段指标函数之和 全过程和它的任一后部子过程的指标函数等于各阶段指标函数之和 N Noteote 指标函数应具有指标函数应具有可分离性可分离性，即，即V Vk,n k,n可表示为： 可表示为： V Vk,

6、n k,n（ （s sk k，u uk k，s sk+1 k+1， ，u uk+1 k+1， ，s sn n，u un n）= = V Vk,n k,n（ （s sk k，u uk k，s sk+1 k+1， ，u uk+1 k+1， ，s sn n，u un n）= = 或或 且且对于对于Vk+1，n单调性单调性,满足递推关系满足递推关系 第13页/共84页 ),()( , ).( nnkknk uu kk ususVoptsf nk ),()( , )( , nkknk sPp kk psVoptsf knknk n kj nkkkkjjjnk VusvusvV ,1, ),(),( 第1

7、4页/共84页 ),(),(*),( , )( 1, 111, 1 )( , 11, 1 ,11, 11, 1 nkknk sPp Kk sPp nn psVoptpsVoptpsV knknkkk 第15页/共84页 )(),()( 11 )( kkkkk sDu kk sfusvoptsf k k k 第16页/共84页 （边界条件）0)( )()(,()( 55 1 )( min sf sufsusvsf kkkkkk sDu kk kkk 第17页/共84页 ),( 0)( )(),()( 1 11 11 )( kkkk nn kkkk sDu kk usTs sf sfusvopts

8、f kkk ),( 1)( )(),()( 1 11 11 )( kkkk nn kkkk sDu kk usTs sf sfusvoptsf kkk 第18页/共84页 2 6 AB2 B1 B3 C1 C2 C3 D1 D2 E 2 4 3 7 4 3 2 4 1 5 4 3 3 3 3 4 6 4 0 2 4 3 7 4 8 9 7 11 第19页/共84页 ),( 0)( ,2, 1)(),()( 1 10 11 )( 1 1 kkkk kkkkk sDu kk usTs sf nksfusvoptsf kkk 第20页/共84页 ),( 0)( )(),()( 1 11 11 )(

9、kkkk nn kkkk sDu kk usTs sf sfusvoptsf kkk )(,),( 11 sfsf nn 第21页/共84页 )( 11 sf ),(),()( , 11, 1 )( * , 11, 11 * 1 1, 1, 1 nn sPp nn psVoptpsVsf nn 第22页/共84页 ),( 0)( )(),()( 1 11 11 )( kkkk nn kkkk sDu kk usTs sf sfusvoptsf kkk ),( 1)( )(),()( 1 11 11 )( kkkk nn kkkk sDu kk usTs sf sfusvoptsf kkk 第2

10、3页/共84页 第24页/共84页 解解: 2年划分年划分2个阶段，个阶段， 表示表示K个阶段高负荷生产的设备台数个阶段高负荷生产的设备台数, 表示第表示第K个阶段完好的设备台数个阶段完好的设备台数 状态转移方程状态转移方程: -3分分 时，时， 时，时， 为最优解和最优值为最优解和最优值-10分分 xxg8)( yyh6)( k u k s ),(9 . 04 . 0 1kkkk usus 0)(,)()(68)( 3311 0 max sfsfususf kkkkk su kk kk 2k ）取 22222 0 222 0 22 ( ,8)62()(68)( maxmax 2222 sus

11、suususf susu 1k ）令0( ,2 .1322 .138)(68)( 1111 u0 2111 u0 11maxmax 1111 usussususf ss 0 1 u13200)1000(,900 12 fzu 111112 5 .09 .0)(9 .04 .0ususus 第25页/共84页 nju buauaua st ugugugz j nn nn , 2 , 10 )()()(max 2211 2211 用动态规划求解上述静态模型有一个统一的方法： 如同线性规划问题中可以将约束条件看成资源限制一样，这里也可以这样理解，将现有数量为 个单位的某种资源用来生产 种产品，问如何

12、分配使总利润最大。 设工厂的决策者分 阶段来考虑这个问题，如果是逆序递推法，决策者首先考虑的是第 种产品生产几件，消耗资源多少，然后考虑第 种和第 种产品各生产多少，消耗资源多少；依次向前递推，在第 阶段时考虑第 种，直到第 种产品各生产多少，消耗资源多少。 bn n 1n n k kn n 第26页/共84页 （1）把问题划分为n个阶段，取 为第k阶段的决策变量，或者理解为 第k种产品生产的件数，第k阶段的效益为 ， K子过程的指标函数为各阶段效益之和。 k u ), 2 , 1(),(nkug kk ), 2 , 1()( , nkugV n kj jjnk （2）如何选择状态变量 k s

13、？ ) 1 , 1,( 1 nnkuass kkkk 令 表示可供第 种产品直到第 种产品消耗的资源数。 显然 ， 而且 无后效性，第 阶段（产品）消耗的资源数为 状态转移方程为： k s k n 0 k s k sk kku a 第27页/共84页 k u 0 k s 0 k u kkk asu/0 kkkkkk asuusD/0|)( bSbssS kkk 1 ,0| )( kk sf （3）决策变量 的取值范围： 由 ， 得 于是决策集合： 允许状态集合： （4）最优值函数 表示从第k阶段到第n阶段指标函数的最优值 逆序递推方程： 0)( ) 1 , 1,()()(max)( 11 11

14、 )( nn kkkk sDx kk sf nnksfxgsf kkk 第28页/共84页 nju buauaua st ugugugz j nn nn , 2 , 10 )()()(max 2211 2211 （1）把问题划分为n个阶段，取 为第k阶段的决策变量，第k种产品生 产的件数，第k阶段的效益为 ， 指标函数为各阶段效益之积。 k u ), 2 , 1(),(nkug kk ), 2 , 1()( , nkugV jj n kj nk 第29页/共84页 （2）如何选择状态变量 k s？ 令 表示可供第 种产品直到第 种产品消耗的资源数。 显然 ， 而且 无后效性，第 阶段（产品）消

15、耗的资源数为 状态转移方程为： k s k n 0 k s k sk kku a ) 1 , 1,( 1 nnkuass kkkk 第30页/共84页 k u 0 k s 0 k u kkk asu/0 kkkkkk asuusD/0|)( bSbssS kkk 1 ,0| )( kk sf （3）决策变量 的取值范围： 由 ， 得 于是决策集合： 允许状态集合： （4）最优值函数 表示从第k阶段到第n阶段指标函数的最优值 逆序递推方程： 1)( ) 1 , 1,()()(max)( 11 11 )( nn kkkk sDx kk sf nnksfxgsf kkk 第31页/共84页 3 ,

16、2 , 10 10543 654max 321 321 ju uuu st uuuz j kkkk uass 1 10 1 s kkk asu/0 0)( ) 1 , 2 , 3()()(max)( 44 11 )( sf ksfugsf kkkk sDu kk kkk 06max)()(max)( 3 5/0 4433 )( 33 33333 usfugsf susDu 5/ 33 su 5/6)( 333 ssf 取 ， 状态转移方程： 223 4uss 第32页/共84页 当k=2时 )4/( 4/5)5/620/1 (5/65/max 5/65max)()(max)( 22 2222

17、4/0 32 4/0 3322 )( 22 22 22222 su sssu susfugsf su susDu 取 状态转移方程 ： 当k=1时 112 3uss ) 3/( 3/44/ )3(54max 4/54max)()(max)( 11 1111 3/0 21 3/0 2211 )( 11 11 11111 su susu susfugsf su susDu 取 10 1 s 3/403/1043/4)( 111 ssf 由 得 3/10 1 u 03/103103 112 uss 04/ 22 su 00404 223 uss 05/ 33 su 3/40)0 , 0 , 3/10

18、( * zu T 第33页/共84页 3 , 2 , 10 6 max 321 3 32 2 1 ju uuu st uuuz j kkk uss 1 6 1 s60 kk su 1)( ) 1 , 2 , 3()()(max)( 44 11 )( sf ksfugsf kkkk sDu kk kkk 3 3 0 4433 )( 33 33333 max)()(max)(usfugsf susDu 33 su 3 333 )(ssf 取 ， 状态转移方程： 223 uss 第34页/共84页 当k=2时 )4/( 256/27)(max max)()(max)( 22 4 2 3 222 0

19、3 32 0 3322 )( 22 22 22222 su susu susfugsf su susDu 取 状态转移方程 ： 当k=1时 112 uss ) 3/(, 2716 1 )( 256 27 max)()(max)( 11 6 1 4 11 2 1 0 2211 )( 11 11111 sus ususfugsf susDu 取 6 1 s 108)( 11 sf 由 得 23/ 11 su 426 112 uss 14/ 22 su 314 223 uss 3 33 su 108)3 , 1 , 2( * zu T 第35页/共84页 月份k0123456 需求量dk 08532

20、74 单位工时ak 111813172010 5 , 4 , 3 , 2 , 1 , 00 294723582 102017131811min 543210 543210 ju uuuuuu st uuuuuuz j 第36页/共84页 0)( )(min)( 77 1 )( sf dusfuasf kkkkkk sDu kk kKK ) 4( 0 , 1 , 2 , 3 , 4 , 5 , 6 66 ds k )11(10min)( 555 11 55 55 suasf su 第37页/共84页 )( 44 sf )( 444 min sDu )( 444544 dusfua )( 444m

21、in sDu )( 444 min sDu )( 33 sf )( 333 min sDu )( 333433 dusfua )( 333 min sDu 第38页/共84页 )( 333mins Du )( 22 sf )( 222mins Du )( 222322 dusfua )( 222 min sDu 329174 22 su 第39页/共84页 )( 11 sf)( 111211 dusfua )( 111mins Du 377135 11 su )( 00 sf )( 000mins Du )( 000100 dusfua )( 000mins Du 442187 00 su )

22、( 111mins Du 第40页/共84页 k 0 1 2 3 4 5 6 sk2959974 uk7493040 dk0853274 第41页/共84页 1 u 2 u 0,8 2117 2415310max 2121 2 22 2 11 2 222 2 111 uuuust uuuu uuuuuuz k u k s kkk uss 1 第42页/共84页 kkkkk suusD0|)( 8,80| 1 ssss kkk 0)( ) 1 , 2()()(max)( 33 11 )( sf ksfugsf kkkk sDu kk kkk 允许决策集合为允许决策集合为 允许状态集合为允许状态集

23、合为 基本方程基本方程 k=2时时 ) 4 11 (8 4 11 8 121 )( 4 11 0211 211max)()(max)( 22 2222 2 22 2 22 0 3322 )( 22 22222 us sususs uusfugsf susDu 取 取 当k=1时 88 4 11 , 8 121 7 4 11 80,32840)8(2)8(11)7( max )8()7(max )()7(max)()(max)( 1 2 11 1 2 11 2 11 2 11 80 12 2 11 80 112 2 11 0 2211 )( 11 1 1 11111 uuu uuuuuuu uf

24、uu usfuusfugsf u u susDu 第43页/共84页 4 21 0 8 121 7 8 4 21 32840 )( 1 2 11 1 2 11 1 uuu uuu u ）（最大值为 ）（最大值为 ， 2 7 4 21 )( 4 21 027 8 4 21 628 )( 1 11 11 1 u uu uu u 2 7 1 u 4/112/92/78 112 uss 4/11 2 u 375.27| ) 8 121 7()8( 2 7 2 111 1 u uuf 取取时，时， 所以所以 第44页/共84页 0 1 ij x 否则 套设备个分厂分配得第ji 3 1 6 1 max i

25、j ijij xcZ 6 0 1 j ij x 3 1 6 1 64 ij ij jx 第45页/共84页 第46页/共84页 444 11 0 )( 1 , 2 , 3)(max)( ssf ksfusf kkk su kk kk %)101)(max)()(max)( 333 0 4433 0 33 3333 ususfsusf susu 0)%)101)( 3 333 u usu %102 3 3 s u 333 %)102()(ssf %)101)(%)(102()( 2233 ussf 444444 )()(suufsf 第47页/共84页 %)101)(%)(102(max)(ma

26、x)( 222 0 332 0 22 2222 ususfusf susu 2 2 2 %)101(%)101(1 s u 2 2 22 %)101(%)101(1)(ssf %)101)( 112 uss %)101)(400( 12 us %)101)(400(%)101 (%)101 (1 )( 1 2 22 usf 第48页/共84页 %)101)(400(%)101 (%)101 (1max)400()( 1 2 1 4000 111 1 uufsf u 0%)101)(400(%)101 (%)101 (1 1 1 2 1 n uu 2 .86%)101 (%)101 (%)101

27、 (1 400 132 1 u 1.43)400( 1 f 第49页/共84页 第50页/共84页 第51页/共84页 kkk uss 1 0|)( kkkkk suusD 0)( 1 , 2, 2, 1,)()(max)( 11 1 0 nn kkkkk su kk sf nnnkusfugsf kk 第52页/共84页 套 数 利 润 分 厂 0 1 2 3 4 5 6 1 0 3 5 6 7 6 5 2 0 4 6 7 8 9 10 3 0 2 5 9 8 8 7 第53页/共84页 0|)( kkkkk suusD kkk uss 1 0)( 1 , 2 , 3)()(max)( 44

28、 11 0 sf ksfugsf kkkk su kk kk 第54页/共84页 f g3（3）+f4（s4=s3-u3） f3（s3） u3* u3 s3 0 1 2 3 4 5 6 0 0 0 0 1 0 221 2 0 2 5 52 3 0 2 5 993 4 0 2 5 9 8 93 5 0 2 5 9 8 893 60 2 5 9 8 8 79 3 K=3 第55页/共84页 f g2（u2）+ f3（s3=s2-u2） F2（s2） u2* s3 u2 S2 0123456 0 0+0 000 1 0+2=24+0=4 410 2 0+5=54+2=66+0=6 61，21，0 3

29、 0+9=94+5=96+2=87+0=7 90，13，2 4 0+9=94+9=136+5=117+2=98+0=8 1313 5 0+9=94+9=136+9=157+5=128+2=109+0=9 1523 6 0+9=94+9=136+9=157+9=168+5=139+2=1110+0=10 1633 K=2 第56页/共84页 f g1（u1）+ f2（s2=s1-u1） f1（s1 ） u1* s2 u1 s1 0 1 2 3 4 56 40+13 =13 3+9 =12 5+6 =11 6+4 =10 7+0 =7 1304 50+15 =15 3+13 =16 5+9 =14

30、 6+6 =12 7+4 =11 6+0 =6 1614 60+16 =16 3+15 =18 5+13 =18 6+9 =15 7+6 =13 6+4 =10 5+0 =5 181,25，4 从上表看出最优值和最优解为： F1（4）=13 ， u1=0，u2=1，u3=3 F1（5）=16，u1=1，u2=1，u3=3 F1（6）=18，u1=1，u2=2，u3=3或 u1=2，u2=1，u3=3 第57页/共84页 0)( 3 , 2 , 1)()(max)( 10 1 )( 1 1 sf ksfugsf kkkk sDu kk kkk 第58页/共84页 K=2 g1（u1）+ f0（s

31、1） f1（s2） u1* s2 u10123456 00+000 13+0=331 25+0=552 36+0=663 47+0=774 56+0=665 65+0=556 表1-5 第59页/共84页 K=2 g2（u2）+ f1（s2） f2（s3） u1* s3 u20123456 00+000 10+3=34+0=441 20+5=54+3=76+0=671 30+6=64+5=96+3=97+0=791,2 40+7=74+6=106+5=1 1 7+3=1 0 8+0=8112 50+7=74+7=116+6=1 2 7+5=1 2 8+3=1 1 9+0 =9 122,3 60

32、+7=74+7=116+7=1 3 7+6=1 3 8+5=1 3 9+3 =12 10+0= 10 132,3, 4 表 1-6 第60页/共84页 K=3 g3（u3）+ f2（s3） f3 （ s4 ） u 3* u3 s4 0123456 40+11=112+9=135+7=129+4=1 3 8+0=8133 50+12=1 2 2+11=1 3 5+9=149+7=1 6 8+4=128+0=8163 60+13=1 3 2+12=1 4 5+11=16 9+9=1 8 8+7=158+4=1210+0=1 0 183 s s4 4=6=6时，即购时，即购6 6套设备，套设备，f

33、f3 3(6) =18(6) =18为最大值为最大值, ,反向追踪反向追踪 可知最优策略为可知最优策略为p p1 1， ，3 3（ （s s3 3=6=6）=1=1，2 2，33或或22，1 1，33。 第61页/共84页 N j jju vZ 1 max N j jj Wuw 1 第62页/共84页 0)( )(max)( 11 11 /0 NN jjjj wsu jj sf sfuvsf jjj 第63页/共84页 )(30max)( 443 /0 33 333 sfusf wsu jwjvj 1265 2380 3130 第64页/共84页 u3 3 30 u3 f3（3）u3* 012

34、345 00 00 1030 301 203060 602 30306090 903 40306090120 1204 503060901201501505 第65页/共84页 )3(80max)( 2232 /0 22 222 usfusf wsu u2 2 80 u2+f3（2-3 u2） f2（2） u2* 3 01 00+0=0 000 10+30=30 3001 20+60=60 6002 30+90=9080+0=809003 40+120=12080+30=11012004 50+150=15080+60=14015005 第66页/共84页 )2(65max)( 1121 20

35、 11 1 usfusf u u1 1 65u1+f2（1-2u1） f1（1） u1 * 012 50+150 =150 65+90 =155 130+30 =160 1602 j123 wj511 uj*201 第67页/共84页 第68页/共84页 部位 巡逻队数 预期损失 ABCD 218382434 314352231 410312125 第69页/共84页 )()(min)( 11 )( kkkk sDu kk sfugsf kkk 第70页/共84页 )()(min)( 5544 )( 44 444 sfugsf sDu )(min)( 44 )( 44 444 ugsf sDu

36、 第71页/共84页 u4 s4 g4（u4） f4（s4） u4 * s5 234 2343420 334313130 43431252540 53431252540 63431252540 第72页/共84页 )()(min)( 4433 )( 33 333 sfugsf sDu u3 s3 g3（u3）+ f4（s3- u3） f3（s3） u3 * s4 234 424+34=585822 524+31=5522+34=565523 624+25=4922+31=5321+34=554924 724+25=4922+25=4721+31=524734 824+25=4922+25=47

37、21+25=464644 第73页/共84页 )()(min)( 3322 )( 22 222 sfugsf SDu u2 s2 g 2（u2）+ f3（s2- u2） f2（s2） u2 * s3 234 838+49=8735+55=9031+58=898726 938+47=8535+49=8431+55=868436 1038+46=8435+47=8231+49=808046 第74页/共84页 )()(min)12()( 2211 )12( 111 11 sfugfsf Du u1 s1 g1（u1）+ f2（s1- u1） f1（s1） u1* s2 234 1218+80=9814+84=9810+87=979748 第75页/共84页 销售点 地区 012345 1067111521 20912172329 301014192023 第76页/共84页 k x k s kkkkk sxxss 0, 1 0)(,)()()( 4411 0 max sfsfxgsf kkkk sx kk kk 3k f 3