2015年暑假数学建模培训讲义装箱问题

1、装箱问题装箱问题 装箱问题（装箱问题（Bin Packing）是一个经典的组合优化）是一个经典的组合优化 问题，有着广泛的应用，在日常生活中也屡见不鲜问题，有着广泛的应用，在日常生活中也屡见不鲜 . 设有许多具有同样结构和负荷的箱子设有许多具有同样结构和负荷的箱子 B1，B2， 其数量足够供所达到目的之用其数量足够供所达到目的之用 . 每个箱子的负荷（可为每个箱子的负荷（可为 长度、重量长度、重量 etc.）为为 C ,今有今有 n 个负荷为个负荷为 wj，0 wj C j = 1，2，n 的物品的物品 J1，J2，Jn 需要装入箱内需要装入箱内. 是指寻找一种方法，使得能以最小数量的箱子数将

2、是指寻找一种方法，使得能以最小数量的箱子数将 J1，J2，Jn 全部装入箱内全部装入箱内 1 装箱问题的描述 由于由于 wi C，所以，所以 BP 的最优解的箱子数不超过的最优解的箱子数不超过 n 设设 箱子箱子 Bi 被使用被使用 否则否则 物品物品 Jj 放入箱子放入箱子 Bi 中中 否则否则 则装箱问题的整数线性规划模型为则装箱问题的整数线性规划模型为： 约束条件（约束条件（1）表示：一旦箱子）表示：一旦箱子 Bi 被使用，放入被使用，放入 Bi 的物品总负荷不超过的物品总负荷不超过 C ； 约束条件（约束条件（2）表示：每个物品恰好放入一个箱子中）表示：每个物品恰好放入一个箱子中 .

3、上述装箱问题是这类问题最早被研究的，也是提上述装箱问题是这类问题最早被研究的，也是提 法上最简单的问题，称为一维装箱问题法上最简单的问题，称为一维装箱问题 但但 装箱问题的其他一些提法装箱问题的其他一些提法： 1、在装箱时，不仅考虑长度，同时考虑重量或面积、在装箱时，不仅考虑长度，同时考虑重量或面积、 体积体积 etc . 即二维、三维、即二维、三维、装箱问题装箱问题； 2、对每个箱子的负荷限制不是常数、对每个箱子的负荷限制不是常数 C ; 而是而是 最优目标可如何提？最优目标可如何提？ 3、物品、物品J1，J2，Jn 的负荷事先并不知道，来货是的负荷事先并不知道，来货是 随到随装；即随到随装

4、；即 在线（在线（On-Line）装箱问题；）装箱问题； 4、由于场地的限制，在同一时间只能允许一定数量的、由于场地的限制，在同一时间只能允许一定数量的 箱子停留现场可供使用箱子停留现场可供使用, etc . 1 装箱问题的描述 BP 的应用举例的应用举例： 1、下料问题下料问题 轧钢厂生产的线材一般为同一长度轧钢厂生产的线材一般为同一长度, 而用而用 户所需的线材则可能具有各种不同的尺寸户所需的线材则可能具有各种不同的尺寸, 如何根据用如何根据用 户提出的要求，用最少的线材截出所需的定货；户提出的要求，用最少的线材截出所需的定货； 2、 二维二维 BP 玻璃厂生产出长宽一定的大的平板玻璃玻璃

5、厂生产出长宽一定的大的平板玻璃, 但用户所需玻璃的长宽可能有许多差异，如何根据用但用户所需玻璃的长宽可能有许多差异，如何根据用 户提出的要求，用最少的平板玻璃截出所需的定货户提出的要求，用最少的平板玻璃截出所需的定货; 3、计算机的存贮问题计算机的存贮问题 如要把大小不同的共如要把大小不同的共 10 MB 的的 文件拷贝到磁盘中去，而每张磁盘的容量为文件拷贝到磁盘中去，而每张磁盘的容量为 1. 44 MB , 已知每个文件的字节数不超过已知每个文件的字节数不超过 1.44 MB , 而且一个文件而且一个文件 不能分成几部分存贮，如何用最少的磁盘张数完成不能分成几部分存贮，如何用最少的磁盘张数完

