动态规划在投资分配问题中的应用.ppt

《动态规划在投资分配问题中的应用.ppt》由会员分享，可在线阅读，更多相关《动态规划在投资分配问题中的应用.ppt（16页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、动态规划在投资分配问题中的应用人员分工 1项目简介撰写报告XX2Matlab仿真PPT制作XX3材料收集模型设计XX问题描述小结问题求解和仿真问题分析目录目录问题描述目录项目简介小结问题求解和仿真问题分析4问题描述股票A股（万元）B股（万元）C股（万元）投入资金/百万元00001606575280851003105110120411514013551301601506150175180假设某公司投入股市600万元的资金给4只股票,各只股票所得到的利润与投资金额大小的关系如下表。试问应如何分配投资的资金才能使总利润最大？问题分析目录项目简介问题描述小结问题求解和仿真问题分析首先我们对资金的分配规

2、定一个顺序：A股票B股票C股票将问题按分配过程分为三个阶段，根据动态规划逆序算法，可设：fk(xk)表示将资金xk分配到第k只股票所得到的最大收益值，因而可得出递推方程：阶段数k=1，2，3（即A、B、C三只股票的编号分别为1，2，3）；状态变量xk表示分配给第k只股票至第3只股票的资金数（即第k阶段初尚未分配的资金数）；决策变量uk表示分配给第k只股票的资金数；状态转移方程：xk+1=xk-uk;gk(uk)表示uk百万元分配到第k只股票所得的收益值，它由上表可查得；问题求解和仿真目录项目简介问题描述小结问题分析问题求解和仿真k=3时，股票C的分配方案和总收益。最大收益：u30123456最

3、优决策u3*最有总收益f3x3000010751752075100210030751001203120407510012013541355075100120135150515060751001201351501806180u20123456最优决策u2*最有总收益f2x2000017565065210014085114031201651601101165413518518518514011855150200205210215160421561802152202302402351754240问题求解和仿真k=2时，股票B的分配方案和总收益。最大收益：问题求解和仿真k=1时，股票A的分配方案和总收

4、益。最大收益：u10123456最优决策u2*最有总收益f2x1=62402752652702552702751275故最优方案是：投资A股票100万，B股票400万，C股票100万。总利润为275万元。问题求解和仿真动态规划流程框图m=1;A=0 60 80 105 115 130 150;B=0 65 85 110 140 160 175;C=0 75 100 120 135 150 180;for i=1:7 for j=1:7 for k=1:7 if i+j+k=9 d(m)=A(i)+B(j)+C(k);E(m,1)=i;E(m,2)=j;E(m,3)=k;m=m+1;else c

5、ontinue;end end endendMAXNum=d(1);for l=1:size(d,2)if d(l)MAXNum MAXNum=d(l);p=l;else continue;endendfor l=1:size(d,2)if d(l)=MAXNum E(l,:)else continue;endendMAXNum本例matlab代码运行结果以容易得到最大利润为275，最优分配方案为：（1，4，1）小结目录项目简介问题描述问题求解和仿真问题分析小结算法时间复杂度优点缺点改进方法动态规划O(minnc,2n)可求得最优决策序列速度较慢建立动态规划递归方程回溯法能够获得最优解时间复杂

6、度较高判断右子树时，按效率密度vi/wi对剩余对象排序分枝-限界法O(2n)速度较快，易求解占用的内存较大，效率不高最大收益或最小消耗分枝-限界法，FIFO法贪心算法O(nlogn)可以达到局部最优解，用时少不能考虑到整体最优解，程序可读性低于动态规划对范围广的问题可以产生接近的最优解查阅文献发现，对于求解本例，将动态规划算法与其他其他算法进行比较，各算法的时间复杂度，以及改进方法如下：各有的优缺点其它注意事项以及经验小结当股票只数很多,或投资分配的单位比较小时,计算工作量就很大,这时必须利用计算机来帮助完成。动态规划在资源分配中已经被广泛应用，这说明动态规划是在解决资源分配这类问题的有效方法。各种算法设计方法有各自不同的特点，针对不同的问题领域，它们有不同的效率和优缺点，因此要注意“对症下药”，对具体问题进行具体分析。15谢谢！