《数学建模---第八章-装箱问题概述》由会员分享，可在线阅读，更多相关《数学建模---第八章-装箱问题概述（34页珍藏版）》请在金锄头文库上搜索。
1、 第八章第八章 装箱问题装箱问题组合优化理论组合优化理论 Combinatorial Optimization Theory第八章第八章 装箱问题装箱问题1 装箱问题的描述装箱问题的描述2 装箱问题的最优解值下界装箱问题的最优解值下界3 装箱问题的近似算法装箱问题的近似算法第八章第八章第八章第八章 装箱问题装箱问题装箱问题装箱问题 装箱问题（装箱问题（Bin Packing）是一个经典的组合优化）是一个经典的组合优化问题，有着广泛的应用，在日常生活中也屡见不鲜问题，有着广泛的应用，在日常生活中也屡见不鲜 .1 装箱问题的描述装箱问题的描述 设有许多具有同样结构和负荷的箱子设有许多具有同样结构和
2、负荷的箱子 B1，B2，其数量足够供所达到目的之用其数量足够供所达到目的之用 . 每个箱子的负荷（可为每个箱子的负荷（可为长度、重量长度、重量 etc.）为为 C ,今有今有 n 个负荷为个负荷为 wj，0 wj C j = 1，2，n 的物品的物品 J1，J2，Jn 需要装入箱内需要装入箱内.装箱问题：装箱问题：装箱问题：装箱问题： 是指寻找一种方法，使得能以最小数量的箱子数将是指寻找一种方法，使得能以最小数量的箱子数将J1，J2，Jn 全部装入箱内全部装入箱内. .1 1 装箱问题的描述装箱问题的描述 由于由于 wi C，所以，所以 BP 的最优解的箱子数不超过的最优解的箱子数不超过 n
3、. .设设箱子箱子 Bi 被使用被使用否则否则物品物品 Jj 放入箱子放入箱子 Bi 中中否则否则则装箱问题的整数线性规划模型为则装箱问题的整数线性规划模型为：约束条件（约束条件（1）表示：一旦箱子）表示：一旦箱子 Bi 被使用，放入被使用，放入 Bi 的物品总负荷不超过的物品总负荷不超过 C ；约束条件（约束条件（2）表示：每个物品恰好放入一个箱子中）表示：每个物品恰好放入一个箱子中 .第八章第八章 装箱问题装箱问题 上述装箱问题是这类问题最早被研究的，也是提上述装箱问题是这类问题最早被研究的，也是提法上最简单的问题，称为一维装箱问题法上最简单的问题，称为一维装箱问题 . . 但但装箱问题的
4、其他一些提法装箱问题的其他一些提法：1、在装箱时，不仅考虑长度，同时考虑重量或面积、在装箱时，不仅考虑长度，同时考虑重量或面积、 体积体积 etc . 即二维、三维、即二维、三维、装箱问题装箱问题；2、对每个箱子的负荷限制不是常数、对每个箱子的负荷限制不是常数 C ; 而是而是最优目标可如何提？最优目标可如何提？3、物品、物品J1，J2，Jn 的负荷事先并不知道，来货是的负荷事先并不知道，来货是 随到随装；即随到随装；即 在线（在线（On-Line）装箱问题；）装箱问题；4、由于场地的限制，在同一时间只能允许一定数量的、由于场地的限制，在同一时间只能允许一定数量的 箱子停留现场可供使用箱子停留
5、现场可供使用, etc . 1 1 装箱问题的描述装箱问题的描述BP 的应用举例的应用举例：1、下料问题下料问题 轧钢厂生产的线材一般为同一长度轧钢厂生产的线材一般为同一长度, 而用而用户所需的线材则可能具有各种不同的尺寸户所需的线材则可能具有各种不同的尺寸, 如何根据用如何根据用户提出的要求，用最少的线材截出所需的定货；户提出的要求，用最少的线材截出所需的定货；2、 二维二维 BP 玻璃厂生产出长宽一定的大的平板玻璃玻璃厂生产出长宽一定的大的平板玻璃,但用户所需玻璃的长宽可能有许多差异，如何根据用但用户所需玻璃的长宽可能有许多差异，如何根据用户提出的要求，用最少的平板玻璃截出所需的定货户提出
6、的要求，用最少的平板玻璃截出所需的定货;3、计算机的存贮问题计算机的存贮问题 如要把大小不同的共如要把大小不同的共 10 MB 的的文件拷贝到磁盘中去，而每张磁盘的容量为文件拷贝到磁盘中去，而每张磁盘的容量为 1. 44 MB ,已知每个文件的字节数不超过已知每个文件的字节数不超过 1.44 MB , 而且一个文件而且一个文件不能分成几部分存贮，如何用最少的磁盘张数完成不能分成几部分存贮，如何用最少的磁盘张数完成 .4、生产流水线的平衡问题生产流水线的平衡问题 给定流水节拍给定流水节拍 C , 如何设置如何设置最少的工作站，（按一定的紧前约束）沿着流水线将任最少的工作站，（按一定的紧前约束）沿
7、着流水线将任务分配到各工作站上务分配到各工作站上 . 称为带附加优先约束的称为带附加优先约束的 BP . BP 是容量限制的工厂选址问题的特例之一是容量限制的工厂选址问题的特例之一.Go back第八章第八章 装箱问题装箱问题2 装箱问题的最优解值下界装箱问题的最优解值下界 由于由于 BP 是是 NP-C 问题，所以求解考虑问题，所以求解考虑 一是尽可能一是尽可能改进简单的穷举搜索法，减少搜索工作量改进简单的穷举搜索法，减少搜索工作量 . 如如: : 分支分支定界法；二是启发式（近似）算法定界法；二是启发式（近似）算法 . 显然显然 是它的一个最优解是它的一个最优解 . 2 2 装箱问题的最优
8、解值下界装箱问题的最优解值下界Theorem 3.1BP 最优值的一个下界为最优值的一个下界为表示不小于表示不小于 a 的最小整数的最小整数.Theorem 3.2 设设 a 是任意满足是任意满足 的整数的整数,对对 BP 的任一实例的任一实例 I , 记记则则是最优解的一个下界是最优解的一个下界 . .第八章第八章 装箱问题装箱问题aCC/2C-aI1I2I3Proof : 仅考虑对仅考虑对 I1,I2,I3中物品的装箱中物品的装箱 .中物品的长度大于中物品的长度大于C/2 ,每个物品需单独放入一个箱子，每个物品需单独放入一个箱子，这就需要这就需要 个箱子个箱子 .又又 中每个物品长度至少为
9、中每个物品长度至少为 a , 但可能与但可能与 I2 中的中的物品共用箱子物品共用箱子，它不能与它不能与 I1 中的物品共用箱子中的物品共用箱子,与与 I2 中的物品如何？中的物品如何？ 由于放由于放 I2 中物品的中物品的 个箱子的剩余个箱子的剩余总长度为总长度为 在最好的情形下，在最好的情形下， 被被 I3 中的物品全部充满，故剩中的物品全部充满，故剩下总长度下总长度 将另外至少将另外至少 个附加的箱子个附加的箱子 .Note: 可能小于零可能小于零是最优解的一个下界是最优解的一个下界 .2 2 装箱问题的最优解值下界装箱问题的最优解值下界问问 ？ 未必！未必！ 如如Corollary 3
10、.1记记则则 L2 是装箱问题的最优解的一个下界，且是装箱问题的最优解的一个下界，且 .Proof :L2 为最优解的下界是显然的为最优解的下界是显然的 .( (若证明若证明 ，则可得，则可得 ) )当当 a = 0 时，时， 是所有物品是所有物品 .Go back第八章第八章 装箱问题装箱问题3 装箱问题的近似算法装箱问题的近似算法一、一、NF ( Next Fit ) 算法算法 设物品设物品 J1，J2,，Jn 的长度分别为的长度分别为 w1，w2,，wn箱子箱子 B1，B2，的长均为的长均为 C ，按物品给定的顺序装箱，按物品给定的顺序装箱 . 先将先将 J1 放入放入 B1, 如果如果
11、 则将则将 J2 放入放入 B1 如果如果 而而则则 B1 已放入已放入 J1，J2,，Jj，将其，将其关闭关闭，将，将 Jj+1 放入放入 B2 .同法进行，直到所有物品装完为止同法进行，直到所有物品装完为止 .特点特点： 1、按物品给定的顺序装箱、按物品给定的顺序装箱；2、关闭原则关闭原则 . 对当前要装的物品对当前要装的物品 Ji 只关心具有最大下标的已使只关心具有最大下标的已使用过的箱子用过的箱子 Bj 能否装得下？能否装得下？能能. 则则 Ji 放入放入 Bj ；否；否 . 关闭关闭 Bj ，Ji 放入新箱子放入新箱子 Bj+1 .计算复杂性为计算复杂性为 O(n).3 3 装箱问题
12、的近似算法装箱问题的近似算法Example 1物品物品J1J2J3J4J5J6wj674283I : C = 10J1J5J6J4J3J2B1B2B3B4B5J1J2J3J4J5J6Solution :首先，将首先，将 J1 放入放入 B1; ;由于由于 J2 在在 B1 中放不下中放不下, 所所以关闭以关闭 B1 , 将将 J2 放入放入 B2 ,J3 在在 B2 中放不下中放不下(不考虑不考虑B1 是否能装是否能装), 所以关闭所以关闭 B2将将 J3 放入放入 B3，解为解为:其余为零，其余为零，第八章第八章 装箱问题装箱问题Theorem 3.3Proof :先证先证再说明不可改进再说
13、明不可改进设设 I 为任一实例，为任一实例，(要证要证 )显然，由显然，由 得得反证反证如果如果 ,则则 对任意对任意 i = 1, 2, k由于起用第由于起用第 2i 个箱子是因为第个箱子是因为第 2i -1 个箱子放不下第个箱子放不下第2i个箱子中第一个物品个箱子中第一个物品,因此这两个箱子中物品的总长度因此这两个箱子中物品的总长度大于大于 C ，所以前，所以前 2k 个箱子中物品的总长度大于个箱子中物品的总长度大于 Ck .这与这与 矛盾矛盾 .考虑实例考虑实例 I : C = 1,3 3 装箱问题的近似算法装箱问题的近似算法二、二、FF ( First Fit ) 算法算法 设物品设物
14、品 J1，J2,，Jn 的长度分别为的长度分别为 w1，w2,，wn箱子箱子 B1，B2，的长均为的长均为 C ，按物品给定的顺序装箱，按物品给定的顺序装箱 .物品物品J1J2J3J4J5J6wj674283I : C = 10 用用 NF 算法装算法装箱箱, 当放入当放入 J3 时时, 仅看仅看 B2是否能放入，因是否能放入，因 B1 已关闭已关闭,参见参见 EX .1但事实上，但事实上，B1 此时是能放得下此时是能放得下 J3 的的 .如何修正如何修正 NF 算算法法先将先将 J1 放入放入 B1，若，若 , 则则 J2 放入放入 B1 , 否否则，则，J2 放入放入 B2 ; 若若 J2
15、 已放入已放入 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+1 ，将，将 Jj+
16、1 放入放入 Bi+1 ，如此继续，直到所有物品装完为止，如此继续，直到所有物品装完为止 . 计算复杂性为计算复杂性为 O(nlogn).特点特点：1、按物品给定的顺序装箱、按物品给定的顺序装箱；2、对于每个物品对于每个物品 Jj 总是放在能容纳它的具总是放在能容纳它的具 有最小标号的箱子有最小标号的箱子 .但精度比但精度比NF 算法更高算法更高3 3 装箱问题的近似算法装箱问题的近似算法Theorem 3.4Theorem 3.5对任意实例对任意实例 I ，而且存在而且存在 任意大的实例任意大的实例 I ，使，使因而因而第八章第八章 装箱问题装箱问题Example 2物品物品J1J2J3J4
17、J5J6wj674283I : C = 10J1J5J6J4J3J2B1B2B3B4B5J1J2J3J4J5J6Solution :首先，将首先，将 J1 放入放入 B1; ;由于由于 J2 在在 B1 中放不下中放不下, 所所以将以将 J2 放入放入 B2 , 对于对于 J3 , 先检查先检查 B1 是否能是否能容纳下容纳下, 能能 . 所以将所以将 J3 放放入入 B1，解为解为:其余为零，其余为零，3 3 装箱问题的近似算法装箱问题的近似算法Example 3物品物品J1J2J3J4J5J6wj678324I : C = 10J1J4J3J2Solution :用用 NF 算法算法B1B
18、2B3B4B5J1J2J6J5J3J4B1B2B3B4B5J1J2J6J5J3J4J6J5用用 FF 算法算法 参见参见 EX .3 用用 FF 算法装箱算法装箱, 当放入当放入 J4 时时, B1 能容纳能容纳J4 就放入就放入 B1 ，而事实上，放入，而事实上，放入 B2 更好更好 .第八章第八章 装箱问题装箱问题三、三、BF ( Best Fit ) 算法算法 与与 FF 算法相似，按物品给定的顺序装箱，区别在算法相似，按物品给定的顺序装箱，区别在于对于每个物品于对于每个物品 Jj 是放在一个使得是放在一个使得 Jj 放入之后，放入之后，Bi 所所剩余长度为最小者剩余长度为最小者 . 即
19、在处理即在处理 Jj 时，若时，若 B1，B2,，Bi 非空，而非空，而 Bi+1 尚尚未启用，设未启用，设 B1，B2,，Bi 所余的长度为所余的长度为若若则将则将 Jj 放入放入 Bi+1 内内;否则，从否则，从 的的 Bk 中，选取中，选取 一个一个 Bl 使得使得 为最小者为最小者 . .BF 算法的绝对性能比、计算复杂性与算法的绝对性能比、计算复杂性与 FF 算法相同算法相同 .Example 4物品物品J1J2J3J4J5J6wj678324I : C = 103 3 装箱问题的近似算法装箱问题的近似算法J1J4J3J2J6J5B1B2B3B4B5J1J2J6J5J3J4Solut
20、ion :用用 BF 算法算法解为解为:其余为零，其余为零，而而而而 此为最优解此为最优解此为最优解此为最优解. .第八章第八章 装箱问题装箱问题四、四、FFD ( First Fit Decreasing ) 算法算法 FFD 算法是先将物品按长度从大到小排序，然后用算法是先将物品按长度从大到小排序，然后用FF 算法对物品装箱算法对物品装箱 . 该算法的计算复杂性为该算法的计算复杂性为 O(nlogn).Example 5物品物品J1J2J3J4J5J6wj674283I : C = 10J1J5J6J4J3J2Solution :已知已知：物品物品J5J2J1J3J6J4wj876432B
21、1B2B3B4B5J1J2J3J4J5J6是最优的是最优的 . .NFD 算法？算法？ BFD 算法？算法？3 3 装箱问题的近似算法装箱问题的近似算法Theorem 3.6Proof :显然对任意实例显然对任意实例 I ，有，有记记首先证明两个结论首先证明两个结论：(1) FFD 算法所用的第算法所用的第 个箱子中每个的个箱子中每个的长度不超过长度不超过记记 wi 是放入第是放入第 个箱子中的第一个物品个箱子中的第一个物品,只需证只需证用反证法，若不然，则有用反证法，若不然，则有 ，因此，因此 FFD算法中前算法中前 个箱子中个箱子中, 每个箱子至多有两个物品每个箱子至多有两个物品 .第八章
22、第八章 装箱问题装箱问题 可证明存在可证明存在 使前使前 k 个恰各含一个物品，后个恰各含一个物品，后 个箱子各含两个物品个箱子各含两个物品. . 因为若不然，则存在两个箱子因为若不然，则存在两个箱子 使使 Bp有两有两个物品个物品 , Bq 有一个物品有一个物品 因物品已从大到因物品已从大到小排列，故小排列，故 , 因此因此 从从而可以将而可以将wi 放入放入 Bq 中，矛盾中，矛盾.3 3 装箱问题的近似算法装箱问题的近似算法 因为因为 FFD 未将未将 wk+1,，wi 放入前放入前 k 个箱子，说明个箱子，说明其中任一个箱子已放不下其中任一个箱子已放不下, 故在最优解中也至少有故在最优
23、解中也至少有 k 个个箱子不含箱子不含 wk+1,，wi 中任一个物品中任一个物品 . 假设就是前假设就是前 k 个个箱子，因此在最优解中，箱子，因此在最优解中， wk+1,，wi-1 也会两两放入第也会两两放入第个箱子中，且因为这些物品长度大于个箱子中，且因为这些物品长度大于 , 所以所以每个箱子中只有两个物品，且每个箱子中只有两个物品，且 已放不下已放不下 . 但最但最优解中优解中 wi 必须放入前必须放入前 个箱子中，矛盾个箱子中，矛盾. 故故(2) FFD 算法放入第算法放入第 个箱子中物品数不超过个箱子中物品数不超过而如果至少有而如果至少有 个物品放入第个物品放入第个箱子中，记前个箱
24、子中，记前 个物品的长度为个物品的长度为 .第八章第八章 装箱问题装箱问题记记 FFD 算法中前算法中前 个箱子中每个箱子物品总长为个箱子中每个箱子物品总长为 显然，对任意显然，对任意否则长为否则长为 的物品可放入第的物品可放入第 j 个箱子中，因此个箱子中，因此矛盾矛盾 .所以所以 (2) 结论成立结论成立 . 由由(1)、(2) 知知FFD 算法比最优算法多用的箱子是用算法比最优算法多用的箱子是用来放至多来放至多 个物品，而每个物品长不超过个物品，而每个物品长不超过 ，因此，因此3 3 装箱问题的近似算法装箱问题的近似算法因此因此因为因为 如果如果 ，则，则 ，故不妨设，故不妨设 考虑实例
25、考虑实例 I ：物品集长度为物品集长度为 , C 为箱长为箱长. 说明说明 是不可改进的是不可改进的 .第八章第八章 装箱问题装箱问题 比较比较 NF 算法、算法、FF ( BF ) 算法、算法、FFD 算法，它们算法，它们的近似程度一个比一个好，但这并不是说的近似程度一个比一个好，但这并不是说 NF、FF(BF)就失去了使用价值就失去了使用价值 .1、FF(BF)、FFD 算法都要将所有物品全部装好后算法都要将所有物品全部装好后 , 所所有箱子才能一起运走，而有箱子才能一起运走，而 NF 算法无此限制，很适合装算法无此限制，很适合装箱场地小的情形；箱场地小的情形；2 2、FFD 算法要求所有
26、物品全部到达后才开始装箱算法要求所有物品全部到达后才开始装箱, 而而 NF、FF(BF) 算法在给某一物品装箱时，可以不知道算法在给某一物品装箱时，可以不知道下一个物品的长度如何，适合在线装箱下一个物品的长度如何，适合在线装箱 . .存储罐注液问题存储罐注液问题第八章第八章 装箱问题装箱问题 某化工厂有某化工厂有 9 个不同大小的存储罐，有一些已经装个不同大小的存储罐，有一些已经装某液体某液体 . 现新到一批液体化工原料需要存储，这些液体现新到一批液体化工原料需要存储，这些液体不能混合存储，它们分别是不能混合存储，它们分别是 1200 m3 苯，苯，700 m3 丁醇，丁醇，1000 m3 丙
27、醇，丙醇，450 m3 苯乙醇和苯乙醇和1200 m3 四氢呋喃四氢呋喃 . 下表列出每个存储罐的属性下表列出每个存储罐的属性(单位单位: m3), 问应如何将新到问应如何将新到的液体原料装罐的液体原料装罐, 才能使保留未用的存储罐个数最多才能使保留未用的存储罐个数最多?存储罐编号存储罐编号123456789容容 量量500400400600600900800800800当前内容当前内容-苯苯-四氢呋喃四氢呋喃-体体 积积100300第八章第八章 装箱问题装箱问题Solution :存储罐编号存储罐编号123456789容容 量量500400400600600900800800800当前内容当
28、前内容-苯苯-四氢呋喃四氢呋喃-体体 积积100300 分别记苯、丁醇、丙醇、苯乙醇、四氢呋喃分别记苯、丁醇、丙醇、苯乙醇、四氢呋喃为第为第1，2，3，4，5种液体种液体 . 显然，新到液体应尽可能显然，新到液体应尽可能装入已存有此种液体的罐中装入已存有此种液体的罐中 . 所以余下液体为：所以余下液体为：900 m3 苯，苯，700 m3 丁醇，丁醇，1000 m3 丙醇，丙醇，450 m3 乙醇和乙醇和700 m3 四氢呋喃四氢呋喃 . 剩余空罐剩余空罐为为1，3，4，5，6，8，9 . 由于不允许混合，每种液体由于不允许混合，每种液体至少需要至少需要1个空罐个空罐 .令令第第 i 种液体装
29、入第种液体装入第 j 个存储罐个存储罐否则否则记第记第 j 个空罐的容量为个空罐的容量为 cj ，j = 1, 3, 4, 5, 6, 8, 9,第第 i 种剩余液体的体积为种剩余液体的体积为 li , i = 1, 2, 3, 4, 5 .第八章第八章 装箱问题装箱问题整数规划模型整数规划模型： 表示第表示第j 个个 空罐被使用空罐被使用每个罐子至多每个罐子至多装一种液体装一种液体每种液体的体积每种液体的体积不能超过装这些不能超过装这些液体的罐子的总液体的罐子的总容量容量将将 li、cj 代入，可用代入，可用 Lindo 、Lingo 等软件求解等软件求解 .第八章第八章 装箱问题装箱问题
30、1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 当问题的数据很大时，当问题的数据很大时，IP 的计算复杂性很高，可的计算复杂性很高，可考虑采用近似算法或启发式算法求解考虑采用近似算法或启发式算法求解 . 900 700 1000 450 700500 400 400 600 600 900 800 800 800苯苯苯苯丁丁 醇醇丙丙 醇醇乙乙 醇醇四四氢氢呋呋喃喃四四氢氢呋呋喃喃 如利用如利用 FFD 算法思想算法思想：对每一种液体，将空罐按对每一种液体，将空罐按容积排成非增序容积排成非增序，若需若需 k 个罐子，则装入具有连贯序个罐子，则装入具有连贯序号的罐子，使这
31、号的罐子，使这 k 个空罐中最大容积空罐序号最大个空罐中最大容积空罐序号最大 . . 6 8 9 4 5 1 3 7 2 6 8 9 4 5 1 3 7 2500400400600 600900800800 800苯苯四四氢氢呋呋喃喃苯苯丁丁 醇醇丙丙 醇醇丙丙 醇醇乙乙 醇醇四四氢氢呋呋喃喃第八章第八章 装箱问题装箱问题 如果算法再细一点，只需要一个空罐的液体先装，如果算法再细一点，只需要一个空罐的液体先装，效果会好一些效果会好一些 . 6 8 9 4 5 1 3 7 2 6 8 9 4 5 1 3 7 2 900 700 1000 450 700500400400600 600900800800 800苯苯苯苯丁丁 醇醇丙丙 醇醇乙乙 醇醇四四氢氢呋呋喃喃四四氢氢呋呋喃喃苯苯丁丁 醇醇丙丙 醇醇丙丙 醇醇乙乙 醇醇四四氢氢呋呋喃喃 后一种装法的空罐容积大，这是因为只需一个空罐后一种装法的空罐容积大，这是因为只需一个空罐的液体先装时，这部分装罐实现了最优的液体先装时，这部分装罐实现了最优 . 需要两个及以需要两个及以上空罐时，寻找最优算法的计算量就会变大上空罐时，寻找最优算法的计算量就会变大 .第八章第八章 装箱问题装箱问题 完完34 以上有不当之处，请大家给与批评指正，以上有不当之处，请大家给与批评指正，谢谢大家！谢谢大家！
