动态规划习题答案
- 格式：pdf
- 大小：108.38 KB
- 文档页数：20
2.某公司有资金4百万元向A,B和C3个项目追加投资，各个项目可
以有不同的投资额（百万元计），相应的效益如表所示。问怎样分配
资金，使总效益值最大？##
表8－47
投 资 额Wk (X
k)
（项目k#01234
1#（A）－41486066
2#（B ）40425060－
3#（C）－64687884
解：设S1－A,B,C项目的总投资额，S2－B、C项目的总投资额
S
3－C项目的投资额；
X
k－k项目的投资额；
（X1－A项目的投资额，X2－B项目的投资额，X3－C项目的投资
额）
W
k（Sk,X
k）－对K项目投资Xk后的收益：Wk（Sk,X
k）＝Wk (X
k)
T
k (S
k,X
k)－S
k+1=S
k-X
k
f
k (S
k)－当K至第3项目允许的投资额为S
k时所能获得的最大收益。
为获得最大利润，必须将4百万全部投资，假设有4阶段存在，有S
4＝0，建立递归方程
f
4 (S
k)=0
f
k (S
k)=max{ W
k (X
k)+f
k +1(S
k+1)} k=3,2,1
X
k∈Dk(S
k)
第一步，K=3
f
4(S
4)=0
f
3 (S
3)=max{W
3 (X
3)+f
4 (S
4)}
X
3∈D3(S
3)
S
4=S
3-X
3
S3f
3 (S
3)X
3*
1641
2682
3783
4844
第二步：
K=2 f
2 (S
2)=max{W
2 (X
2)+f
3 (S
3)}
X
2∈D2(S
2)
S
3=S
2-X
2 W
2 (X
2)+f
3 (S
2-X
2)
S
2X
2 =0X
2 =1X
2 =2X
2 =3f
2 (S
2)X
2 *
140+64－－－1040
240+6842+64－－1080
340+7842+6850+64－1180
440+8442+7850+6860+641240，3第三步：
K=1 f
1 (S
1) =max {W
1 (X
1)+ f
2 (S
2)}
X
1∈D1(S
1)
S
2= S
1- X
1
W
1 (X
1)+ f
2 (S
1- X
1)
S
1X
1=0X
1=1X
1=2X
1=3f
1 (S
1)X
1 *
4－41+118 48+10860+1041643
S
1=4 → S
2=1 → S
3=1
↓ ↓ ↓
X
1*=3 X
2*=0 X
3*=1A投资3百万， B不投资 C投资1百万。
总收益 164百万元。
3.（最优分配问题）有一个仪表公司打算向它的3个营业区设
立6家销售店。每个营业区至少设一家，所获利润如表。问设立的
6家销售店数应如何分配，可使总利润最大？
营 业 区Ak利 润
w
k(x)A
1A
2A
3
销售
店数x1
2
3
4200
280
330
340210
220
225
230180
230
260
280
解：sk——对k#,…,3#营业区允许设立的销售店数
xk——对k#营业区设立的销售店数
w
k (s
k,x
k)——对k#营业区设立x
k销售店后的利润：
wk (sk,,xk)= wk (xk)
T
k (s
k, x
k)——s
k +1= s
k - x
k
f
k (s
k)——当第k至第3个营业区允许设立的销售店数为
s
k时所能获得的最大利润
递归方程：f
4(s
4)=0
f
k (s
k)=max ｛wk (xk)+ fk+1(sk+1)｝, k=3,2,1
xk∈Dk(sk)
k=3时，有方程
f
4 (s
4)=0
f3(s3)= max ｛w3(x3)+ f4(s4) ｝
x
3∈D3(s3)
s3=s2—x2
s3f3(s3)x3*
11801
22302
32603
42804
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=4
2210+180///3901
3210+230220+180//4401
4210+260220+230225+180/4701
5210+280220+260225+230230+1804901
k=1,有方程
f1(s1)= max ｛w1(x1)+ f2(s2) ｝
x1∈D1(s1)
s2=s1—x1
w
1(x
1)+ f2(s
1—x
1)
s
1
x
1=1x
1=2x
1=3x
1=4f
1(s
1
)x
1*
6200+490280+470330+440340+3907703
s1=6 → s2=3 → s3=2
↓ ↓ ↓
x
1*=3 x
2*=1 x
3*=2
分别A1、A2、A3营业区设立3家、1家、2家销售店，最大利润
为770 4．用动态规划方法求解下列模型：
maxf=10X
1+4X
2+5X
3
s.t. 3X
1+5 X
2+4 X
3≤15
0≤X
1≤2 0≤X
2≤2 X
3≥0 ，X
j为整数 j=1,2,3
解：收费C1=10 C
2=4 C
3=5
X
1为货物1的装载件数
X
2为货物2的装载件数
X
3为货物3的装载件数
分3阶段
S
1为货物1、2、3允许的装载重量（3X1+5 X
2+4 X
3的允许值）
S
2为货物2、3允许装载的重量（5 X2+4 X
3的允许值）
S
3 为货物3允许装载的重量（4 X3的允许值）
第一步：K=3
f
4(S
4)=0
f
3(S
3)= max{5X
3+ f
4(S
4)| X
3∈D
3（S3）}
S
4= S
3 -4 X
3
S
30~34~78~1112~15
D
3(S
3){0}{0,1}{0,1,2}{0,1,2,3}
S
3X
3=0X
3=1X
3=2X
3=3f
3 (S
3)X
3*
0~30+0__________________00
4~70+05+0____________51
8~110+05+010+0______102
12~150+05+010+015+0153
第二步：K=2
f
2(S
2)= max{4X
2+ f
3(S
3)| X
2∈D
2（S2）}
S
3= S
2 -5 X
2
划分点：
04812
004812S
20~45~910~15
D
2 (S
2){0}{0,1}{0,1,2}
5591317
1010141822
4X
2+ f
3(S
2 -5 X
2)
S
2X
2=0X
2=1X
2=2f
2 (S
2)X
2*
0~30+0____________00
40+5____________50
5~70+54+0______50
80+104+0______100
90+104+5______100
10~110+104+58+0100
120+154+58+0150130+154+108+0150
14~150+154+108+5150
第三步：K=1
f
1(S
3)= max{10X
1+ f
2(S
2)| X
1∈D
1（S1）}
S
2= S
1-3 X1
10X
1+ f
2(S
1-3 X1)
S
1X
1=0X
1=1X
1=2f
1 (S
1)X
1*
150+1510+1520+10302
顺序追踪：最优策略为
S
1=15 → S
2=9 → S
3=9
