《动态规划习题答案》由会员分享，可在线阅读，更多相关《动态规划习题答案（19页珍藏版）》请在金锄头文库上搜索。
1、2.某公司有资金4百万元向A,B和C3个项目追加投资，各个项目可以有不同的投资额（百万元计），相应的效益如表所示。问怎样分配资金，使总效益值最大？#表847Wk (Xk)（项目k#投 资 额012341#（A）414860662#（B ）404250603#（C）64687884解：设S1A,B,C项目的总投资额，S2B、C项目的总投资额S3C项目的投资额；Xkk项目的投资额；（X1A项目的投资额，X2B项目的投资额，X3C项目的投资额）Wk（Sk,Xk）对K项目投资Xk后的收益：Wk（Sk,Xk）Wk (Xk)Tk (Sk,Xk)Sk+1=Sk-Xkfk (Sk)当K至第3项目允许的投资额为
2、Sk时所能获得的最大收益。为获得最大利润，必须将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
3、 *140+641040240+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)+
5、fk+1(sk+1), k=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+18049
6、01k=1,有方程f1(s1)= 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
7、的装载件数X2为货物2的装载件数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)| X3D3（S3）S4= 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
8、第二步：K=2 f2(S2)= max4X2+ f3(S3)| X2D2（S2）S3= 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)| X
9、1D1（S1） S2= S1-3 X1 10X1+ 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
10、 wk(sk, xk)xk产生的价值：wk(sk, 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 0+30
