运筹学习题解答(chap8 动态规划) .pdfVIP

第八章动态规划

一、用逆序法求解下列问题

1、P237,8.1有600万元资金用于三个工厂的更新改造，投资数以百万元

为单位取整数，已知工厂II的投资不超过300万元，工厂I和III的投资均不少

于100万元，又不超过400万元，已知各工厂投资更新改造后，每年可增加的效

益如下表，试用动态规划方法确定投资分配方案，使预期效益为最大。(单位：

万元)

投资0

100200300400

工厂

I--361114

II051012-

III--481115

解：该问题可分为3个阶段，分别为分配资金给Ⅰ、Ⅱ、Ⅲ三个厂。

设k为阶段变量，第k个阶段给第k个厂分配设备；

S是第k个阶段的状态变量，表示可分配给第k个厂到第3个厂的设备数；

k

x是第k个阶段的决策变量，表示分配给第k个厂的设备数；

k

状态转移方程：SSx，并且S4。

k1kk1

指标函数：f(S)max[r(s,x)f(S)]

kkkkkk1k1

x

k

f(S)0

44

下面按照逆序解法求解。

第三阶段：S100,200,300,400，500万，Sx,

333

X

3f(S)r(s,x)f(S)X

33333333

100200300400

S

3

10044100

200488200

300481111300

40048111515400

50048111515400

第二阶段：S200,300,400,500万。SSx

2322

X

2f(S)