11动态规划应用举例

第九章：动态规划应用举例

第一节：资源分配问题分配问题：将数量一定的一种或若干种资源 (例如原材料，资金，机器设备，劳力，食 品等等),恰当地分配给若干个使用者，使 效益函数最优。

资源分配

离 散

连 续

1.1 多元投资分配问题(离散) 设有某种原料，总数量为a,用于生产n种产品。若分配数量 xi用于生产第i种产品，其收益为gi(xi),问应如何分配，才能使 生产n种产品的总收入最大？MaxZ g1 x1 g 2 x2 g n xn x1 x2 xn a s.t. xi 0 i 1,2, , n

静态规划

决策变量uk表示分配给生产第k种产品的原料数量，即uk=xk; 设状态变量sk表示分配用于生产第k种产品至第n种产品的原料 数量； 状态转移方程： sk+1=sk-uk=sk-xk 决策集合：Dk(sk)={uk|0 uk=xk sk} 最优值函数fk(sk)表示数量为sk的原料分配给第k种产品至第n 种产品所得到的最大总收益，动态规划的递推关系为：

f k (sk ) max {g k ( xk ) f k 1 (sk xk )} 0 xk sk f n (sn ) max g n ( xn ) xn sn

k n 1, ,1

例1

某大型公司拟将某种高效率的设备5台分配给所属的甲、

乙、丙三个工厂，各工厂若获得这种设备之后，可以为公司提 供的盈利如表。问这五台设备如何分配给各工厂，才能使公司 得到的盈利最大。工厂 盈利 设备台数 0 1 2 3 4 5 甲 0 3 7 9 12 13 乙 0 5 10 11 11 11 丙 0 4 6 11 12 12

解：将问题按工厂分为三个阶段，甲乙丙分别编号为1,2,3。 用k表示，即阶段变量 决策变量uk表示分配给第k个工厂的设备台数，即uk=xk; 设状态变量sk表示为分配给第k个工厂至第3工厂的设备台数； 状态转移方程： sk+1=sk-uk=sk-xk 决策集合：Dk(sk)={uk|0 uk=xk sk} 最优值函数fk(sk)表示数量为sk的设备台数分配给第k个工厂至 第n个工厂所得到的最大总收益，动态规划的递推关系为：

f k ( sk ) max { g k ( xk ) f k 1( sk xk )} 0 xk sk f n ( sn ) max g n ( xn ) n 3 xn sn

k 3, ,1

用逆推法当阶段k=3时，0 s3 5, 0 x3 s3,有

f 3 s3 max [ g3 x3 f 4 s4 ]0 x3 s3

f 4 ( s4 ) 0

s3 0

f 3 (0) max {g 3 ( x3 ) f 4 ( s4 )} g 3 (0) 00 x3 s3 * x3 (0) 0

x3(s3)

s3 1

g 3 (0) f 3 (1) max {g 3 ( x3 ) f 4 ( s4 )} max 4 0 x3 s3 x3 0,1 g (1) 3 * x3 (1) 1

s3 2

g 3 (0) f 3 (2) max {g 3 ( x3 ) f 4 ( s4 )} max g 3 (1) 6 0 x3 s3 x3 0,1, 2 g (2) 3 * x3 (2) 2

s3 3

g 3 (0) g (1) 3 f 3 (3) max {g 3 ( x3 ) f 4 ( s4 )}

max 11 0 x3 s3 x3 0,1, 2,3 g ( 2) 3 g 3 (3) * x3 (3) 3

s3 4

g 3 ( 0) g (1) 3 f 3 (4) max {g 3 ( x3 ) f 4 ( s4 )} max g 3 (2) 12 0 x3 s3 x3 0,1, 2,3, 4 g (3) 3 g 3 ( 4) * x3 (4) 4

s3 5

g3( 0 ) g3( 1 ) g3( 2 ) f3( 5 ) max { g3( x3 ) f 4 ( s4 )} max 12 0 x3 s3 x3 0 ,1,2 ,3,4 ,5 g ( 3 ) 3 g3( 4 ) g3( 5 ) x* ( 5 ) 4 ,5 3

结果列于下表：x3 s3 0 1 2 3 4 5 0 0 1 4 6 11 12 12 g3(x3) 2 3 4 5 f3(s3) 0 4 6 11 12 12 x*3 0 1 2 3 4 4,5

当阶段k=2时， s3=s2-x2, 0 s2 5, 0 x2 s2,有

s2 0

f 2 (0) max {g 2 ( x2 ) f 3 ( s3 )} g 2 (0) 00 x2 s 2 * x2 (0) 0

