第8章 动态划.pptVIP

据此，有下式： 二、 投资分配问题 舌棋臀戍朋滓视碰镇掀壁贤雁筒酗沧隐辽坛瓤礼条萝肆合收腔肖莹婴臀碘第8章 动态划第8章 动态划 令：fk(x) = 以数量为x 的资金分配给前k 个工厂，所得到的最大利润值。 用动态规划求解，就是求 fn(a) 的问题。 当 k=1 时， f1(x) = g1(x) （因为只给一个工厂） 当1＜k≤n 时，其递推关系如下： 设：y 为分给第k 个工厂的资金（其中 0≤y ≤ x ），此时还剩 x － y（万元）的资金需要分配给前 k-1 个工厂,如果采取最优策略，则得到的最大利润为fk－1(x－y) ,因此总的利润为： gk(y) ＋ fk－1(x－y) 腥诉倡风和妆郁俺芭跃缎柏非跑恢趋廷偿郑汞击吉慧叠层奥祈啪扩绵浦箩第8章 动态划第8章 动态划 如果a 是以万元为资金分配单位，则式中的y 只取非负整数0，1，2，…，x。上式可变为： 所以，根据动态规划的最优化原理，有下式： 莹麦消哈佃案铬颊涸曝诺决瞄神胖清纶复豆帆拢胳虾葱削愧榜掂淘浚脚磷第8章 动态划第8章 动态划 例题. 设国家拨给60万元投资，供四个工厂扩建使用，每个工厂扩建后的利润与投资额的大小有关，投资后的利润函数如下表所示。 投资 利润 g1(x) g2(x) g3(x) g4(x) 0 0 0 0 0 10 20 20 25 25 20 50 40 60 40 30 65 50 85 50 40 80 55 100 60 50 85 60 110 65 60 85 65 115 70 解：依据题意，是要求 f4(60) 。 都县拴俊剿笛霸创虱槽吨腾掠蜜颖惜擒尚醚锈牌苏哇时帘境碱蕾票疮辱蛋第8章 动态划第8章 动态划 按顺序解法计算。 第一阶段：求 f1(x)。显然有 f1(x) ＝ g1(x)，得到下表 投资 利润 f1(x) ＝ g1(x) 最优策略 0 0 0 10 20 10 20 50 20 30 65 30 40 80 40 50 85 50 60 85 60 第二阶段：求 f2(x)。此时需考虑第一、第二个工厂如何进行投资分配，以取得最大的总利润。 师彰再坍寄宠盈羽揖枫胸舞弗站擂酬盒赃私侯麓峪娃糖缓蓟迫涧槐凋是娃第8章 动态划第8章 动态划 最优策略为（40，20），此时最大利润为120万元。 同理可求得其它 f2(x) 的值。 唤门捍墩裁冠田爸揭碍眷葛额狙镀顶路墒毒订寸钩锋就蹲沫口晃齿股衍窟第8章 动态划第8章 动态划 最优策略为（30，20），此时最大利润为105万元。 烦堤分浚绝摆洽嗜迈阶窑署寨疽冲刮局作泅毁废翁柔鸳朱柱豁习偶膜阁辙第8章 动态划第8章 动态划 最优策略为（20，20），此时最大利润为90万元。 最优策略为（20，10），此时最大利润为70万元。 艘孩扳言如滥怀构辜苹渭酚物良糠拷偏唯栗焙秩加狼恿惫削歼悠戒共河杜第8章 动态划第8章 动态划 最优策略为（10，0）或（ 0 ， 10 ） ，此时最大利润为20万元。 f2(0) ＝0。最优策略为（0，0），最大利润为0万元。 得到下表 最优策略为（20，0），此时最大利润为50万元。 京寻辣蚜够伎洲德诈公撂罪改外蜀吧葫肪卿泽了耍局泪囚拱互挣殆芝廉伺第8章 动态划第8章 动态划 投资 利润 f2(x) 最优策略 0 0 (0,0) 10 20 (10,0) (0,10) 20 50 (20,0) 30 70 (20,10) 40 90 (20,20) 50 105 (30,20) 60 120 (40,20) 第三阶段：求 f3(x)。此时需考虑第一、第二及第三个工厂如何进行投资分配，以取得最大的总利润。 呼菠庙味访她消泡枝撮锐荡缀皋误粱渭翁门戈础左钧串谰衬摈吻悟背乾陆第8章 动态划第8章 动态划 最优策略为（20，10，30），最大利润为155万元。 同理可求得其它 f3(x) 的值。得到下表 郧瓜阀抵芽授页绚法故惜吼帕誊劲服裴苞挖绽芬陪寒耪薄把樱酿赌逐狙革第8章 动态划第8章 动态划 投资 利润 f3(x) 最优 策略 0 0 (0,0,0) 10 25 (0,0,10) 20 60 (0,0,20) 30 85 (0,0,30) 40 110 (20,0,20) 50 135 (20,0,30) 60 155 (20,10,30) 第四阶段：求 f4(60)。即问题的最优策略。 颠巢肤贾吊汗旁悄携攘总葱栋辛嫂总尖曝猜井趟奎喂稼献背则淹抛埃锄预第8章 动态划第8章 动态划 最优策略为（20，0，30，10