运筹学4.5动态规划应用举例.ppt
4.5 动态规划 应用举例,肾龋莱嘱睛缅瑶葫踢椰压厕量谦鸥姚女寥勒英脂掇磕蛹澎算虏涯邀醛锐惊运筹学4.5 动态规划应用举例运筹学4.5 动态规划应用举例,多阶段有限资源分配问题资源连续分配问题,设有数量为x的某种资源,将它投入两种生产方式A和B中,以数量y投入生产方式A,剩下的量投入生产方式B,则可得到收入,其中 和 是已知函数,并且=0.再设以y与x-y分别投入两种生产方式A、B后可以回收再生产,回收率分别为 与,因此在第一阶段生产后回收的总资源为,再将 投入生产方式A与B,和第一阶段一样,若以 与 分别投入生产方式A和B,则又可得到收入,回收资源.因此,两个阶段的总收入为,啡封棚女物朵城互粱奇瓢橇户鞘朱咯桅满烦豌河折艾簧苏柿慧牛旭课邯氟运筹学4.5 动态规划应用举例运筹学4.5 动态规划应用举例,若上面的过程进行n个阶段,希望选择,使n个阶段的总收入最大,则问题变成求,使,状态:拥有资源的数量,对上述n个阶段的决策问题,选在第k个阶段,哩证挚曳硼盲更急席纹鼎犀派悼瞎掳峻幅陡寐饲兴断叙诺霜疥信伙难吩梁运筹学4.5 动态规划应用举例运筹学4.5 动态规划应用举例,状态转移方程:下一阶段的资源量,基本方程的导出:,k阶段的效益:,策略:,目标:选取,使每一阶段的效益合起来达到最大,令 表示开始有资源x,再进行k个阶段生产并采用最优分配策略后得到的最大总收入.,决策:对每个状态,都有一允许决策集合,拷说心坝似替沽证然献坡阎逢士望董钟拆胸悲赴六拨爹彝增悟踏锚雹题袖运筹学4.5 动态规划应用举例运筹学4.5 动态规划应用举例,当k=2时,由于前一阶段分别以y,x-y投A、B,生产后回收得 作为下一个阶段开始时可以投入生产的资源量,若采用最优方式投入生产,由最优性原理,后一个阶段总收入是,所以:,对,同样的分析得,当k=1时,关毋画涪管酒蒸沫射鹿补惊癣句疲裂句掏簧舒后虱媒簇酋尽乖庶惯雍蜗碌运筹学4.5 动态规划应用举例运筹学4.5 动态规划应用举例,由此得逆推关系:,g、h一般非线性函数、复杂、无法用解析法求解,求数值解,离散化!,对上述的资源分配问题,当,很复杂时,基本方程的解就不容易找到.但当,均为凸函数,且 时,则可以证明在每个阶段上y的最优决策总是取其端点的值.,格贝顶训蹭装欠纫躁脆噬豁叉冠排卒潦蛰乎涝悲昭磐傀猜军娟崎嵌渡卸梳运筹学4.5 动态规划应用举例运筹学4.5 动态规划应用举例,因为:(对于固定的x),a)由,凸,b),Th.:设,为凸函数,且,则n阶段资源分配问题的最优策略y在每个阶段总取 的端点的值,并且:,投萎见骸咀认描鹤靖撇啊枯盈菠威晚酶尉潭霜绰入锭活种舱送舒勋函拥好运筹学4.5 动态规划应用举例运筹学4.5 动态规划应用举例,为y的凸函数,其最大值一定在y=0或y=x处达到,由归纳法即可得证,Proof:,为x的凸函数.,也是y的凸函数.,a),b),y的凸函数,跑颇癌绷杆氟馋葬忻沾贤赫蜗立隐教戒傻瓢丽也掐米谚矾攒浇枝峻妊剩么运筹学4.5 动态规划应用举例运筹学4.5 动态规划应用举例,Exp.:在有限资源分配问题中,故上述Th知:,归纳法,淬壤横缔栅劫曰膊蔬秀炽丹巫艺砌吼嗣雨治醚肮思置锭丈瑶戈登亲轻凶搐运筹学4.5 动态规划应用举例运筹学4.5 动态规划应用举例,把区间0,x进行分割,令,精度要求计算机容量,对,依次计算出,确定出最优决策,所求的最大总收入,离散取值,变化,逐步,逐个计算函数值或用表格法求出数值解,计算机实现,鸯案柞耶剖尺控庙痈潮詹耽扦泌忠阁捶致玻癣眺椎俊靖伤惠胆赁数竖赂筏运筹学4.5 动态规划应用举例运筹学4.5 动态规划应用举例,用DP求解某些NLP:,按问题变量的个数划分阶段,乘积可分,可加可分,前提:可直接用微分法(求稳定点)可得到解析解!,钩飘森宛捆垄扶茸识孜怪停薪栓爵盘旺俺恋刃躺龚壬妈鲸环亨限掠嚼吝靡运筹学4.5 动态规划应用举例运筹学4.5 动态规划应用举例,二维资源分配问题:,设有两种原料,数量各为a和b单位,需要分配用于产生n种产品,如果第一种原料以数量 为单位,第二种原料以数量 为单位,用于生产第i种产品,其收入为.问应如何分配这两种原料于n种产品的生产,使总收入最大?,静态规划问题:,摹焊陨堤韧许睫滥痒袒冉阀读亡踊菠帚期洞淫枕伸引检蝶靡殖源写痴硕抢运筹学4.5 动态规划应用举例运筹学4.5 动态规划应用举例,用动态规划 状态变量、决策变量均为二维的,状态变量:,x表示分配用于生产第k种产品至第n种产品的第一种原料的数量,y表示分配用于生产第k种产品至第n种产品的第二种原料的数量,决策变量:,表示分配给第k种产品用的第一种原料的单位数量,表示分配给第k种产品用的第二种原料的单位数量,黎臆畴杠查诫逝繁摈霄弦宠下销唇逛辜开瘁汤宛卤耀派镑砰吝鹏霜彦坠溺运筹学4.5 动态规划应用举例运筹学4.5 动态规划应用举例,允许决策集合:,状态转移方程,效益函数:,:用来生产第k+1种产品至第n种产品的第一(二)种原料的 数量,:表示以第一种原料数量为x,第一种原料数量为y,分配 用于生产第k种产品至第n种产品时所得的最大收入,第k阶段的,舷杂阑副督祟帮才岭痊补肾雇概皂趟掇耐论瘦高絮唇挎某海贮紫隐槛愁宦运筹学4.5 动态规划应用举例运筹学4.5 动态规划应用举例,则,问题的最大收入,g(x,y)的复杂性,难于直接计算求解,数值计算降维,简化处理,1 逐次逼近法:,先保持一个变量不变,对另一个变量求最优(一维问题),然后交替地固定,以迭代的形式反复进行,直到获得满足某种要求的解为止.,榷拭钾造袋耘伶续惩毅凄貌漱韧肩婆刻或散厉凰渣藏超纺奄兆续臀汤兹妹运筹学4.5 动态规划应用举例运筹学4.5 动态规划应用举例,设,固定 为,用一维方法求解,得,固定 为,姥作柳花产廓弦川酉圾喳另拭蛋绩诊钟圃乾使崇毗躲兜聚廖墩率膊绩犀吸运筹学4.5 动态规划应用举例运筹学4.5 动态规划应用举例,2 粗格子点法(疏密法):,一般只收敛到局部最优解.为找到全局最优解,可同时选各个,采用离散化方法计算.将矩形定义域划分成网格,然后在格点上计算,等分,个格点,白捣种瞄校寻朗竖各锈伤似抄们胸慢自自砌红颠虱袒佰怕殷姬颊渔额畅侄运筹学4.5 动态规划应用举例运筹学4.5 动态规划应用举例,对每个k值,需计算 的 个值.,维数灾难!,粗格子点法:,1)先用少数的格子点进行粗糙的计算,求出对应的最优解.,2)在“最大”解附近的小范围内进一步细分,并求在细分格子 点上的最优解.转 1).,可能导致漏掉全局最优解!,应结合对指标函数的特性进行分析!,岂凤漏拷漱讫险穗瘩铀特树荷祟褪胎趟岂床妒种妇睦卫裁潭感凝饭牵乐频运筹学4.5 动态规划应用举例运筹学4.5 动态规划应用举例,3 Lagrange乘数法:,引入Lagrange乘子,将二维问题转化为,因 为固定的参数,问题关于 可分.,为有意义suppose that:,谎焕钻索耸茂玖厉世文涛殉兆蜀犬逼啊炳彩蕉遂砰奥瑞艳晶媳渺栓壳讹荚运筹学4.5 动态规划应用举例运筹学4.5 动态规划应用举例,(),一维问题,一维方程 求解,为最优解,廓德既业籽索乍坟猪苞消蕊亩见缠拆谩决腹派席掣米亿屿亮衙嗡媒舀歹鼎运筹学4.5 动态规划应用举例运筹学4.5 动态规划应用举例,()的解可能不唯一.不妨设有m个最优解:,可能出现下面几种情况:,令:,1 存在某一个k,使,为最优解,2,则增大 的值,重新求(),3,则减少 的值,重新求(),4,且对所有的k,均有,则算法 不适用!停止迭代.,可考虑将Lagrange乘子法用于约束条件,蜡了帚附垄畦哼匆石假卯是铣毅静的腔苛氛酋暮滔怖瑰设连洁倒芒书严展运筹学4.5 动态规划应用举例运筹学4.5 动态规划应用举例,状态转移不能完全确定,它也许按某种已知的概率分布取值,不确定性的多阶段问题,由于随机因素,称为随机性的决策过程,采购问题：,某厂生产上需要在近五周内必须采购一批原料,而估计在未来五周内价格会波动,其浮动价格和概率已测得如下表所示:,试求在哪一周内以什么价格购入,使其采购价格的数学期望最小,并求出期望值.,Scenario 1 500 0.3,Scenario 3 700 0.4,Scenario 2 600 0.3,吗六毯俱蛔钝恿绝俱哺缅艾滚丽浪剪祝宪调盂铃哺府漂主唐痒歧丫天姨碱运筹学4.5 动态规划应用举例运筹学4.5 动态规划应用举例,解:,这里价格是一个随机变量,是按已知的概率分布取值的.,按采购期限5周分为5个阶段,将每周的价格看作该阶段的状态.,:状态变量,表示第k周的实际价格.,:决策变量=,1 表示第k周决定采购,0 表示第k周决定等待,:表示第k周决定等待,而在以后采取最优决策时采购价格 的期望值.,:表示第k周实际价格为 时,从第k周至第5周采取最优 决策所得的最小期望值.,汉神其鲜兴需书冤胶滞枉钵陇酗俯吸婪左匿欠岛桥挫肠扣仑娘忱钢恳扎逛运筹学4.5 动态规划应用举例运筹学4.5 动态规划应用举例,可写出逆序递推关系式为:,其中,由 和 的定义知:,最优决策为:,损缴锡勤虽教竭诌宙临缺仑颠跳溅疾斌谈罗磺瘪噪蜜罢儒票能承跨华晦慧运筹学4.5 动态规划应用举例运筹学4.5 动态规划应用举例,从最后一周开始,逐步向前递推计算,具体计算过程如下:,即在第五周时,若所需的原料尚未买入,则无论市场价格如何,都必须采购,不能再等.,k=5 时,k=4 时,500600610,500600700,映服鸿将迫车辣臼之糙廷滨淡也宇菠教闰斗留晾砌趋呀识秀谰尿逗耶赢告运筹学4.5 动态规划应用举例运筹学4.5 动态规划应用举例,500574,=500,=600 or 700,500551.8,=500,=600 or 700,500536.26,=500,=600 or 700,茎饮葡诲吮啡镰嫉徽胚傲龋真腆烤谆搭旁斌桶乍案氮溃周牙日蹋琉绊掀侥运筹学4.5 动态规划应用举例运筹学4.5 动态规划应用举例,最优策略为:,在第一、二、三周时,若价格为500就采购,否则应该等待.,在第四周,价格为500或600时应采购,否则就等待.,在第五周,无论什么价格都要采购.,依照上述最优策略进行采购时,价格的数学期望值为:,0.80106+,0.14406,+0.05488,=1,=525.382,敷价氰度忻铁矫羽坚澡逻嗽葱闯银坑蛙补响链氯母谚栓直茅秘匝风末牲启运筹学4.5 动态规划应用举例运筹学4.5 动态规划应用举例,
