资源预览内容
第1页 / 共19页
第2页 / 共19页
第3页 / 共19页
第4页 / 共19页
第5页 / 共19页
第6页 / 共19页
第7页 / 共19页
第8页 / 共19页
第9页 / 共19页
第10页 / 共19页
亲,该文档总共19页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
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+30
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号