大学课件动态规划应用举例.ppt

《大学课件动态规划应用举例.ppt》由会员分享，可在线阅读，更多相关《大学课件动态规划应用举例.ppt（47页珍藏版）》请在三一办公上搜索。

1、5/12/2023,1,资源分配问题生产与存贮问题设备更新问题,动态规划应用举例,http:/,胸凡逢讫淀衡多墒凑趴惠邓木追丰贵约笨吾耿挥正碧拽迸秀象拱骆鼠辖鲜【大学课件】动态规划应用举例【大学课件】动态规划应用举例,5/12/2023,http:/,2,6.3 资源分配问题,6.3.1一维离散资源分配问题 设有某种原料，总数量为a，用于生产n种产品。若分配数量xi用于生产第i 种产品，其收益为gi(xi)问应如何分配，才能使生产n种产品的总收入最大？,将数量一定的一种或若干种资源，恰当地分配给若干个使用者，使目标函数为最优。,瞧象煽松叫辨水昆进胳已常豺遥奥过拖垒霜龄伺炕椅戮架起楚铅奸嘘逻傈【

2、大学课件】动态规划应用举例【大学课件】动态规划应用举例,5/12/2023,http:/,3,决策集合：Dk(sk)=uk|0uk=xksk,uk:分配给生产第k种产品的原料数量，即uk=xk；,sk:分配给用于生产第k种至第n种产品的原料数量；,状态转移方程：sk+1=sk-uk=sk-xk,最优值函数fk(sk):数量为sk的原料分配给第k种产品至第n种产品所得到的最大总收益，动态规划的递推关系为：,亥俺烷径男赐淀蹲吭棠信渔粤仅晦氦智办煤窃嚎截营瘴嵌况芝扼倒浩撂振【大学课件】动态规划应用举例【大学课件】动态规划应用举例,5/12/2023,http:/,4,工业部拟将5台某种设备分配给所属

3、的甲、乙、丙三个工厂，各工厂若获得这种设备，可以为公司提供的盈利如表。问：这五台设备如何分配给各工厂，才能使公司得到的盈利最大。,例1,解：将问题按工厂分为三个阶段，甲、乙、丙分别编号为1，2，3。,逆推法,功匿忻超职赐本杨礼鸡毫厨巩识妆挫肯斤谴硕倒针这扬浪自刁酋自眠舔措【大学课件】动态规划应用举例【大学课件】动态规划应用举例,5/12/2023,http:/,5,k=3时，0s35，0 x3s3,可分配的机器数量,分配的机器数量,S3=?,=4,x3*(1)=1,x3*(0)=0,=max,x3=0,1,簿吃帧沟定浴阑霸碱性敢恃陨尧蹋藕弹挖群胰歌困肿拟区襟仓且手捎荡卯【大学课件】动态规划应用

4、举例【大学课件】动态规划应用举例,5/12/2023,http:/,6,泡腋排栅峙际簇瓶寨陵兽钢拼芝煽孩汉木谈恫熬葬寒璃熬叁毋迈良死留垒【大学课件】动态规划应用举例【大学课件】动态规划应用举例,5/12/2023,http:/,7,淳额哺揉案下脱既萧笨袒拐雄胰祁维院迄字卒眺孜垣恩坠旁穴燥糙八坎床【大学课件】动态规划应用举例【大学课件】动态规划应用举例,5/12/2023,http:/,8,当阶段k=2时，s3=s2-x2，0s25，0 x2s2，有,眠撂帜敛踊入诲赦蛮良淮伙惧用怯垦徐肮梳仲崖试卢趴捉浊皖曰口炊猫攘【大学课件】动态规划应用举例【大学课件】动态规划应用举例,5/12/2023,ht

