第五章 动态规划应用举例（书第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 = + + ++ ≤ ++ ≤ ≥ = " " " " 动态规划：
f(s,)= max {c(u)+f+(se-弘e,4-y4)},k=n,…,1 f+1(S+l,ln+i)=0 最终求得f(a,b)即为最大价值。 §5.3生产与存储问题 在生产与经营管理中，经常会遇到要合理安排生产与库存的问题，达到既满足社会需求，又尽量降 低成本费用。因此，如何正确制定生产策略，确定不同阶段的生产量和库存量，使总的生产成本和库存 费用最小，这就是生产与存储问题。 某公司对某种产品要制定一个阶段的生产计划。己知它的初始库存为零。在第k阶段末社会对该 产品的需求为dk,公司必须保证供应，并且生产数量为x的产品时的成本为c(x),并且产量上限为m。 若第k阶段末库存量为，则存储费用为(y)。问该公司如何制定每个阶段的生产计划，使总费用最小？ 静态模型： min:=2c,()+h(c) k=1 S. %=0,yn=0 4=2g,-d,k=1…,n-1 I= 0≤xg≤m,k=1,…,n y4≥0，k=1,…,n 动态规划（顺序求解法）：设 阶段：按月份划分，以上月多余产品入库后为阶段开始： 状态变量：第k阶段末的库存量（即第+1阶段开始时的库存量），允许状态集 0s≤mmt-含4，三.渔6 j=0 决策变量x:第k阶段的生产量 状态转移方程：V=Vk-1+一d,即V-1=V+一x 由%=0,0≤yk-1≤6-1，k=2,…,n,得允许决策集： x=y+d,max{yg+dk-δ-1,0}≤x≤min{yk+d,m,k=2,…,n 阶段指标函数C(x)+h,(v),子过程指标函数具体加性； 最优值函数(v):从第1阶段初始库存量为0到第k阶段末库存量为时的最小总费用。 得到基本方程： f(v)= md盟m+dmU-+d-)+c()+ha(》,k=2,…,n min (v)=min c(x)+h(v) x1=y+41 最终求得fn(O)。 6
6 1 0,1, ,min , 1 11 ( , ) max { ( ) ( , )}, , ,1 ( , )0 k k k k k k k k k k k k kk k kk s t u w v n nn f s t c u f s wu t vu k n fst + ⎧ ⎫ ⎪ ⎪ ⎡ ⎤⎡ ⎤ = ⎨ ⎬ ⎢ ⎥⎢ ⎥ ⎪ ⎪ ⎩ ⎭ ⎣ ⎦⎣ ⎦ + ++ ⎧ = +− − = ⎪ ⎨ ⎪ ⎩ = " " 最终求得 1f (,) a b 即为最大价值。 §5.3 生产与存储问题 在生产与经营管理中，经常会遇到要合理安排生产与库存的问题，达到既满足社会需求，又尽量降 低成本费用。因此，如何正确制定生产策略，确定不同阶段的生产量和库存量，使总的生产成本和库存 费用最小，这就是生产与存储问题。 某公司对某种产品要制定一个 n 阶段的生产计划。已知它的初始库存为零。在第 k 阶段末社会对该 产品的需求为 dk，公司必须保证供应，并且生产数量为 xk的产品时的成本为 ck(xk)，并且产量上限为 m。 若第 k 阶段末库存量为 vk，则存储费用为 hk(vk)。问该公司如何制定每个阶段的生产计划，使总费用最小？ 静态模型： 1 0 1 min ( ) ( ) . . 0, 0 ( ), 1, , 1 0 , 1, , 0, 1, , n kk kk k n k k jj j k k z cx hv st v v v x dk n x mk n vk n = = = + = = = −= − ≤≤ = ≥ = ∑ ∑ " " " 动态规划（顺序求解法）：设 阶段：按月份划分，以上月多余产品入库后为阶段开始； 状态变量 vk：第 k 阶段末的库存量(即第 k+1 阶段开始时的库存量)，允许状态集 0 1 0 min{ , } k n k j jk j jk v mk d d δ = =+ ≤≤ −∑ ∑ 决策变量 xk：第 k 阶段的生产量 状态转移方程： kk kk 1 vv xd = +− − ，即 k k kk 1 v vdx − = + − 由 0 11 0,0 , 2, , k k v v kn δ =≤≤ = − − " ，得允许决策集： 111 x = + v d ， max{ ,0} min{ , }, 2, , kkk k kk 1 v d x v dmk n δ +− ≤≤ + = − " 阶段指标函数 () () kk kk cx hv + ，子过程指标函数具体加性； 最优值函数 ( ) k k f v ：从第 1 阶段初始库存量为 0 到第 k 阶段末库存量为 vk时的最小总费用。 得到基本方程： 1 11 1 1 min{ ,0} min{ , } 11 11 11 ( ) min { ( ) ( ) ( )}, 2, , ( ) min { ( ) ( )} kkk k kk kk k k k k kk kk v d x v dm xvd f v f v d x cx hv k n fv cx hv δ − − +− ≤≤ + = + ⎧ = +− + + = ⎪ ⎨ = + ⎪ ⎩ " 最终求得 (0) nf
o x4=0 例53.1设n=4,C(x)=3+xx=1,…,6,h(y)=0.5yk, >6 k 1 2 3 d 2 3 2 δk 4 6 4 k=1时：f(g)=min{c(x)+h()以，0≤y≤6=4 X=+ x1=v1+2 2 3 4 5 6 f(vi) x 6 5+0 2 1 6+0.5 6.5 3 2 7+1 8 4 3 8+1.5 9.5 5 4 9+2 11 6 =2时：f5(2)= mt+3-4m盟mt+36(+3-)+G()+h,(2)},0≤y2≤d=6 0 2 3 6 5(2) 写 9.5+0+0 8+4+0 6.5+5+0 5+6+0 9.5 0 1 11+0+0.5 9.5+4+0.5 8+5+0.5 6.5+6+0.5 5+7+0.5 11.5 0 2 11+4+1 9.5+5+1 8+6+1 6.5+7+1 5+8+1 14 5 3 11+5+1.59.5+6+1.5 8+7+1.5 6.5+8+1.5 5+9+1.5 15.5 G 4 11+6+2 9.5+7+2 8+8+2 6.5+9+2 17.5 6 JN 11+7+2.5 9.5+8+2.5 8+9+2.5 19.5 6 6 11+8+3 9.5+9+3 21.5 6 k=3时： ()= min max{+2-6,05x3≤minfv3+2,6} {f(3+2-x)+C(x3)+h(3)},0≤y≤δ3=4 3 龙 3 0 1 2 3 6 (2) 书 14+0+0 11.5+4+0 9.5+5+0 14 0 1 15.5+0+0.5 14+4+0.5 11.5+5+0.5 9.5+6+0.5 16 0,3 17.5+0+1 15.5+4+1 14+5+1 11.5+6+1 9.5+7+1 17.5 4 3 19.5+0+1.5 17.5+4+1.5 15.5+5+1.5 14+6+1.5 11.5+7+1.5 9.5+8+1.5 19 4 21.5+0+2 19.5+4+2 17.5+5+2 15.5+6+2 14+7+2 11.5+8+29.5+9+2 20.5 6 =4时： f(v4)= min {f3(v+4-x4)+c4(x4)+h(v4)},y4=0 4=max{4+4-4,0sx4smin{4+4,6 F V4 0 1 2 3 (2) 女 0 20.5+0+0 19+4+0 17.5+5+016+6+0 14+7+0 20.50 y4=0→x4=0→y3=y4+d4-x4=4→x=6→y2=y3+43-x=0 →x2=0→%=2+d2-x2=3→x=5→%=%+d1-x1=0
7 例 5.3.1 设 n=4， 0 0 ( ) 3 1, ,6 6 k kk k k k x cx x x x ⎧ = ⎪ =+ = ⎨ ⎪ ⎩∞ > " ， ( ) 0.5 kk k hv v = ， k 1 2 3 4 k d 2 3 2 4 k δ 4 6 4 k=1 时： 1 1 11 11 11 1 1 2 ( ) min { ( ) ( )},0 4 x v fv cx hv v δ = + = + ≤≤= x1=v1+2 v1 2 3 4 5 6 f1 (v1) * 1 x 0 5+0 5 2 1 6+0.5 6.5 3 2 7+1 8 4 3 8+1.5 9.5 5 4 9+2 11 6 k=2 时： 2 22 22 12 2 2 2 22 max{ 3 4,0} min{ 3,6} ( ) min { ( 3 ) ( ) ( )} v xv f v f v x cx hv +− ≤ ≤ + = +− + + ， 2 2 0 6 ≤ v ≤ = δ x2 v2 0 1 2 3 4 5 6 f2 (v2) * 2 x 0 9.5+0+0 8+4+0 6.5+5+0 5+6+0 9.5 0 1 11+0+0.5 9.5+4+0.5 8+5+0.5 6.5+6+0.5 5+7+0.5 11.5 0 2 11+4+1 9.5+5+1 8+6+1 6.5+7+1 5+8+1 14 5 3 11+5+1.5 9.5+6+1.5 8+7+1.5 6.5+8+1.5 5+9+1.5 15.5 6 4 11+6+2 9.5+7+2 8+8+2 6.5+9+2 17.5 6 5 11+7+2.5 9.5+8+2.5 8+9+2.5 19.5 6 6 11+8+3 9.5+9+3 21.5 6 k=3 时： 3 33 33 23 3 33 33 max{ 2 6,0} min{ 2,6} ( ) min { ( 2 ) ( ) ( )} v xv f v f v x cx hv +− ≤ ≤ + = +− + + ， 3 3 0 4 ≤ v ≤ = δ x3 v3 0 1 2 3 4 5 6 f2 (v2) * 3 x 0 14+0+0 11.5+4+0 9.5+5+0 14 0 1 15.5+0+0.5 14+4+0.5 11.5+5+0.5 9.5+6+0.5 16 0,3 2 17.5+0+1 15.5+4+1 14+5+1 11.5+6+1 9.5+7+1 17.5 4 3 19.5+0+1.5 17.5+4+1.5 15.5+5+1.5 14+6+1.5 11.5+7+1.5 9.5+8+1.5 19 5 4 21.5+0+2 19.5+4+2 17.5+5+2 15.5+6+2 14+7+2 11.5+8+2 9.5+9+2 20.5 6 k=4 时： 4 4 44 44 34 4 4 4 44 max{ 4 4,0} min{ 4,6) ( ) min { ( 4 ) ( ) ( )} v v xv f v f v x cx hv = +− ≤ ≤ + = +− + + ， 4 v = 0 x4 v4 0 1 2 3 4 F2 (v2) * 4 x 0 20.5+0+0 19+4+0 17.5+5+0 16+6+0 14+7+0 20.5 0 * ** * 4 4 34 44 3 23 33 * ** * 2 1 2 2 2 1 01 11 00 46 0 0 3 5 0 v x vvdx x vvdx x vvd x x v vdx =→ =→ = + − =→ =→ = + − = → =→ = + − =→ =→ = + − =
即最优策略：x1=5,x=0,x=6,x4=0。 得表格 阶段i 0 1 2 3 4 需求量d 2 3 2 4 生产量x 5=2+3 0 6=2+4 0 库存量 0 3 0 0 即1x=0,i=1,2,3,4,也即>0→x=0,-1=0→x>0,i=1,2,3,4。 若对每个1，有·x=0,则称该生产与存储问题具体再生产性质。如果y=0,则称阶段1为再 生产点。例如阶段0和n为再生产点。 设1和1是两个相邻的生产点，j≤i,即y-1=0,y,>0,s=j,i-1,y=0,则 y=∑4，x=0,s=j+l,1,y=∑4，s=j小，1 即阶段j到阶段i的产品全部由阶段j生产。设c(j,)为阶段j到阶段i的总成本，则 cU,)=c,2d)+h.(2d) =4 动态规划： 阶段：再生产点： 状态：再生产点i: 决策：i之前的再生产点1： 最优值函数f:y=0时从阶段1到阶段i的最小成本，则递推关系： f=min+c(ji)),i=1....n Isisi 6=0 最后求得fn。 例5.3.2用再生产性质求解例5.2.1。 先求出c(j,): c(1,1)=c(2)=5,c(L,2)=c(5)+h(3)=9.5,c(1,3)=c(7)+h(5)+h(3)=0, c(1,4)=c(11)+h(9)+h(6)+h(4)=∞ c(2,2)=Cc,(3)=6,c(2,3)=c,(5)+h(3)=9,c(2,4)=c,(9)+h,(6)+h(4)=0 c(3,3)=c(2)=5,c(3,4)=c(6)+h(4)=11 c(4,4)=c4(4)=7 1 2 3 4 方 广 1 0+5 5 1 0+9.5 5+6 9.5 1 3 0+60 5+9 9.5+5 14 0+0 5+0 9.5+11 14+7 20.5
8 即最优策略： **** 1234 xxxx ==== 5, 0, 6, 0 。 得表格 阶段 i 0 1 2 3 4 需求量 di - 2 3 2 4 生产量 xi - 5=2+3 0 6=2+4 0 库存量 vi 0 3 0 4 0 即 * 1 0, 1,2,3,4 i i vx i − ⋅= = ，也即 * * 1 1 0 0, 0 0, 1,2,3,4 i ii i v xv xi − − >⇒ = =⇒ > = 。 若对每个 i，有 * 1 0 i i v x − ⋅ = ，则称该生产与存储问题具体再生产性质。如果 0 i v = ，则称阶段 i 为再 生产点。例如阶段 0 和 n 为再生产点。 设 j-1 和 i 是两个相邻的生产点， j ≤ i ，即 1 0, 0, , 1, 0 js i v v sji v − = >= −= " ，则 , 0, 1 , i j ss s j x dx s j i = = = =+ ∑ " ， 1 , , i s t t s v ds j i = + = = ∑ " 即阶段 j 到阶段 i 的产品全部由阶段 j 生产。设 c ji (,) 为阶段 j 到阶段 i 的总成本，则 1 1 (,) ( ) ( ) i ii j s st s j s j ts c j ic d h d − = = =+ = + ∑ ∑ ∑ 动态规划： 阶段：再生产点 i； 状态：再生产点 i； 决策：i 之前的再生产点 j-1； 最优值函数 i f ： 0 i v = 时从阶段 1 到阶段 i 的最小成本，则递推关系： 1 1 0 min{ ( , )}, 1, , 0 i j j i f f c ji i n f − ≤ ≤ ⎧ =+= ⎪ ⎨ ⎪⎩ = " 最后求得 nf 。 例 5.3.2 用再生产性质求解例 5.2.1。 先求出 c ji (,) ： 1 c c (1,1) (2) 5 = = ， 1 1 c ch (1,2) (5) (3) 9.5 =+= ， 112 c chh (1,3) (7) (5) (3) = + + =∞ ， 1 123 c c hhh (1,4) (11) (9) (6) (4) = + + + =∞ 2 c c (2,2) (3) 6 = = ， 2 2 c ch (2,3) (5) (3) 9 =+= ， 223 c chh (2,4) (9) (6) (4) = + + =∞ 3 c c (3,3) (2) 5 = = ， 3 3 c ch (3,4) (6) (4) 11 =+= 4 c c (4,4) (4) 7 = = j i 1 2 3 4 i f * j 1 0+5 5 1 2 0+9.5 5+6 9.5 1 3 0+ ∞ 5+9 9.5+5 14 2 4 0+ ∞ 5+ ∞ 9.5+11 14+7 20.5 3
i=4→‘(4)=3→阶段2为再生产点→x=d3+d4=6,x4=0 →i=2→j(2)=1→阶段0为再生产点→x=d,+d2=5,x=0 所以最优策略：x=5,x=0,x=6,x4=0最优值f4=20.5。 例5.3.3书P229 月份k 0 2 3 4 5 6 需求量dk 0 8 5 3 2 7 4 单位工时ak 11 18 13 17 20 10 阶段：按月份划分，以上月产品已送入，本月需求未送出为阶段开始（先供应再生产）： 状态变量sk:第k阶段开始时的库存量，允许状态集： So=2,S7=0,d≤S4≤H,k=1,…,5 决策变量：第k阶段的生产量 状态转移方程：541=S-d+4,k=0,…,6 由S7=0和d≤Sk≤H,k=1,…,6,得允许决策集U(S): 6=0,6=d6,45=d6+d5-S5,max{dk1+ds-Sk,0}≤44≤H+ds-Sk,k=0,…,4 阶段指标函数：a4 最优值函数(S):第k阶段开始时库存量为s时，从第k阶段初到第6阶段末的最小总耗费工时 [f(s)=min{a4s+f+(ss+4s-d)},k=6,…,0 U(sk) f(s7)=0 最终求出f(2)。 k=6:s6=d6=4,U6(s6)={4。=0}, f6(s6)=min{as6}=0,4。=0 =0 k=5:7≤s≤9，U(s5)={u=d6+d-S}={4=11-s}, f5s)=mi,a,4}=1011-s.4=11- k=4:2≤s4≤9,9-S4=max{9-s4,0}=max{d3+d4-s4,0}≤u4≤H+d4-s4=11-s4, f)F,-mi盟a4+f5+4,-d,} =。mim{204+110-10s4+44-2)} 9-54≤4≤11-4 =g-m10u,-10s,+130} =10(9-34)-1054+130=220-20s4 4=9-54 k=3:3≤s3≤9，max{5-S3,0}=max{d4+d3-S,0}≤43≤H+d3-S3=l2-S3, 9
9 * i j =→ =→ 4 (4) 3 阶段 2 为再生产点 * * 334 4 →=+= = xdd x 6, 0 * →= → =→ i j 2 (2) 1 阶段 0 为再生产点 * * 1 12 2 →=+ = = xdd x 5, 0 所以最优策略： **** 1234 xxxx ==== 5, 0, 6, 0 最优值 4f = 20.5。 例 5.3.3 书 P229 月份 k 0 1 2 3 4 5 6 需求量 dk 0 8 5 3 2 7 4 单位工时 ak 11 18 13 17 20 10 阶段：按月份划分，以上月产品已送入，本月需求未送出为阶段开始（先供应再生产）； 状态变量 sk：第 k 阶段开始时的库存量，允许状态集： 0 7 s s = = 2, 0 ， , 1, ,5 k k d s Hk ≤≤ = " 决策变量 uk：第 k 阶段的生产量 状态转移方程： 1 , 0, ,6 k kkk s s d uk + =−+ = " 由 7 s = 0 和 , 1, ,6 k k d s Hk ≤≤ = " ，得允许决策集 ( ) U s k k ： 6 6 65 6 5 5 1 0, , ,max{ ,0} , 0, ,4 k kk k kk u s du d d s d d s u H d sk = = =+− +− ≤≤+− = + " 阶段指标函数： k k a u 最优值函数 ( ) k k f s ：第 k 阶段开始时库存量为 sk时，从第 k 阶段初到第 6 阶段末的最小总耗费工时 1 ( ) 7 7 ( ) min { ( )}, 6, ,0 () 0 k kk k k kk k k k k uUs f s au f s u d k f s + ∈ ⎧ = + +− = ⎪ ⎨ ⎪⎩ = " 最终求出 0f (2) 。 k=6： 6 6 s d = = 4 ， 66 6 Us u ( ) { 0} = = ， 6 * 6 6 66 6 0 ( ) min{ } 0, 0 u f s au u = = = = k=5： 5 7 9 ≤ ≤ s ， 55 5 6 5 5 5 5 Us u d d s u s ( ) { } { 11 } = = +− = =− ， 5 5 * 5 5 55 5 5 5 11 ( ) min { } 10(11 ), 11 u s f s au s u s = − = = − =− k=4： 4 2 9 ≤ ≤ s ， 4 4 5 44 4 44 4 9 max{9 ,0} max{ ,0} 11 −= − = + − ≤≤+ −=− s s d d s u Hd s s ， 44 4 44 4 44 4 4 4 44 5 4 4 4 9 11 4 44 9 11 4 4 9 11 * 44 4 4 4 ( ) min { ( )} min {20 110 10( 2)} min {10 10 130} 10(9 ) 10 130 220 20 9 su s su s su s f s au f s u d u su u s ss s u s −≤ ≤− −≤ ≤− −≤ ≤− = + +− = + − +− = −+ = − − + = − =− k=3： 3 3 9 ≤ ≤ s ， max{5 ,0} max{ ,0} 12 3 4 33 3 33 3 − s = + − ≤≤+ −=− d d s u Hd s s
f(5）=s-m盟-a,4+f4s+4-d} min{174+220-20s3+43-3)} max5-53,0ss12-53 5m25--3,-205+280} =-312-3)-20s3+280=244-17S34=12-S3 k=2:5≤s2≤9，max{8-s2,0}=max{d3+d2-s2,0}≤42≤H+d2-S2=14-s2, 万(，)=maa+f+4-d》 =-m214-134+244-175,+4-5} =-s4-44-175,+329y =-414-52)-17s2+329=273-13s24=14-52 k=l:8≤s≤9,13-S=max{l3-s,0}=max{d2+d41-S,0}≤4≤H+d1-S,=17-S, f(s)=g-m盟-{a4+f方s+4-d)》 =14m-184+273-13(6+4-8} =1m盟-54-138+37} =413-3)-13s,+377=442-183,4=13-3 k=0:s。=2,8-s。=max{8-5o,0}=max{d1+d-so,0}≤4≤H+d-s=9-s, f(,)=-盟。a%+f+6-d》 二gm盟14+42-18+24} =-9--74-18+442} =-7(9-s)-18s。+442=379-11s4=9-56 50=2→4=9-5=7→S1=-d0+4=9→4=13-S,=4→S2=S,-d1+4=5 →4=14-52=9→53=52-d2+4=9→4=12-S=3→54=S3-d3+4=9 4=9-34=0→35=54-d4+4=7→4=11-35=4→6=3-d+4=4 →46=0 得最优策略：4=7,4=4,42=9,4=3,4=0,4=4,6=0，最优值f0(2)=379-22=357。 §5.4复合系统工作可靠性问题 若某种机器的工作系统由个部件串联组成，只要有一个部件失灵，整个系统就不能工作。为提高 系统工作的可靠性，在每各部件上均装有其备用部件，并且设计了备用部件自动投入装置。显然，备用 部件个数越多，整个系统的可靠性越大，但系统的成本、重量、体积等增大。因此，需考虑在一定限制 条件下，如何选择各部件的备用件个数，使整个系统的工作可靠性最大。 0
10 33 3 33 3 33 3 3 3 33 4 3 3 3 max{5 ,0} 12 3 33 max{5 ,0} 12 3 4 max{5 ,0} 12 * 33 3 3 3 ( ) min { ( )} min {17 220 20( 3)} min { 3 20 280} 3(12 ) 20 280 244 17 12 su s su s su s f s au f s u d u su u s ss s u s − ≤≤− − ≤≤− − ≤≤− = + +− = + − +− = −− + =− − − + = − = − k=2： 2 5 9 ≤ ≤ s ， max{8 ,0} max{ ,0} 14 2 3 22 2 22 2 − s = + − ≤≤+ −=− d d s u Hd s s ， 22 2 22 2 22 2 2 2 22 3 2 2 2 max{8 ,0} 14 2 22 max{8 ,0} 14 2 2 max{8 ,0} 14 * 22 2 2 2 ( ) min { ( )} min {13 244 17( 5)} min { 4 17 329} 4(14 ) 17 329 273 13 14 su s su s su s f s au f s u d u su u s ss s u s − ≤≤− − ≤≤− − ≤≤− = + +− = + − +− = −− + =− − − + = − = − k=1： 1 8 9 ≤ ≤ s ， 1 1 2 11 1 11 1 13 max{13 ,0} max{ ,0} 17 −= − = + − ≤≤ + −= − s s d d s u Hd s s ， 11 1 11 1 11 1 1 1 11 2 1 1 1 13 17 1 11 13 17 1 1 13 17 * 11 1 1 1 ( ) min { ( )} min {18 273 13( 8)} min {5 13 377} 4(13 ) 13 377 442 18 13 su s su s su s f s au f s u d u su u s ss s u s −≤≤ − −≤≤ − −≤≤ − = + +− = + − +− = −+ = − − + = − =− k=0： 0 s = 2 ， 0 0 1 00 0 00 0 8 max{8 ,0} max{ ,0} 9 − = − = + − ≤ ≤ + − =− s s d d s u Hd s s ， 00 0 00 0 00 0 0 0 00 1 0 0 0 8 9 0 00 8 9 0 1 8 9 * 00 0 0 0 ( ) min { ( )} min {11 442 18( )} min { 7 18 442} 7(9 ) 18 442 379 11 9 su s su s su s f s au f s u d u su u s ss s u s − ≤ ≤− − ≤ ≤− − ≤ ≤− = + +− = +− + = −− + =− − − + = − = − 0 s = 2 * * 0 0 10 00 → =− =→ = − + = u s ssdu 97 9 * * 1 1 2111 → = − =→ = − + = u s s sdu 13 4 5 * * 2 2 32 22 → = − =→ = − + = u s ssdu 14 9 9 * * 3 3 4333 → = − =→ = − + = u s s sdu 12 3 9 * * 4 4 54 44 → =− =→ = − + = u s ssdu 90 7 * * 5 5 6555 → = − =→ = − + = u s ssdu 11 4 4 * 6 → = u 0 得最优策略： ******* 01 23456 uuuuuuu ======= 7, 4, 9, 3, 0, 4, 0 ，最优值 0f (2) 379 22 357 = −= 。 §5.4 复合系统工作可靠性问题 若某种机器的工作系统由 n 个部件串联组成，只要有一个部件失灵，整个系统就不能工作。为提高 系统工作的可靠性，在每各部件上均装有其备用部件，并且设计了备用部件自动投入装置。显然，备用 部件个数越多，整个系统的可靠性越大，但系统的成本、重量、体积等增大。因此，需考虑在一定限制 条件下，如何选择各部件的备用件个数，使整个系统的工作可靠性最大