6、成 . 4、生产流水线的平衡问题生产流水线的平衡问题 给定流水节拍给定流水节拍 C , 如何设置如何设置 最少的工作站，（按一定的紧前约束）沿着流水线将任最少的工作站，（按一定的紧前约束）沿着流水线将任 务分配到各工作站上务分配到各工作站上 . 称为带附加优先约束的称为带附加优先约束的 BP . BP 是容量限制的工厂选址问题的特例之一是容量限制的工厂选址问题的特例之一. Go back 由于由于 BP 是是 NP-C 问题，所以求解考虑问题，所以求解考虑 一是尽可能一是尽可能 改进简单的穷举搜索法，减少搜索工作量改进简单的穷举搜索法，减少搜索工作量 . 如如: : 分支分支 定界法；二是启发

7、式（近似）算法定界法；二是启发式（近似）算法 . 显然显然 是它的一个最优解是它的一个最优解 . 2 装箱问题的最优解值下界 Theorem 3.1BP 最优值的一个下界为最优值的一个下界为 表示不小于表示不小于 a 的最小整数的最小整数. Theorem 3.2 设设 a 是任意满足是任意满足 的整数的整数,对对 BP 的任一实例的任一实例 I , 记记 则则 是最优解的一个下界是最优解的一个下界 a C C/2 C-a I1I2I3 Proof : 仅考虑对仅考虑对 I1,I2,I3中物品的装箱中物品的装箱 . 中物品的长度大于中物品的长度大于C/2 , 每个物品需单独放入一个箱子，每个物

8、品需单独放入一个箱子， 这就需要这就需要 个箱子个箱子 . 又又 中每个物品长度至少为中每个物品长度至少为 a , 但可能与但可能与 I2 中的中的 物品共用箱子物品共用箱子， 它不能与它不能与 I1 中的物品共用箱子中的物品共用箱子, 与与 I2 中的物品如何？中的物品如何？ 由于放由于放 I2 中物品的中物品的 个箱子的剩余个箱子的剩余 总长度为总长度为 在最好的情形下，在最好的情形下， 被被 I3 中的物品全部充满，故剩中的物品全部充满，故剩 下总长度下总长度 将另外至少将另外至少 个附加的箱子个附加的箱子 . Note: 可能小于零可能小于零 是最优解的一个下界是最优解的一个下界 .

9、2 装箱问题的最优解值下界 问问 ？ 未必！未必！ 如如 Corollary 3.1记记 则则 L2 是装箱问题的最优解的一个下界，且是装箱问题的最优解的一个下界，且 . Proof :L2 为最优解的下界是显然的为最优解的下界是显然的 . 若证明若证明 ，则可得，则可得 当当 a = 0 时，时， 是所有物品是所有物品 . Go back 一、一、NF ( Next Fit ) 算法算法 设物品设物品 J1，J2,，Jn 的长度分别为的长度分别为 w1，w2,，wn 箱子箱子 B1，B2，的长均为的长均为 C ，按物品给定的顺序装箱，按物品给定的顺序装箱 . 先将先将 J1 放入放入 B1,

10、 如果如果 则将则将 J2 放入放入 B1 如果如果 而而 则则 B1 已放入已放入 J1，J2,，Jj，将其，将其关闭关闭，将，将 Jj+1 放入放入 B2 . 同法进行，直到所有物品装完为止同法进行，直到所有物品装完为止 . 特点特点： 1、按物品给定的顺序装箱、按物品给定的顺序装箱； 2、关闭原则关闭原则 . 对当前要装的物品对当前要装的物品 Ji 只关心具有最大下标的已使只关心具有最大下标的已使 用过的箱子用过的箱子 Bj 能否装得下？能否装得下？ 能能. 则则 Ji 放入放入 Bj ；否；否 . 关闭关闭 Bj ，Ji 放入新箱子放入新箱子 Bj+1 . 计算复杂性为计算复杂性为 O