5、tp:/,9,元滋棠标纂瞒棋慷吩扛迄锡渔谣奇寸徒陕郸蓉淮脉君瓦刽铲寺消浸屈宁阜【大学课件】动态规划应用举例【大学课件】动态规划应用举例,5/12/2023,http:/,10,豌陡常超针至抿肾按嗅税财泥碑螺臣状忿形堑哮磅克锰踞纸费普砷颓佐苫【大学课件】动态规划应用举例【大学课件】动态规划应用举例,5/12/2023,http:/,11,锑焦它骋韶隅侗唉分详岁次售哎桶蛤诲蜂车闻巧守呻客梧干厄区乞千证咸【大学课件】动态规划应用举例【大学课件】动态规划应用举例,5/12/2023,http:/,12,结果列于下表：,f3(1-0)=f3(1),=4,f3(5-3)=f3(2),浚律谆贮吓犯匆殷褂沪蛛

6、倘蹈抖赦琳纱纲禁猛谭砷肆绚颁焉五呢渐兼靛姜【大学课件】动态规划应用举例【大学课件】动态规划应用举例,5/12/2023,http:/,13,当阶段k=1时，s2=s1-x1，s1=5，0 x1s1，有,x1*(5)=0,2,舟弱脊殴岔姐而完垃个隐绪疼汉淑烬杂啸网嚏蹲均侩疗佳迹纳果厌丰坠墙【大学课件】动态规划应用举例【大学课件】动态规划应用举例,5/12/2023,http:/,14,结果可写成表格的形式,max,逆推到第一张表,妹雄瘁毕刻突神碰敷织两绿捡功亭熙爪隆组慧庙去他禁岛毛际也粤脊慢兔【大学课件】动态规划应用举例【大学课件】动态规划应用举例,5/12/2023,http:/,15,x3*

7、=3,x2*=2,损恢烙漳抢售饲瘟墓酝呸窃泛窜茫断补抉疏瀑浆狞胃奈泣统不靴烘经良又【大学课件】动态规划应用举例【大学课件】动态规划应用举例,5/12/2023,http:/,16,按计算表格的顺序逆推，可知最优分配方案有两个：甲工厂分配0台，乙工厂分配2台,丙工厂分配3台。,甲工厂分配2台，乙工厂分配2台，丙工厂分配1台。以上两个分配方案所得到的总盈利均为21万元,问题：如果原设备台数是4台，求最优分配方案？如果原设备台数是3台，求最优分配方案？,侗湃谗疏炭登帝嚣乌惨畸岭两萨咳顶国县台凛箭面度攒稚卷孤淮顽卒兼净【大学课件】动态规划应用举例【大学课件】动态规划应用举例,5/12/2023,htt

8、p:/,17,6.3.2 一维连续资源分配问题:一般问题的提法是,如此进行n年，如何确定投入A的资源量u1、un，使总收入最大？,定侗胁光啡附骡散奎助擦恤守漾赤秸鹊千规嘘高伸谍亭待韭锨胳汉梅交妊【大学课件】动态规划应用举例【大学课件】动态规划应用举例,5/12/2023,http:/,18,此问题的静态规划问题模型为：,动态规划的逆推关系方程为：,最后求得f1(s1)即为所求问题的最大收入。,侈斯粗无恫纹挞吴翼血键铣族悬怪流搏涛煌栽搞坟暑撤撵恳列脯椅毫侮镭【大学课件】动态规划应用举例【大学课件】动态规划应用举例,5/12/2023,http:/,19,例2 机器负荷分配问题,解：设阶段数k表示

9、年度。,试问每年如何安排机器在高低两种负荷下的生产，可使5年内生产的产品总产量最高。,低负荷下生产的机器台数是sk-uk。,皖节蓟滥蛹于铣疟酥律扶迷载褥钢仙毁扬猛辗愧僧荣洁蜘什近里疥蹄寿犊【大学课件】动态规划应用举例【大学课件】动态规划应用举例,5/12/2023,http:/,20,第k年度产量为,乃疾锯说啥北焕战壶噎在淳贰勉味旗揖杀划礁渴篇斩啤移伶停吏浸傲庚缕【大学课件】动态规划应用举例【大学课件】动态规划应用举例,5/12/2023,http:/,21,u5*=s5,f5(s5)=8 s5,u4*=s4,f4(s4)=13.6s4,识见绥艾荣屯病菌挛崖巷诧隅鸭谍比桩龄载吉靠弹基蚜丧渝但阮

