动态规划习题答案(共20页)

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项目允许的投资额为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 *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家销售店。每个营业区至少设一家，所获利润如表。问设立的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=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(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的装载件数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第二步：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)| X1D1（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 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+309+163009 0+30 9+303911012 0+46 9+30460s 4=s3-3x3x3D3(s3)f3(s3)=max9x3+f4(s4)k=3 s212x2+f3(s2-4x2)f2(s2)x2* x2=0 x2=102 0+0 0030+9 9045 0+16 12+01606 0+30 12+03007 0+30 12+93008 0+30 12+163009 0+39 12+1639010 0+46 12+304601112 0+46 12+30460s3=s2-4x2x2D2(s2)f2(s2)=max12x2+f3(s3)k=2s2=s1-3x1 s1=12x1D1(s1)f1(s1)=max12x1+f2(s2)k=1s112x1+f2(s1-3x1)f1(s1)x1*x1=0x1=1120+46 12+39511s1=12 s2=9 s3=9 s4=6 s5=6x1*=1 x2*=0 x3*=1 x4*=0 x5*=111今设计一种由4个元件串联而成的部件，为提高部件的可靠性，每一元件可以由1个、2个或3个并联的单位元件组成。关于元件K（K=1，2，3，4）配备j个并联单位元件（j=1，2，3）后的可靠性Rkj和成本Ckj由表给出，假设该部件的总成本允许为15个单位，试问如何确定各元件的单位元件配备数目，使系统的可靠性最高？jK=1K=2K=3K=4R1jC1jR2jC2jR3jC3jR4jC4j10.740.620.930.8320.7550.840.82530.857解：逆序解法。Sk仪表上配备k#，4#元件时允许使用的费用XkK#元件所选用的单位元件Wk（Sk，Xk）K#元件采用单位元件时的可靠性，有Wk（Sk，Xk）=RkxkTk（Sk，Xk）Sk+1= Sk - Ckxkfk（Sk）在费用限额为Sk的条件下，k#，3#元件串联时相应部分可获得的最大可靠性递归方程 f4（S5）=1 fk（Sk）= maxWk（Sk，Xk）fk+1（Sk+1），K=4,3,2,1.第一步，对K=4, S4R4x4F4（S1）X4*X4=1X4=230.70.8140.80.8150.80.820.82260.70.820.822第二步: S3R3x3f1（S3 C3x3）f2（S2）X3*X3=160.90.80.72170.90.80.72180.90.820.738190.90.820.7381第三步，对K=2, S2R2x2f3（S2 C2x2）f2（S2）X2*X2=1X2=280.60.720.432190.60.720.4321100.60.7380.80.720.5762110.60.7380.80.720.5762 第四步，对K=4, f4（S4）= maxR4x4f3（S3）S3= S4 C4x4，S4=15S1R1x1f2（S41 C1x1）f1（S4）X*1X1=1 X1=2 X1=3150.70.576 0.750.576 0.850.4320.4322S1=15 S3=10 S2=6 S1=3 X1*=2 X2*=2 X3*=1 X4*=1元件1为2个，元件2为2个，元件3为1个，元件4为1个，可靠性为0.432。顺序解法：Sk仪表上配备1#，K#元件时允许使用的费用XkK#元件所选用的单位元件Wk（Sk，Xk）K#元件采用单位元件时的可靠性，有Wk（Sk，Xk）=RkxkTk（Sk，Xk）Sk-1= Sk - Ckxkfk（Sk）在费用限额为Sk的条件下，1#，K#元件串联时相应部分可获得的最大可靠性递归方程 f0（S0）=1 fk（Sk）= maxWk（Sk，Xk）fk-1（Sk-1），K=1，2，3，4第一步，对K=1, f1（S1）= maxR1x14S17S1=4，5，6，7S14567D1（S1）11,21,21,2,3S1R1x1f1（S1）X1*X1=1X1=2X1=340.70.7150.70.750.75260.70.750.75270.70.750.80.83第二步，对K=2, f2（S2）= maxR2x2f1（S1）S1= S2 C2x26S29S2=6，7，8，9S26789D2（S2）111,21,2S2R2x2f1（S2 C2x2）f2（S2）X2*X2=1X2=260.60.70.42170.60.750.45180.60.750.80.70.56290.60.80.80.750.62第三步，对K=3, f3（S3）= maxR3x3f2（S2）S2= S3 C3x39S212S2=9，10，11，12S39101112D3（S3）1111S3R3x3f2（S3 C3x3）f3（S3）X3*X3=190.90.420.3781100.90.450.4051110.90.560.5041120.90.60.541第四步，对K=4, f4（S4）= maxR4x4f3（S3）S3= S4 C4x4，S4=15S4R4x4f3（S4 C4x4）f4（S4）X4*X4=1X4=2150.80.540.820.4050.4321S4=15 S3=12 S2=9 S1=5 X4*=1 X3*=1 X2*=2 X1*=2元件1为2个，元件2为2个，元件3为1个，元件4为1个，可靠性为0.432。