运筹学动态规划应用举例.ppt

《运筹学动态规划应用举例.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第七章动态规划多阶段决策过程的最优化动态规划的基本概念和基本原理动态规划模型的建立与求解动态规划在经济管理中的应用第四节动态规划在经济管理中的应用连续变量的离散化解法先介绍连续变量离散化的概念。如投资分配问题的一般静态模型为：模型中：阶段数、总投资、各阶段投资数、各阶段收益、决策变量、状态变量状态转移方程、基本方程、指标函数、最优指标函数建立它的动态规划模型，其基本方程为：其状态转移方程为:由于与都是连续变量，当各阶段指标没有特殊性而较为复杂时，要求出会比较困难，因而求全过程的最优策略也就相当不容易，这时常常采用把

2、连续变量离散化的办法求其数值解。具体做法如下：（1）令，把区间[0，a]进行分割，的大小可依据问题所要求的精度以及计算机的容量来定。(2)规定状态变量及决策变量只在离散点上取值，相应的指标函数就被定义在这些离散值上，于是递推方程就变为：其中作为离散化例子，在例5中规定状态变量和决策变量只在给出的离散点上取值，见例6。（3）按逆序方法，逐步递推求出，最后求出最优资金分配方案。问如何分配投资数额才能使总效益最大?例5某公司有资金10万元，若投资于项目i(i=1,2,3)的投资额为xi时，其效益分别为：例6连续变量的离散

3、化解法解令，将区间[0，10]分割成0，2，4，6，8，10六个点，即状态变量集合为允许决策集合为，与均在分割点上取值。动态规划基本方程为：当k=3时，式中与的集合均为：计算结果见表7-1。02468100832721282000246810当k=3时，表7-1当k=2时，计算结果见表7-2。02468100020240246024680246810081832263672504454128906862722001461088680900183672128200024000表7-2当k=1时，计算结果见表7-3。表

4、7-31010101010100246810200136886050402000最大收益为，与例5结论完全相同。计算结果表明，最优决策为：应指出的是：这种方法有可能丢失最优解，一般得到原问题的近似解。一、背包问题一位旅行者携带背包去登山，已知他所能承受的背包重量限度为akg，现有n种物品可供他选择装入背包，第i种物品的单件重量为aikg，其价值是携带数量xi的函数ci(xi)(i=1,2,…,n)，问旅行者应如何选择携带各种物品的件数，以使总价值最大？例1有一辆最大货运量为10t的卡车，用以装载3种货物，每种货物的

5、单位重量及相应单位价值见下表，应如何装载可使总价值最大？货物编号i123单位重量(t)345单位价值ci456逆序解法：阶段k：k=1,2,3状态变量sk:第k阶段可以装载第k种到第3种货物的重量。决策变量xk:决定装载第k种货物的数量。状态转移方程:sk+1=sk-akxk最优指标函数fk(sk):当可装载重量为sk,装载第k种到第3种货物所获得的最大价值。基本方程：当阶段k=3时，有s3012345678910x3000000101010101012c3+f40000006060606060612f300000

6、6666612x3*00000111112当阶段k=2时，有s2012345678910x2000001010101012012012c2+f3000005+0656565651065+610125+610f200005666101112x2*00001000210当阶段k=1时，有s110x10123c1+f3124+68+512f213x1*2二、生产经营问题在生产和经营管理中，经常遇到如何合理地安排生产计划、采购计划以及仓库的存货计划和销售计划，使总效益最高的问题。下面通过例子来说明对不同特点问题的不同处理技

7、巧。例2生产与存贮问题某工厂生产并销售某种产品，已知今后四个月市场需求预测如表，又每月生产j单位产品费用为：每月库存j单位产品的费用为，该厂最大库存容量为3单位，每月最大生产能力为6单位，计划开始和计划期末库存量都是零。试制定四个月的生产计划，在满足用户需求条件下总费用最小。假设第i+1个月的库存量是第i个月可销售量与该月用户需求量之差；而第i个月的可销售量是本月初库存量与产量之和。12342324用动态规划方法求解时，对有关概念作如下分析：(1)阶段：每个月为一个阶段，k＝1，2，3，4。(2)状态变量：为第k个

8、月初的库存量。(3)决策变量：为第k个月的生产量。(4)状态转移方程：(5)最优指标函数：表示第k月状态为时，采取最佳策略生产，从本月到计划结束(第4月末)的生产与存贮最低费用。（6）基本方程：k＝4，s5=s4+u4-g4=0，所以u4=g4-s4=4-s4，s4可取0，1，2，3。s40123u44321C+E+f576+0.55+14+1.5f476.