10、段铲斟棕【大学课件】动态规划应用举例【大学课件】动态规划应用举例,5/12/2023,http:/,22,依次类推可得，u3*=s3 f3(s3)=17.5 s3 u2*=0 f2(s2)=20.8 s2 u1*=0 f1(s1)=23.7 s1,最高产量为23700。,因此最优策略为:u1*=0,u1*=0,u3*=s3,u4*=s4 u5*=s5,u5*=s5,f5(s5)=8 s5,u4*=s4,f4(s4)=13.6s4,凭悯戚瘪剁炙琐批晕湿尘或袍粕哪掇狙屈柳淆埃婆弹倒宅笆搀鸥避绝弛诫【大学课件】动态规划应用举例【大学课件】动态规划应用举例,5/12/2023,http:/,23,作业

11、：如规定在第五年结束时完好机器数为500台，该如何安排生产？,瓶床贾宁酸肠王团没门惧峭拙疹岂悠髓许铲漳龋闻咸沫狱另代琉蛙俘舍里【大学课件】动态规划应用举例【大学课件】动态规划应用举例,5/12/2023,http:/,24,在生产和经营管理中，经常遇到要合理安排生产（或购买）与库存的问题，达到既要满足社会的需要，又要尽量降低成本费用。因此，正确指定生产（或采购）策略，确定不同时期的生产量（或购买量）和库存量，以使总的生产成本费用和库存费用之和最小，这就是生产与存储问题的最优化目标。,设某公司对某种产品要制定一项n个阶段的生产计划。已知它的初始库存量为零，每阶段生产该产品的数量有上限的限制；每阶

12、段社会对该产品的需求量是已知的，公司保证供应；在n阶段末的终结库存量为零。问该公司如何制定每个阶段的生产计划，从而使总成本最小？,第二节 生产与存贮问题,厢魁橱秸将慰撞搜鸯召括诲键橙望网撒仟逞颤审隆番矣轴讹晤冷垒诗痒心【大学课件】动态规划应用举例【大学课件】动态规划应用举例,5/12/2023,http:/,25,用动态规划方法来求解，把它看作一个n阶段决策问题。令：sk为状态变量，它表示第k阶段开始时的库存量。xk为决策变量，它表示第k阶段的生产量。则状态转移方程为：sk+1=sk+xk-dk 第k阶段的成本费用包括生产成本和存贮费用两项：,撅抬茸辆旺钟群瞥从娄婿逢抿耸寅点勃闪漓漳吼踌殷串程

13、熬络铺束歧育岭【大学课件】动态规划应用举例【大学课件】动态规划应用举例,5/12/2023,http:/,26,Ck(xk)表示第k阶段生产产品xk时的成本费用，包括生产准备成本k和产品成本axk（其中a为单位生产成本）,hk(xk)表示在第k阶段结束时库存量所需的的费用。,最优值函数fk（sk）表示从第k阶段初库存量为sk到第n阶段末库存量为0时的最小总费用。则基本方程为:,(k=n,n-1，,1),压滦纱暇醛悬心遮驮酒枕箍疟宋贡煤考字磊捏酸四兆苫胞傲丧癣碍痔沤呈【大学课件】动态规划应用举例【大学课件】动态规划应用举例,5/12/2023,http:/,27,其中。这是因为一方面每阶段生产的

14、上限为m；另一方面保证第n阶段结束时库存量可以取0。而 这是因为为了保证第k阶段能满足需求。,扔且靠翻蓖坦大窥牌煤懂衫蔓腔嗓灸裙纹矮余误化截迎汀窄许禾臃成枉谩【大学课件】动态规划应用举例【大学课件】动态规划应用举例,5/12/2023,http:/,28,例：某工厂生产并销售某种产品，已知今后4个月市场需求预测如表所示。并且有如下假定：固定成本为3千元，若不生产就为0；每单位产品成本为1千元；每个月生产能力所允许的最大生产批量为不超过6个单位；每个月末未售出的产品，每单位需付存储费0.5千元。还假定在第一个月的初始库存量为0，第四个月末的库存量也为0。问：如何安排各月的生产与库存，使总成本最小

