一章动态规划应用举例.pptVIP

* 第6章 动态规划应用举例 第1节 资源分配问题 1.1 一维资源分配问题 资源分配问题可描述如下：设有某种原料，总数量为a，分配给n个使用者。已知第i个使用者得到数量xi的该种资源，可创造的收益为gi(xi)。问应如何分配该资源，才能使总收益最大。 用动态规划法处理这种问题时，通常把给各个使用者分配资源的过程分别看成一个阶段，按使用者分成先后的n个阶段。即先给第1个使用者分配资源，为第一阶段；再给第2个使用者分配，为第二阶段；依此类推，最后给第n个使用者分配，为第n阶段。 静态规划模型： 按使用者划分为n个阶段，k=1,2,..,n； 取第k阶段初（给第k个使用者分配资源时）资源的剩余量sk为状态变量，s1=a； 取分配给第k个使用者的资源数量xk为决策变量，0≤xk≤sk (k=1,2,…,n-1)， xn= sn； 状态转移方程为sk+1=sk-xk； 指标函数为Vk,n=?gj(xj)； 基本方程为： （k=n-1,…,2,1） 由于资源数量常常要求取整数，则状态变量和决策变量也就取整数，所以求解时常采用列表的形式。 例2 某工业部门根据国家计划安排，拟将五台某种高效率的机器分配给所属的甲、乙、丙三个工厂，各工厂得到不同数量的机器可获得的收益如下表。问应如何分配机器，才能使各厂的总效益最大。 0 0 0 3 5 4 7 10 6 9 11 11 12 11 12 13 11 12 0 1 2 3 4 5 甲 乙 丙 机器数 解： 分成3个阶段，k=1,2,3； sk为状态变量，s1=5； xk为决策变量，0≤xk≤sk，x3=s3； 状态转移方程sk+1= sk-xk ； 基本方程为： fk(sk)＝ max {gk(xk)+fk+1(sk+1)} k=2,1 0≤xk≤ sk f3(s3)＝s3 (x3*= s3) 当k=3时： 12 12* 5 5 12 12* 4 4 11 11* 3 3 6 6* 2 2 4 4* 1 1 0 0* 0 0 f3(s3) g3(x3) x3 s3 当k=2时： 21 0+12=12 5+12=17 10+11=21* 11+6=17 11+4=15 11+0=11 0 1 2 3 4 5 5 16 0+12=12 5+11=16* 10+6=16* 11+4=15 11+0=11 0 1 2 3 4 4 14 0+11=11 5+6=11 10+4=14* 11+0=11 0 1 2 3 3 10 0+6=6 5+4=9 10+0=10* 0 1 2 2 5 0+4=4 5+0=5* 0 1 1 0 0+0=0* 0 0 f2(s2) g2(x2)+f3(s3) x2 s2 当k=1时： 21 0+21=21* 3+16=19 7+14=21* 9+10=19 12+5=17 13+0=13 0 1 2 3 4 5 5 f1(s1) g1(x1)+f2(s2) x1 s1 总效益最大为21万元，分配方案为： (1)甲—0台, 乙—2台, 丙—3台；(2)甲—2台, 乙—2台, 丙—1台。 1.2 二维资源分配问题 二维资源分配问题可描述如下：设有两种原料，数量各为a和b，分配给n个使用者。已知第i个使用者得到两种资源的数量各为xi和yi时，可创造的收益为gi(xi, yi)。问应如何分配该资源，才能使总收益最大。 与一维资源分配问题类似，把给各个使用者分配资源的过程分别看成一个阶段，按使用者分成先后的n个阶段。由于要分配两种资源，所以状态变量要有两个，决策变量也要有两个。 静态规划模型： 按使用者划分为n个阶段，k=1,2,..,n； 取第k阶段初（给第k个使用者分配资源时）两种资源各自的剩余量sk和tk为状态变量, s1=a, t1=b； 取分配给