15. 082 和6. 855j 最短路径2： 批量r-堆(lot-sizing r-heaps)应用.pdf

15. 082 和 6. 855J 最短路径2： 批量R-堆(lot-sizing R-Heaps)应用 1 应用19. 19 动态批量(Dynamic Lot Sizing)(1) K 个时期，需求一个产品. 在时期j 的需求是d . 假设 j 对于j= 1. . k ，d 0 j 在时期j 生产p 个单位产品需要的代价是：a + b p j j j j h :从时期j携带库存产品的单位代价h j: j 问题：满足需求的最小代价方式是什么？ 2 应用19. 19 动态批量(1) 在弧(0,j)上的流：在时期j 生产的产品总量 在弧(j,j+1)上的流：从时期j带来的库存产品总数 引理：在时期j有生产，或者从时期j-1带来库存，两者 不能同时存在. 3 引理：在时期j有生产，或者从时期j-1 带来库存，两者 不能同时存在. 假设现在从时期j-1得到库存，且时期j有生产. 令时期i 是最后一个先于时期j 的有生产的时期，例如，j=7和 i=4. 断言：存在存放在时期i,i+1,…,j-1的库存 4 那么存在一个带有正流的圈C . C = 0-4-5-6-7-0. 令x07是在(0,7)上的流. 环绕C 发送Δ单位的流的代价是线性的(忽略固定的生产费用 ). 令Q = b4+ h4+ h5+ h6–b7. •如果Q 0，那么解可以通过发送一个单位的环绕C 的流得到 改善 •如果Q 0，那么解可以通过少量减少在C中的流改善. •如果Q=0，那么解可以通过增加环绕C 的流x07个单位得到改 善. •这种矛盾构成了引理. 5 推论：在时期i的生产对某j来说恰好满足在时期i,i+1,…,j- 1 中的需求. 考虑两个相继的生产时期i和j. 那么在时期i的生产必须满 足在时期i+1到j-1 阶段的需求. 令c 是流的(总) 的代价： ij 6 令Cij 是为满足在时期i,i+1,…,j-1需求(包括库存的代价) 在而时期i 的生产代价. 创建一个从结点1到K+1的图 ，(i,j)的代价就是cij 每一条从1到K+1 的路径给出一个生产和库存调度. 路径的代价就是调度的代价. 解释：在时期1，6，8，11生产 结论：从结点1到结点K+1 的最小代价路径给出最小代价批量解. 7 桶实现回顾 潜在的瓶颈：