最优化理论chap7_动态规划应用

最优化理论chap7_动态规划应用

ID:44051730

大小:706.00 KB

页数:66页

时间:2019-10-18

最优化理论chap7_动态规划应用_第1页
最优化理论chap7_动态规划应用_第2页
最优化理论chap7_动态规划应用_第3页
最优化理论chap7_动态规划应用_第4页
最优化理论chap7_动态规划应用_第5页
资源描述:

《最优化理论chap7_动态规划应用》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库

1、第七章动态规划动态规划问题的基本概念和基本原理动态规划模型的建立与求解应用举例马氏决策规划应用举例1。背包问题2。生产经营问题3。设备更新问题4。复杂系统可靠性问题5。货郎担问题背包问题一般提法:旅行者携带背包登山,能承受的背包重量上限是b千克,现有n种物品,每件的重量是ai千克,每种物品的价值为ci(xi),是其数量xi的函数,问旅行者如何规划,使携带物品的总价值最大?推广:装载问题、资源分配问题、决策问题等背包问题标准模型xi为整数转化为动态规划问题:阶段:分为n个阶段k=1,2,…,n状态变量sk:k阶段时的可背的重量,则s1=b决策变量u

2、k:k阶段选择第k种物品的数量,uk=xk状态转移方程:sk+1=sk-akxk决策集合Dk(sk):{xk

3、0xk[sk/ak]}阶段指标函数vk(sk,uk):k阶段放入物品的价值。vk(sk,uk)=ck(xk)递推方程:fk(sk)=max{ck(xk)+fk+1(sk+1)}0xk[sk/ak]fn+1(sn+1)=0装载问题例3:最大载重为10吨的卡车,其货物的单位重量及相应单位价值如下表所示,问如何装载使货物的总价值最大?货物i123单位重量ai345单位价值ci456例3模型maxz=4x1+5x2+6x3s.t.3x1+

4、4x2+5x310xi0xi为整数i=1,2,3第1步k=3f3(s3)=max{6x3+f4(s4)}=max{6x3}0x3[s3/5]0x3[s3/5]s3012345678910x3000000101010101012f3(s3)000006666612x3*00000111112第2步k=2f2(s2)=max{5x2+f3(s2-4x2)}0x2[s2/4]s2012345678910x2000001010101012012012s30123405162738409511062v2+f30000056565656510

5、61110121110f2(s2)00005666101112x2*00001000210第3步k=1f1(s1)=max{4x1+f2(s1-3x1)}0x1[10/3]s110x10123s210741v1+f212101312f1(s1)13x1*2s2012345678910x2000001010101012012012s30123405162738409511062c2+f3000005656565651061110121110f2(s2)00005666101112x2*00001000210s3012345678910x3000

6、000101010101012f3(s3)000006666612x3*00000111112算法分析算法的复杂度与允许状态的大小直接相关应尽可能缩小允许状态的范围允许状态s2=s1-3x1s110x10123s210741s214710x200101012s3140731062s3=s2-4x2求解k=3f3(s3)=max{6x3+f4(s4)}=max{6x3}0x3[s3/5]0x3[s3/5]s3012346710x3000000101012f3(s3)000006612x3*00000112s214710x200101012s

7、3140731062v2+f300565121110f2(s2)05612x2*0100s110x10123s210741v1+f212101312f1(s1)13x1*2解法总结初始条件已知逆序解法初始条件已知终点状态多个顺序+逆序设备更新问题设备:使用时间t:越长效益r(t):越小维修费u(t):越大更新费c(t):越大问:更新方案,使n期内总收益最大问题分析阶段:分为n个阶段k=1,2,…,n状态变量sk:设备已使用时间t决策变量xk:xk=Keep保留xk=Replacement更新状态转移方程:sk+1=sk+1xk=Ksk+1=1

8、xk=R阶段指标:第k阶段的总收益vk(sk,xk)=rk(sk)-uk(sk)xk=Kvk(sk,xk)=rk(0)-uk(0)-ck(sk)xk=R迭代方程最优指标函数fk(sk):第k阶段起的最大总收益。fk(sk)xk=Kxk=Rfn+1(sn+1)=0为折扣因子例4例4:某新设备的收益、维修费和更新费如下表,折扣因子=1,设计最优更新方案。t012345rk(sk)54.543.7532.5uk(sk)0.511.522.53ck(sk)0.51.52.22.533.5(单位:万元)迭代方程fk(sk)xk=Kxk=Rk=5s5=0

9、,1,2,3,4k=1s1=0顺序+逆序第1步x1*=Kk=1s1=0第2步k=2s2=1x2=Kx2=R第3步k=3s3=1,2x3(

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。