11、(n). 3 装箱问题的近似算法 Example 1 物品物品J1J2J3J4J5J6 wj 674283 I : C = 10 J1J5 J6 J4 J3 J2 B1B2B3B4B5 J1J2 J3 J4 J5 J6 Solution : 首先，将首先，将 J1 放入放入 B1 由于由于 J2 在在 B1 中放不下中放不下, 所所 以关闭以关闭 B1 , 将将 J2 放入放入 B2 , J3 在在 B2 中放不下中放不下(不考虑不考虑 B1 是否能装是否能装), 所以关闭所以关闭 B2 将将 J3 放入放入 B3， 解为解为: 其余为零，其余为零， Theorem 3.3 Proof : 先

12、证先证 再说明不可改进再说明不可改进 设设 I 为任一实例，为任一实例，(要证要证 ) 显然，由显然，由 得得 反证反证如果如果 ,则则 对任意对任意 i = 1, 2, k 由于起用第由于起用第 2i 个箱子是因为第个箱子是因为第 2i -1 个箱子放不下第个箱子放不下第2i 个箱子中第一个物品个箱子中第一个物品,因此这两个箱子中物品的总长度因此这两个箱子中物品的总长度 大于大于 C ，所以前，所以前 2k 个箱子中物品的总长度大于个箱子中物品的总长度大于 Ck . 这与这与 矛盾矛盾 . 考虑实例考虑实例 I : C = 1, 3 装箱问题的近似算法 二、二、FF ( First Fit

13、) 算法算法 设物品设物品 J1，J2,，Jn 的长度分别为的长度分别为 w1，w2,，wn 箱子箱子 B1，B2，的长均为的长均为 C ，按物品给定的顺序装箱，按物品给定的顺序装箱 . 物品物品J1J2J3J4J5J6 wj 674283 I : C = 10 用用 NF 算法装算法装 箱箱, 当放入当放入 J3 时时, 仅看仅看 B2是否能放入，因是否能放入，因 B1 已关闭已关闭, 参见参见 EX .1 但事实上，但事实上，B1 此时是能放得下此时是能放得下 J3 的的 . 如何修正如何修正 NF 算算 法法 先将先将 J1 放入放入 B1，若，若 ,则则 J2 放入放入 B1 , 否否

14、 则，则，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+1 放入首先找到的能放入首先找到的能 放得下的箱子，如果都放不下，则启用箱子放得下的箱子，如果都放不下，则启用箱子 Bi+

15、1 ，将，将 Jj+1 放入放入 Bi+1 ，如此继续，直到所有物品装完为止，如此继续，直到所有物品装完为止 . 计算复杂性为计算复杂性为 O(nlogn). 特点特点：1、按物品给定的顺序装箱、按物品给定的顺序装箱； 2、对于每个物品对于每个物品 Jj 总是放在能容纳它的具总是放在能容纳它的具 有最小标号的箱子有最小标号的箱子 . 但精度比但精度比NF 算法更高算法更高 3 装箱问题的近似算法 Theorem 3.4 Theorem 3.5 对任意实例对任意实例 I ， 而且存在而且存在 任意大的实例任意大的实例 I ，使，使 因而因而 Example 2 物品物品J1J2J3J4J5J6

16、wj 674283 I : C = 10 J1J5 J6 J4 J3 J2 B1B2B3B4B5 J1J2 J3 J4 J5 J6 Solution : 首先，将首先，将 J1 放入放入 B1 由于由于 J2 在在 B1 中放不下中放不下, 所所 以将以将 J2 放入放入 B2 , 对于对于 J3 , 先检查先检查 B1 是否能是否能 容纳下容纳下, 能能 . 所以将所以将 J3 放放 入入 B1， 解为解为: 其余为零，其余为零， 3 装箱问题的近似算法 Example 3 物品物品J1J2J3J4J5J6 wj 678324 I : C = 10 J1 J4 J3J2 Solution :

17、 用用 NF 算法算法 B1B2B3B4B5 J1J2 J6 J5 J3 J4 B1B2B3B4B5 J1J2 J6 J5 J3 J4 J6 J5 用用 FF 算法算法 参见参见 EX .3 用用 FF 算法装箱算法装箱, 当放入当放入 J4 时时, B1 能容纳能容纳 J4 就放入就放入 B1 ，而事实上，放入，而事实上，放入 B2 更好更好 . 三、三、BF ( Best Fit ) 算法算法 与与 FF 算法相似，按物品给定的顺序装箱，区别在算法相似，按物品给定的顺序装箱，区别在 于对于每个物品于对于每个物品 Jj 是放在一个使得是放在一个使得 Jj 放入之后，放入之后，Bi 所所 剩余