s2 1

f 2 (1) max {g 2 ( x2 ) f 3 ( s3 )}0 x2 s 2 * x2 (1) 1

g 2 (0) f 3 (1) 0 4 max max 5 x2 0,1 g (1) f (0) 2 3 x2 0,1 5 0

s2 2

f 2 (2) max {g 2 ( x2 ) f 3 ( s3 )}0 x2 s 2 * x2 (2) 2

g 2 (0) f 3 (2) 0 6 max g 2 (1) f 3 (1) max 5 4 10 x2 0,1, 2 g (2) f (0) x2 0,1, 2 10 0 3 2 s2 3 f 2 (3) max {g 2 ( x2 ) f 3 ( s3 )}0 x2 s 2

g 2 (0) f 3 (3) 0 11 g (1) f (2) 5 6 2 3 max max 14 x2 0,1, 2,3 g ( 2) f (1) 3 2 x2 0,1, 2,3 10 4 g 2 (3) f 3 (0) 11 0

* x2 (3) 2

s2 4

f 2 (4) max {g 2 ( x2 ) f 3 ( s3 )}0 x2 s 2

g 2 (0) f 3 (4) 0 12 g (1) f (3) 5 11 3 2 max g 2 (2) f 3 (2) max 10 6 16 x2 0,1, 2,3, 4 g (3) f (1) x2 0,1, 2,3, 4 11 4 3 2 11 0 g 2 (4) f 3 (0) s2 5 f 2 (5) max {g 2 ( x2 ) f 3 ( s3 )}0 x2 s 2

* x2 (4) 1,2

g 2 (0) f 3 (5) g (1) f (4) 3 2 g 2 (2) f 3 (3) max x2 0,1, 2,3, 4,5 g (3) f ( 2) 3 2 g 2 (4) f 3 (1) g 2 (4) f 3 (1)

0 12 5 12 10 11 max 21 x2 0,1, 2,3, 4,5 11 6 11 4 11 0

* x2 (5) 2

结果列于下表：x2 s2 0 1 2 3 4 5 0 0 0+4 0+6 0+11 0+12 0+12 g2(x2)+f3(s2-x2) 1 2 3 5+0 5+4 5+6 5+11 5+12 4 5 f2(s2) x*2

10+0 10+4 10+6 10+11

0 0 5 1 10 2 11+0 14 2 11+4 11+0 16 1,2 11+6 11+4 11+0 21 2

当阶段k=1时， s2=s1-x1, s1=5, 0 x1 s1,有

s1 5

f1 ( s1 )

max {g1 ( x1 ) f 2 ( s2 )}0 x1 s1

g1 (0) f 2 (5) g (1) f (4) 2 1 g1 (2) f 2 (3) max {g1 ( x1 ) f 2 ( s1 x1 )} max x1 , 0,1, 2,3, 4,5 g1 (3) f 2 (2) g1 (4) f 2 (1) g1 (5) f 2 (0) 0 21 3 16 7 14 * max x1 (5) 0,2 21, 9 10 12 5 13 0

结果可写成表格的形式x1 s1 5 0 0+21 g1(x1)+f2(s1-x1) 1 2 3 3+16 7+14 9+10 4 5 12+5 13+0 f1(s1) x*1 21 0,2

然后按计算表格的顺序反推，可知最优分配方案有两个： 由于x1*=0,根据s2=s1-x1*=5-0=5,查表知x2*=2,由s3=s2-x2*=52=3,故x3*=s3=3。即得甲工厂分配0台，乙工厂分配2台，丙工 厂分配3台。 由于x1*=2,根据s2=s1-x1*=5-2=3,查表知x2*=2,由s3=s2-x2*=32=1,故x3*=s3=1。即得甲工厂分配2台，乙工厂分配2台，丙工 厂分配1台。 以上两个分配方案所得到的总盈利均为21万元。

问题：如果原设备台数是4台，求最优分配方案？ 如果原设备台数是3台，求最优分配方案？

1.2 资源连续分配问题: 一般问题的提法是 A种生产 数量u1投入 收益g(u1) 年终资源回收率a B种生产 数量s1-u1 收益h(s1-u1) 年终资源回收率b 第二年 资源数量 s2=au1+b(s1-u1) 到n年 A种生产 数量u2投入;收益g(u2);年终资源回收率a B种生产 数量s2-u2;收益h(s2-u2);年终资源回收率b

第一年

资源数 …… 此处隐藏：2343字，全部文档内容请下载后查看。喜欢就下载吧 ……