《动态规划习题答案》由会员分享，可在线阅读，更多相关《动态规划习题答案（19页珍藏版）》请在金锄头文库上搜索。
1、细心整理2.某公司有资金4百万元向A,B和C3个工程追加投资，各个工程可以有不同的投资额百万元计，相应的效益如表所示。问怎样支配资金，使总效益值最大？#表847Wk (Xk)工程k#投 资 额012341#A414860662#B 404250603#C64687884解：设S1A,B,C工程的总投资额，S2B、C工程的总投资额S3C工程的投资额；Xkk工程的投资额；X1A工程的投资额，X2B工程的投资额，X3C工程的投资额WkSk,Xk对K工程投资Xk后的收益：WkSk,XkWk (Xk)Tk (Sk,Xk)Sk+1=Sk-Xkfk (Sk)当K至第3工程允许的投资额为Sk时所能获得的最大收
2、益。为获得最大利润，必需将4百万全部投资，假设有4阶段存在，有S40，建立递归方程f4 (Sk)=0fk (Sk)=max Wk (Xk)+fk +1(Sk+1) k=3,2,1 XkDk(Sk)第一步，K=3 f4(S4)=0 f3 (S3)=maxW3 (X3)+f4 (S4) X3D3(S3) S4=S3-X3S3f3 (S3)X3*1641268237834844其次步：K=2 f2 (S2)=maxW2 (X2)+f3 (S3) X2D2(S2) S3=S2-X2 W2 (X2)+f3 (S2-X2)S2X2 =0X2 =1X2 =2X2 =3f2 (S2)X2 *140+64104
3、0240+6842+641080340+7842+6850+641180440+8442+7850+6860+641240，3第三步：K=1 f1 (S1) =max W1 (X1)+ f2 (S2) X1D1(S1) S2= S1- X1 W1 (X1)+ f2 (S1- X1)S1X1=0X1=1X1=2X1=3f1 (S1)X1 *441+118 48+10860+1041643 S1=4 S2=1 S3=1 X1*=3 X2*=0 X3*=1A投资3百万， B不投资 C投资1百万。总收益 164百万元。 3.最优支配问题有一个仪表公司打算向它的3个营业区设立6家销售店。每个营业区至少设
4、一家，所获利润如表。问设立的6家销售店数应如何支配，可使总利润最大？利 润wk(x)营 业 区AkA1A2A3 销售店数x1234200280330340210220225230180230260280解：sk对k#,3#营业区允许设立的销售店数 xk对k#营业区设立的销售店数 wk (sk,xk)对k#营业区设立xk销售店后的利润：wk (sk,xk)= wk (xk) Tk (sk, xk)sk +1= sk - xk fk (sk)当第k至第3个营业区允许设立的销售店数为sk时所能获得的最大利润递归方程：f4(s4)=0fk (sk)=max wk (xk)+ fk+1(sk+1), k
5、=3,2,1xkDk(sk)k=3时，有方程f4 (s4)=0f3(s3)= max w3(x3)+ f4(s4) x3D3(s3)s3=s2x2s3f3(s3)x3*11801223023260342804k=2,有方程f2(s2)= max w2(x2)+ f3(s3) x2D2(s2)s3=s2x2s2w2(x2)+ f3(s2x2)f2(s2)x2*x2=1x2=2x2=3x2=42210+180/39013210+230220+180/44014210+260220+230225+180/47015210+280220+260225+230230+1804901k=1,有方程f1(s
6、1)= max w1(x1)+ f2(s2) x1D1(s1)s2=s1x1s1w1(x1)+ f2(s1x1)f1(s1)x1*x1=1x1=2x1=3x1=46200+490280+470330+440340+3907703s1=6 s2=3 s3=2 x1*=3 x2*=1 x3*=2分别A1、A2、A3营业区设立3家、1家、2家销售店，最大利润为770 4用动态规划方法求解以下模型：maxf=10X1+4X2+5X3s.t. 3X1+5 X2+4 X3150X12 0X22 X30 ，Xj为整数 j=1,2,3解：收费C1=10 C2=4 C3=5X1为货物1的装载件数X2为货物2的装
7、载件数X3为货物3的装载件数分3阶段S1为货物1、2、3允许的装载重量3X1+5 X2+4 X3的允许值S2为货物2、3允许装载的重量5 X2+4 X3的允许值S3 为货物3允许装载的重量4 X3的允许值第一步：K=3f4(S4)=0f3(S3)= max5X3+ f4(S4)| X3D3S3S4= S3 -4 X3S303478111215D3(S3)00,10,1,20,1,2,3S3X3=0X3=1X3=2X3=3f3 (S3)X3*030+0_00470+05+0_518110+05+010+0_10212150+05+010+015+0153其次步：K=2 f2(S2)= max4X
8、2+ f3(S3)| X2D2S2S3= S2 -5 X2S204591015D2 (S2)00,10,1,2划分点：0481200481255913171010141822S24X2+ f3(S2 -5 X2)f2 (S2)X2*X2=0X2=1X2=2030+0_0040+5_50570+54+0_5080+104+0_10090+104+5_10010110+104+58+0100120+154+58+0150130+154+108+015014150+154+108+5150第三步：K=1f1(S3)= max10X1+ f2(S2)| X1D1S1 S2= S1-3 X1 10X1+
9、 f2(S1-3 X1)S1X1=0X1=1X1=2f1 (S1)X1*150+1510+1520+10302依次追踪：最优策略为S1=15 S2=9 S3=9 X1*=2 X2*=0 X3*=2最优装载方案为：货物1装2件；货物2不装；货物3装2件装载收费为30元5.用动态规划方法解以下01背包问题： Max f =12x1+12x2+9x3+16x4+30x5； s.t. 3x1+4x2+3x3+4x4+6x512; xj=0,1, j=1,，5解： 本问题分为5个阶段。令 skakxk+a4x4的允许值 xk第k阶段xk取值，xk=0，1 wk(sk, xk)xk产生的价值：wk(sk,
10、 xk)=c kxk Tk(sk, xk)sk+1=sk- akxk fk(sk)在akxk+ a4x4sk的条件下，c kxk+c 4x4能取得的最大值。xkDk(sk)fk(sk)=maxckxk+fk+1(sk+1),k=5,4,3,2,1f6(s6)=0递归方程为 x5D5(s5)k=5 f5(s5)=max30x5s5 30x5f5(s5)x5*x5=0x5=105000612030301s 5=s4-4x4x4D4(s4)f4(s4)=max16x4+f5(s5)k=4 s416x4+f5(s4-4x4)f4(s4)x4*x4=0 x4=1030+000450+016+0161690+3016+030010120+30 16+30461s39x3+f4(s3-3x3)f3(s3)x3*x3=0x3=1020+0 0030+0 9+091450+16 9+01606 0+30 9+030078
