(大学数学实验 资源分配问题 资源分配问题 用x表示将手中资源x分配给工厂k,k+1…,N时的 k-2Bf /(2)=ma [82 (u )+f,(x, )1= max [&, (u,)+/(r2-,) 最大利润,原问题即为计算f(M) 0)=maxg2(a2)+f2(0-2)=g2(0)+f(0)=0+0=0 f(x4)=max[8k(a4)+fk+(xk+)k=N,N-1,…,1, 0=m4g:{)+(-吗2月=mg:0+f(g20+(O fx+(x+)= max0+32+0=3 (2)=mayg:(a2)+f(2-)=mag:0)+f(28:0)+f(g2(2)+0 具体计算(例) M=4,N=3,边界条件∫(x小=f0)=0 f03)=muNg2{a2)+f(3-n2 axg2(0)+f(3g2(1)+f(2)g2(2)+f(g2(3)+f(0) k=3A:f(x)=maNg, (u,)+/(0)]=8,(x, 增函数) max0+7,2+55+35+0}=8 (4)=mNg)+4一月 f0)=8:(0=0f(1)=8(1)=3f3(2)=83(2)=5 =mg2(0)+f(4),g2()+f(3),g2(2)+f1(2)g2(3)+f(D),g2(4)+f(0) f(3)=g()=7,J(4)=85(4)=8 max0+82+75+5,6+38+0=10 大学学实编) 资源分配问题 klRt /(,)=max[g, (u, )+/2 (x2 )] max[g,(u,)+f2(x-1) 应用动态规划方法解整数规划 实例3:单产品、无能力限制的批量问题 m8(4)+f(4-4月 maxg(0)+f2(4),81(1)+f2(3),81(2)+f2(2g1(3)+f2(281(4)+f2(0 max80+10,4+8,6+5,7+3,7+0=12. min=∑(sy,+cx+h) 最优解n=12=24=1,最大利润为:=f1(4)=12 5.ln+x1-l1=d1,t=1,2,…,T, 推广:非线性整数规划问题,如 min==x2 +2x2+4x2 l。=0, x1,x2,x3∈z g(a2)=42-5B (学学奖 大学费学买验 假设费用均非负,则在景优解中4“420,即多24=3(千元=50千元),=1(千元千件 可以证明:一定存在满足条件1x=01≤t≤T)的 d1=2d2=3d3=2d4=4(千件) 最优解 具体计算过程如下 可以只考虑x∈d1,d+d1n,…,d+d1n+…+d} f=3+50*4+0+0=203 用表示当t时段初始库存为0时,从时段到T时段的 f=min{3+502+4)+1*4+0,3+50*2+0+11}=306 子问题的最优费用值 =min43+50(3+2+4)+1(2+4)+1*4+0,3+50(3+2)+1·2+11, 3+50*3+0+18}=458 f=min{3+502+3+2+4)+1(3+2+4)+1(2+4)+1*4+0 m,+c∑4+∑句+f可>0 3+2)+1(3+2)+1·2+11 +0(2+3)+1*3+18,3+50*2+0+26}=561 最优值(费用)为f X=(2,5,0,4)最优值为561(千元)6 资源分配问题 用fk(xk) 表示将手中资源xk分配给工厂k,k+1,…, N 时的 最大利润，原问题即为计算 f1(M) M=4，N=3，边界条件 f4(x4) = f4(0) =0 ⎩ ⎨ ⎧ = = + = − + + + + ≤ ≤ ( ) 0. ( ) max [ ( ) ( )], , 1, ,1, 1 1 1 1 0 N N k k k k u x k k f x f x g u f x k N N k k L k=3时： （增函数） ( ) max[ ( ) (0)] ( ) 3 3 4 3 3 0 3 3 3 3 f x g u f g x u x = + = ≤ ≤ (0) (0) 0; f3 = g3 = (1) (1) 3; f3 = g3 = (2) (2) 5; f3 = g3 = (3) (3) 7; f3 = g3 = (4) (4) 8 f3 = g3 = 具体计算（例） k=2时： ( ) max [ ( ) ( )] max [ ( ) ( )] 2 2 3 2 2 0 2 2 3 3 0 2 2 2 2 2 2 f x g u f x g u f x u u x u x = + = + − ≤ ≤ ≤ ≤ (0) max[ ( ) (0 )] (0) (0) 0 0 0; 2 2 3 2 2 3 0 0 2 2 = + − = + = + = ≤ ≤ f g u f u g f u max{0 3,2 0} 3; (1) max[ ( ) (1 )] max{ (0) (1), (1) (0)} 2 2 3 2 2 3 2 3 0 1 2 2 = + + = = + − = + + ≤ ≤ f g u f u g f g f u max{0 5,2 3,5 0} 5; (2) max[ ( ) (2 )] max{ (0) (2), (1) (1), (2) (0)} 2 2 3 2 2 3 2 3 2 3 0 2 2 2 = + + + = = + − = + + + ≤ ≤ f g u f u g f g f g f u max{0 7,2 5,5 3,6 0} 8; max{ (0) (3), (1) (2), (2) (1), (3) (0)} (3) max[ ( ) (3 )] 2 3 2 3 2 3 2 3 2 2 3 2 0 3 2 2 = + + + + = = + + + + = + − ≤ ≤ g f g f g f g f f g u f u u max{0 8,2 7,5 5,6 3,8 0} 10; max{ (0) (4), (1) (3), (2) (2), (3) (1), (4) (0)} (4) max[ ( ) (4 )] 2 3 2 3 2 3 2 3 2 3 2 2 3 2 0 4 2 2 = + + + + + = = + + + + + = + − ≤ ≤ g f g f g f g f g f f g u f u u 资源分配问题 k=1时： ( ) max[ ( ) ( )] max[ ( ) ( )] 1 1 2 1 1 0 1 1 2 2 0 1 1 1 1 1 1 f x g u f x g u f x u u x u x = + = + − ≤ ≤ ≤ ≤ max{0 10,4 8,6 5,7 3,7 0} 12. max{ (0) (4), (1) (3), (2) (2), (3) (1), (4) (0)} (4) max[ ( ) (4 )] 1 2 1 2 1 2 1 2 1 2 1 1 2 1 0 4 1 1 = + + + + + = = + + + + + = + − ≤ ≤ g f g f g f g f g f f g u f u u 最优解 ,最大利润为 . 1, 2, 1 * 3 * 2 * u1 = u = u = (4) 12 1 * z = f = 推广：非线性整数规划问题，如： + ∈ + + = = + + − − − x x x Z st x x x z x x x x x x 1 2 3 1 2 3 1 2 3 2 3 2 2 2 1 , , . . 4 min 2 4 3 5 M=4, N=3 1 2 1 1 1 g (u ) = u − u 2 2 g2 (u2 ) = 2u2 −3u 3 2 g 3 (u3 ) = 4u3 − 5u 资源分配问题 应用动态规划方法解整数规划 , 0, 1,2, , . 0, 1,2, , , 0, 0, 1, 0, . . , 1,2, , , min ( ) 0 1 1 x I t T I t T x x y st I x I d t T z s y c x h I t t t t t t t t t t t t t t T t t L L L ≥ = = = ⎩ ⎨ ⎧ = > = + − = = = + + − = ∑ 实例3：单产品、无能力限制的批量问题 可以只考虑 可以证明：一定存在满足条件 的 最优解. 用ft 表示当t时段初始库存为0时，从t时段到T 时段的 子问题的最优费用值 最优值（费用）为 f1 . 假设费用均非负，则在最优解中 ，即 I 0 = IT = 0 ∑ ∑ = = = T t t T t xt d 1 1 0(1 ) It−1 xt = ≤ t ≤ T t { } dt dt dt dt dt dT x ∈ 0, , + +1,L, + +1 +L+ ⎪ ⎪ ⎩ ⎪ ⎪ ⎨ ⎧ ≤ ≤ ⎪ ⎩ ⎪ ⎨ ⎧ + + + > = = = ∑ ∑ ∑ − = + − = − = + ≤ ≤ + + + 1 . min [ ], 0, , 0. 0, 1 1 1 1 1 1 1 1 t T s c d d h f d f d f f t i t i j t i j i t t t i t T t t t T τ τ τ τ X=(2,5,0,4), 最优值为561（千元） T=4， （千元）， （千元）， （千元 st = 3 ct = 50 ht = 1 /千件） 2 (千件) d1 = d2 = 3 2 d3 = 4 d4 = 具体计算过程如下： f 5 = 0; f 4 = 3+50*4+0+0=203; f 3 = min{3+50(2+4)+1*4+0,3+50*2+0+11}=306; f 2 = min{3+50(3+2+4)+1(2+4)+1*4+0,3+50(3+2)+1*2+11, 3+50*3+0+18}=458; f 1 = min{3+50(2+3+2+4)+1(3+2+4)+1(2+4)+1*4+0, 3+50(2+3+2)+1(3+2)+1*2+11, 3+50(2+3)+1*3+18, 3+50*2+0+26} = 561