运筹学14-动态规划II-11培训资料.ppt

第14讲 动态规划II 本讲提纲——动态规划应用举例 1. 资源分配问题 2. 背包问题 3. 机器负荷分配问题 4. 生产-库存问题 1. 资源分配问题 一般提法：设有某种资源，总量为a，可分配给n种生产经营活动，已知若向第i种活动分配xi数量的资源，可获得收益gi(xi)，问应如何分配资源，可获得最大收益？ 该问题的动态规划模型为： 阶段：按生产经营活动划分阶段，k=1,2,…,n 状态变量：sk表示可用于分配给第k至第n阶段的资源数量 决策变量： xk表示分配给第k阶段的资源数量 允许决策集合：Dk(sk)={xk |0≤ xk ≤sk} 状态转移方程： sk+1 = sk- xk 动态规划方程： 例：设有300万元资金用于3个工厂的扩建，已知每个工厂的利润增长额同投资额的大小有关，见下表。问应如何确定对这3个工厂的投资额，使总利润增长额最大。 投资额 工厂 0 100 200 300 1 0 2.5 4 10 2 0 3 5 8.5 3 0 2 6 9 表1 利润增长额 （万元） s3 D3(s3) r3(s3, x3) f3(s3) x3* 0 0 0* 0 0 100 0 100 0 2* 2 100 200 0 100 200 0 2 6* 6 200 300 0 100 200 300 0 2 6 9* 9 300 k = 3: k = 2：根据递归方程，最优指标函数为 状态转移方程： s2 D2(s2) s3 r2(s2, x2)+f3(s3) f2(s2) x2* 0 0 0 0+f3(0)=0+0=0* 0 0 100 0 100 100 0 0+f3(100)=0+2=2 3+f3(0)=3+0=3* 3 100 200 0 100 200 200 100 0 0+ f3(200)=0+6=6* 3+ f3(100)=3+2=5 5+ f3(0)=5+0=5 6 0 300 0 100 200 300 300 200 100 0 0+ f3(300)=0+9=9* 3+ f3(200)=3+6=9* 5+ f3(100)=5+2=7 8.5+f3(0)=8.5+0=8.5 9 0,100 k = 2: k = 1：根据递归方程，最优指标函数为 状态转移方程： s1 D1(s1) s2 r1(s1, x1)+f2(s2) f1(s1) x1* 300 0 100 200 300 300 200 100 0 0+ f2(300)=0+9=9 2.5+ f2(200)=2.5+6=8.5 4+ f2(100)=4+3=7 10+f2(0)=10+0=10* 10 300 k = 1: s1 D1(s1) s2 r1(s1, x1)+f2(s2) f1(s1) x1* 300 0 100 200 300 300 200 100 0 0+ f2(300)=0+9=9 2.5+ f2(200)=2.5+6=8.5 4+ f2(100)=4+3=7 10+f2(0)=10+0=10* 10 300 s2 D2(s2) s3 r2(s2, x2)+f3(s3) f2(s2) x2* 0 0 0 0+f3(0)=0+0=0* 0 0 100 0 100 100 0 0+f3(100)=0+2=2 3+f3(0)=3+0=3* 3 100 200 0 100 200 200 100 0 0+ f3(200)=0+6=6* 3+ f3(100)=3+2=5 5+ f3(0)=5+0=5 6 0 300 0 100 200 300 300 200 100 0 0+ f3(300)=0+9=9* 3+ f3(200)=3+6=9* 5+ f3(100)=5+2=7 8.5+f3(0)=8.5+0=8.5 9 0,100 s3 D3(s3) r3(s3, x3) f3(s3) x3* 0 0 0* 0 0 100 0 100 0 2* 2 100 200 0 100 200 0 2 6* 6 200 300 0 100 200 300 0 2 6 9* 9 300 (3) 回溯寻优 2. 背包问题 一般的提法为：一旅行者携带背包去登山。已知他所能承受的背包重量的极限为W(千克)，现有n种物品可供他选择装入背包。第i种物品的单位重量为 (千克)，第i种物品