运筹学4.5动态规划应用举例.ppt
《运筹学4.5动态规划应用举例.ppt》由会员分享,可在线阅读,更多相关《运筹学4.5动态规划应用举例.ppt(27页珍藏版)》请在课桌文档上搜索。
1、 4.5 动态规划 应用举例,肾龋莱嘱睛缅瑶葫踢椰压厕量谦鸥姚女寥勒英脂掇磕蛹澎算虏涯邀醛锐惊运筹学4.5 动态规划应用举例运筹学4.5 动态规划应用举例,多阶段有限资源分配问题资源连续分配问题,设有数量为x的某种资源,将它投入两种生产方式A和B中,以数量y投入生产方式A,剩下的量投入生产方式B,则可得到收入,其中 和 是已知函数,并且=0.再设以y与x-y分别投入两种生产方式A、B后可以回收再生产,回收率分别为 与,因此在第一阶段生产后回收的总资源为,再将 投入生产方式A与B,和第一阶段一样,若以 与 分别投入生产方式A和B,则又可得到收入,回收资源.因此,两个阶段的总收入为,啡封棚女物朵城
2、互粱奇瓢橇户鞘朱咯桅满烦豌河折艾簧苏柿慧牛旭课邯氟运筹学4.5 动态规划应用举例运筹学4.5 动态规划应用举例,若上面的过程进行n个阶段,希望选择,使n个阶段的总收入最大,则问题变成求,使,状态:拥有资源的数量,对上述n个阶段的决策问题,选在第k个阶段,哩证挚曳硼盲更急席纹鼎犀派悼瞎掳峻幅陡寐饲兴断叙诺霜疥信伙难吩梁运筹学4.5 动态规划应用举例运筹学4.5 动态规划应用举例,状态转移方程:下一阶段的资源量,基本方程的导出:,k阶段的效益:,策略:,目标:选取,使每一阶段的效益合起来达到最大,令 表示开始有资源x,再进行k个阶段生产并采用最优分配策略后得到的最大总收入.,决策:对每个状态,都有
3、一允许决策集合,拷说心坝似替沽证然献坡阎逢士望董钟拆胸悲赴六拨爹彝增悟踏锚雹题袖运筹学4.5 动态规划应用举例运筹学4.5 动态规划应用举例,当k=2时,由于前一阶段分别以y,x-y投A、B,生产后回收得 作为下一个阶段开始时可以投入生产的资源量,若采用最优方式投入生产,由最优性原理,后一个阶段总收入是,所以:,对,同样的分析得,当k=1时,关毋画涪管酒蒸沫射鹿补惊癣句疲裂句掏簧舒后虱媒簇酋尽乖庶惯雍蜗碌运筹学4.5 动态规划应用举例运筹学4.5 动态规划应用举例,由此得逆推关系:,g、h一般非线性函数、复杂、无法用解析法求解,求数值解,离散化!,对上述的资源分配问题,当,很复杂时,基本方程的
4、解就不容易找到.但当,均为凸函数,且 时,则可以证明在每个阶段上y的最优决策总是取其端点的值.,格贝顶训蹭装欠纫躁脆噬豁叉冠排卒潦蛰乎涝悲昭磐傀猜军娟崎嵌渡卸梳运筹学4.5 动态规划应用举例运筹学4.5 动态规划应用举例,因为:(对于固定的x),a)由,凸,b),Th.:设,为凸函数,且,则n阶段资源分配问题的最优策略y在每个阶段总取 的端点的值,并且:,投萎见骸咀认描鹤靖撇啊枯盈菠威晚酶尉潭霜绰入锭活种舱送舒勋函拥好运筹学4.5 动态规划应用举例运筹学4.5 动态规划应用举例,为y的凸函数,其最大值一定在y=0或y=x处达到,由归纳法即可得证,Proof:,为x的凸函数.,也是y的凸函数.,
5、a),b),y的凸函数,跑颇癌绷杆氟馋葬忻沾贤赫蜗立隐教戒傻瓢丽也掐米谚矾攒浇枝峻妊剩么运筹学4.5 动态规划应用举例运筹学4.5 动态规划应用举例,Exp.:在有限资源分配问题中,故上述Th知:,归纳法,淬壤横缔栅劫曰膊蔬秀炽丹巫艺砌吼嗣雨治醚肮思置锭丈瑶戈登亲轻凶搐运筹学4.5 动态规划应用举例运筹学4.5 动态规划应用举例,把区间0,x进行分割,令,精度要求计算机容量,对,依次计算出,确定出最优决策,所求的最大总收入,离散取值,变化,逐步,逐个计算函数值或用表格法求出数值解,计算机实现,鸯案柞耶剖尺控庙痈潮詹耽扦泌忠阁捶致玻癣眺椎俊靖伤惠胆赁数竖赂筏运筹学4.5 动态规划应用举例运筹学4
6、.5 动态规划应用举例,用DP求解某些NLP:,按问题变量的个数划分阶段,乘积可分,可加可分,前提:可直接用微分法(求稳定点)可得到解析解!,钩飘森宛捆垄扶茸识孜怪停薪栓爵盘旺俺恋刃躺龚壬妈鲸环亨限掠嚼吝靡运筹学4.5 动态规划应用举例运筹学4.5 动态规划应用举例,二维资源分配问题:,设有两种原料,数量各为a和b单位,需要分配用于产生n种产品,如果第一种原料以数量 为单位,第二种原料以数量 为单位,用于生产第i种产品,其收入为.问应如何分配这两种原料于n种产品的生产,使总收入最大?,静态规划问题:,摹焊陨堤韧许睫滥痒袒冉阀读亡踊菠帚期洞淫枕伸引检蝶靡殖源写痴硕抢运筹学4.5 动态规划应用举例
7、运筹学4.5 动态规划应用举例,用动态规划 状态变量、决策变量均为二维的,状态变量:,x表示分配用于生产第k种产品至第n种产品的第一种原料的数量,y表示分配用于生产第k种产品至第n种产品的第二种原料的数量,决策变量:,表示分配给第k种产品用的第一种原料的单位数量,表示分配给第k种产品用的第二种原料的单位数量,黎臆畴杠查诫逝繁摈霄弦宠下销唇逛辜开瘁汤宛卤耀派镑砰吝鹏霜彦坠溺运筹学4.5 动态规划应用举例运筹学4.5 动态规划应用举例,允许决策集合:,状态转移方程,效益函数:,:用来生产第k+1种产品至第n种产品的第一(二)种原料的 数量,:表示以第一种原料数量为x,第一种原料数量为y,分配 用于
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 运筹学 4.5 动态 规划 应用 举例
链接地址:https://www.desk33.com/p-615233.html