2.某公司有资金4百万元向A,B和C3个项目追加投资，各个项目可以有不同的投资额（百万元计），相应的效益如表所示。

问怎样分配资金，使总效益值最大？##表8－47解：设S－A,B,C项目的总投资额，S－B、C项目的总投资额21S－C 项目的投资额；3X－k项目的投资额；k（X－A项目的投资额，X－B项目的投资额，X－C项目的投资额）312W（S,X）－对K项目投资X后的收益：W（S,X）＝W (X) kkkkkkkkk T (S,X)－S=S-X kk+1kkkk f (S)－当K至第3项目允许的投资额为S时所能获得的最大收益。

kkk为获得最大利润，必须将4百万全部投资，假设有4阶段存在，有S＝0，建立递归方程4f(S)=0k4f (S)=max{ W (X)+f(S)} k=3,2,1 k+1kk +1kkk X∈D(S)kkk第一步，K=3f(S)=044 f (S)=max{W (X)+f (S)} 434333X∈D(S) 333S=S-X334第二步：)} f (S (X (S)=max{W)+f K=2 322322) X∈D(S 222-X =S S232W (X)+f (S-X)22322第三步：)} (S (X) =max f (S {W)+ f K=1 211121) DX∈(S111- X S= S 121)(X- X)+ f (SW1 12 11S=4 →S=1 →S=1 312↓↓↓X*=3 X*=0 X*=1312百万。

1投资C 不投资B 百万，3投资A．总收益164百万元。

3.（最优分配问题）有一个仪表公司打算向它的3个营业区设立6家销售店。

每个营业区至少设一家，所获利润如表。

问设立的6家销售店数应如何分配，可使总利润最大？利润营业区A k (x) wA A A k321180 200 1 210230 2 220 280 销售260 3 330 225 店数x2803404 230解：## ,3营业区允许设立的销售店数s——对k,…k#营业区设立的销售店数——对k x k x销售店后的利润：)——对k#营业区设立 w(s,x kkk k)(x (sw,,x)= w kkkk k = s - x) T (s x——s kkk,kkk +1s3个营业区允许设立的销售店数为至第) f (s——当第k kkk时所能获得的最大利润递归方程：)=0(sf44．f (s)=max ｛wk (xk)+ fk+1(sk+1)｝, k=3,2,1 kk xk∈Dk(sk)k=3时，有方程f (s)=044f3(s3)= max ｛w3(x3)+ f4(s4) ｝x∈D3(s3) 3s3=s2—x2k=2,有方程｝｛f2(s2)= max w2(x2)+ f3(s3)D2(s2) ∈x2x2 —s3=s2k=1,有方程｝f1(s1)= max ｛w1(x1)+ f2(s2)D1(s1) x1∈x1 s2=s1—s3=2 s2=3 s1=6 →→↓↓↓*=2 *=3 xx*=1 x321家销售店，最大利润为2家、1家、3营业区设立A3、A2、A1分别7704．用动态规划方法求解下列模型：maxf=10X+4X+5X 321≤15+4 Xs.t. 3X+5 X312≤2 0≤X≤2 X≥0 ，X为整数≤0Xj=1,2,3 j321解：收费C=10 C=4 C=5 312X为货物1的装载件数1X为货物2的装载件数2X为货物3的装载件数3分3阶段S为货物1、2、3允许的装载重量（3X+5 X+4 X的允许值）3121S为货物2、3允许装载的重量（5 X+4 X的允许值）322S为货物3允许装载的重量（4 X的允许值）33第一步：K=3f(S)=044f(S)= max{5X f(S)| X∈D（S）} 3333+4433S S -4 X334=S0~34~78~1112~15D(S) {0}{0,1}{0,1,2}{0,1,2,3}33S X=0 X=1 X=2 X=3 f (S) X* 3333333300~3 0+0__________________0+0 5+0 ______ ______ 4~7 5 10+0 5+0 8~11 10+0 ______ 10 20+0 5+0 10+0 15+0 12~15 15 3第二步：K=2f(S)= max{4X f(S)| X∈D（S）} 2222+3322S= S -5 X210~15 0~45~9S2{0,1,2} {0,1}) {0}D (S22划分点：第三步：K=1f(S)= max{10X f(S)| X∈D（S } ）11+132211．S= S-3 X 11210X f(S-3 X) 11+12顺序追踪：最优策略为=9 S S=9 →S=15 →312↓↓↓*=2X *=0 X*=2 X 321装不装；货物32件最优装载方案为：货物1装2件；货物2 装载收费为30元5.用动态规划方法解下列0—1背包问题：Max f =12x+12x+9x+16x+30x；52143s.t.3x+4x+3x+4x+6x≤12; 53241x=0,1, j=1,……，5 j解：本问题分为5个阶段。

令sax+…+ax的允许值4k4kk——x第k阶段x取值，x=0，1kkk——w(s, x)——x产生的价值：w(s, x)=cx kkkkkk kkkT(s, x)——s=s- ax kkkk+1kkk f(s)——在ax+…+ ax≤s的条件下，cx+…+cx能4 4kkkkk44 kk取得的最大值。

．递归方程为f(s)=066 f(s)=max{cx+f(s)},k=5,4,3,2,1k+1kkkkk+1k=5f(s}55x∈D(s)555(3055==0~5000—1306~1230f(s)=max{16x+f(s)} 54454k=4 ) D(s∈x444s=s-4x 44 5f(s)=max{9x+f(s)}k=3 43433x∈D(s)333 s=s -3x 3 43)}(sf(s)=max{12x+f32223k=2 x∈D(s)222s=s -4x 232*2k=1f(s)=max{12x+f(s)}21121x∈D(s)111s=s-3x s=121211sf(s) x* )(s3xf12x1-11+21111x=0x=11112+391510+46 12s=12 s=9 s=9 s=6 s=654321x=1x*=0 x*=1 x*=0 x*=1*5142311．今设计一种由4个元件串联而成的部件，为提高部件的可靠性，每一元件可以由1个、2个或3个并联的单位元件组成。

关于元件K （K=1，2，3，4）配备j个并联单位元件（j=1，2，3）后的可靠性R和成本C由表给出，假设该部件的总成本允许为15个单位，试kjkj 问如何确定各元件的单位元件配备数目，使系统的可靠性最高？解：逆序解法。

S ——仪表上配备k#，…，4#元件时允许使用的费用 k X ——K#元件所选用的单位元件 k W （S ，X ）——K#元件采用单位元件时的可靠性，有 kkk W （S ，X ）=Rx kkkk k T （S ，X ）——S SCx kkkk - kk+1=k fS ——在费用限额为S 元件串联时相应3#，…，k#的条件下，k ）k （k 部分可获得的最大可靠性递归方程 fS=1 （）54 fS max ｛W （S ，X ）﹒fS ｝，K=4,3,2,1. ）k+1kk （k （k ）=kk+1第一步，对K=4,第二步:S f（S）X*Rx﹒CxfS3232）31（33 –33=1 X36 0.9×0.8 0.72 11 0.8 0.727 0.9×1 0.820.7388 ×0.91×9 0.90.820.738第三步，对K=2,S f（S）X*xRx﹒fSC2222）22–3（2 22=2 =1XX228 0.6×0.72 0.432 1 —1 0.4320.69 —×0.72第四步，对K=4, fS= max｛Rx﹒fS｝）（34（4）434S SCxS=1544 –43=，4S CxRx﹒fS1）1141–2（11X* f（S）114=3X =2 =1 X X 11115 0.7×0.576 0.75×0.576 0.85×0.432 0.432 2SSSS=3=6 →=10 →=15 →1231↓↓↓↓X*=2 X*=2 X*=1 X*=1 4132元件1为2个，元件2为2个，元件3为1个，元件4为1个，可靠性为0.432。

顺序解法：S——仪表上配备1#，…，K#元件时允许使用的费用k X——K#元件所选用的单位元件k W（S，X）——K#元件采用单位元件时的可靠性，有kkk W（S，X）=Rx kkkk k T（S，X）——S SCx kkkk-1=kk -k fS——在费用限额为S的条件下，1#，…，K#元件串联时相应kk）k（部分可获得的最大可靠性递归方程fS=1（）00fS max｛W（S，X）﹒fS｝，K=1，2，3，4 ）k）kk-1kk-1=（kk（第一步，对K=1, fS= max｛Rx｝11（）114＜＝S＜＝7 1S=｛4，5，6，7｝1S 4 5 6 7 1｛1,2,3｝｛1,2｝SD ｛1｝｛1,2｝）11（S f（S）X*Rx111111=3 X=1XX=2 1110.7 ——4 1 0.72 —0.75 0.750.752 —0.750.76 0.7530.80.7570.70.8第二步，对K=2, fS= max｛Rx﹒fS｝）2（2（12）12S SCx2–1= 2 26＜＝S＜＝9 2S=｛6，7，8，9｝21 —0.450.6×7 0.752 8 0.750.560.8×0.70.6×20.80.60.69 ××0.750.8第三步，对K=3, fS= max｛Rx﹒fS｝）3（（）32233S SCx33 –2=39＜＝S12＜＝2．S=｛9，10，11，12｝21 ×10 0.90.45 0.4051 0.911 ×0.560.504112×0.60.540.9第四步，对K=4, fS= max｛Rx﹒fS｝）4（34）3（44S SCxS=1544–3=4 ，4S f（S）X*Rx﹒fSCx4444）43（4 –444=2XX=14415 0.8×0.54 0.82×0.405 0.432 1SSSS=5=9 =12 →→=15 →1324↓↓↓↓X*=1 X*=1 X*=2 X*=2 1423元件1为2个，元件2为2个，元件3为1个，元件4为1个，可靠。