![点击分享此内容可以赚币 分享](/master/images/share_but.png)
一般数学模型的动态规划解法.pptx
《一般数学模型的动态规划解法.pptx》由会员分享,可在线阅读,更多相关《一般数学模型的动态规划解法.pptx(27页珍藏版)》请在咨信网上搜索。
1、 安徽科技学院安徽科技学院 运筹与优化运筹与优化例例1 某公司有资金某公司有资金10万元,若投资于项目万元,若投资于项目i(i=1,2,3)的投的投资额为资额为xi时,其收益分别为时,其收益分别为g1(x1)=4x1,g2(x2)=9x2,g3(x3)=2x32,问应如何分配投资数额才能使总收益最大?问应如何分配投资数额才能使总收益最大?一、非线性规划问题的动态规划解法一、非线性规划问题的动态规划解法 解解 静态规划模型:静态规划模型:第四节第四节 一般数学模型的动态规划解法一般数学模型的动态规划解法1.连续变量的一般解法连续变量的一般解法 安徽科技学院安徽科技学院 运筹与优化运筹与优化为了应
2、用动态规划方法求解,人为地赋予它为了应用动态规划方法求解,人为地赋予它“时段时段”的概念,将投资项目排序,首先考虑对项目的概念,将投资项目排序,首先考虑对项目1投资,投资,然后考虑对项目然后考虑对项目2投资投资,即把问题划分为,即把问题划分为3个阶个阶段,每个阶段只决定对一个项目应投资的金额。段,每个阶段只决定对一个项目应投资的金额。通常把决策变量通常把决策变量uk定为原静态规划的变量定为原静态规划的变量xk即设即设状态变量和决策变量有密切关系,状态变量一般状态变量和决策变量有密切关系,状态变量一般为累计量或随递推过程变化的量。为累计量或随递推过程变化的量。可把每阶段可供使用的资金定为状态变量
3、可把每阶段可供使用的资金定为状态变量sk,初始,初始状态为状态为s1=10 安徽科技学院安徽科技学院 运筹与优化运筹与优化u1为可分配用于第一种项目的最大资金,则第一阶为可分配用于第一种项目的最大资金,则第一阶段时有:段时有:第二阶段第二阶段(k=2)时,状态变量时,状态变量s2为余下可投资于其为余下可投资于其余两个项目的资金,即:余两个项目的资金,即:一般地,当第一般地,当第k段时段时 安徽科技学院安徽科技学院 运筹与优化运筹与优化于是有于是有状态变量状态变量sk:第第k阶段可以投资于第阶段可以投资于第k项到第项到第3个项目个项目的资金的资金决策变量决策变量xk:决定给第决定给第k项目的资金
4、项目的资金状态转移方程:状态转移方程:sk+1=sk-uk指标函数:指标函数:最优指标函数最优指标函数fk(sk):当可投资金为当可投资金为sk时,投资第时,投资第k-3项所得最大收益。基本方程为:项所得最大收益。基本方程为:安徽科技学院安徽科技学院 运筹与优化运筹与优化0ss2x2当当k=2时,时,这是一个函数求极值问这是一个函数求极值问题题,利用微分方法可求得利用微分方法可求得该函数有极小值该函数有极小值.当当k=3时,时,显然当显然当,函数取极大值为,函数取极大值为 安徽科技学院安徽科技学院 运筹与优化运筹与优化要讨论要讨论s2的具体情况的具体情况:当当 时,时,当当 时,时,此时此时此
5、时此时到此,第二阶段的决策已经作出到此,第二阶段的决策已经作出 安徽科技学院安徽科技学院 运筹与优化运筹与优化减函数减函数此结论与前矛盾,故舍去此结论与前矛盾,故舍去当当k=1时,时,时时注:此时注:此时由前面分析可知由前面分析可知而而 安徽科技学院安徽科技学院 运筹与优化运筹与优化另取另取此时此时又是一个求极值问题,微分求解又是一个求极值问题,微分求解比较比较0,10的端点的端点当当 时,时,当当 时,时,再由递推方程递推:再由递推方程递推:最优方案为全部资金投到第三个项目最优方案为全部资金投到第三个项目 安徽科技学院安徽科技学院 运筹与优化运筹与优化2.连续变量的离散化解法连续变量的离散化
6、解法:例如投资分配问题例如投资分配问题的一般静态模型为:的一般静态模型为:建立它的动态规划模型,其基本方程为:建立它的动态规划模型,其基本方程为:其状态转移方程为:其状态转移方程为:sk+1=sk-xk 安徽科技学院安徽科技学院 运筹与优化运筹与优化 由于由于sk与与xk都是连续变量,当各阶段指标都是连续变量,当各阶段指标gk(xk),没有特没有特殊性质而较为复杂时,要求出殊性质而较为复杂时,要求出fk(sk)比较困难,因而求全过程比较困难,因而求全过程的最优策略也就相当不容易,这时常常采用把连续变量离的最优策略也就相当不容易,这时常常采用把连续变量离散化的方法求其数值解,具体做法如下:散化的
7、方法求其数值解,具体做法如下:(1)令)令sk=0,2,m=a,把区间把区间0,a进行分割,进行分割,的的大小可依据问题所要求的精度及计算机的容量来定。大小可依据问题所要求的精度及计算机的容量来定。(2)规定状态变量)规定状态变量sk及决策变量及决策变量xk只在离散的点只在离散的点0,2,m上取值,相应的指标函数上取值,相应的指标函数fk(sk)就被定义在这些离散值上,就被定义在这些离散值上,于是递推方程变为:于是递推方程变为:其中其中 安徽科技学院安徽科技学院 运筹与优化运筹与优化(3)按逆序方法,逐步递推求出)按逆序方法,逐步递推求出fn(sn),f1(s1),最后求出,最后求出最优资金分
8、配方案。最优资金分配方案。例例2 用连续变量的离散化求解用连续变量的离散化求解解解 令令 ,将区间,将区间0,10分割成分割成0,2,6,8,10六个点,即状六个点,即状态变量态变量sk集合为集合为0,2,4,6,8,10允许决策集合为允许决策集合为 均在分割点上取值。均在分割点上取值。安徽科技学院安徽科技学院 运筹与优化运筹与优化动态规划基本方程为:动态规划基本方程为:当当k=3时,时,其中其中s3和和x3的集合均为的集合均为0,2,4,6,8,10,计算结果如下表计算结果如下表s30246810f3(s3)083272128200 x3*0246810 安徽科技学院安徽科技学院 运筹与优化
9、运筹与优化计算结果如下表计算结果如下表s20246810 x200 20 2 40 2 4 60 2 4 6 80 2 4 6 8 10g2+f30 8 1832 26 3672 50 44 54128 90 68 62 72200 146 108 86 80 90f20183672128200 x2*024000当当k=2时,时,计算结果如下表计算结果如下表s110 x10246810g1+f220013688605040f1200 x1*0当当k=1时,时,安徽科技学院安徽科技学院 运筹与优化运筹与优化计算结果表明,最优决策为:计算结果表明,最优决策为:最大收益为:最大收益为:与例与例5结
10、论完全相同。结论完全相同。注意:这种方法有可能丢失最优解,一般得到原问题注意:这种方法有可能丢失最优解,一般得到原问题的近似解的近似解 安徽科技学院安徽科技学院 运筹与优化运筹与优化练练 习习用连续变量的离散化方法求解下面的非线性规划用连续变量的离散化方法求解下面的非线性规划令令sk=0,1,2,3,4,列表求解列表求解逆序解法逆序解法:基本方程基本方程:注意到注意到目标函目标函数是乘数是乘积的形积的形式:式:安徽科技学院安徽科技学院 运筹与优化运筹与优化 背包问题的一般提法是:一位旅行者携带背包去登山、已背包问题的一般提法是:一位旅行者携带背包去登山、已知他所能承受的背包重量限度为知他所能承
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 一般 数学模型 动态 规划 解法
![提示](https://www.zixin.com.cn/images/bang_tan.gif)
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【a199****6536】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【a199****6536】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。