2021年第讲动态规划投资分配问题.ppt

投资分配问题
*
第讲动态规划投资分配问题
*
现有数量为a（万元）的资金，计划分配给n 个工厂,用于扩大再生产。
假设：xi 为分配给第i 个工厂的资金数量（万元）；gi(xi)为第i 个工厂得到资金后提供的利润值（万元）。
问题：如何确定各工厂的资金数，使得总的利润为最大。
据此，有下式：
*
第讲动态规划投资分配问题
*
令：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)
投资分配问题
*
第讲动态规划投资分配问题
*
如果a 是以万元为资金分配单位，则式中的y 只取非负整数0，1，2，…，x。上式可变为：
所以，根据动态规划的最优化原理，有下式：
投资分配问题
*
第讲动态规划投资分配问题
*
设国家拨给60万元投资，供四个工厂扩建使用，每个工厂扩建后的利润与投资额的大小有关，投资后的利润函数如下表所示。
投资
利润
0
10
20
30
40
50
60
g1(x)
0
20
50
65
80
85
85
g2(x)
0
20
40
50
55
60
65
g3(x)
0
25
60
85
100
110
115
g4(x)
0
25
40
50
60
65
70
依据题意，是要求 f4(60) 。
投资分配问题
*
第讲动态规划投资分配问题
*
按顺序解法计算。
第一阶段：求 f1(x)。显然有 f1(x) ＝ g1(x)，得到下表
投资
利润
0
10
20
30
40
50
60
f1(x) ＝ g1(x)
0
20
50
65
80
85
85
最优策略
0
10
20
30
40
50
60
第二阶段：求 f2(x)。此时需考虑第一、第二个工厂如何进行投资分配，以取得最大的总利润。
投资分配问题
*
第讲动态规划投资分配问题
*
最优策略为（40，20），此时最大利润为120万元。
同理可求得其它 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万元。
投资分配问题
*
第讲动态规划投资分配问题
*