动态规划习题答案0001

1、2.某公司有资金 4百万元向 A,B 和 C3个项目追加投资，各个项目可 以有不同的投资额（百万元计） ，相应的效益如表所示。问怎样分配 资金，使总效益值最大？ #表 8 47Wk （X k） （项目 k#投资额01234#1#（A）41486066#2#（B ）40425060#3#（C）64687884解：设 S1A,B,C 项目的总投资额， S2B、C 项目的总投资额S3C 项目的投资额；Xkk 项目的投资额；（X1A 项目的投资额，X2B 项目的投资额，X3C项目的投资额） Wk（Sk,Xk）对 K 项目投资 Xk后的收益： Wk（ Sk,X k） W k （Xk） Tk （Sk,Xk

2、） Sk+1=Sk -X kfk （Sk）当 K 至第 3项目允许的投资额为 Sk 时所能获得的最大收益。 为获得最大利润，必须将 4 百万全部投资，假设有 4 阶段存在，有 S40，建立递归方程f4 （Sk）=0k=3,2,1fk (Sk)=max W k (X k)+f k +1 (Sk+1)XkDk(Sk)第一步， K=3f4(S4)=0f3 (S3)=maxW 3 (X3)+f4 (S4)X 3 D3(S3)S4=S3-X 3S3f3 (S3)X3*1641268237834844第二步：K=2f2 (S2)=maxW 2 (X2)+f3 (S3)X2D2(S2)W2 (X 2)+f

3、3 (S2-X2)S2X2 =0X2 =1X2 =2X2 =3f2 (S2)X2 *140+641040240+6842+641080340+7842+6850+641180440+8442+7850+6860+641240，3第三步：K=1f1 (S1) =max W1 (X1)+ f2 (S2)X1D1(S1)S2= S1- X1S1=4S2=1S3=1W1 (X1)+ f2 (S1- X1)S1X1=0X1=1X1=2X1=3f1 (S1)X1 *441+11848+160+101643084X1*=3X2*=0A 投资 3 百万，B 不投资X3*=1C 投资 1 百万总收益 164 百

4、万元。3. (最优分配问题)有一个仪表公司打算向它的 3 个营业区设 立 6 家销售店。每个营业区至少设一家，所获利润如表。问设立的 6 家销售店数应如何分配，可使总利润最大？利润wk(x)营业区 AkA1A2A31200210180销售2280220230店数 x33302252604340230280#解： sk对 k#,3 #营业区允许设立的销售店数#x k 对 k 营业区设立的销售店数w k (s k,x k) 对 k#营业区设立 xk 销售店后的利润：wk (s k,x k)= w k (x k)T k (s k, x k) sk +1 = s k - x kf k (s k ) 当

5、第 k 至第 3 个营业区允许设立的销售店数为 sk时所能获得的最大利润递归方程：f 4(s 4)=0fk (s k)=max wk (xk)+ fk+1(sk+1) , k=3,2,1xkDk(sk)k=3 时，有方程f 4 (s 4)=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=s2x2w2(x2)+ f3(s2 x2)f2(s2)x2=1x2=2x2=3x2=4s22210+180/390132

6、10+230220+180/44014210+260220+230225+180/47015210+280220+260225+230230+1804901k=1, 有方程w1(x1)+ f2(s2) f1(s1)= max x1D1(s1) s2=s1x1w1(x 1)+ f2(s 1x1)f 1(s 1x1*s1x1=1x1=2x1=3x1=4)6200+490280+470330+440340+3907703s1=6 s2=3 s3=2x1*=3 x 2*=1 x 3*=2分别 A1、A2、A3营业区设立 3家、1 家、2 家销售店，最大利润为7704用动态规划方法求解下列模型： max

7、f=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）= max5X 3+ f4（S4）| X3D3（S3）S4= S3 -4 X3S303478111215

8、D3(S3)00,10,1,20,1,2,3S3X3=0X3=1X3=2X3=3f3 (S3)X3*030+000470+05+0518110+05+010+010212150+05+010+015+0153第二步： K=2f2(S2)= max4X 2+ 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+00040+550570+54+05080+104+010090+104+510

9、010110+104+58+0100120+154+58+0150130+154+108+015014150+154+108+5150第三步： K=1f1(S3)= max10X 1+ f2(S2)| X1D1(S1)S1X1=0X1=1X1=2f1 (S1)X1*150+1510+1520+10302S2= S1-3 X110X1+ f2(S1-3 X1)顺序追踪：最优策略为 S1=15 S2=9S3=9X3*=2 X1*=2 X2*=0最优装载方案为：货物 1装2件；货物 2不装；货物 3装 2件 装载收费为 30 元5.用动态规划方法解下列 01 背包问题： Max f =12x 1+1

