动态规划习题答案文档格式.docx
《动态规划习题答案文档格式.docx》由会员分享，可在线阅读，更多相关《动态规划习题答案文档格式.docx（17页珍藏版）》请在冰点文库上搜索。
S4=S3-X3
S3
f3（S3）
X3*
第二步:
K=2f2（S2）=max{W2（X2）+f3（S3）}
X2€D2（S2）
S3=S2-X2
W2（X2）+f3（S2-X2）
S2
X2=0
X2=1
X2=2
X2=3
f2（S2）
X2*
i
40+64
一
104
40+68
42+64
108
40+78
42+68
50+64
118
40+84
42+78
50+68
60+64
124
0,3
第三步:
K=1
fi（Si）二max{Wi（Xi）+f2（S2）}
Xi€Di（Si）
S2=Si-X1
Wi（Xi）+f2（Si-Xi）
Si
Xi=0
Xi=1
Xi=2
Xi=3
fi（Si）
Xi*
41+118
48+1
60+10
164
08
Xi*=3X2*=0
A投资3百万，
X3*=i
B不投资
C投资i百万
JJ
总收益164百万元。
3.（最优分配问题）有一个仪表公司打算向它的3个营业区设立6家销售店。
每个营业区至少设一家，所获利润如表。
问设立的6家销售店数应如何分配，可使总利润最大？
利润
Wk（x）
营业
区Ak
A
200
210
180
销售
280
220
230
店数x
330
225
260
340
Sk――对k#,…,3营业区允许设立的销售店数
xk——对k营业区设立的销售店数
wk（Sk,Xk）——对k#营业区设立Xk销售店后的利润：
w（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
s3
f3（s3）
x3*
k=2,有方程
f2（s2）=max{w2（x2）+f3（s3）}
x2€D2（s2）
w2（x2）+f3（s2—x2）
f2（s
2）
x2=1
x2=2
x2=3
x2=4
s2
210+1
80
/
390
210+2
30
220+1
440
220+2
225+1
470
5
225+2
230+1
490
k=1,有方程
{w1（x1）+f2（s2）}
f1（s1）=max
x1€D1（s1）
s2=s1—x1
w（x1）+f2（s1—X1）
f1（S1
X1*
S1
X1=1
X1=2
X1=3
X1=4
）
6
200+4
90
280+4
70
330+4
340+3
770
s1=6ts2=3ts3=2
xi*=3x2*=1x3*=2
分别A1、A2、A3营业区设立3家、1家、2家销售店，最大利润为
4．用动态规划方法求解下列模型：
maxf=10X1+4X2+5X3
s.t.3X1+5X2+4Xs<
15
0<
Ki电0<
X2总X3为,Xj为整数j=1,2,3
收费C1=10C2=4C3=5
X1为货物1的装载件数
X2为货物2的装载件数
X3为货物3的装载件数
分3阶段
Si为货物1、2、3允许的装载重量（3Xi+5X2+4X3的允许值）
S2为货物2、3允许装载的重量（5X2+4X3的允许值）
S3为货物3允许装载的重量（4X3的允许值）
第一步：
K=3
f3（S3）=max{5X3+f4（S4）|X3^D3（S3）}
S4=S3-4X3
0~3
4~7
8~11
12~15
D3（S3）
{0}
{0,1}
{0,1,2}
{0,123}
X3=0
X3=1
X3=2
X3=3
0+0
5+0
10+0
10
15+0
第二步：
K=2
f2（S2）=max{4X2+f3（S3）|X2€D2（S2）}
S3=S2-5X2
0~4
5~9
10~15
D2（S2）
划分点:
8
12
9
13
17
14
18
22
4X2+f3（S2-5X2）
X2*
X2=0
X2=1
X2=2
0+5
5~7
4+0
0+10
4+5
10~11
8+0
0+15
4+10
14~15
8+5
第三步：
fi（S3）=max{10Xi+f2（Sz）|Xi€D（Si）}
S2=S〔-3Xi
10Xi+f2（Si-3Xi）
X1=0
X1=1
f1（S1）
10+15
20+10
顺序追踪：
最优策略为
S3=9
J
X3*=2
Si=15tS2=9t
Xi*=2X2*=0
最优装载方案为：
货物1装2件；
货物2不装；
货物3装2件
装载收费为30元
5.用动态规划方法解下列0—1背包问题：
Maxf=12x1+12x2+9x3+16x4+30x5;
s.t.3x1+4x2+3x3+4x4+6x5<
12;
Xj=0,1,j=1,,5
本问题分为5个阶段。
令
sk--akXk+…+a4X4的允许值
Xk—第k阶段Xk取值，Xk=0,1
Wk（Sk,Xk）Xk产生的价值：
Wk（Sk,Xk）=ckXk
Tk（Sk,Xk）Sk+1=Sk-akXk
fk（Sk）在akXk+…+a4X4<
Sk的条件下，ckXk+…+c4X4能
取得的最大值。
k=5
k=4
fk（Sk）=max{ckXk+fk+i（Sk+i）},k=5,4,3,2,1
S5
30x5
f5（S5）
X5*
X5=0
X5=1
0~5
6〜12
f5（S5）=max{30x5}
X5€D5（S5）
f4（S4）=max{16x4+f5（S5）}
X4€D4（S4）
S5=S4-4X4
S4
16X4+f5（S4-4X4）
f4（S4）
X4*
X4=0
X4=1
4~5
16+0
16
6~9
0+30
10~12
16+30
46
k=3
f3（S3）=max{9x3+f4（S4）}
X3匕D3（S3）
9X3+f4（S3-3X3）
f3（S3）
0~2
9+0
0+16
7〜8
9+16
9+30
39
10〜12
0+46
S4=S3-3X3
k=1厂
k=2
f2（s2）=max{i2x2+f3（s3）}
1|x2GD2（s2）
匸S3=S2-4x2
i2X2+f3（S2-4X2）
f2（S2）
X2=i
0+9
4〜5
0+i6
i2+0
i6
7
i2+9
i2+i6
0+39
io
i2+30
ii~i2
fi（si）=max{12xi+f2（S2）}
xiGDi（si）
.S2=si-3xisi=12
i2xi+f2（si-3xi）
fi（Si）
Xi*
xi=0
xi=i
i2
i2+39
5i
si=12—S2=9—S3=9—►S4=6—^S5=6
X1*=1X2*=0X3*=1X4*=0X5*=1
11.今设计一种由4个元件串联而成的部件，为提高部件的可靠性，每一元件可以由1个、2个或3个并联的单位元件组成。
关于元件K
（K=1，2，3，4）配备j个并联单位元件（j=1，2，3）后的可靠性
Rkj和成本Ckj由表给出，假设该部件的总成本允许为15个单位，试问如何确定各元件的单位元件配备数目，使系统的可靠性最高？
j
K=3
K=4
R1j
C1j
R2j
C2j
R3j
C3j
R4j
C4j
0.7
0.6
0.9
0.8
0.75
0.82
0.85
逆序解法。
Sk仪表上配备k#,…，4#元件时允许使用的费用
XkK#元件所选用的单位元件
Wk（Sk,Xk）――K#元件采用单位元件时的可靠性，有
Wk（Sk,Xk）=RkXk
Tk（Sk,Xk）Sk+仁Sk-CkXk
fk（Sk）――在费用限额为Sk的条件下，k#,…，3#元件串联时相应
部分可获得的最大可靠性
递归方程f4（S5）=1
fk（Sk）=max{Wk（Sk,Xk）•fk+1（Sk+1））,K=4,3,2,1.
第一步，对K=4,
R4X4
F4（S1）
X4=2
R3X3•f1（S3-C3X3）
0.9X0.8
0.72
0.9X0.82
0.738
第三步，对K=2,
R2X2•f3（S2-C2X2）
0.6X0.72
0.432
0.6X0.738
0.8X0.72
0.576
11
第四步，对K=4,f4（S4）=max{R4X4•f3（S3）}
S3=S4-C4X4,S4=15
R1X1•f2（S41-C1X1）
f1（S4）
X*1
X1=1X1=2X1=3
0.7X0.5760.75X0.5760.85X0.432
Sl=15fS3=10fS2=6fSl=3
Xi*=2X2*=2X3*=1X4*=1
元件1为2个，元件2为2个，元件3为1个，元件4为1个，可靠
性为0.432。
顺序解法:
Sk――仪表上配备1#,…，K#元件时允许使用的费用
Wk（Sk,Xk）――K#元件采用单位元件时的可靠性，有
Wk（Sk，Xk）二RkXk
Tk（Sk，Xk）Sk-仁Sk-CkXk
fk（Sk）――在费用限额为Sk的条件下，1#,…，K#元件串联时相应部分可获得的最大可靠性
递归方程fo（So）=1
fk（Sk）=max{Wk（Sk，Xk）•fk-1（Sk-1）}，K=1，2，3，4
第一步，对K=1,f1（S1）=max{R1X1}
4<
=Sk=7
S1={4,5,6,7}
D1（S1）
{1}
{1,2}
{1,2,3}
R1X1
第二步，对K=2,f2（S2）=max{R2x2.fi（Si”
Sl=S2-C2X2
6v=S2V=9
S2={6,7,8,9}
{1,2}
R2X2•f1（S2-C2X2）
0.6X0.7
0.42
0.6X0.75
0.45
0.8X0.7
0.56
0.6X0.8
0.8X0.75
第三步，对K=3,f3（S3）=max{R3X3.f2（S2）}
S2=S3-C3X3
9v=S2<
=12
S2={9,10,11,12}
D3（S3）
R3X3•f2（S3-C3X3）
0.9X0.42
0.378
0.9X0.45
0.405
0.9X0.56
0.504
一一
--
0.9X0.6
0.54
R4X4•f3（S4-C4X4）
f4（S4）
0.8X0.54
0.82X0.405
S4=15tS3=12tS2=9tS1=5
JJJ
X4*=1
X3*=1X2*=2X1*=2
升级会员 