当前位置:首页 >> 理学 >>

动态规划习题


例 1:最短路线问题 某工厂需要把一批货物从城市 A 运到城市 E,中间可经过 B1 、B2、B3、C1、 C2 、C3、D1 、D2 等城市,各城市之间的交通线和距离如下图所示,问应该选择一 条什么路线,使得从 A 到 E 的距离最短? 6 B1 C1 3 8 4 5 D1 5 6 4A B2 9 8 C2 7 2 6 D3 3 6 7 1 8 3 C B3 3 7 下面利用动态规划的逆推归纳法,将例 1 从最后一个城市 E 逐步推算到第 一个城市 A,在此 f k ( sk ) 表示第 k 阶段从城市 sk 到城市 E 最短路。 1)当 k=4 时:要求 f 4 ( s4 ) ,由于第 4 阶段只有两个城市 D1、D2(即 s4 的取 值为 D1、D2) ,从 D1 到 E 只有一条路,故 f 4 ( D1 ) ? d ( D1 , E ) ? 4, u4* ( D1 ) ? E ,同 理 f 4 ( D2 ) ? d ( D2 , E ) ? 3, u4* ( D2 ) ? E 。 2)当 k=3 时:s3 的取值为 C1、C2、C3,从 C1 出发到 E 有两条路,一条是经 过 D1 到 E,另一条是经过 D2 到 E ,显然:

E

?d (C1 , D1 ) ? f 4 ( D1 ) ? ?3 ? 4 ? f 3 (C1 ) ? min ? ? ? min ? ? ? 7, d ( C , D ) ? f ( D ) 5 ? 3 ? ? ? 1 2 4 2 ?

u3* (C1 ) ? D1

即从 C1 出发到 E 的最短路为 7,相应决策为 u3* (C1 ) ? D1 ,最短路线是 C1 →D1→E。 同理
?d (C2 , D1 ) ? f 4 ( D1 ) ? ?6 ? 4? f3 (C2 ) ? ? ??? ? ? 5, ?d (C2 , D2 ) ? f 4 ( D2 ) ? ?2 ? 3 ? ?d (C3 , D1 ) ? f 4 ( D1 ) ? ?1 ? 4 ? f3 (C3 ) ? ? ??? ? ? 5, ?d (C3 , D2 ) ? f 4 ( D2 ) ? ?3 ? 3? u3* (C2 ) ? D2

u3* (C3 ) ? D1

2)当 k=2 时:s2 的取值为 B1、B2、B3,从 B1 出发到 E 有三条路,分别是经 过 C1、C2、C3 到 E,则有:

?d ( B1 , C1 ) ? f 3 (C1 ) ? ?6 ? 7 ? ? ? ? ? f 2 ( B1 ) ? ?d ( B1 , C2 ) ? f3 (C2 ) ? ? ?4 ? 5 ? ? 9, ? d ( B , C ) ? f (C ) ? ? 5 ? 5 ? ? ? 1 3 3 3 ? ?

u2* ( B1 ) ? C2

同理

?d ( B2 , C1 ) ? f3 (C1 ) ? ?8 ? 7 ? ? ? ? ? f 2 ( B2 ) ? ?d ( B2 , C2 ) ? f3 (C2 ) ? ? ?7 ? 5? ? 11, ?d ( B , C ) ? f (C ) ? ?6 ? 5 ? ? ? 2 3 3 3 ? ? ?d ( B3 , C1 ) ? f3 (C1 ) ? ?7 ? 7 ? ? ? ? ? f 2 ( B3 ) ? ?d ( B3 , C2 ) ? f 3 (C2 ) ? ? ?8 ? 5 ? ? 12, ?d ( B3, C ) ? f (C ) ? ?7 ? 5 ? ? ? 3 3 3 ? ?

u2* ( B2 ) ? C3

u2* ( B3 ) ? C3

2)当 k=1 时:s1 的只有一个取值为 A. 从 A 出发到 E 有三条路,分别是经 过 B1、B2、B3 到 E,则有:
?d ( A, B1 ) ? f 2 ( B1 ) ? ?8 ? 9 ? ? ? ? ? f1 ( A) ? min ?d ( A, B2 ) ? f 2 ( B2 ) ? ? min ?9 ? 11 ? ? 17, ?d ( A, B ) ? f ( B ) ? ?6 ? 12 ? ? ? ? 3 2 3 ? u1* ( A) ? B1



于是得到从 A 到 E 的最短距离 17,为了找出最短路线,按计算的顺序逆推 去 , 可 得 到 最 优 策 略 为 :

p1,4 ( A) ? {u1* ( A) ? B1 , u2* ( B1 ) ? C2 , u3* (C2 ) ? D2 , u4* ( D2 ) ? E} ,最短路线是 A→B1→

C2→D2→E。

max z ? x1 x2 2 x3
例 3:逆推解法求解下面问题: ? x1 ? x2 ? x3 ? c

? ? x1 , x2 , x3 ? 0

解: 按问题的变量个数划分阶段,把它看作一个三阶段决策问题。设状态变 量为 s1,s2,s3,s4。并记 s1=c;令变量 x1,x2,x3 为决策变量;各阶段指标按 乘积方式结合。 即令: v1 ( s1 , x1 ) ? x1 , v2 ( s2 , x2 ) ? x2 2 , v3 ( s3 , x3 ) ? x3 令最优值函数 f k(sk)表示为第 k 阶段的初始状态为 sk 时, 从第 k 阶段到第 3 阶段所得到的最大值。 设: s3= x3, s3+ x2=s2, s2+ x1=s1=c 则有:x3=s3, 0≤x2≤s2, 0≤x1≤s1=c 即状态转移方程为: s3=s2-x2, s2 =s1-x1 由逆推解法,

f3 ( s3 ) ? max( x3 ) ? s3 , 即最优解 x3*=s3,
x3 ? s3
0? x2 ? s2

f 2 ( s2 ) ? max[ x2 2 ? x3 ] ? max [ x2 2 ? f3 ( s3 )]
x2 , x3

? max [ x2 2 ? ( s2 ? x2 )] ? max h2 ( s2 , x2 )
0? x2 ? s2 0 ? x2 ? s2



dh2 2 ? 2 x2 s2 ? 3 x2 2 ? 0 ,得 x2 ? s2 和 x2 ? 0 (舍去) 3 dx2
d 2 h2 d 2 h2 2 ,而 ? 2 s ? 6 x | ? ?2 s2 ? 0 ,故 x2 ? s2 为极大值点。 2 2 2 2 x ?2s 3 dx2 dx2 2 3 2
4 2 2 s2 即最优解 x2* ? s2 。 27 3
0? x1 ? s1



所以 f 2 ( s2 ) ?

f1 ( s1 ) ? max[ x1 ? x2 2 ? x3 ] ? max[ x1 ? f 2 ( s2 )]
x1 , x2 , x3

? max[ x1 ?
0? x1 ? s1

4 ( s1 ? x1 )3 ] ? max h1 ( s1 , x1 ) 0? x1 ? s1 27

1 1 4 s1 ,故 f1 ( s1 ) ? s1 4 64 1 1 由于 s1=c,∴ x1* ? c , f1 (c ) ? c 4 4 64 2 1 1 由 s2 =s1-x1*,∴ x2* ? s2 ? c , f 2 ( s2 ) ? c 3 3 2 16 1 1 由 s3 =s2-x2*,∴ x3* ? s3 ? c , f3 ( s3 ) ? c 4 4 1 1 1 因此最优解为: x1* ? c , x2* ? c , x3* ? c , 4 2 4 1 4 最大值为: max z ? f1 (c) ? c 64

求导并令导数等于 0 可得: x1* ?

max z ? x1 x2 2 x3
例 3:用顺推解法求解下面问题: ? x1 ? x2 ? x3 ? c ? ? x1 , x2 , x3 ? 0 解:设 s4=c,决策变量仍为 x1,x2,x3;最优值函数 f k(sk+1)表示为第 k 阶段 末的结束状态为 sk+1,从第 1 阶段到第 k 阶段所得到的最大值。 设: s2= x1, s2+ x2=s3, s3+ x3=s4=c 则有:x1=s2, 0≤x2≤s3, 0≤x3≤s4=c 即状态转移方程为: s2=s3-x2, s3=s4-x3 由顺推解法, f1 ( s2 ) ? max( x1 ) ? s2 , 即最优解 x1*=s2,
x1 ? s2

f 2 ( s3 ) ? max[ x1 ? x2 2 ] ? max [ x2 2 ? f1 (s2 )]
x1 , x2 0? x2 ? s3

? max [ x2 2 ? ( s3 ? x2 )] ?
0? x2 ? s3

4 3 s3 27

最优解 x2* ?

2 s3 。 3

f3 ( s4 ) ? max[ x1 ? x2 2 ? x3 ] ? max [ x3 ? f 2 (s3 )]
x1 , x2 , x3 0 ? x3 ? s4

? max [ x3 ?
0? x3 ? s4

4 1 4 (s4 ? x3 )3 ] ? s4 27 64

最优解 x3* ?

1 s4 4

1 1 由于 s4=c,∴ x3* ? c , f3 (c) ? c 4 4 64 2 1 1 由 s3=s4-x3*,∴ x2* ? s3 ? c , f 2 ( s2 ) ? c 3 2 16 1 1 由 s2=s3-x2*,∴ x1* ? s2 ? c , f3 ( s3 ) ? c 4 4 1 1 1 因此最优解为: x1* ? c , x2* ? c , x2* ? c , 4 2 4 1 最大值为: max z ? c 4 64

max z ? 4 x12 ? x2 2 ? 2 x3 2 ? 12
例 4:用顺推解法求解下面问题: ?3 x1 ? 2 x2 ? x3 ? 9 ? ? x1 , x2 , x3 ? 0 解: 按问题的变量个数划分阶段,把它看作一个三阶段决策问题。 设状态变量为 s0,s1,s2,s3。并记 s3≤9; 令变量 x1,x2,x3 为决策变量; 最优值函数 f k(sk)表示为第 k 阶段末的结束状态为 sk, 从第 1 阶段到第 k 阶 段所得到的最大值。 设: 3x1=s1, s1+2x2=s2, s2+ x3=s3≤9 则有:x1=s1/3,0≤x2≤s2/2 , 0≤x3≤s3≤9 即状态转移方程为: s1=s2-2x2, s2=s3-x3 由顺推解法, f1 ( s1 ) ? max(4 x12 ) ?
x1 ? s1 3

4 2 s1 , 即最优解 x1*=s1/3, 9

f 2 ( s2 ) ? max[4 x12 ? x2 2 ] ? max [? x2 2 ? f1 ( s1 )]
x1 , x2 0? x2 ? s2 2

4 ? max [? x2 2 ? ( s2 ? 2 x2 ) 2 ] ? max h2 ( s2 , x2 ) s s 9 0 ? x2 ? 2 0? x2 ? 2 2 2


dh2 14 16 8 ? x2 ? s2 ? 0 ,得 x2 ? s2 (它不在决策集内) 7 dx2 9 9

s 4 2 1 s2 , h2 ( 2 ) ? ? s2 2 9 2 4 4 2 ∴最大值点为 x2=0。故得到 f 2 ( s2 ) ? s2 及最优解 x2* ? 0 。 9

则最大值在端点上,∵ h2 (0) ?

f3 ( s3 ) ? max[4 x12 ? x2 2 ? 2 x32 ? 12] ? max [2 x3 2 ? 12 ? f 2 ( s2 )]
x1 , x2 , x3 0 ? x3 ? s3

4 ? max [2 x32 ? 12 ? ( s3 ? x3 )2 ] ? max h3 ( s3 , x3 ) 0? x3 ? s3 0 ? x3 ? s3 9



dh3 44 8 2 ? x3 ? s3 ? 0 ,得 x3 ? s3 11 dx3 9 9
dh3 2 44 ? ? 0 ,故该点为极小值点。 dx32 9
4 2 s3 ? 12, h2 ( s3 ) ? 2s32 ? 12 9



而 h3 (0) ?

∴最大值点为 x3=s3。故得到 f3 ( s3 ) ? 2 s3 2 ? 12 及最优解 x3* ? s3 。 由于 s3 不知道,故须在对 s3 求一次极值,即
0? s3 ?9

max f 3 ( s3 ) ? max[2s32 ? 12] ? 174
0? s3 ?9

反推回去即可得最优解为: x1* ? 0 , x2* ? 0 , x3* ? 9 , 最大值为: max z ? f1 (9) ? 174 作业 P214 1,5(1 逆推,2 顺推)

例 1:机器负荷分配问题 某公司新购进 1000 台机床,每台机床都可在高、低两种不同的负荷下进行 生产,设在高负荷下生产的产量函数为 g(x)=10x(单位:百件) ,其中 x 为投入 生产的机床数量, 年完好率为 a=0.7; 在低负荷下生产的产量函数为 h(y)=6y (单 位:百件) ,其中 y 为投人生产的机床数量,年完好率为 b=0.9。计划连续使用 5 年,试问每年如何安排机床在高、低负荷下的生产计划,使在五年内生产的产 品总产量达到最高。 解:该问题可看作一个 5 阶段决策问题,一个年度就是一个阶段。 状态变量 sk 取为第 k 年度度初具有的完好机床台数。 决策变量 xk 为第 k 年度中分配在高负荷下生产的机器台数,则 yk=sk-xk 为 第 k 年度中分配在低负荷下生产的机器台数(假定 xk、sk 皆为连续变量) 。 状态转移方方程为:sk+1=axk+b(sk-xk)=0.7xk+0.9(sk-xk) 第 k 年度的产量为:vk(sk,xk)=10xk+6(sk-xk) 最优值函数 f k (sk ) 表示拥有机床数为 sk 时,从第 k 年度至第五年度采取最 优分配方案进行生产时所获得的最大总产量。 则动态规划的基本方程为:

? ?g ( xk ) ? h(sk ? xk ) ? f k ?1 (sk ?1 )? ? f k ( sk ) ? max xk ? ? ? f n?1 ( sn ?1 ) ? 0
下面第 5 年度开始,用逆推归纳法进行计算。 1)k=5 时,有

f5 ( s5 ) ? max ? g ( x5 ) ? h( s5 ? x5 ) ? f 6 ( s6 )?
0 ? x5 ? s5

? max ?10 x5 ? 6( s5 ? x5 ) ? 0?
0 ? x5 ? s5

? max ?4 x5 ? 6 s5 ?
0 ? x5 ? s5

因 为 f 5 (s5 ) 是 x5 的 单 调 增 加 函 数 , 故 的 最 大 解 为 x5 * ? s5 , 相 应 有 f 5 (s5 ) =10s5。 2) k=4 时,有

f 4 ( s4 ) ? max ? g ( x4 ) ? h( s4 ? x4 ) ? f 5 ( s5 )?
0? x4 ? s4

? max ?10 x4 ? 6(s4 ? x4 ) ? f5 (0.7 x4 ? 0.9(s4 ? x4 ))?
0? x4 ? s4

? max ?10 x4 ? 6(s4 ? x4 ) ? 10(0.7 x4 ? 0.9( s4 ? x4 ))?
0? x4 ? s4

? max ?2 x4 ? 15s4 ?
0? x4 ? s4

因 为 f 4 ( s4 ) 是 x4 的 单 调 增 加 函 数 , 故 的 最 大 解 为 x4 * ? s4 , 相 应 有

f 4 ( s4 ) =17s 。
4

3) k=3 时,有

f3 ( s3 ) ? max ? g ( x3 ) ? h( s3 ? x3 ) ? f 4 ( s4 )?
0 ? x3 ? s3

? max ?10 x3 ? 6( s3 ? x3 ) ? f 4 (0.7 x3 ? 0.9( s3 ? x3 ))?
0? x3 ? s3

? max ?10 x3 ? 6( s3 ? x3 ) ? 17(0.7 x3 ? 0.9( s3 ? x3 ))?
0? x3 ? s3 0? x3 ? s3

? max ?0.6 x3 ? 21.3s3?
因 为 f 3 ( s3 ) 是 x3 的 单 调 增 加 函 数 , 故 的 最 大 解 为 x3 * ? s3 , 相 应 有 f 3 ( s3 ) =21.9s3。

4) 当 k=2 时,有

f 2 ( s2 ) ? max ? g ( x2 ) ? h( s2 ? x2 ) ? f3 ( s3 )?
0 ? x2 ? s2

? max ?10 x2 ? 6( s2 ? x2 ) ? f 3 (0.7 x2 ? 0.9( s2 ? x2 ))?
0? x2 ? s2

? max ?10 x2 ? 6( s2 ? x2 ) ? 21.9(0.7 x2 ? 0.9( s2 ? x2 ))?
0? x2 ? s2

? max ??0.38 x2 ? 25.71s2 ?
0? x2 ? s2

因 为 f 2 ( s2 ) 是 x2 的 单 调 减 少 函 数 , 故 的 最 大 解 为 x2 * ? 0 , 相 应 有 f 2 ( s2 ) =25.71s2。 5) 当 k=1 时,有

f1 ( s1 ) ? max ? g ( x1 ) ? h( s1 ? x1 ) ? f 2 ( s2 )?
0? x1 ? s1

? max ?10 x1 ? 6( s1 ? x1 ) ? f 2 (0.7 x1 ? 0.9( s1 ? x1 ))?
0 ? x1 ? s1

? max ?10 x1 ? 6( s1 ? x1 ) ? 25.71(0.7 x1 ? 0.9( s1 ? x1 ))?
0 ? x1 ? s1 0 ? x1 ? s1

? max ??1.142 x1 ? 29.139 s1?
因 为 f 1 (s1 ) 是 x1 的 单 调 减 少 函 数 , 故 的 最 大 解 为 x1* ? 0 , 相 应 有 f 1 (s1 ) =29.139s1。 由于第 l 阶段的初始状态 s1 是给定的,即 s1=1000,因此最优目标函数值为 f 1 (s1 ) ? f 1 (1000) =29139(百件) 。 计算结果表明:最优策略为 x1* ? 0 , x2 * ? 0 , x3 * ? s3 , x4 * ? s4 , x5 * ? s5 。 即前两年应把年初全部完好机床投入低负荷生产,后三年应把年初全部完好机 床投入高负荷生产。这样所得的产量最高,其最高产量为 29139 百件产品。同 时,从求解过程还可反过来确定每年年初的状态,即每年年初所拥有的完好机 器台数。已知 s1=1000,于是可得:

s2 ? 0.7 x1 ? 0.9( s1 ? x1 ) ? 0.9s1 ? 900(台) s3 ? 0.7 x2 ? 0.9( s2 ? x2 ) ? 0.9s2 ? 810(台) s4 ? 0.7 x3 ? 0.9( s3 ? x3 ) ? 0.7 s3 ? 567(台) s5 ? 0.7 x4 ? 0.9( s4 ? x4 ) ? 0.7 s4 ? 397(台) s6 ? 0.7 x5 ? 0.9( s5 ? x5 ) ? 0.7 s5 ? 278(台)
由此可知最优的决策过程是:第一年将全部 1000 台机器全部投入到低负荷 下进行生产,第一年末机床完好数是 900 台,第二年将 900 台机器继续投入到 低负荷下进行生产,第二年末机床完好数成为 810 台,第三年改变策略将这 810 台机床全部投入到高负荷下进行生产,第三年末机床完好数为 567 台,第四年 将这 567 台机床全部投入到高负荷下进行生产,第四年末机床完好数成为 397 台,第五年将这 397 台机床投入到高负荷下进行生产,这样第五年末剩下的完 好机床数为 278 台,五年共生产产品 29139(百件) 。

二、生产与存储问题 例 2:某企业通过市场调查,估计今后四个时期市场对某种产品的需要量如 下表: 时期(k) 需要量(dk) 1 2(单位) 2 3 3 2 4 4

假定不论在任何时期,生产每批产品的固定成本费为 3(千元),若不生产, 则为零;生产单位产品成本费为 1(千元);每个时期生产能力所允许的最大生产 批量为不超过 6 个单位,则任何时期生产 x 个单位产品的成本费用为: 若 0<x≤6 , 则生产总成本=3 十 1·x 若 x=0 , 则生产总成本=0 又设每个时期末未销售出去的产品,在一个时期内单位产品的库存费用为 0.5(千元),同时还假定第 1 时期开始之初和在第 4 个时期之末,均无产品库存。 现在我们的问题是;在满足上述给定的条件下,该厂如何安排各个时期的生产 与库存,使所花的总成本费用最低? 解:我们将四个时期分为 4 个阶段,设 k 为阶段变量, k=1,2,3,4。 状态变量为 sk,它表示在第 k 个阶段末该产品的库存量。 决策变量为 xk,它表示在第 k 阶段的生产量。 则状态转移方程为:sk-1= sk-xk +dk。 在 第 k 个 阶 段 生 产 准 备 成 本 为 :

xk ? 0 ?0, ? ck ( xk ) ? ?3 ? 1 xk xk ? 1, 2,? , 6 ?? xk ? 6 ?
第 k 个阶段结束时有库存量 sk 所需的存贮费用为: hk ( sk ) 故第 k 个阶段的总成本费用为 ck ( xk ) ? hk ( sk ) 。 则其顺序递推关系式:

? 0.5sk 。

f k ( sk ) ? min [ck ( xk ) ? hk ( sk ) ? f
0 ? xk ?? k

k ?1

( sk ?1 )] k ? 2, 3, 4

? min [ck ( xk ) ? hk ( sk ) ? f
0? xk ?? k

k ?1

( sk ? d k ? xk )]

其中 ? k 边界条件

? min( sk ? d k , 6)
f 0 ( s0 ) ? 0 , f 1 ( s1 ) ? min [c1 ( x1 ) ? h1 (s1 )] 。 0? x ??
1 1

1)当 k=1 时,由于

f 1 ( s1 ) ? min [c1 ( x1 ) ? h1 ( s1 )] ?
0? x1 ??1

0? x1 ? min( s1 ? 2,6)

min

[c1 ( x1 ) ? h1 ( s1 )]

对 s1 的可能取值在 0 至 M ? d1 ? 6 ? 2 ? 4 的值分别进行计算。

s1 ? 0, f 1 (0) ? min[c1 (2) ? h1 (0)] ? min[3 ? 1? 2 ? 0.5 ? 0] ? 5,
x1 ? 2 x2 ? 2

x1* ? 2
x1* ? 3

s1 ? 1, f 1 (1) ? min[c1 (3) ? h1 (1)] ? min[3 ? 1? 3 ? 0.5 ? 1] ? 6.5,
x2 ? 3 x2 ? 3

s1 ? 2, f 1 (2) ? min[c1 (4) ? h1 (2)] ? min[3 ? 1? 4 ? 0.5 ? 2] ? 8,
x2 ? 4 x2 ? 4

x1* ? 4
x1* ? 5
x1* ? 6

s1 ? 3, f 1 (3) ? min[c1 (5) ? h1 (3)] ? min[3 ? 1? 5 ? 0.5 ? 3] ? 9.5,
x2 ? 5 x2 ? 5

s1 ? 4, f 1 (4) ? min[c1 (6) ? h1 (4)] ? min[3 ? 1? 6 ? 0.5 ? 4] ? 11,
x2 ? 6 x2 ? 6

2)当 k=2 时,由于

f 2 ( s2 ) ? min [c2 ( x2 ) ? h2 ( s2 ) ? f 1 ( s1 )]
0 ? x2 ?? 2

?
4

0? x2 ? min( s2 ? 3,6)

min

[c2 ( x2 ) ? h2 ( s2 ) ? f 1 ( s2 ? 3 ? x2 )]

对 s2 的可能取值在 0 至

min[? d j , s1 ? M ? d 2 ] ? min[6, s1 ? 6 ? 3] ? 6
j ?3

( s1 最大可取到 4)的值分别进行计算。

s2 ? 0, f 2 (0) ? min [c2 ( x2 ) ? h2 (0) ? f 1 (3 ? x2 )]
0? x2 ?3