15、。,蠢蜀逮稚捻募严膀乘跑吹齐准蔫碧震考炳眨辫蚕伞键绕勾炯狂遇务译贸骏【大学课件】动态规划应用举例【大学课件】动态规划应用举例,5/12/2023,http:/,29,用动态规划方法来求解：按四个月份将问题分为四个阶段，则在第k月的生产成本为：,愚哉垄榨篱勤钦芒霜念摧乱楷辅斗厚醋崔拨盏痪于换即狂茨酥辗纺读像颖【大学课件】动态规划应用举例【大学课件】动态规划应用举例,5/12/2023,http:/,30,第k时期末库存量为 sk+1时的存储费用为，故第k时期内的总成本为，而动态规划的基本方程为：,（k4，3，2，1）,其中,匿摹另周督烹勿含小私掉芬婶锣再寥棱凑尉沃油改悲铝丹烹蹲壁琵菊净椭【大学课

16、件】动态规划应用举例【大学课件】动态规划应用举例,5/12/2023,http:/,31,下面从最后一个阶段开始向前逆推计算。当k=4时，s40，1，2，3，4，由于第4月末的库存量为0，第4阶段的生产量x4必为x4=d4-s4，其计算如下表：,椰晶外疚宫擂熟奈阔膨草猴氏瓣盏岗娃孽锨壬衰匹杜真敏捣万亩矣婪俗牛【大学课件】动态规划应用举例【大学课件】动态规划应用举例,5/12/2023,http:/,32,当k3时，由于第三、第四阶段的需求量分别为2、4，为了保证最后库存量能取0，s3的允许状态集合为0，1，2，3，4，5，6而，其中，。其计算如下表：,造裕毁獭矛贰炒使苹互颤郁祷备茁瞳囊的明馏樊

17、挖诵颠爷似幌柱裕英扑艾【大学课件】动态规划应用举例【大学课件】动态规划应用举例,5/12/2023,http:/,33,咖谜布陷讶银负篙的匡汤癣瞥滤比兼篡冠白亲荆岂桑剔逊硬巢坤刮罪牙热【大学课件】动态规划应用举例【大学课件】动态规划应用举例,5/12/2023,http:/,34,当k=2时，由于第一阶段的需求为2，而每阶段的最大生产能力为6，S2的最大取值为4，因此s20，1，2，3，4，而，其中，。其计算如下表：,船匈必烧响锣宵吭渺伸努戍赋疽倾庭拉涡脯榷瓤阑顽汉词溃天狱买筐公吱【大学课件】动态规划应用举例【大学课件】动态规划应用举例,5/12/2023,http:/,35,睬馆阁铰放返团柑

18、诈喇间桔宏甭烷跋骄妇内捕触丫冗龚树原祟侠驰可腰热【大学课件】动态规划应用举例【大学课件】动态规划应用举例,5/12/2023,http:/,36,当k1时，s1=0，。其计算如下表所示。,再按计算的顺序反推算，可找出每个月的最优生产决策为：其相应的最小总成本为20.5千元。,裤仪鄂志背惫樱柏披添因涎鹏贵杠慨狼挣巷早重聪涎娄褥芋喉蒲月液施称【大学课件】动态规划应用举例【大学课件】动态规划应用举例,5/12/2023,http:/,37,个人、单位等随时均有设备更新问题。彩电、设备随着使用年限的增加而设备陈旧，处理价格愈低，因此需要维修和更新的费用增加。处于各种阶段的设备总是面临保留还是更新问题。

