一维装箱问题典型算法.ppt

《一维装箱问题典型算法.ppt》由会员分享，可在线阅读，更多相关《一维装箱问题典型算法.ppt（33页珍藏版）》请在三一办公上搜索。

1、第三章 装箱问题,信息处理中的组合优化,Combinatorial Optimization in Information Processing,第三章 装箱问题,1 装箱问题的描述,2 装箱问题的最优解值下界,3 装箱问题的近似算法,第三章 装箱问题,装箱问题（Bin Packing）是一个经典的组合优化问题，有着广泛的应用，在日常生活中也屡见不鲜.,1 装箱问题的描述,设有许多具有同样结构和负荷的箱子 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.,设,则装箱问题的整数线性规划模型为：,约束条件（1）表示：一旦箱子 Bi 被使用，放入 Bi 的物品总负荷不超过 C；,约束条件（2）表示：每个物品恰好放入一个箱子中.,第三章 装箱问题,上述装箱问题是这类问题最早被研究的，也是提法上最简单的问题，称为一维装箱问题.但,装箱问题的其他一些提法：,1、在装箱时，不仅考虑长度，同时考虑重量或面积、体积 etc.即二维、三维、装箱问题；,2、对每个箱子的负荷限制不是常数 C;而是,最优目

3、标可如何提？,3、物品J1，J2，Jn 的负荷事先并不知道，来货是 随到随装；即 在线（On-Line）装箱问题；,4、由于场地的限制，在同一时间只能允许一定数量的 箱子停留现场可供使用,etc.,1 装箱问题的描述,BP 的应用举例：,1、下料问题 轧钢厂生产的线材一般为同一长度,而用户所需的线材则可能具有各种不同的尺寸,如何根据用户提出的要求，用最少的线材截出所需的定货；,2、二维 BP 玻璃厂生产出长宽一定的大的平板玻璃,但用户所需玻璃的长宽可能有许多差异，如何根据用户提出的要求，用最少的平板玻璃截出所需的定货;,3、计算机的存贮问题 如要把大小不同的共 10 MB 的文件拷贝到磁盘中去

4、，而每张磁盘的容量为 1.44 MB,已知每个文件的字节数不超过 1.44 MB,而且一个文件不能分成几部分存贮，如何用最少的磁盘张数完成.,4、生产流水线的平衡问题 给定流水节拍 C,如何设置最少的工作站，（按一定的紧前约束）沿着流水线将任务分配到各工作站上.称为带附加优先约束的 BP.,BP 是容量限制的工厂选址问题的特例之一.,Go back,第三章 装箱问题,2 装箱问题的最优解值下界,由于 BP 是 NP-C 问题，所以求解考虑 一是尽可能改进简单的穷举搜索法，减少搜索工作量.如:分支定界法；二是启发式（近似）算法.,显然 是它的一个最优解.,2 装箱问题的最优解值下界,Theore

5、m 3.1,BP 最优值的一个下界为,表示不小于 a 的最小整数.,Theorem 3.2,设 a 是任意满足 的整数,对 BP 的任一实例 I,记,则,是最优解的一个下界.,第三章 装箱问题,a,C,C/2,C-a,I1,I2,I3,Proof:,仅考虑对 I1,I2,I3中物品的装箱.,中物品的长度大于C/2,每个物品需单独放入一个箱子，这就需要 个箱子.,又 中每个物品长度至少为 a,但可能与 I2 中的物品共用箱子，,它不能与 I1 中的物品共用箱子,与 I2 中的物品如何？,由于放 I2 中物品的 个箱子的剩余总长度为,在最好的情形下，被 I3 中的物品全部充满，故剩下总长度 将另外

6、至少 个附加的箱子.,Note:可能小于零,是最优解的一个下界.,2 装箱问题的最优解值下界,问？,未必！,如,Corollary 3.1,记,则 L2 是装箱问题的最优解的一个下界，且.,Proof:,L2 为最优解的下界是显然的.,(若证明，则可得),当 a=0 时，是所有物品.,Go back,第三章 装箱问题,3 装箱问题的近似算法,一、NF(Next Fit)算法,设物品 J1，J2,，Jn 的长度分别为 w1，w2,，wn箱子 B1，B2，的长均为 C，按物品给定的顺序装箱.,先将 J1 放入 B1,如果 则将 J2 放入 B1,如果 而,则 B1 已放入 J1，J2,，Jj，将其

