动态规划(2).ppt

文档介绍：动态规划(2)
应用举例
1、建立动态规划模型的一般步骤
1 划分阶段。即按时间和空间的先后顺序适当地划分为满足递推关系的若干个阶段。
2 正确选择状态变量。(可知性和无后效性)
3 根据状态变量和决策变量的含义,正确写出状态转移方程
Sk+1=Tk(sk,uk)
4 、最优指标函数fk(sk)及k阶段指标Vk(sk,us)的含义。
5 正确列出最优指标函数的递推关系及边界条件。
2、资源分配问题
所谓分配问题,就是将数量一定的一种或若干种资源(例如原材料,资金,机器设备,劳力,食品等等),恰当地分配给若干个使用者,使效益函数为最优。
资源分配
离
散
连
续
(1)资源离散分配问题
多元投资分配问题
设有某种原料,总数量为a,用于生产n种产品。若分配数量xi用于生产第i种产品,其收益为gi(xi),问应如何分配,才能使生产n种产品的总收入最大?
静态规划
建立动态规划模型
1、决策变量dk表示分配给生产第k种产品的原料数量,dk=xk;
2、设状态变量sk表示为分配给用于生产第k种产品至第n种产品的原料数量;
3、状态转移方程: sk+1=sk-uk=sk-xk
4、决策集合:Dk(sk)={uk|0uk=xksk}
5、最优值函数fk(sk)表示以数量为sk的原料分配给第k种产品至第n种产品所得到的最大总收益,动态规划的递推关系为:
例1:某公司有资金10万元,若投资于项目i(i=1,2,3)的投资额为xi时,其效益分别为
问如何分配投资数额才能使总效益最大
解:可列出静态规划问题的模型如下
应用动态规划求解:
1、分阶段:考虑效益函数的形式,分为三个阶段,即k=1,2,3。
2、确定决策变量dk:通常可以取静态规划中的变量为决策变量,即决
定给第 k个项目投资的资金数。
确定状态变量S k:状态变量与决策变量有密切关系,状态变量一般为累计量或随递推过程变化的量。既第k阶段可以投资于第k项到第3项目的资金数量。
应用动态规划求解:
1、分阶段:考虑效益函数的形式,分为三个阶段,k=1,2,3
2、确定决策变量dk:通常可以取静态规划中的变量为决策变量,即决定给第 k个项目投资的资金数。
3、确定状态变量sk:状态变量与决策变量有密切关系,状态变量一般为累计量或随递推过程变化的量。既第k阶段可以投资于第k项到最后项(第3项目)的资金数量。
4、状态转移方程:Sk+1=sk-xk
5、指标函数
6、最优指标函数fk(sk):当可投资金额为sk时,投资第k项到第3项所得的最大收益数。基本方程为:
解算:
1、当阶段k=3时,有
最优决策为:
最优目标函数: