动态规划应用举例(书第9章)

u5* = s5 = 397, s6 = 0.7u5* + 0.9(s5 − u5* ) = 0.7u5* = 278 。 注：当要求第 5 年结束时，有完好机器 500 台，则
s6
=
au5
+ b(s5
− u5 )
=
500 ⇒
u5
=
500 − 5s5 3
2
得递推关系：
⎧⎪ ⎨ ⎪⎩
fk (sk ) =
（都投入高负荷）
f4 (s4 ) = 0m≤u4a≤xs4{8u4 + 5(s4 − u4 ) + 8(0.7u4 + 0.9(s4 − u4 ))}
u4* = s4
= 0m≤u4a≤xs4{1.4u4 + 12.2s4} = 13.6s4
（都投入高负荷）
u3* = s3
f3 (s3 ) = 0m≤u3a≤xs3{8u3 + 5(s3 − u3 ) + 13.6(0.7u3 + 0.9(s3 − u3 ))} = 17.5s3
令 hiλ (xi ) = myia≥0x{gi (xi , yi ) − λ yi} ，设最优解 yiλ (xi ) 。则得一种资源分配问题：
3
max z = h1λ (x1) + " + hnλ (xn ) s.t. x1 + " + xn = a
xj , j = 1,", n
(4.3.1)
对于(4.3.1)，可用动态规划方法求解，设得到的解为 xiλ ,i = 1,", n ，则得 yiλ = yiλ (xiλ ),i = 1,", n 。若
s.t. sk+1 = auk + b(sk − uk ), k = 2,", n − 1 0 ≤ uk ≤ sk , k = 1,", n
阶段：一年作为一个阶段， k = 1,", n ；
状态变量 sk ：第 k 年初的的资源数量； 决策变量 uk ：第 k 年分配给 A 生产的资源数量， 0 ≤ uk ≤ sk ； 状态转移方程： sk+1 = auk + b(sk − uk ) ；
静态规划： 设 uk ：第 k 年投入 A 生产的资源数，sk ：第 k 年初的资源数，则第 k+1 年初的资源数 sk+1 = auk + b(sk − uk ) ， 第 k 年的产量 g(uk ) + h(sk − uk ) ，得模型：
1
动态规划：
n
∑ max g(uk ) + h(sk − uk ) k =1
（都投入低负荷）
由 s1 = 1000 得
u1* = 0, s2 = 0.7u1* + 0.9(s1 − u1* ) = 0.9s1 = 900 ， u2* = 0, s3 = 0.7u2* + 0.9(s2 − u2* ) = 0.9s2 = 810 ，
u3* = s3 = 810, s4 = 0.7u3* + 0.9(s3 − u3* ) = 0.7u3* = 567 ， u4* = s4 = 567, s5 = 0.7u4* + 0.9(s4 − u4* ) = 0.7u4* = 397 ，
（都投入高负荷）
u2* =0
f2 (s2 ) = 0m≤u2a≤xs2{8u2 + 5(s2 − u2 ) + 17.5(0.7u3 + 0.9(s3 − u3 ))} = 20.8s2
（都投入低负荷）
u1* =0
f1(s1) = 0m≤ua1≤xs1{8u1 + 5(s1 − u1) + 20.8(0.7u1 + 0.9(s1 − u1))} = 23.7s1
视为两种资源的分配：
max z = g1(x1, y1) + " + gn (xn ,, yn ) s.t. x1 + " + xn = X
y1 + " + yn = Y aX + bY ≤ Z x j , y j ≥ 0, j = 1,", n
视为资金的分配：
若分配数量为 zi 的资金给第 i 种产品的生产，则可得收益
⎧⎪ fk (sk ) ⎨
=
max {g
0≤uk ≤ sk
k
(uk
)
+
fk +1 (sk
− uk )}, k
=
n," ,1
⎪⎩ fn+1 (sn+1 ) = 0
最终求得 f1(a) 即为最大收益。 例 5.1.1 P213
a=5，可用表格求解。
注：当 a=4 时，可利用已有结果求得。
5.1.2 一维资源有回收的分配问题
⎧⎪ fk (sk ) = ⎨
max
0≤uk ≤ sk
{8uk
+ 5(sk
− uk ) +
fk+1 (0.7uk
+ 0.9(sk
− uk ))}, k
= 5,",1
⎪⎩ f6 (s6 ) = 0
则
u5* = s5
f5 (s5 ) = 0m≤u5a≤xs5{8u5 + 5(s5 − u5 )} = 0m≤u5a≤xs5{3u5 + 5s5} = 8s5
引入 Lagrange 乘数，将二种资源分配问题转化为一维资源分配问题。
给定 λ ，考虑问题：
max z = g1(x1, y1) + " + gn (xn ,, yn ) − λ( y1 + " + yn ) s.t. x1 + " + xn = a
x j , y j ≥ 0, j = 1,", n
⎧⎪ ⎨
fk
(sk
)
=
max
0≤uk ≤ sk
{g
(uk
)
+
h(sk
− uk ) +
fk +1 (auk
+ b(sk
− uk ))}, k
=
n," ,1
⎪⎩ fn+1 (sn+1 ) = 0
最终求得 f1(s1) 即为最大收益。
例 5.1.2 P217 g(u) = 8u, h(u) = 5u, a = 0.7,b = 0.9, s1 = 1000, n = 5
决策变量 (uk , vk ) ： uk 分配给第 k 种产品的第一种资源的数量(即 uk = xk )， 0 ≤ uk ≤ sk ； vk 分配给第 k 种产品的第二种资源的数量(即 vk = yk )， 0 ≤ vk ≤ tk ；
状态转移方程： sk+1 = sk − uk ， tk+1 = tk − vk ； 指标函数： vk ((sk ,tk ), (uk , vk )) = gk (uk , vk ) ，子过程指标函数为加式； 最优值函数 fk (sk ,tk ) ：以数量为 sk 的第一种资源和数量为 tk 的第二种资源分配给第 k 种产品至第 n 种产 品的生产时可获得的最大收益。
max z = g1(x10 , y1) + " + gn (xn0 ,, yn ) s.t. y1 + " + yn = b
y j ≥ 0, j = 1,", n
设得最优解 y0 = ( y10 ,", yn0 )T 。固定 y0 = ( y10 ,", yn0 )T ，求解一维资源分配问题：
max z = g1(x1, y10 ) + " + gn (xn , yn0 ) s.t. x1 + " + xn = a
设有数量为 s1 的某种资源，可投入 A 和 B 两种生产。对于 A 的生产，产品的年产量 g 和投入生产的 资源数量 u 的关系为 g=g(u)，这时资源的年完好率为 a，0<a<1, 即如果年初资源的数量为 u, 到年终时 完好的资源数为 au。对于 B 的生产，产品的年产量 h 和投入生产的机器数量 u 的关系为 h=h(u)，这时资 源的年完好率为 b，0<b<1, 即如果年初资源的数量为 u, 到年终时完好的资源数为 bu。试问，应当如何 决定每年投入 A 生产的资源数，使 n 年内产品的总产量达到最高。
n
n
∑ ∑ yiλ = b ，则 ( xλ , yλ ) 为原问题最优解，否则调整 λ (可利用插值法)，直到 yiλ = b 。
i =1
i =1
2．最优化，然后交替固定。
n
∑ 先固定 x0 = (x10 ,", xn0 )T ≥ 0 : xi0 = a ，求解一维资源分配问题： i =1
设得最优解 y1 = ( y11,", y1n )T 。重复，得到{xk , yk } ，则{xk , yk } 可收敛到原问题的局部最优解。
5.1.4 资金固定的分配问题
设有两种资源，用于生产 n 种产品。若分配数量为 xi 的第一种资源和数量为 yi 的第二种资源给第 i 种产品的生产，则可得收益 gi (xi, yi)。若第一种资源的价格为 a，第二种资源的价格为 b，现有总资金 Z。 问应如何分配资源，使生产 n 种产品的总收益最大？
x j ≥ 0, j = 1,", n
设得最优解 x1 = (x11,", x1n )T 。固定 x1 = (x11,", x1n )T ，求解一维资源分配问题：
max z = g1(x11, y1) + " + gn (x1n ,, yn ) s.t. y1 + " + yn = b