?c2 (0) ? h2 (0) ? f 1 (3) ? ?0 ? 0 ? 9.5 ? ?c (1) ? h (0) ? f (2) ? ? ? ? 2 ? ?4 ? 0 ? 8 ? 2 1 * ? min ? ? ? min ? ? ? 9.5, x2 ? 0 ?c2 (2) ? h2 (0) ? f 1 (1) ? ?5 ? 0 ? 6.5 ? ? ? ?6 ? 0 ? 5 ? ? ?c2 (3) ? h2 (0) ? f 1 (0) ? ?
s2 ? 1, f 2 (0) ? min [c2 ( x2 ) ? h2 (1) ? f 1 (4 ? x2 )]
0 ? x2 ? 4

?c2 (0) ? h2 (1) ? f 1 (4) ? ?0 ? 0.5 ? 11 ? ?c (1) ? h (1) ? f (3) ? ?4 ? 0.5 ? 9.5? 2 2 1 ? ? ? ? ? ? ? ? ? min ?c2 (2) ? h2 (1) ? f 1 (2) ? ? min ?5 ? 0.5 ? 8 ? ? 11.5, x2* ? 0 ?c (3) ? h (1) ? f (1) ? ?6 ? 0.5 ? 6.5? 2 2 1 ? ? ? ? 7 ? 0.5 ? 5 ? c (4) ? h (1) ? f (0) ? ? ? ? ? 2 1 ? 2 ?

s2 ? 2, f 2 (2) ? min[c2 ( x2 ) ? h2 (2) ? f 1 (5 ? x2 )]
1? x2 ? 5

?c2 (1) ? h2 (2) ? f 1 (4) ? ?4 ? 1 ? 11 ? ?c (2) ? h (2) ? f (3) ? ?5 ? 1 ? 9.5 ? 2 2 1 ? ? ? ? ? ? ? ? ? min ?c2 (3) ? h2 (2) ? f 1 (2) ? ? min ?6 ? 1 ? 8 ? ? 14, x2* ? 5 ?c (4) ? h (2) ? f (1) ? ?7 ? 1 ? 6.5? 2 2 1 ? ? ? ? 8 ? 1 ? 5 ? c (5) ? h (2 ) ? f ( 0 ) ? ? ? ? ? ? 2 2 1 ?

s2 ? 3, f 2 (3) ? min [c2 ( x2 ) ? h2 (3) ? f 1 (6 ? x2 )]
2 ? x2 ?6

?c2 (2) ? h2 (3) ? ?c (3) ? h (3) ? 2 2 ? ? ? min ?c2 (4) ? h2 (3) ? ?c (5) ? h (3) ? 2 ? 2 ? ?c2 (6) ? h2 (3) ?
3? x2 ? 6

f 1 (4) ? ?5 ? 1.5 ? 11 ? ?6 ? 1.5 ? 9.5? f 1 (3) ? ? ? ? ? ? ? f 1 (2) ? ? min ?7 ? 1.5 ? 8 ? ? 15.5, x2* ? 6 ?8 ? 1.5 ? 6.5 ? f 1 (1) ? ? ? ? 9 ? 1.5 ? 5 f 1 (0) ? ? ? ? ? ?

s2 ? 4, f 2 (4) ? min [c2 ( x2 ) ? h2 (4) ? f 1 (7 ? x2 )] ?c2 (3) ? h2 (4) ? ?c (4) ? h (4) ? ? 2 2 ? min ? ?c2 (5) ? h2 (4) ? ? ?c2 (6) ? h2 (4) ? f 1 (4) ? ?6 ? 2 ? 11 ? ? ? f 1 (3) ? ? ?7 ? 2 ? 9.5? * ? ? min ? ? ? 17.5, x2 ? 6 f 1 (2) ? ?8 ? 2 ? 8 ? ? f 1 (1) ? ?9 ? 2 ? 6.5 ? ? ?

s2 ? 5, f 2 (5) ? min [c2 ( x2 ) ? h2 (5) ? f 1 (8 ? x2 )]
4 ? x2 ? 6

?c2 (4) ? h2 (5) ? f 1 (4) ? ?7 ? 2.5 ? 11 ? ? ? ? ? ? min ?c2 (5) ? h2 (5) ? f 1 (3) ? ? min ?8 ? 2.5 ? 9.5? ? 19.5, ?c (6) ? h (5) ? f (2) ? ?9 ? 2.5 ? 8 ? ? ? 2 1 ? 2 ? x2* ? 6
s2 ? 6, f 2 (6) ? min [c2 ( x2 ) ? h2 (5) ? f 1 (9 ? x2 )]
5? x2 ? 6

?c2 (5) ? h2 (6) ? f 1 (4) ? ?8 ? 3 ? 11 ? ? min ? ? ? min ? ? ? 21.5, c (6) ? h (6) ? f (3) 9 ? 3 ? 9.5 ? ? ? 2 2 1 ? x2* ? 6
3)当 k=3 时,由于

f 3 ( s3 ) ? min [c3 ( x3 ) ? h3 ( s3 ) ? f 2 ( s2 )]
0? x3 ?? 3

?

0? x1 ? min( s3 ? d3 ,6)

min

[c3 ( x3 ) ? h3 ( s3 ) ? f 2 ( s3 ? 2 ? x3 )]
? M ? d3 ] ? min[4, 6 ? 6 ? 2] ? 4

