动态规划投资分配问题

《动态规划投资分配问题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第21讲动态规划投资分配问题ACM算法设计与分析——王建芳投资分配问题现有数量为a（万元）的资金，计划分配给n个工厂,用于扩大再生产。假设：xi为分配给第i个工厂的资金数量（万元）；gi(xi)为第i个工厂得到资金后提供的利润值（万元）。问题：如何确定各工厂的资金数，使得总的利润为最大。据此，有下式：令：fk(x)表示以数量为x的资金分配给前k个工厂，所得到的最大利润值。用动态规划求解，就是求fn(a)的问题。当k=1时，f1(x)=g1(x)（因为只给一个工厂）当1＜k≤n时，其递推关系如下：设：y为分给第k

2、个工厂的资金（其中0≤y≤x），此时还剩x－y（万元）的资金需要分配给前k－1个工厂,如果采取最优策略，则得到的最大利润为fk－1(x－y),因此总的利润为：gk(y)＋fk－1(x－y)投资分配问题如果a是以万元为资金分配单位，则式中的y只取非负整数0，1，2，…，x。上式可变为：所以，根据动态规划的最优化原理，有下式：投资分配问题设国家拨给60万元投资，供四个工厂扩建使用，每个工厂扩建后的利润与投资额的大小有关，投资后的利润函数如下表所示。投资利润0102030405060g1(x)020506580858

3、5g2(x)0204050556065g3(x)0256085100110115g4(x)0254050606570依据题意，是要求f4(60)。投资分配问题按顺序解法计算。第一阶段：求f1(x)。显然有f1(x)＝g1(x)，得到下表投资利润0102030405060f1(x)＝g1(x)0205065808585最优策略0102030405060第二阶段：求f2(x)。此时需考虑第一、第二个工厂如何进行投资分配，以取得最大的总利润。投资分配问题最优策略为（40，20），此时最大利润为120万元。同理可求得其

4、它f2(x)的值。投资分配问题最优策略为（30，20），此时最大利润为105万元。投资分配问题最优策略为（20，20），此时最大利润为90万元。最优策略为（20，10），此时最大利润为70万元。投资分配问题最优策略为（10，0）或（0，10），此时最大利润为20万元。f2(0)＝0。最优策略为（0，0），最大利润为0万元。得到下表最优策略为（20，0），此时最大利润为50万元。投资分配问题投资利润0102030405060f2(x)020507090105120最优策略(0,0)(10,0)(0,10)(20,

5、0)(20,10)(20,20)(30,20)(40,20)第三阶段：求f3(x)。此时需考虑第一、第二及第三个工厂如何进行投资分配，以取得最大的总利润。投资分配问题最优策略为（20，10，30），最大利润为155万元。同理可求得其它f3(x)的值。得到下表投资分配问题投资利润0102030405060f3(x)0256085110135155最优策略(0,0,0)(0,0,10)(0,0,20)(0,0,30)(20,0,20)(20,0,30)(20,10,30)第四阶段：求f4(60)。即问题的最优策略。

6、投资分配问题最优策略为（20，0，30，10），最大利润为160万元。投资分配问题THANKS