动态规划习题答案.docx
- 文档编号:2424761
- 上传时间:2023-05-03
- 格式:DOCX
- 页数:17
- 大小:28.02KB
动态规划习题答案.docx
《动态规划习题答案.docx》由会员分享,可在线阅读,更多相关《动态规划习题答案.docx(17页珍藏版)》请在冰点文库上搜索。
动态规划习题答案
2.某公司有资金4百万元向A,B和C3个项目追加投资,各个项目可以有不同的投资额(百万元计),相应的效益如表所示。
问怎样分配资金,使总效益值最大?
##
表8-47
Wk(Xk)
(项目k#
投
资
额
0
1
2
3
4
#
1(A)
—
41
48
60
66
#
2(B)
40
42
50
60
—
#
3(C)
—
64
68
78
84
解:
设Si-A,B,C项目的总投资额,S2-B、C项目的总投资额
S3-C项目的投资额;
Xk-k项目的投资额;
(Xi-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
k=3,2,1
fk(Sk)二max{Wk(Xk)+fk+i(Sk+i)}
Xk€Dk(Sk)
第一步,K=3
f4(S4)=0
f3(S3)=max{W3(X3)+f4(S)}
X3^D3(S3)
S4=S3-X3
S3
f3(S3)
X3*
1
64
1
2
68
2
3
78
3
4
84
4
第二步:
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
0
2
40+68
42+64
一
一
108
0
3
40+78
42+68
50+64
一
118
0
4
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*
4
一
41+118
48+1
60+10
164
3
08
4
Xi*=3X2*=0
A投资3百万,
X3*=i
B不投资
C投资i百万
JJ
总收益164百万元。
3.(最优分配问题)有一个仪表公司打算向它的3个营业区设立6家销售店。
每个营业区至少设一家,所获利润如表。
问设立的6家销售店数应如何分配,可使总利润最大?
利润
Wk(x)
营业
区Ak
A
A
A
1
200
210
180
销售
2
280
220
230
店数x
3
330
225
260
4
340
230
280
#
解:
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*
1
180
1
2
230
2
3
260
3
4
280
4
k=2,有方程
f2(s2)=max{w2(x2)+f3(s3)}
x2€D2(s2)
s3=s2—x2
w2(x2)+f3(s2—x2)
f2(s
2)
x2=1
x2=2
x2=3
x2=4
s2
2
210+1
80
/
/
/
390
1
3
210+2
30
220+1
80
/
/
440
1
4
210+2
60
220+2
30
225+1
80
/
470
1
5
210+2
80
220+2
60
225+2
30
230+1
80
490
1
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
40
340+3
90
770
3
s1=6ts2=3ts3=2
xi*=3x2*=1x3*=2
分别A1、A2、A3营业区设立3家、1家、2家销售店,最大利润为
770
4.用动态规划方法求解下列模型:
maxf=10X1+4X2+5X3
s.t.3X1+5X2+4Xs<15
0 解: 收费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 f4(S4)=0 f3(S3)=max{5X3+f4(S4)|X3^D3(S3)} S4=S3-4X3 S3 0~3 4~7 8~11 12~15 D3(S3) {0} {0,1} {0,1,2} {0,123} S3 X3=0 X3=1 X3=2 X3=3 f3(S3) X3* 0~3 0+0 0 0 4~7 0+0 5+0 5 1 8~11 0+0 5+0 10+0 10 2 12~15 0+0 5+0 10+0 15+0 15 3 第二步: K=2 f2(S2)=max{4X2+f3(S3)|X2€D2(S2)} S3=S2-5X2 S2 0~4 5~9 10~15 D2(S2) {0} {0,1} {0,1,2} 划分点: 0 4 8 12 0 0 4 8 12 5 5 9 13 17 10 10 14 18 22 S2 4X2+f3(S2-5X2) f2(S2) X2* X2=0 X2=1 X2=2 0~3 0+0 0 0 4 0+5 5 0 5~7 0+5 4+0 5 0 8 0+10 4+0 10 0 9 0+10 4+5 10 0 10~11 0+10 4+5 8+0 10 0 12 0+15 4+5 8+0 15 0 13 0+15 4+10 8+0 15 0 14~15 0+15 4+10 8+5 15 0 第三步: K=1 fi(S3)=max{10Xi+f2(Sz)|Xi€D(Si)} S2=S〔-3Xi 10Xi+f2(Si-3Xi) S1 X1=0 X1=1 X1=2 f1(S1) X1* 15 0+15 10+15 20+10 30 2 顺序追踪: 最优策略为 S3=9 J X3*=2 Si=15tS2=9t JJ 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 取得的最大值。 Xk€Dk(Sk) 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 0 0 0 6〜12 0 30 30 1 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 0~3 0+0 0 0 4~5 0+0 16+0 16 1 6~9 0+30 16+0 30 0 10~12 0+30 16+30 46 1 k=3 f3(S3)=max{9x3+f4(S4)} X3匕D3(S3) S3 9X3+f4(S3-3X3) f3(S3) X3* X3=0 X3=1 0~2 0+0 0 0 3 0+0 9+0 9 1 4~5 0+16 9+0 16 0 6 0+30 9+0 30 0 7〜8 0+30 9+16 30 0 9 0+30 9+30 39 1 10〜12 0+46 9+30 46 0 S4=S3-3X3 k=1厂 k=2 f2(s2)=max{i2x2+f3(s3)} 1|x2GD2(s2) 匸S3=S2-4x2 S2 i2X2+f3(S2-4X2) f2(S2) X2* X2=0 X2=i 0~2 0+0 0 0 3 0+9 9 0 4〜5 0+i6 i2+0 i6 0 6 0+30 i2+0 30 0 7 0+30 i2+9 30 0 8 0+30 i2+i6 30 0 9 0+39 i2+i6 39 0 io 0+46 i2+30 46 0 ii~i2 0+46 i2+30 46 0 fi(si)=max{12xi+f2(S2)} xiGDi(si) .S2=si-3xisi=12 Si i2xi+f2(si-3xi) fi(Si) Xi* xi=0 xi=i i2 0+46 i2+39 5i i 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=1 K=2 K=3 K=4 R1j C1j R2j C2j R3j C3j R4j C4j 1 0.7 4 0.6 2 0.9 3 0.8 3 2 0.75 5 0.8 4 0.82 5 3 0.85 7 解: 逆序解法。 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, S4 R4X4 F4(S1) X4* X4=1 X4=2 3 0.7 — 0.8 1 4 0.8 — 0.8 1 5 0.8 0.82 0.82 2 6 0.7 0.82 0.82 2 第二步: S3 R3X3•f1(S3-C3X3) f2(S2) X3* X3=1 6 0.9X0.8 0.72 1 7 0.9X0.8 0.72 1 8 0.9X0.82 0.738 1 9 0.9X0.82 0.738 1 第三步,对K=2, S2 R2X2•f3(S2-C2X2) f2(S2) X2* X2=1 X2=2 8 0.6X0.72 — 0.432 1 9 0.6X0.72 — 0.432 1 10 0.6X0.738 0.8X0.72 0.576 2 11 0.6X0.738 0.8X0.72 0.576 2 第四步,对K=4,f4(S4)=max{R4X4•f3(S3)} S3=S4-C4X4,S4=15 S1 R1X1•f2(S41-C1X1) f1(S4) X*1 X1=1X1=2X1=3 15 0.7X0.5760.75X0.5760.85X0.432 0.432 2 Sl=15fS3=10fS2=6fSl=3 Xi*=2X2*=2X3*=1X4*=1 元件1为2个,元件2为2个,元件3为1个,元件4为1个,可靠 性为0.432。 顺序解法: Sk――仪表上配备1#,…,K#元件时允许使用的费用 XkK#元件所选用的单位元件 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} S1 4 5 6 7 D1(S1) {1} {1,2} {1,2} {1,2,3} S1 R1X1 f1(S1) X1* X1=1 X1=2 X1=3 4 0.7 — — 0.7 1 5 0.7 0.75 — 0.75 2 6 0.7 0.75 — 0.75 2 7 0.7 0.75 0.8 0.8 3 第二步,对K=2,f2(S2)=max{R2x2.fi(Si” Sl=S2-C2X2 6v=S2V=9 S2={6,7,8,9} S2 6 7 8 9 D2(S2) {1} {1} {1,2} {1,2} S2 R2X2•f1(S2-C2X2) f2(S2) X2* X2=1 X2=2 6 0.6X0.7 — 0.42 1 7 0.6X0.75 — 0.45 1 8 0.6X0.75 0.8X0.7 0.56 2 9 0.6X0.8 0.8X0.75 0.6 2 第三步,对K=3,f3(S3)=max{R3X3.f2(S2)} S2=S3-C3X3 9v=S2<=12 S2={9,10,11,12} S3 9 10 11 12 D3(S3) {1} {1} {1} {1} S3 R3X3•f2(S3-C3X3) f3(S3) X3* X3=1 9 0.9X0.42 0.378 1 10 0.9X0.45 0.405 1 11 0.9X0.56 0.504 一一 1 -- 12 0.9X0.6 0.54 1 第四步,对K=4,f4(S4)=max{R4X4•f3(S3)} S3=S4-C4X4,S4=15 S4 R4X4•f3(S4-C4X4) f4(S4) X4* X4=1 X4=2 15 0.8X0.54 0.82X0.405 0.432 1 S4=15tS3=12tS2=9tS1=5 J JJJ X4*=1 X3*=1X2*=2X1*=2 元件1为2个,元件2为2个,元件3为1个,元件4为1个,可靠 性为0.432。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 动态 规划 习题 答案