7、关闭，将 Jj+1 放入 B2.,同法进行，直到所有物品装完为止.,特点：,1、按物品给定的顺序装箱；,2、关闭原则.,对当前要装的物品 Ji 只关心具有最大下标的已使用过的箱子 Bj 能否装得下？能.则 Ji 放入 Bj；否.关闭 Bj，Ji 放入新箱子 Bj+1.,计算复杂性为 O(n).,3 装箱问题的近似算法,Example 1,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 中放不下,所以关闭 B1,将 J2 放入 B2,J3 在 B2 中放不下

8、(不考虑B1 是否能装),所以关闭 B2将 J3 放入 B3，,解为:,其余为零，,第三章 装箱问题,Theorem 3.3,Proof:,先证再说明不可改进,设 I 为任一实例，,(要证),显然，由 得,反证,如果,则 对任意 i=1,2,k,由于起用第 2i 个箱子是因为第 2i-1 个箱子放不下第2i个箱子中第一个物品,因此这两个箱子中物品的总长度大于 C，所以前 2k 个箱子中物品的总长度大于 Ck.,这与 矛盾.,考虑实例 I:C=1,3 装箱问题的近似算法,二、FF(First Fit)算法,设物品 J1，J2,，Jn 的长度分别为 w1，w2,，wn箱子 B1，B2，的长均为 C

9、，按物品给定的顺序装箱.,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+

10、1 放入首先找到的能放得下的箱子，如果都放不下，则启用箱子 Bi+1，将 Jj+1 放入 Bi+1，如此继续，直到所有物品装完为止.,计算复杂性为 O(nlogn).,特点：,1、按物品给定的顺序装箱；,2、对于每个物品 Jj 总是放在能容纳它的具 有最小标号的箱子.,但精度比NF 算法更高,3 装箱问题的近似算法,Theorem 3.4,Theorem 3.5,对任意实例 I，,而且存在 任意大的实例 I，使,因而,第三章 装箱问题,Example 2,I:C=10,J1,J5,J6,J4,J3,J2,B1,B2,B3,B4,B5,J1,J2,J3,J4,J5,J6,Solution:,首先

11、，将 J1 放入 B1;,由于 J2 在 B1 中放不下,所以将 J2 放入 B2,对于 J3,先检查 B1 是否能容纳下,能.所以将 J3 放入 B1，,解为:,其余为零，,3 装箱问题的近似算法,Example 3,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(B

12、est Fit)算法,与 FF 算法相似，按物品给定的顺序装箱，区别在于对于每个物品 Jj 是放在一个使得 Jj 放入之后，Bi 所剩余长度为最小者.,即在处理 Jj 时，若 B1，B2,，Bi 非空，而 Bi+1 尚未启用，设 B1，B2,，Bi 所余的长度为,若,则将 Jj 放入 Bi+1 内;,否则，从 的 Bk 中，选取 一个 Bl,使得 为最小者.,BF 算法的绝对性能比、计算复杂性与 FF 算法相同.,Example 4,I:C=10,3 装箱问题的近似算法,J1,J4,J3,J2,J6,J5,B1,B2,B3,B4,B5,J1,J2,J6,J5,J3,J4,Solution:,用

13、 BF 算法,解为:,其余为零，,而 此为最优解.,第三章 装箱问题,四、FFD(First Fit Decreasing)算法,FFD 算法是先将物品按长度从大到小排序，然后用FF 算法对物品装箱.,该算法的计算复杂性为 O(nlogn).,Example 5,I:C=10,J1,J5,J6,J4,J3,J2,Solution:,已知：,B1,B2,B3,B4,B5,J1,J2,J3,J4,J5,J6,是最优的.,NFD 算法？BFD 算法？,3 装箱问题的近似算法,Theorem 3.6,Proof:,显然对任意实例 I，有,记,首先证明两个结论：,(1)FFD 算法所用的第 个箱子中每个

14、的长度不超过,记 wi 是放入第 个箱子中的第一个物品,只需证,用反证法，若不然，则有，因此 FFD,算法中前 个箱子中,每个箱子至多有两个物品.,第三章 装箱问题,可证明存在 使前 k 个恰各含一个物品，后 个箱子各含两个物品.,因为若不然，则存在两个箱子 使 Bp有两个物品,Bq 有一个物品 因物品已从大到小排列，故,因此 从而可以将wi 放入 Bq 中，矛盾.,3 装箱问题的近似算法,因为 FFD 未将 wk+1,，wi 放入前 k 个箱子，说明其中任一个箱子已放不下,故在最优解中也至少有 k 个箱子不含 wk+1,，wi 中任一个物品.假设就是前 k 个箱子，因此在最优解中，wk+1,

