第五章 动态规划应用举例（书第9章） §5.1资源分配问题 将数量一定的一种或若干种资源（例如原材料、资金、机器设备、劳力、食品等），恰当得分配给 若干个使用者，使目标函数最优。 5.1.1一维资源无回收的分配问题 设有某种资源，总数量为α，用于生产n种产品。若分配数量为x的资源给第i种产品的生产，则 可得收益g(x)。问应如何分配资源，使生产n种产品的总收益最大？ 静态规划： maxz=8(x)+…+gn(xn) S.l.x+…+xn=a x,≥0，j=1,…,n 动态规划：设 阶段：把资源分配给一个产品的生产作为一个阶段，k=1,…,n: 状态变量s:分配给第k种产品至第n种产品的资源数量，0≤s≤a: 决策变量4：分配给第k种产品的资源数量（即山=x),0≤山≤S: 状态转移方程：S+=S-山： 指标函数：，4)=g4(),,4,,5,4,5)=之g,,)(加式) 最优值函数f(S):以数量为S,的资源分配给第k种产品至第种产品的生产时可获得的最大收益。 则得基本方程： f(s)=max{8x(u)+i+(-4)乃，k=n,…,1 (s)=0 最终求得f(a)即为最大收益。 例5.1.1P213 a=5,可用表格求解。 注：当=4时，可马上利用已有结果求得。当=6时，也可利用已有表格再补充数据求得。 5.1.2一维资源有回收的分配问题 设有数量为S1的某种资源，可投入A和B两种生产。对于A的生产，产品的年产量g和投入生产的 资源数量u的关系为g=g(),这时资源的年完好率为a,0<a<l,即如果年初资源的数量为山，到年终时 完好的资源数为au。对于B的生产，产品的年产量h和投入生产的机器数量u的关系为h=h(),这时资 源的年完好率为b,O<b<1,即如果年初资源的数量为4，到年终时完好的资源数为bu。试问，应当如何 决定每年投入A生产的资源数，使n年内产品的总产量达到最高。 静态规划： 设4：第k年投入A生产的资源数，S:第k年初的资源数，则第什1年初的资源数Sk1=a+b(s一4e), 第k年的产量g(4)+hs-,),得模型：
1 第五章 动态规划应用举例(书第 9 章) §5.1 资源分配问题 将数量一定的一种或若干种资源（例如原材料、资金、机器设备、劳力、食品等），恰当得分配给 若干个使用者，使目标函数最优。 5.1.1 一维资源无回收的分配问题 设有某种资源，总数量为 a，用于生产 n 种产品。若分配数量为 xi 的资源给第 i 种产品的生产，则 可得收益 gi (xi)。问应如何分配资源，使生产 n 种产品的总收益最大？ 静态规划： 1 1 1 max ( ) ( ) . . 0, 1, , n n n j z g x g x st x x a xj n = ++ ++= ≥ = " " " 动态规划：设 阶段：把资源分配给一个产品的生产作为一个阶段， k n =1, , " ； 状态变量 k s ：分配给第 k 种产品至第 n 种产品的资源数量，0 k ≤ s ≤ a ； 决策变量 k u ：分配给第 k 种产品的资源数量(即 k k u x = )，0 k k ≤ u s ≤ ； 状态转移方程： k kk 1 s s u + = − ； 指标函数： (, ) () kk k k k vsu gu = ， , 1 (, , ,, , ) () n kn k k n n n j j j k V su sus gu + = " = ∑ （加式） 最优值函数 ( ) k k f s ：以数量为 k s 的资源分配给第 k 种产品至第 n 种产品的生产时可获得的最大收益。 则得基本方程： 1 0 1 1 ( ) max { ( ) ( )}, , ,1 ( )0 k k kk k k k k k u s n n fs gu f s u k n f s + ≤ ≤ + + ⎧ = +−= ⎪ ⎨ ⎪⎩ = " 最终求得 1f ( ) a 即为最大收益。 例 5.1.1 P213 a=5，可用表格求解。 注：当 a=4 时，可马上利用已有结果求得。当 a=6 时，也可利用已有表格再补充数据求得。 5.1.2 一维资源有回收的分配问题 设有数量为 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 年内产品的总产量达到最高。 静态规划： 设 k u ：第 k 年投入 A 生产的资源数，k s ：第 k 年初的资源数，则第 k+1 年初的资源数 1 ( ) k k kk s au b s u + =+ − ， 第 k 年的产量 () ( ) k kk g u hs u + − ，得模型：
max2(g(u,)+hs.-4》 A=I s1.k1=a4k+b(s-4e),k=1,…,n-1 0≤4k≤Sw,k=1,…,n 动态规划： 阶段：一年作为一个阶段，k=1,…,n: 状态变量S:第k年初的的资源数量： 决策变量4：第k年分配给A生产的资源数量，0≤山≤S； 状态转移方程：Sk+1=a+b(Sk-山)； 指标函数：(，4)=g(u)+hs-4),n(S,4,,5,山，Si)=(g,)+hs-4》(加式) i= 最优值函数f(s):第k年初有数量为s的资源时，从第k年至第n年的最大总产量。 则得基本方程： (5x)=max {g(ux)+h(sx -ug)+f(aug +b(sx -u))),k=n,...,1 si ss (S)=0 最终求得(s)即为最大收益。 例5.1.2P217g(u)=8u,h(w)=5u,a=0.7,b=0.9,S=1000,n=5 f(s)=max{8uk+5(sk-4)+f+1(0.7uw+0.9se-4g)},k=5,…,1 0s4u55 f(S6)=0 则 fs)=max84,+5-4,}=max3,+5s,}=8s (都投入高负荷) f(s4)=max{8u+5(s,-4)+8(0.74+0.9(s4-4)} 424 =x1.4u+122,}136s, (都投入高负荷) = f(s3)=max{843+5(s3-4)+13.6(0.74+0.9(s3-43)}=17.53 (都投入高负荷) 的= f5(5,)=ma84+5(,-4)+17.50.74,+0.9(s,-4}=20.83, (都投入低负荷) =0 (s)=max{84,+5(s-4)+20.8(0.741+0.9(s,-4)}=23.7s (都投入低负荷) 由s,=1000得 4=0,52=0.74+0.9(s-4)=0.9s=900,4=0,s3=0.74+0.9(s2-4)=0.9s2=810, 4=S=810,s4=0.74+0.9(s3-4)=0.74=567,4=S4=567,s=0.74+0.9(s4-4)=0.74=397, 4=3=397,56=0.74+0.9(s-4)=0.74=278。 注：当要求第5年结束时，有完好机器500台，则 8=%,+65,-%)=50→4=090-500 3 2
2 1 1 max ( ( ) ( )) . . ( ), 1, , 1 0 , 1, , n k kk k k k kk k k gu hs u st s au b s u k n u sk n = + + − = +− = − ≤≤ = ∑ " " 动态规划： 阶段：一年作为一个阶段， k n =1, , " ； 状态变量 k s ：第 k 年初的的资源数量； 决策变量 k u ：第 k 年分配给 A 生产的资源数量，0 k k ≤ u s ≤ ； 状态转移方程： 1 ( ) k k kk s au b s u + =+ − ； 指标函数： (, ) () ( ) kk k k k k v s u gu hs u = +− ， , 1 ( , , , , , ) ( ( ) ( )) n kn k k n n n k k k j k V s u s u s gu hs u + = " = +− ∑ （加式） 最优值函数 ( ) k k f s ：第 k 年初有数量为 k s 的资源时，从第 k 年至第 n 年的最大总产量。 则得基本方程： 1 0 1 1 ( ) max { ( ) ( ) ( ( ))}, , ,1 ( )0 k k kk k k k k k k k u s n n f s g u h s u f au b s u k n f s + ≤ ≤ + + ⎧ = + −+ + − = ⎪ ⎨ ⎪⎩ = " 最终求得 1 1 f ( ) s 即为最大收益。 例 5.1.2 P217 1 gu uhu ua b s n ( ) 8 , ( ) 5 , 0.7, 0.9, 1000, 5 = == = = = 1 0 6 6 ( ) max {8 5( ) (0.7 0.9( ))}, 5, ,1 () 0 k k kk k k k k k k k u s fs u s u f u s u k f s + ≤ ≤ ⎧ = + −+ + − = ⎪ ⎨ ⎪⎩ = " 则 * 5 5 55 55 55 5 5 5 5 5 5 0 0 ( ) max {8 5( )} max {3 5 } 8 u s us us f s u su u s s = ≤≤ ≤≤ = +−= + = （都投入高负荷） 4 4 * 4 4 4 4 44 4 4 4 4 4 4 0 44 4 0 ( ) max {8 5( ) 8(0.7 0.9( ))} max {1.4 12.2 } 13.6 u s u s u s fs u s u u s u us s ≤ ≤ = ≤ ≤ = + −+ + − = += （都投入高负荷） * 3 3 3 3 33 3 3 3 3 3 3 3 0 ( ) max {8 5( ) 13.6(0.7 0.9( ))} 17.5 u s u s f s u su u su s = ≤ ≤ = + −+ + − = （都投入高负荷） * 2 2 2 0 22 2 2 2 3 3 3 2 0 ( ) max {8 5( ) 17.5(0.7 0.9( ))} 20.8 u u s f s u su u su s = ≤ ≤ = + −+ + − = （都投入低负荷） * 1 1 1 0 11 1 1 1 1 1 1 1 0 ( ) max{8 5( ) 20.8(0.7 0.9( ))} 23.7 u u s f s u su u su s = ≤ ≤ = + −+ + − = （都投入低负荷） 由 1s =1000 得 * ** 1 2 1 11 1 u s u su s = = + −= = 0, 0.7 0.9( ) 0.9 900， * ** 2 3 2 22 2 u s u su s = = + −= = 0, 0.7 0.9( ) 0.9 810， * * ** 33 4 3 33 3 u s s u su u == = + − = = 810, 0.7 0.9( ) 0.7 567 ， * * ** 44 5 4 44 4 u s s u su u == = + − = = 567, 0.7 0.9( ) 0.7 397， * * ** 55 6 5 55 5 u s s u su u == = + − = = 397, 0.7 0.9( ) 0.7 278 。 注：当要求第 5 年结束时，有完好机器 500 台，则 5 6 5 55 5 0.9 500 ( ) 500 3 s s au b s u u − = + − = ⇒=
得递推关系： f(s)=max{8ug+5(sk-4)+f+(0.7u+0.9(s-4)},k=4,…,1 0s丝≤虽 f5(s3)=max{8u+5(s3-4)} 4=0.935-500)/3 5.1.3二维资源分配问题 设有两种资源，总数量分别为a和b,用于生产n种产品。若分配数量为x,的第一种资源和数量为 片的第二种资源给第i种产品的生产，则可得收益g:(x,)。问应如何分配资源，使生产种产品的总收 益最大？ 静态规划： maxz=g(x,)+..+g() S1.x1+…+xn=a y+…+yn=b x,y,≥0，j=1…,n 动态规划：设 阶段：把资源分配给一个产品的生产作为一个阶段，k=1,…,n; 状态变量(S,l4):S为分配给第k种产品至第n种产品的第一种资源的数量，0≤s≤a: 1为分配给第k种产品至第n种产品的第二种资源的数量，0≤1，≤b: 决策变量(，y):4分配给第k种产品的第一种资源的数量（即4=x),0≤4≤S; y%分配给第k种产品的第二种资源的数量（即=），0≤≤1： 状态转移方程：Sk1=Sk一山，11=l-V: 指标函数：(S,),(u,)》=g(,),子过程指标函数为加式： 最优值函数f(S,4):以数量为S的第一种资源和数量为1的第二种资源分配给第k种产品至第n种产 品的生产时可获得的最大收益。 则得递推关系： f(,l)=max{8(uk,y)+f+(se-,-k,)},k=n,…,1 0e (S)=0 最终求得f(a,b)即为最大收益。 求解方法： 1.Lagrange乘数法 引入Lagrange乘数，将二种资源分配问题转化为一维资源分配问题。 给定入，考虑问题： maxz=8(x1,)+…+8n(xn,yn)-2y+…+yn) S1.X1+…+xn=a xj,y,≥0，j=1,…,n 令h(x)=max{8(x,y)-y},设最优解y(x)。则得一种资源分配问题： y20
3 得递推关系： 5 5 1 0 55 5 5 5 (0.9 500) / 3 ( ) max {8 5( ) (0.7 0.9( ))}, 4, ,1 ( ) max {8 5( )} k k kk k k k k k k k u s u s fs u s u f u s u k fs u s u + ≤ ≤ = − ⎧ = + −+ + − = ⎪ ⎨ = +− ⎪ ⎩ " 5.1.3 二维资源分配问题 设有两种资源，总数量分别为 a 和 b，用于生产 n 种产品。若分配数量为 xi 的第一种资源和数量为 yi 的第二种资源给第 i 种产品的生产，则可得收益 gi (xi, yi)。问应如何分配资源，使生产 n 种产品的总收 益最大？ 静态规划： 111 1 1 max ( , ) ( ,, ) . . , 0, 1, , nn n n n j j z g x y g x y st x x a y yb xy j n = + + ++= ++ = ≥ = " " " " 动态规划：设 阶段：把资源分配给一个产品的生产作为一个阶段， k n =1, , " ； 状态变量(,) k k s t ： k s 为分配给第 k 种产品至第 n 种产品的第一种资源的数量，0 k ≤ ≤ s a ； kt 为分配给第 k 种产品至第 n 种产品的第二种资源的数量，0 k ≤ ≤ t b ； 决策变量(,) k k u v ： k u 分配给第 k 种产品的第一种资源的数量(即 k k u x = )，0 k k ≤ u s ≤ ； k v 分配给第 k 种产品的第二种资源的数量(即 k k v y = )，0 k k ≤ v t ≤ ； 状态转移方程： k kk 1 s s u + = − ， k kk 1 t tv + = − ； 指标函数： (( , ),( , )) ( , ) k kk k k k k k v st uv guv = ，子过程指标函数为加式； 最优值函数 (,) k kk f s t ：以数量为 k s 的第一种资源和数量为 kt 的第二种资源分配给第 k 种产品至第 n 种产 品的生产时可获得的最大收益。 则得递推关系： 1 0 0 1 11 ( , ) max { ( , ) ( , ,)}, , ,1 ( , )0 k k k k k kk k k k k k kk k u s v t n nn fst guv f s ut v k n fst + ≤ ≤ ≤ ≤ + ++ ⎧ = + −− = ⎪ ⎨ ⎪ ⎩ = " 最终求得 1f (,) a b 即为最大收益。 求解方法： 1．Lagrange 乘数法 引入 Lagrange 乘数，将二种资源分配问题转化为一维资源分配问题。 给定 λ ，考虑问题： 111 1 1 max ( , ) ( ,, ) ( ) . . , 0, 1, , nn n n n j j z g x y g x yy y st x x a xy j n = ++ − ++ λ ++= ≥ = " " " " 令 0 ( ) max{ ( , ) } i i i iii i y h x g x y y λ λ ≥ = − ，设最优解 ( ) i i y x λ 。则得一种资源分配问题：
maxz=h(x)+…+h(xn) S.l.x+…+xn=a (4.3.1) X,j=1,…,n 对于(4.3.1)，可用动态规划方法求解，设得到的解为x,i=1,…,n,则得y=y(x,),i=1,…,n。若 广=b,则(K,y)为原问题最优解，否则调整元何利用插值法，直到∑=b。 i1 2.逐次逼近法 保持一个变量不变，对另一变量实现最优化，然后交替固定。 先固定x=(,,xy≥0：∑x=a,求解一维资源分配问题： maxz=g(x,)+.+g (xm,,y) S1.y+…+yn=b y≥0，j=1,…,n 设得最优解y=(,…,)了。固定y°=(，…，y)了，求解一维资源分配问题： max==g1)++g(xy) S.l.x+…+xn=a x,≥0，j=1,…,n 设得最优解x=(x,…,x)了。固定x=(x,…x)了，求解一维资源分配问题： max==g()++g(x,y) s.1.乃+…+yn=b y,≥0j=1,…,n 设得最优解y=(y,…,y)了。重复，得到{x,y},则{x,y}可收敛到原问题的局部最优解。 5.1.4资金固定的分配问题 设有两种资源，用于生产种产品。若分配数量为x的第一种资源和数量为的第二种资源给第i 种产品的生产，则可得收益g(x)。若第一种资源的价格为α，第二种资源的价格为b,现有总资金Z。 问应如何分配资源，使生产n种产品的总收益最大？ 视为两种资源的分配： max==g(x,)+..+g(y) S1.x+…+xn=X y+…+yn=Y aX+bY≤Z xj,y,≥0，j=1,…,n 视为资金的分配： 若分配数量为，的资金给第i种产品的生产，则可得收益
4 1 1 1 max ( ) ( ) . . , 1, , n n n j z hx hx st x x a xj n λ λ = ++ ++= = " " " (4.3.1) 对于(4.3.1)，可用动态规划方法求解，设得到的解为 , 1, , i x i n λ = " ，则得 ( ), 1, , i ii y y xi n λ λλ = = " 。若 1 n i i y b λ = ∑ = ，则 ( ) λ λ x , y 为原问题最优解，否则调整 λ (可利用插值法)，直到 1 n i i y b λ = ∑ = 。 2．逐次逼近法 保持一个变量不变，对另一变量实现最优化，然后交替固定。 先固定 00 0 0 1 1 ( , , ) 0: n T n i i x x xa = x = ≥= " ∑ ，求解一维资源分配问题： 0 0 11 1 1 max ( , ) ( ,, ) . . 0, 1, , nn n n j z g x y g x y st y y b yj n = ++ ++ = ≥ = " " " 设得最优解 00 0 1 (,,)T n y = y y " 。固定 00 0 1 (,,)T n y = y y " ，求解一维资源分配问题： 0 0 111 1 max ( , ) ( , ) . . 0, 1, , nnn n j z g x y g x y st x x a xj n = ++ ++= ≥ = " " " 设得最优解 11 1 1 (, , )T n x = x " x 。固定 11 1 1 (, , )T n x = x " x ，求解一维资源分配问题： 1 1 11 1 1 max ( , ) ( ,, ) . . 0, 1, , nn n n j z g x y g x y st y y b yj n = ++ ++ = ≥ = " " " 设得最优解 11 1 1 (, , )T n y = y y " 。重复，得到{,} k k x y ，则{,} k k x y 可收敛到原问题的局部最优解。 5.1.4 资金固定的分配问题 设有两种资源，用于生产 n 种产品。若分配数量为 xi 的第一种资源和数量为 yi 的第二种资源给第 i 种产品的生产，则可得收益 gi (xi, yi)。若第一种资源的价格为 a，第二种资源的价格为 b，现有总资金 Z。 问应如何分配资源，使生产 n 种产品的总收益最大？ 视为两种资源的分配： 111 1 1 max ( , ) ( ,, ) . . , 0, 1, , nn n n n j j z g x y g x y st x x X y yY aX bY Z xy j n = ++ ++= ++ = + ≤ ≥ = " " " " 视为资金的分配： 若分配数量为 zi 的资金给第 i 种产品的生产，则可得收益
Re)8(,） 得一维资源分配问题 maxz=R()+…+Rn(zn) S.l.31+…+2n=Z 2j≥0，j=1,…,n §5.2背包问题 有一个人带一个背包上山，起可携带的物品重量最多α公斤。设有n种物品可供选择装入背包中。 己知代第i种物品每件重量为"，公斤，若携带x件，则上山过程中的作用（价值）为℃x)。问此人应如何 选择携带的物品（即各几件），使所起作用（总价值）最大？这就是著名的背包问题。 与背包问题类似的问题有很多，例如工厂中的下料问题，运输中的货物装载问题，人造卫星内的物 品装载问题。 静态问题： maxz=C(x)+…+cn(xn) s.1.11+…+nxn≤a x,≥0，intj=1,…,n 动态规划：设 阶段：把背包内装入一种物品作为一个阶段，k=L,…,: 状态变量s:用于装第k种物品至第n种产品的总重量，0≤s≤a; 决策变量4：装第k种物品的数量（即u,=x),允许决策集：0≤w山，≤s,山：it,即 U(s)={4=0,l, 状态转移方程：Sk+1=Sx一州4； 指标函数：，4)=c4),,4,,4=e)(加武) 最优值函数f(S):当背包中可装入第k种物品至第n种物品的总重量为S,时可获得的最大价值。 则得基本方程： (Sx)=max fcr(ux)+(sx-wxug)),k =n,...,1 fn+(Sn+)=0 最终求得(a)即为最大价值。 二维背包问题：两种限制 静态规划： maxz=C(x)+…+cn(xn) s.t.9x1+…+1wnxn≤a x+…+vnxn≤b x,≥0，int,j=l,…,n 动态规划： 5
5 0 / ( ) max ( , ) i i i i ii k i y zb z by R z g y ≤ ≤ a − = 得一维资源分配问题 1 1 1 max ( ) ( ) . . 0, 1, , n n n j z Rz Rz st z z Z zj n = ++ ++= ≥ = " " " §5.2 背包问题 有一个人带一个背包上山，起可携带的物品重量最多 a 公斤。设有 n 种物品可供选择装入背包中。 已知代第 i 种物品每件重量为 wi 公斤，若携带 xi件，则上山过程中的作用(价值)为 ci(xi)。问此人应如何 选择携带的物品(即各几件)，使所起作用(总价值)最大？这就是著名的背包问题。 与背包问题类似的问题有很多，例如工厂中的下料问题，运输中的货物装载问题，人造卫星内的物 品装载问题。 静态问题： 1 1 1 1 max ( ) ( ) . . 0,int, 1, , n n n n j z cx cx st wx w x a x j n = ++ ++ ≤ ≥ = " " " 动态规划：设 阶段：把背包内装入一种物品作为一个阶段， k n =1, , " ； 状态变量 k s ：用于装第 k 种物品至第 n 种产品的总重量，0 k ≤ s ≤ a ； 决策变量 k u ：装第 k 种物品的数量(即 k k u x = )，允许决策集：0 ≤ wu s kk k ≤ ， k u :int，即 ( ) { | 0,1, , } k kk k k k s Us uu w ⎡ ⎤ = = ⎢ ⎥ ⎣ ⎦ " ； 状态转移方程： k k kk 1 s s wu + = − ； 指标函数： (, ) () kk k k k vsu cu = ， , 1 (, , ,, , ) () n kn k k n n n j j j k V su sus cu + = " = ∑ （加式） 最优值函数 ( ) k k f s ：当背包中可装入第 k 种物品至第 n 种物品的总重量为 k s 时可获得的最大价值。 则得基本方程： 1 0,1, , 1 1 ( ) max { ( ) ( )}, , ,1 ( )0 k k k k k k k k k kk s u w n n f s c u f s wu k n f s + ⎡ ⎤ = ⎢ ⎥ ⎣ ⎦ + + ⎧ = +− = ⎪ ⎨ ⎪ ⎩ = " " 最终求得 1f ( ) a 即为最大价值。 二维背包问题：两种限制 静态规划： 1 1 1 1 1 1 max ( ) ( ) . . 0,int, 1, , n n n n n n j z cx cx st wx w x a vx vx b x j n = + + ++ ≤ ++ ≤ ≥ = " " " " 动态规划：