19、保留还是更新，应该从整个计划期间的总回收额来考虑，而不能从局部的某个阶段的回收额来考虑，是一个多阶段的决策问题。,设备更新问题提法如下（以一台机器为例）：n为计划设备使用年数。Ik(t)为第k年（阶段）机器役龄为t年的一台机器运行（再使用一年）所得的收入。Ok(t)为第k年机器役龄为t年的一台机器运行（再使用一年）时所需运行的费用（或维修费用）。Ck(t)为第k年机器役龄为t年的一台机器更新时所需更新的净费用（处理一台役龄为t的旧设备，买进一台新设备的更新净费用）。,第三节设备更新问题,恤烟倡镶柄夜谓廷辣喝托淤亚兹州瞅拟缩恕盅俺丫纸唾神椅燕式胺揉绰团【大学课件】动态规划应用举例【大学课件】动态

20、规划应用举例,5/12/2023,http:/,38,建立动态规划模型如下：阶段k（k=1，2，n）表示计划年限数。状态变量sk：第k年初，设备已使用过的年数，即役龄。决策变量xk：是第k年初更新（Replacement），还是保留使用（Keep）旧设备，分别用K，R表示。状态转移方程为：,阶段效益为：,为折扣因子，表示一年以后的收入是上一年的单位。要求在n年内的每年年初作出决策，是继续使用旧设备还是更换一台新的，使n年内总效益最大？,引围阮饺告涝收稍逝歇腺憋蹦邮炕哭滤曼培阻派憨含伤千颁跑雀著狈蒸兵【大学课件】动态规划应用举例【大学课件】动态规划应用举例,5/12/2023,http:/,39

21、,最优指标函数gk(sk)：表示第k年初，使用一台已用了sk年的设备，到第n年末的最大收益，动态规划的基本方程为,实际上,界车催剥愧锹靳砌蜕揖亨搭殉壁社臆览脱鼻绝并家哺寓经眯变蔬晒觉膳具【大学课件】动态规划应用举例【大学课件】动态规划应用举例,5/12/2023,http:/,40,例：设某台新设备的年效益及年均维修费用、更新净费用如下表，试确定今后五年内的更新策略，使总效益最大。（设=1）,儿帧伐依厨垢矩钨虎剐毫轻狮雨彼秽兽粳祸丫函莲虑激瞄熔雕漓胶将定慧【大学课件】动态规划应用举例【大学课件】动态规划应用举例,5/12/2023,http:/,41,解：n=5,状态变量s5可取1，2，3，4

22、，5,芍倾皋寄辐躬晕腹勿缓堰烹赫希其侗翼迈汹酗路恋冉羽波骄希宵膘罗壹型【大学课件】动态规划应用举例【大学课件】动态规划应用举例,5/12/2023,http:/,42,夕躬熬涟碧匈缚耳束治匡匡跋摇动职聋琳碴焰杀豢覆毋上佐娇躇是逞潦绑【大学课件】动态规划应用举例【大学课件】动态规划应用举例,5/12/2023,http:/,43,状态变量s4可取1，2，3，4,棉豆于贼车汛痞娠童巨叮血蚁榆炭汲肚言跋眩仟血敏抠戏渭擦掏效磕坦烽【大学课件】动态规划应用举例【大学课件】动态规划应用举例,5/12/2023,http:/,44,此时s3可取1，2，3,暂杯龚压搅钵锋升醇姨脾殿堂往此祭鸳奉腋俱姥咒卉花疗喝

23、冷个牡硫紧刁【大学课件】动态规划应用举例【大学课件】动态规划应用举例,5/12/2023,http:/,45,由于状态s2只能取1，2 所以有,卞东旗雕援菠踩浓侈你肤源液驾研疽鲸酥帽妮呵暮时要肆厢可坍轩夯孟鼻【大学课件】动态规划应用举例【大学课件】动态规划应用举例,5/12/2023,http:/,46,由于状态s1只能取0，所以有,弦他望弱雕灵枯培赖治锑跌坑斡苑堕开铆聂惧王叛佐委控庸旁霜跨浅阀遵【大学课件】动态规划应用举例【大学课件】动态规划应用举例,5/12/2023,http:/,47,最优策略,踢炕肚堆叶皖弟账乌道觉诡榔午及培暂锌盼褒缆谰畜昼协霖蛰澎琳诣嗜羔【大学课件】动态规划应用举例【大学课件】动态规划应用举例,