10、2x 2+9x 3+16x 4+30x 5； s.t. 3x 1+4x 2+3x 3+4x 4+6x 5 12;xj=0,1, j=1, ， 5 解： 本问题分为 5 个阶段。令skakxk+a4x4 的允许值 xk第 k 阶段 xk 取值， xk=0， 1wk(sk, xk)xk产生的价值： wk(sk, xk)=c kxkTk(sk, xk) sk+1 =sk- akxkfk(sk)在 akxk+ a4x 4 sk 的条件下， c kxk+c 4x4能取得的最大值。s530x5f5(s5)x5*x5=0x5=105000612030301f4(s4)=max16x 4+f5(s5)x4 D

11、4(s4)递归方程为f6(s6)=0k=5fk(sk)=maxc kxk+fk+1(sk+1),k=5,4,3,2,1xk Dk(sk)f5(s5)=mDax30x 5k=4s 5=s4-4x 4s416x4+f5(s4-4x4)f4(s4)x4*x4=0x4=1030+000450+016+0161690+3016+030010120+3016+30461k=3f3(s3)=max9x 3+f 4(s4) x3 D3(s3)s39x 3+f 4(s3-3x 3)f3(s3)x3*x3=0x3=1020+00030+09+091450+169+016060+309+0300780+309+16

12、30090+309+3039110120+469+30460s 4=s3-3x 3s3=s2-4x 2k=2k=1s2=s1-3x 1s1=12f 2(s2)=max12x 2+f3(s3) x2D2(s2)s212x2+f3(s2-4x2)f 2(s2)x2*x2=0x2=1020+00030+990450+1612+016060+3012+030070+3012+930080+3012+1630090+3912+16390100+4612+3046011120+4612+30460f1(s1)=max12x 1+f2(s2) x1 D1(s1)s112x1+f2(s1-3x1)f1(s1)

13、x1*x1=0x1=1120+4612+39511s1=12s2=9s3=9s4=6 s5=6x1*=1x2*=0 x3*=1x4*=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

14、.8320.7550.840.82530.857解：逆序解法。Sk仪表上配备 k#， 4#元件时允许使用的费用X k K#元件所选用的单位元件Wk（Sk，Xk） K#元件采用单位元件时的可靠性，有Wk（Sk，Xk）=RkxkTk（Sk，Xk） Sk+1= Sk - Ckxk f k（ Sk） 在费用限额为 Sk的条件下， k#，3#元件串联时相应部分可获得的最大可靠性 递归方程 f4（S5） =1fk（Sk）= maxW k（ Sk， X k） f k+1 （ Sk+1 ），K=4,3,2,1. 第一步，对 K=4,S4R4x4F4（ S1）X4*X4=1X4=230.70.8140.80.8

15、150.80.820.82260.70.820.822第二步:S3R3x3f 1（ S3 C3x3）f 2（ S2）X3*X3=160.90.80.72170.90.80.72180.90.820.738190.90.820.7381第三步，对 K=2,S2R2x2f 3（ 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（S41C

16、1x1）f1（ S4）X* 1X1=1X1=2X1=3150.70.576 0.750.576 0.85 0.4320.4322S1=15 S3=10 S2=6 S1=3X1*=2X2*=2X3*=1X4*=1元件 1为2个，元件 2为2个，元件 3为1个，元件 4为1个，可靠 性为 0.432。顺序解法：Sk仪表上配备 1#， K#元件时允许使用的费用Xk K#元件所选用的单位元件Wk（Sk，Xk） K#元件采用单位元件时的可靠性，有Wk（Sk，Xk）=RkxkTk（Sk，Xk） Sk-1= Sk - Ckxkf k（ Sk） 在费用限额为 Sk的条件下， 1#， ，K#元件串联时相应 部分

17、可获得的最大可靠性递归方程 f0（S0） =1fk（Sk） = maxWk（Sk， Xk）fk-1（Sk-1 ），K=1，2，3，4第一步，对 K=1, f1（S1） = maxR1x14 S1 7S1=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 C2x26 S2 9S2=6，7，8，9S26789D2（S2）111,21,2S2R2x2f 1（ S2 C2x2）f 2（ 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 C3x39 S2 12S2=9，10，11，12S39101112D3（S3）1111S3R3x3f 2（ S