动态规划教学PPT.ppt

4动态规划 4 1多阶段决策问题与动态规划4 2动态规划的基本概念4 3动态规划的步骤4 4动态规划的应用1求解静态规划问题2资源分配问题3不确定性采购问题4排序问题 例2机器负荷分配问题某种机器可以在高低两种不同的负荷下进行生产 在高负荷下进行生产时 产品的年产量g和投入生产的机器数量u的关系为g g u 这时机器的年完好率为a 0 a 1 在低负荷下生产时 产品的年产量h和投入生产的机器数量v的关系为h h v 这时机器的年完好率为b a b 1 假定开始生产时完好的机器数量为s1 要求制定一个五年计划 在每年开始时决定机器在两种不同负荷下生产的数量 使五年内产品的总产量最高 4 1多阶段决策问题与动态规划 多阶段决策问题和我们前面遇到的决策问题不同 它是和时间有关的 与时间有关的活动过程称为动态过程 其优化方法称为动态规划 而与时间无关的活动过程称为静态过程 相应的的优化方法称为静态规划 1 阶段 stage 把所研究的决策问题 按先后顺序划分为若干相互联系的决策步骤 以便按一定的次序进行求解 描述阶段的变量称阶段变量 常用k表示 2 状态 state 状态表示每个阶段开始时所处的自然状况或客观条件 它描述了影响决策的因素随决策进程的变化情况 它既是前面阶段所作决策的结果 又是本阶段作出决策的出发点和依据 描述状态的变量称为状态变量 第k阶段的状态变量常用sk表示 通常 在第一阶段状态变量s1是确定的 称初始状态 3 决策 decision 决策表示在某一阶段处于某种状态时 决策者在若干种方案中作出的选择决定 描述决策的变量称决策变量 第k阶段的决策变量常用uk表示 决策变量的取值会受到状态变量的制约 被限制在某一范围之内 4 2动态规划的基本概念 一 4 策略 policy 把从第一阶段开始到最后阶段终止的整个决策过程 称为问题的全过程 而把从第k阶段开始到最后阶段终止的决策过程 或称为k子过程 在全过程上 各阶段的决策按顺序排列组成的决策序列p1 n u1 u2 un 称为全过程策略 简称策略 而在k子过程上的决策序列pk n uk uk 1 un 称为k子过程策略 也简称子策略 5 状态转移方程若第k阶段的状态变量值为sk 当决策变量uk的取值决定后 下一阶段状态变量sk 1的值也就完全确定 即sk 1的值对应于sk和uk的值 这种对应关系记为sk 1 tk sk uk 称为状态转移方程 状态转移方程描述了由一个阶段的状态到下一阶段的状态的演变规律 4 2动态规划的基本概念 二 6 指标函数和最优值函数指标函数分为阶段指标函数和过程指标函数 阶段指标函数是对某一阶段的状态和决策产生的效益值的度量 用vk sk uk 表示 过程指标函数是指过程所包含的各阶段的状态和决策所产生的总的效益值 记为vk n vk n sk uk sk 1 uk 1 sn un 动态规划所要求的过程指标函数应具有可分离性 即可表达为它所包含的各阶段指标函数的函数形式 常见的两种过程指标函数形式是 各阶段指标函数的和vk n vj sj uj 各阶段指标函数的积vk n vj sj uj 把过程指标函数vk n对k子过程策略pk n求最优 得到一个关于状态sk的函数 称为最优值函数 记为fk sk 即fk sk optvk n sk uk sn un uk un式中的 opt optimization 可根据具体问题而取min或max fk sk 表示第k阶开始状态为sk的情况下到末状态为sn作最优策略对应的指标值 7 基本方程通常动态规划问题的最优值函数满足递推关系式 设过程指标函数为各阶段指标函数的和的形式 即vk n vj sj uj 则有fk sk opt vk sk uk fk 1 sk 1 uk dk sk k n n 1 1 递推方程fn 1 sn 1 0边界条件递推方程和边界条件一起称为动态规划的基本方程 可根据边界条件 从k n开始 由后向前逆推 逐步求得各阶段的最优决策和相应的最优值 最后求出f1 s1 时 就得到整个问题的最优解 称为逆序解法 此问题的基本方程为fk sk min dk uk fk 1 sk 1 uk dk sk k 6 5 4 3 2 1f7 s7 0 4 3动态规划的步骤 一 当k 6时 按基本方程由后向前继续递推有 当k 5时 当k 4时 当k 3时 当k 2时 当k 1时 由此可以看出 a到g的最短路长为18 路径为 a b1 c2 d1 e2 f2 g 现在把动态规划法的步骤归纳如下 1 将所研究问题的过程划分为n个恰当的阶段 k 1 2 n 2 正确地选择状态变量sk 并确定初始状态s1的值 3 确定决策变量uk以及各阶段的允许决策集dk sk 4 给出状态转移方程 5 给出满足要求的过程指标函数vk n及相应的最优值函数 6 写出递推方程和边界条件 建立基本方程 7 按照基本方程递推求解 以上步骤是动态规划法处理问题的基本步骤 其中的前六步是建立动态规划模型的步骤 4 3动态规划的步骤 二 顺序解法 即解题顺序与决策顺序一致 4 3动态规划的顺序解法 三 即是在第k阶段末状态sk 1已知的情况下 确定前面的决策uk 使从初始状态s1到第k阶段末状态sk 1的策略最优 此时的状态转移方程应为 从sk 1出发通达uk解出sk 即从sk 1 tk sk uk 中反解出sk sk trk sk 1 uk fk sk 1 表示第k阶末状态为sk的情况下到第1阶初始状态为s1作最优策略对应的指标值 顺序解法基本方程为 fk sk 1 opt vk sk 1 uk fk 1 sk uk drk sk 1 k 1 n 递推方程f0 s1 0边界条件 4 3动态规划的顺序解法 三 fk sk 表示第k阶末状态为sk的情况下到第1阶初始状态为s1作最优策略对应的指标值 则顺序解法基本方程为 fk sk opt vk sk uk fk 1 sk 1 uk drk sk k 1 n 递推方程f0 s0 0边界条件 如果sk表示第k阶段末状态 s0表示第1阶段初始状态 注 贝尔曼 ballman 最优化原理作为整个过程的最优策略具有这样的性质 即无论过去的状态和决策如何 对前面的决策所形成的状态而言 余下的诸决策必须构成最优策略 这就是说 不管引导到这个现时状态的头一个状态和决策是什么 所有的未来决策应是最优的 例 机器负荷问题某种机器可以在高低两种不同的负荷下进行生产 在高负荷下进行生产时 产品的年产量g和投入生产的机器数量u的关系为g 8u 这时机器的年完好率为a 0 7 在低负荷下生产时 产品的年产量h和投入生产的机器数量v的关系为h 5v 这时机器的年完好率为b 0 9 假定开始生产时完好的机器数量为s1 要求制定一个五年计划 在每年开始时决定机器在两种不同负荷下生产的数量 使五年内产品的总产量最高 1 按年数划分为5个阶段 k 1 2 3 4 5 2 取第k年初完好的机器数sk为状态变量 s1 1000 3 取第k年投入高负荷的机器数xk为决策变量 0 xk sk 4 状态转移方程为sk 1 0 7xk 0 9 sk xk 0 9sk 0 2xk 5 指标函数为vk 5 8xj 5 sj xj 5sj 3xj 6 基本方程为fk sk max 5sj 3xj fk 1 sk 1 k 5 4 3 2 10 xk skf6 s6 0 解 当k 5时 f5 s5 max 5s5 3x5 f6 s6 max 5s5 3x5 8s5 x5 s5 0 x5 s50 x5 s5 当k 4时 f4 s4 max 5s4 3x4 8s5 max 5s4 3x4 8 0 9s4 0 2x4 0 x4 s40 x4 s4 max 12 2s4 1 4x4 13 6s4 x4 s4 0 x4 s4 当k 3时 f3 s3 max 5s3 3x3 13 6s4 max 5s3 3x3 13 6 0 9s3 0 2x3 0 x3 s30 x3 s3 max 17 24s3 0 28x3 17 5s3 x3 s3 0 x3 s3 当k 2时 f2 s2 max 5s2 3x2 17 52s3 max 5s2 3x2 17 52 0 9s2 0 2x2 0 x2 s20 x2 s2 max 20 77s2 0 504x2 20 7s4 x2 0 0 x2 s2 当k 1时 f1 s1 23 7s1 x1 0 f1 1000 23700 s1 1000 x1 0 s2 900 x2 0 s3 810 x3 810 s4 576 x4 576 s5 397 x5 397 某些静态规划问题可用动态规划法来求解 例用动态规划法求解maxz x1 x22 x3x1 x2 x3 cxi 0i 1 2 3 4 4动态规划的应用 一 1求解静态规划问题 4 5动态规划模型举例 4 5 1产品生产计划安排问题例1某工厂生产某种产品的月生产能力为10件 已知今后四个月的产品成本及销售量如表所示 如果本月产量超过销售量时 可以存储起来备以后各月销售 一件产品的月存储费为2元 试安排月生产计划并做到 1 保证满足每月的销售量 并规定计划期初和期末库存为零 2 在生产能力允许范围内 安排每月生产量计划使产品总成本 即生产费用加存储费 最低 例1产品生产计划安排 设xk为第k阶段生产量 则有直接成本dk sk xk ckxk 2sk状态转移公式为sk 1 sk xk yk总成本递推公式 第四阶段 即第4月份 由边界条件和状态转移方程s5 s4 x4 y4 s4 x4 6 0得s4 x4 6或x4 6 s4估计第四阶段 即第4月份初库存的可能状态 s4 0 5 第四阶段最优决策表 第三阶段 最大可能库存量7件由状态转移方程 s4 s3 x3 12 0及x3 10 可知s3 2 7 minx3 5由阶段效果递推公式有 f3 2 d3 2 10 f4 0 2 2 80 10 456 1260得第三阶段最优决策表 如下 第三阶段最优决策表 第二阶段 最大可能库存量4件由状态转移方程 s3 s2 x2 7 2及x2 10 可知s2 0 4 minx2 5由阶段效果递推公式有 f2 1 d3 1 10 f3 4 2 1 72 10 1104 1826 得第二阶段最优决策表 如下 第三阶段最优决策表 第四阶段 初始库存量s4 0由状态转移方程 s3 s4 x4 6 0可知x4 6 由阶段效果递推公式有 f4 0 6 d4 0 6 f3 0 10 70 6 1902 2322得第四阶段最优决策表 如下 回溯得此表 例2生产 库存管理问题 连续变量 设某厂计划全年生产某种产品a 其四个季度的订货量分别为600公斤 700公斤 500公斤和1200公斤 已知生产产品a的生产费用与产品的平方成正比 系数为0 005 厂内有仓库可存放产品 存储费为每公斤每季度1元 求最佳的生产安排使年总成本最小 解 四个季度为四个阶段 采用阶段编号与季度顺序一致 设sk为第k季初的库存量 则边界条件为s1 s5 0设xk为第k季的生产量 设yk为第k季的订货量 sk xk yk都取实数 状态转移方程为sk 1 sk xk yk仍采用反向递推 但注意阶段编号是正向的目标函数为 例2生产 库存管理问题 连续变量 第一步 第四季度 总效果f4 s4 x4 0 005x42 s4由边界条件有 s5 s4 x4 y4 0 解得 x4 1200 s4将x4 代入f4 s4 x4 得 f4 s4 0 005 1200 s4 2 s4 7200 11s4 0 005s42第二步 第三 四季度 总效果f3 s3 x3 0 005x32 s3 f4 s4 将s4 s3 x3 500代入f3 s3 x3 得 例2生产 库存管理问题 连续变量 第三步 第二 三 四季度 总效果f2 s2 x2 0 005x22 s2 f3 s3 将s3 s2 x2 700代入f2 s2 x2 得 注意 最优阶段总效果仅是当前状态的函数 与其后的决策无关 例2生产 库存管理问题 连续变量 第四步 第一 二 三 四季度 总效果f1 s1 x1 0 005x12 s1 f2 s2 将s2 s1 x1 600 x1 600代入f1 s1 x1 得 由此回溯 得最优生产 库存方案x1 600 s2 0 x2 700 s3 0 x3 800 s4 300 x4 900 4 5 2资源分配问题 例3某公司有9个推销员在全国三个不同市场推销货物 这三个市场里推销人员数与收益的关系如下表 试作出使总收益最大的分配方案 解 设分配人员的顺序为市场1 2 3 采用顺向阶段编号 设sk为第k阶段尚未分配的人员数 边界条件为s1 9设xk为第k阶段分配的推销人员数 采用反向递推 状态转移方程为sk 1 sk xk靜态规划为 例3第三阶段 给第三市场分配 s3有0 9种可能 第三阶段最优决策表如下 允许推销人员没用完时 允许推销人员没用完时 例3第二阶段 给第二市场分配 s2有0 9种可能 第二阶段最优决策表如下 第一阶段 给第一市场分配 由边界条件s1 9 第一阶段最优决策表如下 得决策过程 x1 2 x2 0 x3 7 f1 218即市场1分配2人 市场2不分配 市场3分配7人最优解与分配的顺序有关吗 4 5 2资源分配问题 例4项目选择问题某工厂预计明年有a b c d四个新建项目 每个项目的投资额wk及其投资后的收益vk如下表所示 投资总额为30万元 问如何选择项目才能使总收益最大 上述问题的静态规划模型如下 这是一类0 1规划问题该问题是经典的旅行背包问题 knapsack 该问题是np complete 例4项目选择问题 解 设项目选择的顺序为a b c d 1 阶段k 1 2 3 4分别对应d c b a项目的选择过程2 第k阶段的状态sk 代表第k阶段初尚未分配的投资额3 第k阶段的决策变量xk 代表第k阶段分配的投资额4 状态转移方程为sk 1 sk wkxk5 直接效益dk sk xk vk或06 总效益递推公式 该问题的难点在于各阶段的状态的确定 当阶段增加时 状态数成指数增长 下面利用决策树来确定各阶段的可能状态 例4第一阶段 项目d 的选择过程 s1 8时 x1只能取0 w1 8 v1 5 例4第二阶段 项目c 的选择过程 例4第三阶段 项目b 的选择过程 第四阶段 项目a 的选择过程 4 5 3串联系统可靠性问题 例5有a b c三部机器串联生产某种产品 由于工艺技术问题 产品常出现次品 统计结果表明 机器a b c产生次品的概率分别为pa 30 pb 40 pc 20 而产品必须经过三部机器顺序加工才能完成 为了降低产品的次品率 决定拨款5万元进行技术改造 以便最大限度地提高产品的成品率指标 现提出如下四种改进方案 方案1 不拨款 机器保持原状 方案2 加装监视设备 每部机器需款1万元 方案3 加装设备 每部机器需款2万元 方案4 同时加装监视及控制设备 每部机器需款3万元 采用各方案后 各部机器的次品率如下表 例5串联机器可靠性问题 解 为三台机器分配改造拨款 设拨款顺序为a b c 阶段序号反向编号为k 即第一阶段计算给机器c拨款的效果 设sk为第k阶段剩余款 则边界条件为s3 5 设xk为第k阶段的拨款额 状态转移方程为sk 1 sk xk 目标函数为maxr 1 pa 1 pb 1 pc 仍采用反向递推第一阶段 对机器c拨款的效果r1 s1 x1 d1 s1 x1 r0 s0 x0 d1 s1 x1 第二阶段最优决策表 第二阶段 对机器b c拨款的效果由于机器a最多只需3万元 故s2 2递推公式 r2 s2 x2 d2 s2 x2 r1 s1 x1 例 r2 3 2 d2 3 2 r1 1 1 1 0 2 0 9 0 72得第二阶段最优决策表 第二阶段最优决策表 第三阶段 对机器a b c拨款的效果边界条件 s3 5递推公式 r3 s3 x3 d3 s3 x3 r2 s2 x2 例 r3 5 3 d3 5 3 r2 2 2 1 0 05 0 64 0 608得第三阶段最优决策表 第二阶段最优决策表 回溯 有多组最优解 i x3 1 x2 3 x1 1 r3 0 8 0 9 0 9 0 648ii x3 2 x2 2 x1 1 r3 0 9 0 8 0 9 0 648iii x3 2 x2 3 x1 0 r3 0 9 0 9 0 8 0 648 资源分配问题可描述如下 设有某种原料 总数量为a 分配给n个使用者 已知第i个使用者得到数量xi的资源 可创造的收益为gi xi 问应如何分配该资源 才能使总收益最大 4 4动态规划的应用 二 用动态规划法处理这种问题时 通常把给一个使用者分配资源的过程看成一个阶段 按n个使用者分成先后n个决策阶段 即先给第1个使用者分配资源 为第一阶段 再给第2个使用者分配 为第2阶段 依此类推 最后给第n个使用者分配 为第n阶段 2资源分配问题 例某工业部门根据国家计划安排 拟将五台某种高效率的机器分配给所属的甲 乙 丙三个工厂 各工厂得到不同数量的机器可获得的收益如下表 问应如何分配机器 才能使各厂的总效益最大 某单位准备在以后的n个时期内采购一批物资 各时期的价格不是确定的 而是按照某种已知的概率分布取值 试制定采购策略 确定在哪一时期以什么价格采购 能使采购价的数学期望值最低 这类问题也适合用动态规划法进行处理 下面通过实例加以说明 例7某厂生产上需要在近五周内采购一批原料 而估计在未来五周的价格有波动 其浮动价格和概率策得如下表 试确定该厂应在哪一周