运筹学74动态规划应用举例

《运筹学74动态规划应用举例》由会员分享，可在线阅读，更多相关《运筹学74动态规划应用举例（59页珍藏版）》请在文档大全上搜索。

1、第七章第七章 动态规划动态规划 n多阶段决策过程的最优化多阶段决策过程的最优化n动态规划的基本概念和基本原理动态规划的基本概念和基本原理 n动态规划模型的建立与求解动态规划模型的建立与求解n动态规划在经济管理中的应用动态规划在经济管理中的应用 第四节第四节 动态规划在经济管理中的应用动态规划在经济管理中的应用 连续变量的离散化解法连续变量的离散化解法 先介绍连续变量离散化的概念。如投资分配问题先介绍连续变量离散化的概念。如投资分配问题的一般静态模型为：的一般静态模型为： niiixgz1)(max), 2 , 1(01nixaxinii模型中：阶段数、总投资、各阶段投资数、各阶段收益、决策变量

2、、状模型中：阶段数、总投资、各阶段投资数、各阶段收益、决策变量、状态变量态变量 状态转移方程、基本方程、指标函数、最优指标函数状态转移方程、基本方程、指标函数、最优指标函数建立它的动态规划模型，其基本方程为：建立它的动态规划模型，其基本方程为：0)(1 ,2, 1,)()(max)(11110nnkkkksxkksfnnksfxgsfkk其状态转移方程为其状态转移方程为: :kkkxss1 由于由于 与与 都是连续变量，当各阶段指标都是连续变量，当各阶段指标 没没有特殊性而较为复杂时，有特殊性而较为复杂时， 要求出要求出 会比较困难，因而求会比较困难，因而求全过程的最优策略也就相当不容易，这时

3、常常采用把连续变量全过程的最优策略也就相当不容易，这时常常采用把连续变量离散化的办法求其数值解。具体做法如下：离散化的办法求其数值解。具体做法如下： kskx)(kkxg)(kksf（1 1） 令令 ，把区间把区间 0 0，aa进行分割，进行分割， 的大小可的大小可依据问题所要求的精度以及计算机的容依据问题所要求的精度以及计算机的容量来定。量来定。 amsk,2,0 (2) (2) 规定状态变量规定状态变量 及决策变量及决策变量 只在离散点只在离散点 上取值，相应的指标上取值，相应的指标函数函数 就被定义在这些离散值上，于是递推方就被定义在这些离散值上，于是递推方程就变为：程就变为： kskx

4、am,2,0)(kksf0)()()(max)(111,2, 1 ,0nnkkkqpkksfpsfpgsf其中其中 pxsqkk, 作为离散化例子，在例作为离散化例子，在例5 5中规定状态变量和决中规定状态变量和决策变量只在给出的离散点上取值，见例策变量只在给出的离散点上取值，见例6 6。 （ 3 3 ） 按 逆 序 方 法 ， 逐 步 递 推 求按 逆 序 方 法 ， 逐 步 递 推 求出出 ，最后求出最，最后求出最优资金分配方案。优资金分配方案。)(,),(11sfsfnn问如何分配投资数额才能使总效益最大问如何分配投资数额才能使总效益最大? ?23332221112)(,9)(,4)(x

5、xgxxgxxg例例5 5 某公司有资金某公司有资金1010万元，若投资于项目万元，若投资于项目i(i=1,2,3)i(i=1,2,3)的投资额为的投资额为x xi i时，其效益分别为：时，其效益分别为： 例例6 6 连续变量的离散化解法连续变量的离散化解法)3,2, 1(,010.294max3212321ixxxxtsxxxZi解解 令令 ，将区间，将区间00，1010分割成分割成0 0，2 2，4 4，6 6，8 8，1010六个点，即状态变量六个点，即状态变量 集合为集合为 2ks10,8,6,4,2,0允许允许决策集合为决策集合为 ， 与与 均在分割点上取值。均在分割点上取值。 kk

6、sx0kxks动态规划基本方程为：动态规划基本方程为： 0)(1 ,2, 3)()(max)(4410sfkxsfxgsfkkkkksxkkkk当当k=3k=3时，时， 230332max)(33xsxsf式中式中 与与 的集合均为：的集合均为： 计算结果见表计算结果见表7-17-1。 3s3x10,8,6,4,2,03s)(33sf*3x02468100832721282000246810当当k=3时，时， 表表7-1 230332max)(33xsxsf当当k=2时，时， )(9max)(223202222xsfxsfsx0)(1 , 2 , 3)()(max)(4410sfkxsfxgs

7、fkkkkksxkkkk计算结果见表计算结果见表7-27-2。 2s2x32fg 2f*2x024681000 20 2 40 2 4 60 2 4 6 80 2 4 6 8 1008 1832 26 3672 50 44 54128 90 68 62 72200 146 108 86 80 900 18 36 72 128 2000 24 0 0 0表表7-2 7-2 当当k=1时，时， 0)(1 , 2 , 3)()(max)(4410sfkxsfxgsfkkkkksxkkkk计算结果见表计算结果见表7-37-3。 表表7-3 )(4max)(1121100111xsfxsfx1s1x21

8、fg 1f*1x 10 101010 10100246810200136886050402000最大收益为最大收益为 ，与例，与例5 5结论完全相同。结论完全相同。 10, 0, 0*3*2*1xxx200)10(1f计算结果表明，最优决策为：计算结果表明，最优决策为： 应指出的是：这种方法有可能丢失最优解，应指出的是：这种方法有可能丢失最优解，一般得到原问题的近似解。一般得到原问题的近似解。 一、背包问题一、背包问题 一位旅行者携带背包去登山，已知他所能承受的背包重一位旅行者携带背包去登山，已知他所能承受的背包重量限度为量限度为a kg，现有，现有n种物品可供他选择装入背包，第种物品可供他选

9、择装入背包，第i种种物品的单件重量为物品的单件重量为ai kg，其价值是携带数量，其价值是携带数量xi的函数的函数ci(xi)(i=1,2,n)，问旅行者应如何选择携带各种物品的件，问旅行者应如何选择携带各种物品的件数，以使总价值最大？数，以使总价值最大？ ), 2 , 1(0)(max11nixaxaxcziniiiniii且为整数例例1 有一辆最大货运量为有一辆最大货运量为10t的卡车，用以装载的卡车，用以装载3种货物，种货物，每种货物的单位重量及相应单位价值见下表，应如何装载可每种货物的单位重量及相应单位价值见下表，应如何装载可使总价值最大？使总价值最大？ ) 3 , 2 , 1(010

10、543654max321321ixxxxxxxzi且为整数货物编号i123单位重量(t)345单位价值ci456逆序解法：逆序解法：阶段阶段k： k=1,2,3状态变量状态变量sk:第第k阶段可以装载第阶段可以装载第k种到第种到第3种货物的重量。种货物的重量。决策变量决策变量xk:决定装载第决定装载第k种货物的数量。种货物的数量。状态转移方程状态转移方程:sk+1=sk-akxk最优指标函数最优指标函数fk(sk):当可装载重量为当可装载重量为sk,装载第装载第k种到第种到第3种货物所获得的种货物所获得的最大价值。最大价值。基本方程：基本方程：0)(1 , 2 , 3)()(max)(4411

11、/ , 1 , 0sfksfxcsfkkkkasxkkkkk当阶段当阶段k=3时，有时，有6max)(35/, 03333xsfsxs3012345678910 x3000000 10 10 10 10 10 1 2c3+f4000000 60 60 60 60 60 6 12f3000006666612x3*00000111112当阶段当阶段k=2时，有时，有)(5max)(3324/, 02222sfxsfsx s2012345678910 x200000 10 10 10 10 1 20 1 20 1 2c2+f300000 5+06 56 56 56 5 106 5+6 1012 5+