十动态规划的应用---资源分配问题辩析.ppt

* * 设有某种原料，总数量为 a，用于生产 n 种产品。若分配数量 xi 用于生产第 i 种产品，其收益为 gi ( xi )，问应如何分配，才能使生产 n 种产品的总收入最大？ 资源分配问题 1 资源平行分配问题 Max Z = g1(x1)+g2(x2)+ ?+gn(xn) s.t. x1+ x2 + ? + xn = a xi ? 0 i = 1, 2, ?, n 静态规划模型 不考虑回收 例3 某公司拟将5台某种设备分配给所属的甲、乙、丙三个工厂，各工厂若获得这种设备，可以为公司提供的盈利如表。 问：这五台设备如何分配给各工厂，才能使公司得到的盈利最大。 0 4 6 11 12 12 0 5 10 11 11 11 0 3 7 9 12 13 0 1 2 3 4 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 如何划分阶段 s1的可达状态集合 s2的可达状态集合 s3的可达状态集合 决策变量 uk(sk) 0? ? sk 3个阶段 xk 状态转移方程？ 甲 乙 丙 0 1 2 3 4 5 0 3 7 9 12 13 0 5 10 11 11 11 0 4 6 11 12 12 s1 s2 s3 3 2 1 x1 x2 x3 基本方程? 指标函数gk(xk)? s4 解：将问题按工厂分为三个阶段，甲、乙、丙分别编号为1，2，3。 决策变量xk:: 分配给生产第 k 个工厂的设备数量 分配给第 k 个工厂至第 3 个工厂的设备数量（第k阶段开始剩余的设备数量）。 状态变量 sk : 甲 乙 丙 0 1 2 3 4 5 0 3 7 9 12 13 0 5 10 11 11 11 0 4 6 11 12 12 Dk ( sk )={ uk|0?uk= xk ? sk } 基本方程： 数量为 sk 的设备分配给第 k 个工厂至第 3 个工厂所得到的最大总收益 状态转移方程: sk+1 = sk - xk xk的取值范围？ 甲 乙 丙 0 1 2 3 4 5 0 3 7 9 12 13 0 5 10 11 11 11 0 4 6 11 12 12 x3*(0) = 0 x3*(1) = 1 x3*(2) = 2 x3*(3) = 3 k =3，s3=0,1,2,3,4,5，0? x3 ? s3 s3 = 0 s3 = 3 甲 乙 丙 0 1 2 3 4 5 0 3 7 9 12 13 0 5 10 11 11 11 0 4 6 11 12 12 0 4 6 11 12 12 s3 = 2 s3 = 1 甲 乙 丙 0 1 2 3 4 5 0 3 7 9 12 13 0 5 10 11 11 11 0 4 6 11 12 12 x3*(5) = 4,5 x3*(4) = 4 0 4 6 11 12 12 x3 s3 g3(x3) f3(s3) x*3 0 1 2 3 4 5 0 1 2 3 4 5 0 4 6 11 12 12 12 0 4 6 11 12 12 0 1 2 3 4 4,5 结果可写成表格的形式: s3 = 4 s3 = 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 k =2，s3 = s2 - x2，s2=0,1,2,3,4,5，0? x2 ? s2，有 x2*(0) = 0 s2 = 0 x3 s3 g3(x3) f3(s3) x*3 0 1 2 3 4 5 0 1 2 3 4 5 0 4 6 11 12 12 12 0 4 6 11 12 12 0 1 2 3 4 4,5 x2*(1) =1 s2 = 1 甲 乙 丙 0 1 2 3 4 5 0 3 7 9 12 13 0 5 10 11 11 11 0 4 6 11 12 12 x3 s3 g3(x3) f3(s3) x*3 0 1 2 3 4 5 0 1 2 3 4 5 0 4 6 11 12 12 12 0 4 6 11 12 12 0 1 2 3 4 4,5 x2*(2) =2 s2 = 2 甲 乙 丙 0 1 2 3 4 5 0 3 7 9 12 13 0 5 10 11 11 11