最新动态规划习题答案

2.某公司有资金4百万元向A,B和C3个项目追加投资，各个项目可以有不同的投资额（百万元计），相应的效益如表所示。问怎样分配资金，使总效益值最大？##

表8－47

解：设S1－A,B,C项目的总投资额，S2－B、C项目的总投资额

S3－C项目的投资额；

X k－k项目的投资额；

（X1－A项目的投资额，X2－B项目的投资额，X3－C项目的投资额）W k（S k,X k）－对K项目投资X k后的收益：W k（S k,X k）＝W k (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阶段存在，有S4＝0，建立递归方程

f4 (S k)=0

f k (S k)=max{ W k (X k)+f k +1(S k+1)} k=3,2,1

X k∈D k(S k)

第一步，K=3

f4(S4)=0

f3 (S3)=max{W3 (X3)+f4 (S4)}

X3∈D3(S3)

S4=S3-X3

第二步：

K=2 f2 (S2)=max{W2 (X2)+f3 (S3)}

X2∈D2(S2)

S3=S2-X2

W2 (X2)+f3 (S2-X2)

第三步：

K=1 f1 (S1) =max {W1 (X1)+ f2 (S2)}

X1∈D1(S1)

S2= S1- X1

W1 (X1)+ f2 (S1- X1)

S1=4 →S2=1 →S3=1

↓↓↓

X1*=3 X2*=0 X3*=1

A投资3百万，B不投资C投资1百万。

总收益164百万元。

3.（最优分配问题）有一个仪表公司打算向它的3个营业区设立6家销售店。每个营业区至少设一家，所获利润如表。问设立的6家销售店数应如何分配，可使总利润最大？

解：s k——对k#,…,3#营业区允许设立的销售店数

x k——对k#营业区设立的销售店数

w k (s k,x k)——对k#营业区设立x k销售店后的利润：

w k (s k,,x k)= w k (x k)

T k (s k, x k)——s k +1= s k - x k

f k (s k)——当第k至第3个营业区允许设立的销售店数为s k 时所能获得的最大利润

递归方程：

f4(s4)=0

f k (s k)=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

k=2,有方程

f2(s2)= max ｛w2(x2)+ f3(s3) ｝

x2∈D2(s2)

s3=s2—x2

k=1,有方程

f1(s1)= max ｛w1(x1)+ f2(s2)

｝ x1∈D1(s1) s2=s1—x1

s1=6 → s2=3 → s3=2

↓ ↓ ↓

x1*=3 x2*=1 x3*=2

分别A1、A2、A3营业区设立3家、1家、2家销售店，最大利润为770

4．用动态规划方法求解下列模型：

maxf=10X1+4X2+5X3

s.t. 3X1+5 X2+4 X3≤15

0≤X1≤2 0≤X2≤2 X3≥0 ，X j为整数j=1,2,3

解：收费C1=10 C2=4 C3=5

X1为货物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=3

f4(S4)=0

f3(S3)= max{5X3+ f4(S4)| X3∈D3（S3）}

S4= S3 -4 X3

第二步：K=2

f2(S2)= max{4X2+ f3(S3)| X2∈D2（S2）} S3= S2 -5 X2

划分点：

第三步：K=1

f1(S3)= max{10X1+ f2(S2)| X1∈D1（S1）}

S2= S1-3 X1

10X1+ f2(S1-3 X1)

顺序追踪：最优策略为

S1=15 →S2=9 →S3=9

↓↓↓

X1*=2 X2*=0 X3*=2

最优装载方案为：货物1装2件；货物2不装；货物3装2件装载收费为30元

5.用动态规划方法解下列0—1背包问题：

Max f =12x1+12x2+9x3+16x4+30x5；

s.t. 3x1+4x2+3x3+4x4+6x5≤12;

x j=0,1, j=1,……，5

解：本问题分为5个阶段。令

s k——a k x k+…+a4x4的允许值

x k——第k阶段x k取值，x k=0，1

w k (s k , x k )——x k 产生的价值：w k (s k , x k )=c k x k T k (s k , x k )——s k+1=s k - a k x k

f k (s k )——在a k x k +…+ a 4x 4≤s k 的条件下，c k x k +…+c 4x 4能

取得的最大值。

递归方程为

k=5 f 5(s 5}