对 s3 的可能取值在 0 至 min[ d 4 , s2

( s2 最大可取到 6)的值分别进行计算。

s3 ? 0, f 3 (0) ? min [c3 ( x3 ) ? h3 (0) ? f 2 (2 ? x2 )]
0? x3 ? 2

?c2 (0) ? h2 (0) ? f 2 (2) ? ?0 ? 0 ? 14 ? ? ? ? ? ? min ?c2 (1) ? h2 (0) ? f 2 (1) ? ? min ?4 ? 0 ? 11.5? ? 14, ?c (2) ? h (0) ? f (0) ? ?5 ? 0 ? 9.5 ? ? ? ? 2 2 2 ? x3* ? 0
s3 ? 1, f 3 (1) ? min[c3 ( x3 ) ? h3 (1) ? f 2 (3 ? x2 )]
0? x3 ?3

?c2 (0) ? h2 (1) ? f 2 (3) ? ?0 ? 0.5 ? 15.5? ?c (1) ? h (1) ? f (2) ? ? ? ? 2 ? ?4 ? 0.5 ? 14 ? 2 2 ? min ? ? ? min ? ? ? 16, c (2) ? h (1) ? f (1) 5 ? 0.5 ? 11.5 2 2 ? 2 ? ? ? ? ? ?6 ? 0.5 ? 9.5 ? ? ?c2 (3) ? h2 (1) ? f 2 (0) ? ? x3* ? 0或3

s3 ? 2, f 3 (2) ? min [c3 ( x3 ) ? h3 (2) ? f 2 (4 ? x2 )]
0 ? x3 ? 4

?c2 (0) ? h2 (2) ? f 2 (4) ? ?0 ? 1 ? 17.5 ? ?c (1) ? h (2) ? f (3) ? ?4 ? 1 ? 15.5? 2 2 2 ? ? ? ? ? ? ? ? ? min ?c2 (2) ? h2 (2) ? f 2 (2) ? ? min ?5 ? 1 ? 14 ? ? 17.5, ?c (3) ? h (2) ? f (1) ? ?6 ? 1 ? 11.5 ? 2 2 ? 2 ? ? ? ? ? ?7 ? 1 ? 9.5 ? ? ?c2 (4) ? h2 (2) ? f 2 (0) ? ? x3* ? 4

s3 ? 3, f 3 (3) ? min[c3 ( x3 ) ? h3 (3) ? f 2 (5 ? x2 )]
0? x3 ? 5

?c2 (0) ? h2 (3) ? f 2 (5) ? ?0 ? 1.5 ? 19.5 ? ?c (1) ? h (3) ? f (4) ? ?4 ? 1.5 ? 17.5 ? 2 2 2 ? ? ? ? ? ? ? ? ? min ?c2 (2) ? h2 (3) ? f 2 (3) ? ? min ?5 ? 1.5 ? 15.5 ? ? 19, ?c (3) ? h (3) ? f (2) ? ?6 ? 1.5 ? 14 ? 2 2 2 ? ? ? ? 7 ? 0.5 ? 11 .5 ? c (4) ? h (3) ? f (1) ? ? ? ? ? ? 2 2 2 ? x3* ? 5

s3 ? 4, f 3 (4) ? min [c3 ( x3 ) ? h3 (4) ? f 2 (6 ? x2 )]
0? x3 ? 6

?c2 (0) ? h2 (4) ? f 2 (6) ? ?0 ? 2 ? 21.5? ?c (1) ? h (4) ? f (5) ? ? 4 ? 2 ? 19.5 ? 2 2 ? 2 ? ? ? ?c2 (2) ? h2 (4) ? f 2 (4) ? ?5 ? 2 ? 17.5 ? ? ? ? ? ? min ?c2 (3) ? h2 (4) ? f 2 (3) ? ? min ?6 ? 2 ? 15.5 ? ? 20.5, ?c (4) ? h (4) ? f (2) ? ?7 ? 2 ? 14 ? 2 2 2 ? ? ? ? ?c2 (5) ? h2 (4) ? f 2 (1) ? ?8 ? 2 ? 11.5 ? ? ? ?9 ? 2 ? 9.5 ? ? ? ?c2 (6) ? h2 (4) ? f 2 (0) ? x3* ? 6
4)当 k=4 时,由于要求的第 4 个阶段结束时的库存量为 0,即 s4=0,因此只 须计算

f 4 (0) ? min [c4 ( x4 ) ? h4 (0) ? f 3 (s3 )] ? min[c4 ( x4 ) ? h4 (0) ? f 3 (4 ? x4 )]
0 ? x4 ? 4 0 ? x1 ? 4

?c4 (0) ? h2 (0) ? f 3 (4) ? ?0 ? 0 ? 20.5? ? ? ?4 ? 0 ? 19 ? ?c4 (1) ? h2 (0) ? f 3 (3) ? ? ? ? ? ? ? ? min ?c4 (2) ? h2 (0) ? f 3 (2) ? ? min ?5 ? 0 ? 17.5 ? ?c (3) ? h (0) ? f (1) ? ?6 ? 0 ? 16 ? 4 2 3 ? ? ? ? 7 ? 0 ? 14 ? ? ? ? c (4) ? h (0) ? f (0) ? ? 2 3 ? 4 ? ? 20.5 , x4* ? 0
再按计算的顺序反推回去,可得到每个时期的确最优生产决策为:

x1* ? 5, x2* ? 0, x3* ? 6, x4* ? 0 。其相应的最小总成本为 20.5 千元。
三、设备更新问题 例 3: 设某企业在第一年初购买一台新设备, 该设备在五年内的年运行收益、 年运行费用及更换新设备的净费用如下表: (单位:万元) 年份(k) 役龄(t) 第一年 运行收益 g k (t ) 运行费用 rk (t ) 更新费用 ck (t )

0 22 6 18 0 23 6 19 第二年 1 21 8 22 0 23 5 19 第三年 1 21 7 23 2 18 10 28 0 24 5 20 1 22 7 24 第四年 2 19 10 30 3 16 15 38 0 25 4 20 1 23 6 24 第五年 2 20 9 30 3 17 14 38 4 14 20 48 试为该企业制定一个五年中的设备更新策略,使得企业在五年内总收益达到 最大? 解:这是一个 n=5 阶段且初始状态为 s1=0 的设备更新问题,有关符号假定如 上,目标是要求 f1 (0) ,下面用逆推归纳法进行计算。

f k ( sk ) ? max ?vk ( sk , xk ) ? f k ?1 ( sk ?1 )?
xk

xk ? K ? ? g k ( sk ) ? rk ( sk ) ? f k ?1 ( sk ?1 ), ? max ? ? g (0) ? r (0) ? c ( s ) ? f ( s ), x ? R k k k k ?1 k ?1 k ? k ?
1)当 k=5 时,有

? x5 ? K : g5 (0) ? r5 (0) ? f 5 (0) ? max ? ? ? x5 ? R : g5 (0) ? r5 (0) ? c5 (0) ? ? K : 25 ? 4 ? ? max ? x5* ? K ? ? 21, ? R : 25 ? 4 ? 20 ?

? K : g 5 (1) ? r5 (1) ? f5 (1) ? max ? ? R : g (0) ? r (0) ? c (1) ? 5 5 5 ? ? K : 23 ? 6 ? ? max ? x5* ? K ? ? 17, ? R : 25 ? 4 ? 24 ?

