动态规划习题答案.docVIP

2.某公司有资金4百万元向A,B和C3个项目追加投资，各个项目可以有不同的投资额（百万元计），相应的效益如表所示。问怎样分配资金，使总效益值最大？## 表8－47 Wk (Xk)（项目k#投 资 额012341#（A）－414860662#（B ）40425060－3#（C）－64687884 解：设S1－A,B,C项目的总投资额，S2－B、C项目的总投资额 S3－C项目的投资额； Xk－k项目的投资额； （X1－A项目的投资额，X2－B项目的投资额，X3－C项目的投资额） Wk（Sk,Xk）－对K项目投资Xk后的收益：Wk（Sk,Xk）＝Wk (Xk) Tk (Sk,Xk)－Sk+1=Sk-Xk fk (Sk)－当K至第3项目允许的投资额为Sk时所能获得的最大收益。 为获得最大利润，必须将4百万全部投资，假设有4阶段存在，有S4＝0，建立递归方程 f4 (Sk)=0 fk (Sk)=max{ Wk (Xk)+fk +1(Sk+1)} k=3,2,1 Xk∈Dk(Sk) 第一步，K=3 f4(S4)=0 f3 (S3)=max{W3 (X3)+f4 (S4)} X3∈D3(S3) S4=S3-X3 S3f3 (S3)X3*1641268237834844 第二步： K=2 f2 (S2)=max{W2 (X2)+f3 (S3)} X2∈D2(S2) S3=S2-X2 W2 (X2)+f3 (S2-X2) S2X2 =0X2 =1X2 =2X2 =3f2 (S2)X2 *140+64－－－1040240+6842+64－－1080340+7842+6850+64－1180440+8442+7850+6860+641240，3 第三步： K=1 f1 (S1) =max {W1 (X1)+ f2 (S2)} X1∈D1(S1) S2= S1- X1 W1 (X1)+ f2 (S1- X1) S1X1=0X1=1X1=2X1=3f1 (S1)X1 *4－41+118 48+10860+104 164 3  S1=4 → S2=1 → S3=1 ↓ ↓ ↓ X1*=3 X2*=0 X3*=1 A投资3百万， B不投资 C投资1百万。 总收益 164百万元。 3.（最优分配问题）有一个仪表公司打算向它的3个营业区设立6家销售店。每个营业区至少设一家，所获利润如表。问设立的6家销售店数应如何分配，可使总利润最大？ 利 润 wk(x) 营 业 区AkA1A2A3 销售 店数x1 2 3 4200 280 330 340210 220 225 230180 230 260 280 解：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)=0 fk (sk)=max ｛wk (xk)+ fk+1(sk+1)｝, k=3,2,1 xk∈Dk(sk) k=3时，有方程 f4 (s4)=0 f3(s3)= max ｛w3(x3)+ f4(s4) ｝ x3∈D3(s3) s3=s2—x2 s3f3(s3)x3*11801223023260342804 k=2,有方程 f2(s2)= max ｛w2(x2)+ f3(s3) ｝ x2∈D2(s2) s3=s2—x2 s2w2(x2)+ f3(s2—x2)f2(s2)x2*x2=1x2=2x2=3x2=42210+180///39013210