动态第三节动态应用举例

动态态规划应用举—分配问 等），可以投入下面讨论m=1的资源分配问设有数量为x0的某种资源，可投入n种生产。设以数量为xi的资源投入第i种生产，所得的效益gi(xi，问如何分配这种资源，能使总效益最大静态模数量为xi的资源投入i种生产所得的效益gixi所以，总效益g1(x1)g2(x2)gn(xn另外，xi的应满足约x1x2xn静态模型

2gi(xi2s.tx1

xi

0,i1,2,,n这个模型是一个静态模型，是线性或非线性规①阶段变选取n种生产过程作为阶段变②状态变把投入第种生产至第种生产的资源总量取为状态变量；③决策变把投入第k种生产的物资数量xk作为决策即，决策变uku1u1

阶段ununu2u2ukuk1第k阶段

x第k种生产至第n种生产的资源总~第k+1种生x至第n种生的资源总④状态转移方 ——第k种生产至第n种生产的资源总 -——第k+1种生产至第n种生产的资源总状态转移方

~xukx决策集

D(xk)uk0ukxk⑤策略

u1x1,u2x2,,un子策略：ukxk,uk1xk1,,un段指标阶段指标函数d(x,ukgkxkggj(xj第k阶段的效第k阶段到终点益指标函数Fknfkx表示以数量x的资源投入第k种生产⑦动态规划方由最优化原理，得动态规划方nfk(x) gi(xkpk,nPk,nik

g(xk) (xxk0ukxk

kfn1(x) kn,n要完成的任务是：求u1,u2,,un 最大，即F1,n 达到最大f1(x0)例题 五台设备分配给甲，乙个工厂，每个厂得到设备，年 情况如表3.1所示，问：分配给各厂设备各多少台，才使各厂总 最大。表甲乙丙000045解：这是一个一维分配问题，其中x0=5，g1x1g2(x2g3(x3分别为甲乙丙工厂在得到x1x2x3台设备后的值。由最优化原理，得动态规划方 (x)

g(xk) (xxkk0uk

xk

kf4x

k32由于x=0，1，2，3，4，5，状态变量已经离K=3f

(x)

g(x33由表3.1，

0u3

x3u30,f3(0)0u32,f3(2)6u34,f3(4)12

u31,f3(1)4u33,f3(3)u35,f3(5)12所以，u34或u3下面对计算过程做出解ukxk是决策变量，投入第k种生产的物资数 ——第k种生产至第n种生产的资源总量是状态变量0u3f3(0u3

x3

g(x33

表 表示以数量x的资源投入第3种生产时的最资源量x可以取而0uk xk

5当x 所以取值：0，1，…,

f3(0) maxg3(x3)g3(0)0u3当x f3(1)

0u3x3

g3

x3)maxg3(0),g3(1K=2时f2(x) 0u2x2

g(2

) (xx23 (0)

g(0)

u2(0) 0ux )

)

(1 0u2x2

x2

maxg2(0)f3(1),g2(1)f3(0max04,5u21 (2)

g(x2) (2x220u2

x2maxg2(0)f3(2),g2(1)f3(1g2(2)f3(0max06,54,100u22同理可求f2(3)14,u2(3)f2(4)16,u2(4)f2(5)21,u2(5)

u24现在解释u21fkx表示以数量x的资源投入第k种生至第n种生产时的最大max04,50f2(1)

以数量x=1的资源投入第2种生产至第3种生产时的最大决策变uk投入第k的物资决策变uk投入第k的物资

投入第2种生产的物资

u2表示以数量x=1的资源投入第2至第3种生产时的最优K=1时f1(x) 0u1x1

g1(x1)f2(xx1注意f1x)表示以x台设备投入第1至第3 取x=5（应该把所有资源都用上），于是f1(5)

g1(x1)f2(5x10u1x15maxg1(0)f2(5),g1(1)f2(4g1(2)f2(3 g1(3)f2(2g1(4)f

(1)g1(5)f2(0max021,316,714,910,125,130u150u15最后f15求出，u1x1f2xx1f25)f23u252u23

求出所以u3

u3 u10,u22,u3 u12,u22,u3 二背包问有一个人带一个背包上山可带物品重的限度是a公斤。设有种物品可供他选择装入背包中，这种物品 为1，，…，。已知第种物品每件重量为i公斤，在上山过程中的价值是携带量的函数ci(i)。问此人应该如何选择携带物品（各几件），使总价值最大。静态模设xii种物品的装入件数，则背包问nmaxcj(xjj

wjxjj0，整j1,2,,n下面介绍背包问题的动态规划解①阶段变按可装入物品的种类划分n

②状态变策变量决策变ukxk表示装入第k种物品的件

u1

u2

uk

uk1

unw装入第1种物品至第k

第k阶段

xk第k+1阶段状态变

~wxk④状态转移方 ——装入第1种物品至第k种物品的总重~——装入第1种物品至第k+1种物品的总重状态转移方

~wxk

w决策集

D(uk)

uk0uk

xk

第i物品件重

u1x1,u2x2,,un子策略 u1x1,u2x2,,uk段指标阶段指标函数dw,ukckxkk指标函数F1kcjxj第1阶段到第第1阶段到第k阶段前部指标函

第k阶段的价fkx表示当总重量不超过w公斤时，包中可以装入第种物品至第⑦动态规划方由最优化原理，得动态规划方f1(w)

x10,1,ww1

c1(x1fk(w)

ck(xk)fk1(wwkxkxk0,1,wwk要完成的任务是：

u1,u2,,un

2k使总价值达最大，即F1 达到最大fn(a例题maxf4x15x26x3x14x25x3xi

0整数,i1,2

可带物 第i种物品每件重量为 公nmaxcj(xjj

量的限aaa

wjxjjj0，整数j1,2为求f310)

f3(10)

4x15x263x14x25x3xi0整数i12 4x15x2(6x33x14x2105xi0整数i12

6x3

4x1

x2105x30x30整数

3x14x2105xi0,整数,i1,2 maxx3f2(105x3x30,1x3

x3

x3max0f2(10),6f2(5),12f2(0可看出，要计算f3(10 ，需计算出f2(10,f2(5),f2(0

.下面分别计f2(10

装入1

公斤

,f2(5,f2(0

公斤含义同

f2(10)

4x153x14x2xi0整数i1 4x1(5x23x1104xi0整数i1

5x

4x2104x20 3x1104 2x20,整数, x10,数 max5x2f1(104x2x20,1maxf1(10),5f1(6),10f1(2f2(10)max5x2f1(104x2x20x2

x2maxf1(10),5f1(6),10f1(2f1(10

f1(6

最大价

当总重量过w=6公斤

f1(2

f2(5)

4x153x14x2xi0整数i1max5x2f1(54x2x20maxf1(5),5f1(1f2(0)

4x153x14x2xi0整数i1max5x2f1(04x2x2f1(0可看出，要计，需计算

f2(10),f2(6),f2(0f1(10),f1(6),f1(5),f1(2),f1(1),f1(0下面分别计由 f1(w)

x1x10=4×(不超过w/3的最大整数 相应的最优决策为x1ww——装入第1种物品至第1种物品的总重量，

时，对应f1(w

当w10 时x1w33f1(10)4312

，此x1 w

时x1w3

，此f1(6)42

x1 w

时x1w3

，此f1(5)41同理，可算出其他

x1f1(2)40f1(1)40f1(0)40

x1x1x1于f2(10)maxf1(10),5f1(6),10f1(0f2(10) max5x2f2(10) max5x2f1(104x2x20,1maxf1(10),5f1(6),10f1(2最大值当w当w时x1w3，此