? K : g5 (2) ? r5 (2) ? f5 (2) ? max ? ? R : g (0) ? r (0) ? c (2) 5 5 5 ? ? ? K : 20 ? 9 ? ? max ? x5* ? K ? ? 11, ? R : 25 ? 4 ? 30?
? K : g5 (3) ? r5 (3) ? f5 (3) ? max ? ? R : g (0) ? r (0) ? c (3) ? 5 5 5 ? ? K :17 ? 14 ? ? max ? x5* ? K ? ? 3, ? R : 25 ? 4 ? 38?

? K : g 5 (4) ? r5 (4) ? f 5 (4) ? max ? ? R : g (0) ? r (0) ? c (4) 5 5 5 ? ? ? K :14 ? 20 ? ? max ? x5* ? K ? ? ?6, ? R : 25 ? 4 ? 48 ?
2)当 k=4 时,有

? x4 ? K : g 4 (0) ? r4 (0) ? f 5 (1) ? f 4 (0) ? max ? ? ? x4 ? R : g 4 (0) ? r4 (0) ? c4 (0) ? f 5 (1) ? ? K : 24 ? 5 ? 17 ? ? max ? x4* ? K ? ? 36, ? R : 24 ? 5 ? 20 ? 17 ?

? K : g 4 (1) ? r4 (1) ? f 5 (2) ? f 4 (1) ? max ? ? ? R : g 4 (0) ? r4 (0) ? c4 (1) ? f 5 (1) ? ? K : 22 ? 7 ? 11 ? ? max ? x4* ? K ? ? 26, ? R : 24 ? 5 ? 24 ? 17 ?
? K : g 4 (2) ? r4 (2) ? f5 (3) ? f 4 (2) ? max ? ? R : g (0) ? r (0) ? c (2) ? f (1) ? 4 4 4 5 ? ? K :19 ? 10 ? 3 ? ? max ? x4* ? K ? ? 12, ? R : 24 ? 5 ? 30 ? 17 ?
? K : g 4 (3) ? r4 (3) ? f5 (4) ? f 4 (3) ? max ? ? ? R : g 4 (0) ? r4 (0) ? c4 (3) ? f 5 (1) ? ? K :16 ? 15 ? 6 ? ? max ? x4* ? R ? ? ?2, ? R : 24 ? 5 ? 38 ? 17 ?
3)当 k=3 时,有

? x ? K : g3 (0) ? r3 (0) ? f 4 (1) ? f3 (0) ? max ? 3 ? ? x3 ? R : g 3 (0) ? r3 (0) ? c3 (0) ? f 4 (1) ? ? K : 23 ? 5 ? 26 ? ? max ? x3* ? K ? ? 44, ? R : 23 ? 5 ? 19 ? 26 ?

? K : g3 (1) ? r3 (1) ? f 4 (2) ? f 3 (1) ? max ? ? ? R : g3 (0) ? r3 (0) ? c3 (1) ? f 4 (1) ? ? K : 21 ? 7 ? 12 ? ? max ? x3* ? K ? ? 26, ? R : 23 ? 5 ? 23 ? 26 ?
? K : g3 (2) ? r3 (2) ? f 4 (3) ? f3 (2) ? max ? ? ? R : g3 (0) ? r3 (0) ? c3 (2) ? f 4 (1) ? ? K :18 ? 10 ? 2 ? ? max ? x3* ? R ? ? 16, ? R : 23 ? 5 ? 28 ? 26 ?
4)当 k=2 时,有

? x2 ? K : g 2 (0) ? r2 (0) ? f3 (1) ? f 2 (0) ? max ? ? ? x2 ? R : g 2 (0) ? r2 (0) ? c2 (0) ? f 3 (1) ? ? K : 23 ? 6 ? 26 ? ? max ? x2* ? K ? ? 44, ? R : 23 ? 6 ? 19 ? 26 ?
? K : g 2 (1) ? r2 (1) ? f3 (2) ? f 2 (1) ? max ? ? ? R : g 2 (0) ? r2 (0) ? c3 (1) ? f3 (1) ? ? K : 21 ? 8 ? 16 ? ? max ? x2* ? K ? ? 28, ? R : 23 ? 6 ? 22 ? 26 ?
5)当 k=1 时,有

? x ? K : g1 (0) ? r1 (0) ? f 2 (1) ? f1 (0) ? max ? 1 ? ? x1 ? R : g1 (0) ? r1 (0) ? c1 (0) ? f 2 (1) ? ? K : 22 ? 6 ? 28 ? ? max ? x1* ? K ? ? 44, ? R : 22 ? 6 ? 19 ? 28?
因为

f1 (0)

* =44 , x1 ? K , 由 上 述 计 算 过 程 逆 推 回 去 可 知

x2* ? K , s2 ? 1, f 2 (1) ? 28



x3* ? R, s3 ? 2, f 3 (2) ? 16



x4* ? K , s4 ? 1, f 4 (1) ? 26 ; x5* ? K , s5 ? 2, f 5 (2) ? 11 。即最优的设备更新策
略是{K,K,R,K,K},也就是该企业在第一年初购买一台新设备后连续使用两 年,第三年初再购买一台新设备一直使用到第五年底,这样可使得企业在五年

内的达到最大为方便用 44 万元。 四、背包问题 例 4:设有一辆栽重为 10 吨的卡车,用以装载三种货物,每种货物的单位 重量及单件价值如表所示,问各种货物应装多少件,才能既不超过总重量又使 总价值最大?

货物 单位重量 单件价值

1 3 4

2 4 5

3 5 6

设 xj 表示第 j 种货物的件数(j=1,2,3),则问题可归结为

max z ? 4 x1 +5x2 ? 6x3
s.t

?3 x1 ? 4x2 ? 5x3 ? 10 ? ? x1 , x2 , x3 ? 0整数

解: 用动态规划方法来解,问题变为求 f 3 (10) 。

f3 (10) ?

3 x1 ? 4x2 ?10-5x3

max

[6x3 ? f 2 ( s2 )]