15、，wi-1 也会两两放入第,个箱子中，且因为这些物品长度大于,所以,每个箱子中只有两个物品，且 已放不下.但最优解中 wi 必须放入前 个箱子中，矛盾.故,(2)FFD 算法放入第 个箱子中物品数不超过,而如果至少有 个物品放入第,个箱子中，记前 个物品的长度为.,第三章 装箱问题,记 FFD 算法中前 个箱子中每个箱子物品总长为,显然，对任意,否则长为 的物品可放入第 j 个箱子中，因此,矛盾.,所以(2)结论成立.,由(1)、(2)知FFD 算法比最优算法多用的箱子是用来放至多 个物品，而每个物品长不超过，因此,3 装箱问题的近似算法,因此,因为 如果，则，故不妨设,考虑实例 I：物品集长

16、度为,C 为箱长.,说明 是不可改进的.,第三章 装箱问题,比较 NF 算法、FF(BF)算法、FFD 算法，它们的近似程度一个比一个好，但这并不是说 NF、FF(BF)就失去了使用价值.,1、FF(BF)、FFD 算法都要将所有物品全部装好后,所有箱子才能一起运走，而 NF 算法无此限制，很适合装箱场地小的情形；,2、FFD 算法要求所有物品全部到达后才开始装箱,而 NF、FF(BF)算法在给某一物品装箱时，可以不知道下一个物品的长度如何，适合在线装箱.,存储罐注液问题,第三章 装箱问题,某化工厂有 9 个不同大小的存储罐，有一些已经装某液体.现新到一批液体化工原料需要存储，这些液体不能混合

17、存储，它们分别是 1200 m3 苯，700 m3 丁醇，1000 m3 丙醇，450 m3 苯乙醇和1200 m3 四氢呋喃.下表列出每个存储罐的属性(单位:m3),问应如何将新到的液体原料装罐,才能使保留未用的存储罐个数最多?,第三章 装箱问题,Solution:,分别记苯、丁醇、丙醇、苯乙醇、四氢呋喃为第1，2，3，4，5种液体.显然，新到液体应尽可能装入已存有此种液体的罐中.,所以余下液体为：900 m3 苯，700 m3 丁醇，1000 m3 丙醇，450 m3 乙醇和700 m3 四氢呋喃.剩余空罐为1，3，4，5，6，8，9.由于不允许混合，每种液体至少需要1个空罐.,令,记第

18、j 个空罐的容量为 cj，j=1,3,4,5,6,8,9,第 i 种剩余液体的体积为 li,i=1,2,3,4,5.,第三章 装箱问题,整数规划模型：,表示第j 个 空罐被使用,每个罐子至多装一种液体,每种液体的体积不能超过装这些液体的罐子的总容量,将 li、cj 代入，可用 Lindo、Lingo 等软件求解.,第三章 装箱问题,1 2 3 4 5 6 7 8 9,当问题的数据很大时，IP 的计算复杂性很高，可考虑采用近似算法或启发式算法求解.,900,700,1000,450,700,500,400,400,600,600,900,800,800,800,苯,苯,丁 醇,丙 醇,乙 醇,四

19、氢呋喃,四氢呋喃,如利用 FFD 算法思想：对每一种液体，将空罐按容积排成非增序，若需 k 个罐子，则装入具有连贯序号的罐子，使这 k 个空罐中最大容积空罐序号最大.,6 8 9 4 5 1 3 7 2,500,400,400,600,600,900,800,800,800,苯,四氢呋喃,苯,丁 醇,丙 醇,丙 醇,乙 醇,四氢呋喃,第三章 装箱问题,如果算法再细一点，只需要一个空罐的液体先装，效果会好一些.,6 8 9 4 5 1 3 7 2,900,700,1000,450,700,500,400,400,600,600,900,800,800,800,苯,苯,丁 醇,丙 醇,乙 醇,四氢呋喃,四氢呋喃,苯,丁 醇,丙 醇,丙 醇,乙 醇,四氢呋喃,后一种装法的空罐容积大，这是因为只需一个空罐的液体先装时，这部分装罐实现了最优.需要两个及以上空罐时，寻找最优算法的计算量就会变大.,第三章 装箱问题,完,