运筹学 动态规划2

1、第十章第十章 动态规划应用举例动态规划应用举例运筹学运筹学第九章第九章 动态规划应用举例动态规划应用举例生产与存储问题生产与存储问题本章内容本章内容资源分配问题资源分配问题背包问题背包问题复合系统工作可靠性问题复合系统工作可靠性问题排序问题排序问题设备更新问题设备更新问题货郎担问题货郎担问题第一节第一节 资源分配问题资源分配问题 设总投资额为设总投资额为a万元，拟投资于万元，拟投资于n个项目上，已知个项目上，已知对第对第i个项目投资个项目投资xi万元，收益函数为万元，收益函数为gi(xi)，问应如，问应如何分配资金才可以使总收益最大？何分配资金才可以使总收益最大？这是一个与时间这是一个与时间无

2、明显关系的静态最优化问题，可先列出其静态模无明显关系的静态最优化问题，可先列出其静态模型为：型为： nixaxxgZiniiniii.2.1 0)(max11据此，有下式：据此，有下式： （一）投资分配问题（一）投资分配问题例例1 1 某公司有资金某公司有资金1010万元，若投资于项目（万元，若投资于项目（i=1,2,3i=1,2,3）的投资额为的投资额为x xi i时，其收益分别为时，其收益分别为g g1 1(x(x1 1)=4x)=4x1 1, , g g2 2(x(x2 2)=9x)=9x2 2, g, g3 3(x(x3 3)=2x)=2x3 3, ,问应如何分配投资额才能使问应如何分

3、配投资额才能使总收益最大？总收益最大？123100(1,2,3)ixxxxi123max492Zxxx建立模型：建立模型：例例2 有资金有资金4万元，投资万元，投资A、B、C三个项目，每三个项目，每个项目的投资效益与投入该项目的资金有关。三个项目的投资效益与投入该项目的资金有关。三个项目个项目A、B、C的投资效益（万吨）和投入资金的投资效益（万吨）和投入资金（万元）关系见下表：（万元）关系见下表： 求对三个项目的最优投资分配，使总投资效求对三个项目的最优投资分配，使总投资效益最大。益最大。1 1、阶段、阶段k k：每投资一个项目作为一个阶段；：每投资一个项目作为一个阶段；2 2、状态变量、状态

4、变量x xk k：投资第：投资第k k个项目前的资金数；个项目前的资金数；3 3、决策变量、决策变量d dk k：第：第k k个项目的投资；个项目的投资；4 4、决策允许集合：、决策允许集合：00d dk kx xk k5 5、状态转移方程：、状态转移方程：x xk k+1+1= =x xk k- -d dk k6 6、阶段指标：、阶段指标：v vk k( (x xk k , ,d dk k) )见表中所示；见表中所示；7 7、递推方程：、递推方程：f fk k( (x xk k)=max)=maxv vk k( (x xk k , ,d dk k)+)+f fk k+1+1( (x xk k

5、+1+1)8 8、终端条件：、终端条件：f f4 4( (x x4 4)=0)=0分析：分析：k=4k=4，f f4 4(x(x4 4)=0)=0 x3 D3(x3) x4 v3(x3,d3) v3(x3,d3)+f4(x4) f3(x3) d3* 0 0 0 0 0+0=0 0 0 0 1 0 0+0=0 1 1 0 11 11+0=11* 11 1 0 2 0 0+0=0 1 1 11 11+0=11 2 2 0 30 30+0=30* 30 2 0 3 0 0+0=0 1 2 11 11+0=11 2 1 30 30+0=30 3 3 0 45 45+0=45* 45 3 0 4 0 0

6、+0=0 1 3 11 11+0=11 2 2 30 30+0=30 3 1 45 45+0=45 4 4 0 58 58+0=58* 58 4 k=3k=3，0d0d3 3xx3 3，x x4 4=x=x3 3-d-d3 3k=2k=2，0d0d2 2xx2 2，x x3 3=x=x2 2-d-d2 2k=1k=1，0d0d1 1xx1 1，x x2 2=x=x1 1-d-d1 1最优解为最优解为x1=4, d1*=1, x2=x1-d1=3, d2*=0, x3=x2-d2*=3, d3=3, x4=x3-d3=0，即项目即项目A投资投资1万元，项目万元，项目B投资投资0万元，项目万元，项

7、目C投资投资3万元，最大效益为万元，最大效益为60万吨。万吨。 作业作业 某公司有资金某公司有资金8万元，投资万元，投资A、B、C三个项三个项目，单位投资为目，单位投资为2万元。每个项目的投资效益率与万元。每个项目的投资效益率与投入项目的资金有关。三个项目投入项目的资金有关。三个项目A、B、C的投资的投资效益（万吨）和投入资金（万元）关系见下表：效益（万吨）和投入资金（万元）关系见下表： 项目投入资金 A B C 2 万元 8 万吨 9 万吨 10 万吨 4 万元 15 万吨 20 万吨 28 万吨 6 万元 30 万吨 35 万吨 35 万吨 8 万元 38 万吨 40 万吨 43 万吨 求

8、对三个项目的最优投资分配，使总投资效求对三个项目的最优投资分配，使总投资效益最大。益最大。（二）机器负荷分配问题（二）机器负荷分配问题 例例3 3 某种机器可以在高、低两种负荷下运行。在高某种机器可以在高、低两种负荷下运行。在高负荷条件下运行时，机器完好率为负荷条件下运行时，机器完好率为0.70.7，即如果年初，即如果年初有有u u台完好机器投入运行，则年末时完好机器的数量台完好机器投入运行，则年末时完好机器的数量为为0.7u0.7u台，产量台，产量8 8吨吨/ /台；在低负荷下运行时，机器台；在低负荷下运行时，机器完好率为完好率为0.90.9，产量，产量5 5吨吨/ /台。设开始时有台。设开

9、始时有10001000台完台完好机器，要制订五年计划，每年年初将完好的机器好机器，要制订五年计划，每年年初将完好的机器一部分分配到高负荷运行，剩下的机器分配到低负一部分分配到高负荷运行，剩下的机器分配到低负荷运行，如何分配生产使五年的总产量为最高。荷运行，如何分配生产使五年的总产量为最高。 第第1年年s1s2s3x1x2x3第第2年年第第3年年第第4年年第第5年年s4s5s6x4x5指标值指标值(产量产量)V1(s1,x1)指标值指标值(产量产量)V2(s2,x2)指标值指标值(产量产量)V5(s5,x5)指标值指标值(产量产量)V4(s4,x4)指标值指标值(产量产量)V3(s3,x3)动态

10、规划模型构造动态规划模型构造阶段阶段k： 运行年份（运行年份（k=1,2,3,4,5）；）；状 态 变 量状 态 变 量 sk： 第第 k 年 初 完 好 的 机 器 数年 初 完 好 的 机 器 数（k=1,2,3,4,5）；）；决策变量决策变量xk： 第第k年投入高负荷运行的机器数；年投入高负荷运行的机器数；状态转移方程：状态转移方程：sk+1=0.7xk+0.9(sk-xk)决策允许集合：决策允许集合：Dk(sk)=xk|0 xk sk阶段指标：阶段指标： vk(sk,xk)=8xk+5(sk-xk)终端条件：终端条件： f6(s6)=0递推方程：递推方程： fk(sk)=maxvk(s

11、k,xk)+fk+1(sk+1) 0 xk sk=max8xk+5(sk-xk)+fk+10.7xk+0.9(sk-xk) 0 xk sk555sx066555sx055853xmax )(sf)x5(s8xmax)(sf5555ss5*5sx 第第5年年s5s6x5指标值指标值(产量产量)V5(s5,x5)+f6(s6)4444444444444550 xs44450 xs4444440 xs4440 xsf (s )max 8x5(sx )f (s ) max 8x5(sx )8s max 8x5(sx )80.7x0.9(sx ) max 1.4x12.2s13.6s4*4sx 第第4年

12、年s4s5x4指标值指标值(产量产量)V4(s4,x4)+f5(s5)f3(s3)=max8x3+5(s3-x3)+f4(s4)0 x3 3 s3 3 =max8x =max8x3 3+5(s+5(s3 3-x-x3 3)+13.6s)+13.6s4 4 0 x3 s3 =max8d =max8d3 3+5(s+5(s3 3-d-d3 3)+13.60.7d)+13.60.7d3 3+0.9(s+0.9(s3 3-d-d3 3) 0 x3 s3 =max0.28x =max0.28x3 3+17.24s+17.24s3 3=17.52s=17.52s3 3 0 x3 s3 x x3 3* *=

13、s=s3 3s3x3第第3年年s4指标值指标值(产量产量)V3(s3,x3)+f4(s4)f2(s2)=max8x2+5(s2-x2)+f3(s3) 0 x2 2 s2 2 =max8x =max8x2 2+5(s+5(s2 2-x-x2 2)+17.52s)+17.52s3 3 0 0 x2 2 s2 2 =max8x =max8x2 2+5(s+5(s2 2-x-x2 2)+17.520.7x)+17.520.7x2 2+0.9(s+0.9(s2 2-x-x2 2)0 0 x2 2 s2 2 =max-0.504x =max-0.504x2 2+20.77s+20.77s2 2=20.77

14、s=20.77s2 20 0 x2 2 s2 2x x2 2* *=0=0s2s3x2第第2年年指标值指标值(产量产量)V2(s2,x2)+f3(s3)f1(s1)=max8x1+5(s1-x1)+f2(s2)0 x1 1 s1 1 =max8x =max8x1 1+5(s+5(s1 1-x-x1 1)+20.77s)+20.77s2 2 0 0 x1 1 s1 1 =max8x =max8x1 1+5(s+5(s1 1-x-x1 1)+20.770.7x)+20.770.7x1 1+0.9(s+0.9(s1 1-x-x1 1)0 0 x1 1 s1 1 =max-0.05x =max-0.0

15、5x1 1+23.69s+23.69s1 1=23.69s=23.69s1 10 0 x1 1 s1 1x x1 1* *=0=0第第1年年s1s2x1指标值指标值(产量产量)V1(s1,x1)+f2(s2)由此可以得到：由此可以得到：f1(s1)=23.69s1,x1*=0f2(s2)=20.77s2,x2*=0f3(s3)=17.52s3,x3*=s3f4(s4)=13.60s4,x4*=s4f5(s5)=8s5x5*=s5用用s1=1000代入，得到五年最大产量为代入，得到五年最大产量为f1(s1)=f1(1000)=23690每年投入高负荷运行的机器数以及每年初完好的机每年投入高负荷运

16、行的机器数以及每年初完好的机器数为：器数为：s1=1000 x1*=0,s2=0.7x1+0.9(s1-x1)=900 x2*=0,s3=0.7x2+0.9(s2-x2)=810 x3*=s3=810,s4=0.7x3+0.9(s3-x3)=567x4*=s4=567,s5=0.7x4+0.9(s4-x4)=397x5*=s5=397,s6=0.7x5+0.9(s5-x5)=278 该例题对该例题对S6没有限制，有时会对最后一年年末没有限制，有时会对最后一年年末完好设备数施以约束，例如完好设备数施以约束，例如S6=300。5555555()| 0.70.9()300,0D SXXSXX即即 下

17、面数需重新算下面数需重新算5504.51500XS 从上题计算结果可以看出从上题计算结果可以看出：前两年低负荷运行，：前两年低负荷运行，后三年高负荷运行。是否有这样的规律，后三年高负荷运行。是否有这样的规律，n年的生年的生产计划，总是前产计划，总是前1t-1年底负荷运行，年底负荷运行，tn年高负荷年高负荷运行。运行。这时决策变量这时决策变量x5的决策允许集合为：的决策允许集合为：则最优设备分配策略是则最优设备分配策略是：从：从1至至t-1年，年初将全年，年初将全部完好设备投入低负荷运行，从部完好设备投入低负荷运行，从t至至n年，年初将年，年初将全部完好设备投入高负荷运行，总产量达到最大。全部完

18、好设备投入高负荷运行，总产量达到最大。条件：条件：g(x)、h(x)为线性函数，且为线性函数，且g(0)=h(0)=0。一般地，设一个周期为一般地，设一个周期为n年，年，高负荷生产时设备的完好率为高负荷生产时设备的完好率为a，单台产量为，单台产量为g；低负荷生产时设备的完好率为低负荷生产时设备的完好率为b，单台产量为，单台产量为h;100()n tn tiiiighaag ba 计算计算t： 某公司有某公司有1000辆运输卡车，在超负荷运输（即每辆运输卡车，在超负荷运输（即每天满载行驶天满载行驶500km以上）情况下，年利润为以上）情况下，年利润为25万元万元/辆，这时卡车的年损坏率为辆，这时

19、卡车的年损坏率为0.3；在低负荷下运输；在低负荷下运输（即每天行驶（即每天行驶300km以下）情况下，年利润为以下）情况下，年利润为16万万元元/辆。年损坏率为辆。年损坏率为0.1。现要制定一个。现要制定一个5年计划，问年计划，问每年年初应如何分配完好车辆在两种不同的负荷下每年年初应如何分配完好车辆在两种不同的负荷下运输的卡车数量，使在第运输的卡车数量，使在第5年年末剩余的完好卡车年年末剩余的完好卡车数量为数量为500台，并且使在台，并且使在5年内的总利润最大？年内的总利润最大？习题习题1：第二节第二节 生产与存储问题生产与存储问题 在生产和经营管理中，经常会遇到要合理在生产和经营管理中，经常

20、会遇到要合理地安排生产地安排生产(或购买或购买)与库存的问题，达到既要与库存的问题，达到既要满足社会的需要，又要尽量降低成本费用。因满足社会的需要，又要尽量降低成本费用。因此，正确制定生产（采购）策略，确定不同时此，正确制定生产（采购）策略，确定不同时期的生产量（或采购量）和库存量，以使总的期的生产量（或采购量）和库存量，以使总的生产成本费用和库存费用之和最小，这就是生生产成本费用和库存费用之和最小，这就是生产和存储问题的目标。产和存储问题的目标。第三节第三节 背包问题背包问题 有一个徒步旅行者，其可携带物品重量的限度为有一个徒步旅行者，其可携带物品重量的限度为w 公公斤，有斤，有n 种物品可

21、供他选择装入包中。已知每种物品的种物品可供他选择装入包中。已知每种物品的重量及使用价值（作用），问此人应如何选择携带的重量及使用价值（作用），问此人应如何选择携带的物品（各几件），使所起作用（使用价值）最大？物品（各几件），使所起作用（使用价值）最大？物品物品 1 2 i n重量（公斤重量（公斤/ /件）件） w1 w2 wi wn使用价值使用价值 c1 c2 ci cn 这就是背包问题。类似的还有运输中的货物装载问这就是背包问题。类似的还有运输中的货物装载问题、人造卫星内的物品装载问题等。题、人造卫星内的物品装载问题等。设设x xi i 为第为第i i 种物品的装件数（非负整数）则问题的数种

22、物品的装件数（非负整数）则问题的数学模型如下：学模型如下：1max()10(1.2.)且 为 整 数niiiiZcxniiixinw xw例题：求下面背包问题的最优解例题：求下面背包问题的最优解123123123max60406032510,0Zxxxxxxx xx且为整数物品物品 1 2 3重量（公斤）重量（公斤） 3 2 5使用价值使用价值 60 40 60例例1 有一辆最大货运量为有一辆最大货运量为10 t 的卡车，用以装载的卡车，用以装载3种种货物，每种货物的单位重量及相应单位价值如表所示。货物，每种货物的单位重量及相应单位价值如表所示。应如何装载可使总价值最大？应如何装载可使总价值最

23、大？分析：分析：状态转移方程状态转移方程：s sk+1k+1=s=sk k-w-wk k* *x xk k物品物品1 13x1s2状态s1v1(s1,u1)=60 x1物品物品2 22x2S3v2(s2,u2)=40 x2物品物品3 35x3S4v3(s3,u3)=60 x3阶段阶段k k： 物品（物品（k=3,2,1k=3,2,1）；）；状态变量状态变量s sk k：从第从第k k种物品到第种物品到第3 3种物品可载重量；种物品可载重量；决策变量决策变量x xk k：装第装第k k种物品数量种物品数量; ;决策允许集合：决策允许集合：D Dk k(s(sk k)=x)=xk k|0|0 x

24、xk k s sk k/w/wk k阶段指标：阶段指标：v vk k(s(sk k,x,xk k)=c)=ck k* *x xk k递推方程递推方程：f fk k(s(sk k)=maxc)=maxck k* *x xk k+f+fk+1k+1(s(sk+1k+1)边界条件边界条件：f f4 4(s(s4 4)=0)=0解：终端条件：解：终端条件：f4(s4)=0k=3时，递推方程为时，递推方程为3333333443005()max()max60ssxxwfsc xfsxs3D3(s3)s460 x3+f4(s4)f3(s3)X*3解：终端条件：解：终端条件：f4(s4)=0k=3时，递推方程为时，递推方程为3333333443005()max()max60ssxxwfsc xfsxs3D3(s3)s460 x3+f4(s4)f3(s3)X*30000+0=0001010+0=000501500+0=060+0=606011001210500+0=060+0=60120+0=1201202k=2时，递推方程为时，递推方程为22222223