18、长度为最小者剩余长度为最小者 . 即在处理即在处理 Jj 时，若时，若 B1，B2,，Bi 非空，而非空，而 Bi+1 尚尚 未启用，设未启用，设 B1，B2,，Bi所余的长度为所余的长度为 若若 则将则将 Jj 放入放入 Bi+1 内内; 否则，从否则，从 的的 Bk 中，选取中，选取 一个一个 Bl 使得使得为最小者为最小者 BF 算法的绝对性能比、计算复杂性与算法的绝对性能比、计算复杂性与 FF 算法相同算法相同 . Example 4 物品物品J1J2J3J4J5J6 wj 678324 I : C = 10 3 装箱问题的近似算法 J1 J4 J3J2 J6 J5 B1B2B3B4B

19、5 J1J2 J6 J5 J3 J4 Solution : 用用 BF 算法算法 解为解为: 其余为零，其余为零， 四、四、FFD ( First Fit Decreasing ) 算法算法 FFD 算法是先将物品按长度从大到小排序，然后用算法是先将物品按长度从大到小排序，然后用 FF 算法对物品装箱算法对物品装箱 . 该算法的计算复杂性为该算法的计算复杂性为 O(nlogn). Example 5 物品物品J1J2J3J4J5J6 wj 674283 I : C = 10 J1J5 J6 J4 J3 J2 Solution : 已知已知： 物品物品J5J2J1J3J6J4 wj 876432

20、 B1B2B3B4B5 J1J2 J3 J4 J5 J6 是最优的是最优的 NFD 算法？算法？ BFD 算法？算法？ 3 装箱问题的近似算法 Theorem 3.6 Proof :显然对任意实例显然对任意实例 I ，有，有 记记 首先证明两个结论首先证明两个结论： (1) FFD 算法所用的第算法所用的第 个箱子中每个的个箱子中每个的 长度不超过长度不超过 记记 wi 是放入第是放入第 个箱子中的第一个物品个箱子中的第一个物品,只需证只需证 用反证法，若不然，则有用反证法，若不然，则有 ，因此，因此 FFD 算法中前算法中前 个箱子中个箱子中, 每个箱子至多有两个物品每个箱子至多有两个物品

21、. 可证明存在可证明存在 使前使前 k 个恰各含一个物品，后个恰各含一个物品，后 个箱子各含两个物品个箱子各含两个物品 因为若不然，则存在两个箱子因为若不然，则存在两个箱子 使使 Bp有两有两 个物品个物品 , Bq 有一个物品有一个物品 因物品已从大到因物品已从大到 小排列，故小排列，故 , 因此因此 从从 而可以将而可以将wi 放入放入 Bq 中，矛盾中，矛盾. 3 装箱问题的近似算法 因为因为 FFD 未将未将 wk+1,，wi 放入前放入前 k 个箱子，说明个箱子，说明 其中任一个箱子已放不下其中任一个箱子已放不下, 故在最优解中也至少有故在最优解中也至少有 k 个个 箱子不含箱子不含

22、 wk+1,，wi中任一个物品中任一个物品 . 假设就是前假设就是前 k 个个 箱子，因此在最优解中，箱子，因此在最优解中， wk+1,，wi-1也会两两放入第也会两两放入第 个箱子中，且因为这些物品长度大于个箱子中，且因为这些物品长度大于 , 所所 以以 每个箱子中只有两个物品，且每个箱子中只有两个物品，且 已放不下已放不下 . 但最但最 优解中优解中 wi 必须放入前必须放入前 个箱子中，矛盾个箱子中，矛盾. 故故 (2) FFD 算法放入第算法放入第 个箱子中物品数不超过个箱子中物品数不超过 而如果至少有而如果至少有 个物品放入第个物品放入第 个箱子中，记前个箱子中，记前 个物品的长度为