?0 ? f 2 (10) ? ? ? ? max[6x3 ? f 2 (10-5x3 )] ? max ?6 ? f 2 (5) ? 5x3 ?10 ?12 ? f (0) ? ? 2 ?
必须先算出 f 2 (10) ,
3 x1 ?10- 4x2

f 2 (5) , f 2 (0) 。而

f 2 (10) ? max [5x2 ? f1 ( s1 )] ?0 ? f1 (10) ? ? ? ? max[5 x2 ? f1 (10-4x2 )] ? max ?5 ? f1 (6) ? 4 x2 ?10 ?10 ? f (2) ? ? 1 ?

f 2 (5) ? max [5x2 ? f1 ( s1 )]
3 x1 ?5-4x2

?0 ? f1 (5) ? ? max[5 x2 ? f1 (5-4x2 )] ? max ? ? 4 x2 ? 5 5 ? f ( 1) ? 1 ?

f 2 (0) ? max [4 x1 +5x2 ] ? max [5x2 ? f1 ( s1 )]
3 x1 ? 4x2 ? 0 3 x1 ? 0-4x2

? max[5 x2 ? f1 (10-4x2 )] ? max ?0 ? f1 (0)? ? f1 (0)
4 x2 ? 0

必须先算出

f1 (10) , f1 (6) , f1(5) , f1 (2) , f1 (1) , f1(0) 。而

s f1 (s1 ) ? max( 4 x1 ) ? 4 ? [ 1 ] 3 x1 ? s1 3
相应的最优策略为 x 1 ? [
s1 ] ,于是得到 3

f1(10) ? 4?3 ?12, x1* ? 3
f1(6) ? 4?2 ?8, x1*? 2

f1(5) ?4?1?4, x1*?1

f1(2) ?4?0?0, x1*?0
f1 (1) ? 4 ? 0 ? 0 ,
从而

x1 * ? 0

f1 (0) ? 4 ? 0 ? 0 , x1* ? 0
?0 ? f1 (10) ? ?0 ? 12? ? ? ? ? f 2 (10) ? max ?5 ? f1 (6) ? ? max ?5 ? 8 ? ? 13, x2 * ? 1 ?10 ? f (2) ? ?10 ? 0? ? ? 1 ? ?

?0 ? f1 (5) ? ?0 ? 4 ? f 2 (6) ? max ? ? max ? ? ? ? 5 , x2 * ? 1 ?5 ? 0 ? ?5 ? f1 (1) ?

f 2 (0) ? max ?0 ? f1 (0)? ? 0, x2 * ? 0
最后得到:

?0 ? f 2 (10) ? ?0 ? 13 ? ? ? ? ? f 3 (10) ? max ?6 ? f 2 (5) ? ? max ?6 ? 5 ? ? 13, x3 * ? 0 ?12 ? f (0) ? ?12 ? 0 ? ? ? 2 ? ?
所以最优装入方案为: x1
*

? 2, x2* ? 1, x3* ? 0 ,最大使用价值为 13。


相关文章:
动态规划-例题众多-详细讲解._图文.ppt
动态规划-例题众多-详细讲解._职业技术培训_职业教育_教育专区。动态规划 参与
动态规划-例题众多-详细讲解_图文.ppt
动态规划-例题众多-详细讲解 - 动态规划 参与竞赛的同学应由竞争关系和独立关系
动态规划习题.doc
动态规划习题 - 第七章 动态规划 规划问题的最终目的就是确定各决策变量的取值,
运筹学动态规划习题_图文.ppt
运筹学动态规划习题 - 习题三 一、某工厂购进100台机器,准备生产A、B 两种
动态规划讲解大全(含例题及答案)_图文.pdf
动态规划讲解大全(含例题及答案) - 动态规划讲解大全 动态规划(dynamic
动态规划习题详解.doc
动态规划习题详解_文学_高等教育_教育专区。动态规划习题 动态规划动态规划是运筹
动态规划练习题(含答案).pdf
动态规划练习题(含答案) - 动态规划练习题 USACO 2.2 Subset
动态规划讲解大全(含例题及答案).doc
动态规划讲解大全(含例题及答案)_IT认证_资格考试/认证_教育专区。最全面、最简练的动态规划讲解,并还有例题,答案适用于C语言学习,数学建模,数据结构等学习 ...
动态规划习题_图文.ppt
动态规划习题 - 动态规划习题课 动态规划理论与方法小结 建立动态规划模型的基本
动态规划习题课_图文.ppt
动态规划习题课 资源分配问题例1 某公司拟将500万元的资本投入所属的甲、乙、丙
动态规划_例题众多_详细讲解_图文.ppt
动态规划_例题众多_详细讲解_工学_高等教育_教育专区。由众多的例题来分别说明动态规整的众多应用方向。 动态规划参与竞赛的同学应由竞争关系和独立关系 (你做你的...
动态规划习题.pdf
动态规划习题 - 例 1:最短路线问题 某工厂需要把一批货物从城市 A 运到城市
动态规划练习题.doc
动态规划练习题 - 开心的金明 题目描述 金明今天很开心,家里购置的新房就要领钥
动态规划习题概要.doc
动态规划习题概要 - 第七章 动态规划 规划问题的最终目的就是确定各决策变量的取
动态规划-例题众多-详细讲解._图文.ppt
动态规划-例题众多-详细讲解. - 动态规划 参与竞赛的同学应由竞争关系和独立关
动态规划练习例题_6944.pdf
动态规划练习例题_6944 - 动态规划练习例题 在棋盘上移动 ? 在一个n×n
动态规划习题答案.doc
动态规划习题答案 - 由复旦大学出版社出版,傅家良主编的运筹学方法与模型第八章动态规划习题答案
第3章 动态规划_习题课1_图文.ppt
第3章 动态规划_习题课1 - 第3章 动态规划 习题课 ? ? ? ? 动态规
基本动态规划问题的扩展(国家集训队 俞玮).doc
基本动态规划问题的扩展(国家集训队 俞玮) - 基本动态规划问题的扩展 应用动态规划可以有效的解决许多问题, 其中有许多问题的数学模型, 尤其对一些自从 57 年就...
动态规划习题集全.doc
动态规划习题集全 - 动态规划专题训练 护卫队 【问题描述】 护卫车队在一条单行
更多相关文章: