《一维装箱问题典型算法ppt课件》由会员分享，可在线阅读，更多相关《一维装箱问题典型算法ppt课件（33页珍藏版）》请在金锄头文库上搜索。
1、 第三章装箱问题 信息处理中的组合优化 CombinatorialOptimizationinInformationProcessing 第三章装箱问题 1装箱问题的描述 2装箱问题的最优解值下界 3装箱问题的近似算法 第三章装箱问题 装箱问题 BinPacking 是一个经典的组合优化问题 有着广泛的应用 在日常生活中也屡见不鲜 1装箱问题的描述 设有许多具有同样结构和负荷的箱子B1 B2 其数量足够供所达到目的之用 每个箱子的负荷 可为长度 重量etc 为C 今有n个负荷为wj 0 wj Cj 1 2 n的物品J1 J2 Jn需要装入箱内 装箱问题 是指寻找一种方法 使得能以最小数量的箱子
2、数将J1 J2 Jn全部装入箱内 1装箱问题的描述 由于wi C 所以BP的最优解的箱子数不超过n 设 则装箱问题的整数线性规划模型为 约束条件 1 表示 一旦箱子Bi被使用 放入Bi的物品总负荷不超过C 约束条件 2 表示 每个物品恰好放入一个箱子中 第三章装箱问题 上述装箱问题是这类问题最早被研究的 也是提法上最简单的问题 称为一维装箱问题 但 装箱问题的其他一些提法 1 在装箱时 不仅考虑长度 同时考虑重量或面积 体积etc 即二维 三维 装箱问题 2 对每个箱子的负荷限制不是常数C 而是 最优目标可如何提 3 物品J1 J2 Jn的负荷事先并不知道 来货是随到随装 即在线 On Lin
3、e 装箱问题 4 由于场地的限制 在同一时间只能允许一定数量的箱子停留现场可供使用 etc 1装箱问题的描述 BP的应用举例 1 下料问题轧钢厂生产的线材一般为同一长度 而用户所需的线材则可能具有各种不同的尺寸 如何根据用户提出的要求 用最少的线材截出所需的定货 2 二维BP玻璃厂生产出长宽一定的大的平板玻璃 但用户所需玻璃的长宽可能有许多差异 如何根据用户提出的要求 用最少的平板玻璃截出所需的定货 3 计算机的存贮问题如要把大小不同的共10MB的文件拷贝到磁盘中去 而每张磁盘的容量为1 44MB 已知每个文件的字节数不超过1 44MB 而且一个文件不能分成几部分存贮 如何用最少的磁盘张数完成
4、 4 生产流水线的平衡问题给定流水节拍C 如何设置最少的工作站 按一定的紧前约束 沿着流水线将任务分配到各工作站上 称为带附加优先约束的BP BP是容量限制的工厂选址问题的特例之一 Goback 第三章装箱问题 2装箱问题的最优解值下界 由于BP是NP C问题 所以求解考虑一是尽可能改进简单的穷举搜索法 减少搜索工作量 如 分支定界法 二是启发式 近似 算法 显然是它的一个最优解 2装箱问题的最优解值下界 Theorem3 1 BP最优值的一个下界为 表示不小于a的最小整数 Theorem3 2 设a是任意满足的整数 对BP的任一实例I 记 则 是最优解的一个下界 第三章装箱问题 a C C
5、2 C a I1 I2 I3 Proof 仅考虑对I1 I2 I3中物品的装箱 中物品的长度大于C 2 每个物品需单独放入一个箱子 这就需要个箱子 又中每个物品长度至少为a 但可能与I2中的物品共用箱子 它不能与I1中的物品共用箱子 与I2中的物品如何 由于放I2中物品的个箱子的剩余总长度为 在最好的情形下 被I3中的物品全部充满 故剩下总长度将另外至少个附加的箱子 Note 可能小于零 是最优解的一个下界 2装箱问题的最优解值下界 问 未必 如 Corollary3 1 记 则L2是装箱问题的最优解的一个下界 且 Proof L2为最优解的下界是显然的 若证明 则可得 当a 0时 是所有物品
6、 Goback 第三章装箱问题 3装箱问题的近似算法 一 NF NextFit 算法 设物品J1 J2 Jn的长度分别为w1 w2 wn箱子B1 B2 的长均为C 按物品给定的顺序装箱 先将J1放入B1 如果则将J2放入B1 如果而 则B1已放入J1 J2 Jj 将其关闭 将Jj 1放入B2 同法进行 直到所有物品装完为止 特点 1 按物品给定的顺序装箱 2 关闭原则 对当前要装的物品Ji只关心具有最大下标的已使用过的箱子Bj能否装得下 能 则Ji放入Bj 否 关闭Bj Ji放入新箱子Bj 1 计算复杂性为O n 3装箱问题的近似算法 Example1 I C 10 J1 J5 J6 J4 J
7、3 J2 B1 B2 B3 B4 B5 J1 J2 J3 J4 J5 J6 Solution 首先 将J1放入B1 由于J2在B1中放不下 所以关闭B1 将J2放入B2 J3在B2中放不下 不考虑B1是否能装 所以关闭B2将J3放入B3 解为 其余为零 第三章装箱问题 Theorem3 3 Proof 先证再说明不可改进 设I为任一实例 要证 显然 由得 反证 如果 则对任意i 1 2 k 由于起用第2i个箱子是因为第2i 1个箱子放不下第2i个箱子中第一个物品 因此这两个箱子中物品的总长度大于C 所以前2k个箱子中物品的总长度大于Ck 这与矛盾 考虑实例I C 1 3装箱问题的近似算法 二
8、FF FirstFit 算法 设物品J1 J2 Jn的长度分别为w1 w2 wn箱子B1 B2 的长均为C 按物品给定的顺序装箱 I C 10 用NF算法装箱 当放入J3时 仅看B2 是否能放入 因B1已关闭 参见EX 1 但事实上 B1此时是能放得下J3的 如何修正NF算法 先将J1放入B1 若 则J2放入B1 否 则 J2放入B2 若J2已放入B2 对于J3则依次检查 B1 B2 若B1能放得下 则J3放入B1 否则查看B2 若B2能放得下 则J3放入B2 否则启用B3 J3放入B3 第三章装箱问题 一般地 J1 Jj已放入B1 Bi箱子 对于Jj 1 则依次检查B1 B2 Bi 将Jj
9、1放入首先找到的能放得下的箱子 如果都放不下 则启用箱子Bi 1 将Jj 1放入Bi 1 如此继续 直到所有物品装完为止 计算复杂性为O nlogn 特点 1 按物品给定的顺序装箱 2 对于每个物品Jj总是放在能容纳它的具有最小标号的箱子 但精度比NF算法更高 3装箱问题的近似算法 Theorem3 4 Theorem3 5 对任意实例I 而且存在任意大的实例I 使 因而 第三章装箱问题 Example2 I C 10 J1 J5 J6 J4 J3 J2 B1 B2 B3 B4 B5 J1 J2 J3 J4 J5 J6 Solution 首先 将J1放入B1 由于J2在B1中放不下 所以将J2
10、放入B2 对于J3 先检查B1是否能容纳下 能 所以将J3放入B1 解为 其余为零 3装箱问题的近似算法 Example3 I C 10 J1 J4 J3 J2 Solution 用NF算法 B1 B2 B3 B4 B5 J1 J2 J6 J5 J3 J4 B1 B2 B3 B4 B5 J1 J2 J6 J5 J3 J4 J6 J5 用FF算法 参见EX 3用FF算法装箱 当放入J4时 B1能容纳J4就放入B1 而事实上 放入B2更好 第三章装箱问题 三 BF BestFit 算法 与FF算法相似 按物品给定的顺序装箱 区别在于对于每个物品Jj是放在一个使得Jj放入之后 Bi所剩余长度为最小者
11、 即在处理Jj时 若B1 B2 Bi非空 而Bi 1尚未启用 设B1 B2 Bi所余的长度为 若 则将Jj放入Bi 1内 否则 从的Bk中 选取一个Bl 使得为最小者 BF算法的绝对性能比 计算复杂性与FF算法相同 Example4 I C 10 3装箱问题的近似算法 J1 J4 J3 J2 J6 J5 B1 B2 B3 B4 B5 J1 J2 J6 J5 J3 J4 Solution 用BF算法 解为 其余为零 而此为最优解 第三章装箱问题 四 FFD FirstFitDecreasing 算法 FFD算法是先将物品按长度从大到小排序 然后用FF算法对物品装箱 该算法的计算复杂性为O nlo
12、gn Example5 I C 10 J1 J5 J6 J4 J3 J2 Solution 已知 B1 B2 B3 B4 B5 J1 J2 J3 J4 J5 J6 是最优的 NFD算法 BFD算法 3装箱问题的近似算法 Theorem3 6 Proof 显然对任意实例I 有 记 首先证明两个结论 1 FFD算法所用的第个箱子中每个的长度不超过 记wi是放入第个箱子中的第一个物品 只需证 用反证法 若不然 则有 因此FFD 算法中前个箱子中 每个箱子至多有两个物品 第三章装箱问题 可证明存在使前k个恰各含一个物品 后个箱子各含两个物品 因为若不然 则存在两个箱子使Bp有两个物品 Bq有一个物品因
13、物品已从大到小排列 故 因此从而可以将wi放入Bq中 矛盾 3装箱问题的近似算法 因为FFD未将wk 1 wi放入前k个箱子 说明其中任一个箱子已放不下 故在最优解中也至少有k个箱子不含wk 1 wi中任一个物品 假设就是前k个箱子 因此在最优解中 wk 1 wi 1也会两两放入第 个箱子中 且因为这些物品长度大于 所以 每个箱子中只有两个物品 且已放不下 但最优解中wi必须放入前个箱子中 矛盾 故 2 FFD算法放入第个箱子中物品数不超过 而如果至少有个物品放入第 个箱子中 记前个物品的长度为 第三章装箱问题 记FFD算法中前个箱子中每个箱子物品总长为 显然 对任意 否则长为的物品可放入第j
14、个箱子中 因此 矛盾 所以 2 结论成立 由 1 2 知FFD算法比最优算法多用的箱子是用来放至多个物品 而每个物品长不超过 因此 3装箱问题的近似算法 因此 因为如果 则 故不妨设 考虑实例I 物品集长度为 C为箱长 说明是不可改进的 第三章装箱问题 比较NF算法 FF BF 算法 FFD算法 它们的近似程度一个比一个好 但这并不是说NF FF BF 就失去了使用价值 1 FF BF FFD算法都要将所有物品全部装好后 所有箱子才能一起运走 而NF算法无此限制 很适合装箱场地小的情形 2 FFD算法要求所有物品全部到达后才开始装箱 而NF FF BF 算法在给某一物品装箱时 可以不知道下一个
15、物品的长度如何 适合在线装箱 存储罐注液问题 第三章装箱问题 某化工厂有9个不同大小的存储罐 有一些已经装某液体 现新到一批液体化工原料需要存储 这些液体不能混合存储 它们分别是1200m3苯 700m3丁醇 1000m3丙醇 450m3苯乙醇和1200m3四氢呋喃 下表列出每个存储罐的属性 单位 m3 问应如何将新到的液体原料装罐 才能使保留未用的存储罐个数最多 第三章装箱问题 Solution 分别记苯 丁醇 丙醇 苯乙醇 四氢呋喃为第1 2 3 4 5种液体 显然 新到液体应尽可能装入已存有此种液体的罐中 所以余下液体为 900m3苯 700m3丁醇 1000m3丙醇 450m3乙醇和7
16、00m3四氢呋喃 剩余空罐为1 3 4 5 6 8 9 由于不允许混合 每种液体至少需要1个空罐 令 记第j个空罐的容量为cj j 1 3 4 5 6 8 9 第i种剩余液体的体积为li i 1 2 3 4 5 第三章装箱问题 整数规划模型 表示第j个空罐被使用 每个罐子至多装一种液体 每种液体的体积不能超过装这些液体的罐子的总容量 将li cj代入 可用Lindo Lingo等软件求解 第三章装箱问题 123456789 当问题的数据很大时 IP的计算复杂性很高 可考虑采用近似算法或启发式算法求解 900 700 1000 450 700 500 400 400 600 600 900 800 800 800 苯 苯 丁醇 丙醇 乙醇 四氢呋喃 四氢呋喃 如利用FFD算法思想 对每一种液体 将空罐按容积排成非增序 若需k个罐子 则装入具有连贯序号的罐子 使这k个空罐中最大容积空罐序号最大 689451372 500 400 400 600 600 900 800 800 800 苯 四氢呋喃 苯 丁醇 丙醇 丙醇 乙醇 四氢呋喃 第三章装箱问题 如果算法再细一点 只需要一个空罐的液体