23、个物品的长度为 . 记记 FFD 算法中前算法中前 个箱子中每个箱子物品总长为个箱子中每个箱子物品总长为 显然，对任意显然，对任意 否则长为否则长为 的物品可放入第的物品可放入第 j 个箱子中，因此个箱子中，因此 矛盾矛盾 . 所以所以 (2) 结论成立结论成立 . 由由(1)、(2) 知知FFD 算法比最优算法多用的箱子是用算法比最优算法多用的箱子是用 来放至多来放至多 个物品，而每个物品长不超过个物品，而每个物品长不超过 ，因此，因此 3 装箱问题的近似算法 因此因此 因为因为 如果如果 ，则，则 ，故不妨设，故不妨设 考虑实例考虑实例 I ：物品集长度为物品集长度为 , C 为箱长为箱长

24、. 说明说明 是不可改进的是不可改进的 . 比较比较 NF 算法、算法、FF ( BF ) 算法、算法、FFD 算法，它们算法，它们 的近似程度一个比一个好，但这并不是说的近似程度一个比一个好，但这并不是说 NF、FF(BF) 就失去了使用价值就失去了使用价值 . 1、FF(BF)、FFD 算法都要将所有物品全部装好后算法都要将所有物品全部装好后 , 所所 有箱子才能一起运走，而有箱子才能一起运走，而 NF 算法无此限制，很适合装算法无此限制，很适合装 箱场地小的情形；箱场地小的情形； FFD 算法要求所有物品全部到达后才开始装箱算法要求所有物品全部到达后才开始装箱, 而而 NF、FF(BF)

25、 算法在给某一物品装箱时，可以不知道算法在给某一物品装箱时，可以不知道 下一个物品的长度如何，适合在线装箱下一个物品的长度如何，适合在线装箱 存储罐注液问题存储罐注液问题 某化工厂有某化工厂有 9 个不同大小的存储罐，有一些已经装个不同大小的存储罐，有一些已经装 某液体某液体 . 现新到一批液体化工原料需要存储，这些液体现新到一批液体化工原料需要存储，这些液体 不能混合存储，它们分别是不能混合存储，它们分别是 1200 m3 苯，苯，700 m3 丁醇，丁醇， 1000 m3 丙醇，丙醇，450 m3 苯乙醇和苯乙醇和1200 m3 四氢呋喃四氢呋喃 . 下表列出每个存储罐的属性下表列出每个存

26、储罐的属性(单位单位: m3), 问应如何将新到问应如何将新到 的液体原料装罐的液体原料装罐, 才能使保留未用的存储罐个数最多才能使保留未用的存储罐个数最多? 存储罐编号存储罐编号123456789 容容 量量 500400400600600900800800800 当前内容当前内容 -苯苯-四氢呋喃四氢呋喃- 体体 积积 100300 Solution : 存储罐编号存储罐编号 123456789 容容 量量 500400400600600900800800800 当前内容当前内容-苯苯-四氢呋喃四氢呋喃- 体体 积积 100300 分别记苯、丁醇、丙醇、苯乙醇、四氢呋喃分别记苯、丁醇、丙醇

27、、苯乙醇、四氢呋喃 为第为第1，2，3，4，5种液体种液体 . 显然，新到液体应尽可能显然，新到液体应尽可能 装入已存有此种液体的罐中装入已存有此种液体的罐中 . 所以余下液体为：所以余下液体为：900 m3 苯，苯，700 m3 丁醇，丁醇，1000 m3 丙醇，丙醇，450 m3 乙醇和乙醇和700 m3 四氢呋喃四氢呋喃 . 剩余空罐剩余空罐 为为1，3，4，5，6，8，9 . 由于不允许混合，每种液体由于不允许混合，每种液体 至少需要至少需要1个空罐个空罐 . 令令 第第 i 种液体装入第种液体装入第 j 个存储罐个存储罐 否则否则 记第记第 j 个空罐的容量为个空罐的容量为 cj ，j = 1, 3, 4, 5, 6, 8, 9, 第第 i 种剩余液体的体积为种