单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第八章 装箱问题,组合优化理论,Combinatorial,Optimization Theory,第八章 装箱问题,1 装箱问题的描述,2 装箱问题的最优解值下界,3 装箱问题的近似算法,第八章 装箱问题,装箱问题（,Bin Packing,）是一个经典的组合优化,问题，有着广泛的应用，在日常生活中也屡见不鲜.,1 装箱问题的描述,设有许多具有同样结构和负荷的箱子,B,1,，,B,2,，,其数量足够供所达到目的之用.每个箱子的负荷（可为,长度、重量,etc,.）,为,C,今有,n,个负荷为,w,j,，0,w,j,C,j,=1，2，,n,的物品,J,1,，,J,2,，,J,n,需要装入箱内.,装箱问题：,是指寻找一种方法，使得能以最小数量的箱子数将,J,1,，,J,2,，,J,n,全部装入箱内,.,1 装箱问题的描述,由于,w,i,C,，所以,BP,的最优解的箱子数不超过,n,.,设,箱子,B,i,被使用,否则,物品,J,j,放入箱子,B,i,中,否则,则装箱问题的整数线性规划模型为,：,约束条件（1）表示：一旦箱子,B,i,被使用，放入,B,i,的物品总负荷不超过,C,；,约束条件（2）表示：每个物品恰好放入一个箱子中,.,第八章 装箱问题,上述装箱问题是这类问题最早被研究的，也是提,法上最简单的问题，称为一维装箱问题,.,但,装箱问题的其他一些提法,：,1、,在装箱时，不仅考虑长度，同时考虑重量或面积、,体积,etc,.,即二维、三维、装箱问题,；,2、对每个箱子的负荷限制不是常数,C,;而是,最优目标可如何提？,3、物品,J,1,，,J,2,，,J,n,的负荷事先并不知道，来货是,随到随装；即 （,On-Line,）装箱问题；,4、由于场地的限制，在同一时间只能允许一定数量的,箱子停留现场可供使用,etc,.,1 装箱问题的描述,BP,的应用举例,：,1、,下料问题,轧钢厂生产的线材一般为同一长度,而用,户所需的线材则可能具有各种不同的尺寸,如何根据用,户提出的要求，用最少的线材截出所需的定货；,2、,二维,BP,玻璃厂生产出长宽一定的大的平板玻璃,但用户所需玻璃的长宽可能有许多差异，如何根据用,户提出的要求，用最少的平板玻璃截出所需的定货,;,3、,计算机的存贮问题,如要把大小不同的共 10,MB,的,文件拷贝到磁盘中去，而每张磁盘的容量为 1.44,MB,已知每个文件的字节数不超过 1.44,MB,而且一个文件,不能分成几部分存贮，如何用最少的磁盘张数完成.,4、,生产流水线的平衡问题,给定流水节拍,C,如何设置,最少的工作站，（按一定的紧前约束）沿着流水线将任,务分配到各工作站上.称为带附加优先约束的,BP,.,BP,是容量限制的工厂选址问题的特例之一.,Go back,第八章 装箱问题,2 装箱问题的最优解值下界,由于,BP,是,NP-C,问题，所以求解考虑 一是尽可能,改进简单的穷举搜索法，减少搜索工作量,.,如:分支,定界法；二是启发式（近似）算法,.,显然,是它的一个最优解.,2 装箱问题的最优解值下界,Theorem,3.1,BP,最优值的一个下界为,表示不小于,a,的最小整数.,Theorem,3.2,设,a,是任意满足 的整数,对,BP,的任一实例 I,记,则,是最优解的一个下界,.,第八章 装箱问题,a,C,C,/2,C-a,I,1,I,2,I,3,Proof,:,仅考虑对,I,1,I,2,I,3,中物品的装箱,.,中物品的长度大于,C,/2,每个物品需单独放入一个箱子，,这就需要 个箱子.,又 中每个物品长度至少为,a,但可能与,I,2,中的,物品共用箱子,，,它不能与,I,1,中的物品共用箱子,与,I,2,中的物品如何？,由于放,I,2,中物品的 个箱子的剩余,总长度为,在最好的情形下，被,I,3,中的物品全部充满，故剩,下总长度 将另外至少 个附加的箱子.,Note:可能小于零,是最优解的一个下界,.,2 装箱问题的最优解值下界,问？,未必！,如,Corollary,3.1,记,则,L,2,是装箱问题的最优解的一个下界，且 .,Proof,:,L,2,为最优解的下界是显然的,.,(,若证明 ，则可得,),当,a,=0 时，是所有物品.,Go back,第八章 装箱问题,3 装箱问题的近似算法,一、,NF,(,Next Fit,)算法,设物品,J,1,，,J,2,，,J,n,的长度分别为,w,1,，,w,2,，,w,n,箱子,B,1,，,B,2,，的长均为,C,，按物品给定的顺序装箱.,先将,J,1,放入,B,1,如果 则将,J,2,放入,B,1,如果 而,则,B,1,已放入,J,1,，,J,2,，,J,j,，将其,关闭,，将,J,j,+1,放入,B,2,.,同法进行，直到所有物品装完为止,.,特点,：,1、按物品给定的顺序装箱,；,2、,关闭原则.,对当前要装的物品,J,i,只关心具有最大下标的已使,用过的箱子,B,j,能否装得下？,能.则,J,i,放入,B,j,；否.关闭,B,j,，,J,i,放入新箱子,B,j,+1,.,计算复杂性为,O,(,n,).,3 装箱问题的近似算法,Example,1,物品,J,1,J,2,J,3,J,4,J,5,J,6,w,j,6,7,4,2,8,3,I,:,C,=10,J,1,J,5,J,6,J,4,J,3,J,2,B,1,B,2,B,3,B,4,B,5,J,1,J,2,J,3,J,4,J,5,J,6,Solution,:,首先，将,J,1,放入,B,1,;,由于,J,2,在,B,1,中放不下,所,以关闭,B,1,将,J,2,放入,B,2,J,3,在,B,2,中放不下(不考虑,B,1,是否能装),所以关闭,B,2,将,J,3,放入,B,3,，,解为,:,其余为零，,第八章 装箱问题,Theorem,3.3,Proof,:,先证,再说明不可改进,设 I 为任一实例，,(要证 ),显然，由 得,反证,如果 ,则 对任意,i,=1,2,k,由于起用第 2,i,个箱子是因为第 2,i,-1 个箱子放不下第2,i,个箱子中第一个物品,因此这两个箱子中物品的总长度,大于,C,，所以前 2,k,个箱子中物品的总长度大于,Ck,.,这与 矛盾.,考虑实例 I:,C,=1,3 装箱问题的近似算法,二、,FF,(,First Fit,)算法,设物品,J,1,，,J,2,，,J,n,的长度分别为,w,1,，,w,2,，,w,n,箱子,B,1,，,B,2,，的长均为,C,，按物品给定的顺序装箱.,物品,J,1,J,2,J,3,J,4,J,5,J,6,w,j,6,7,4,2,8,3,I,:,C,=10,用,NF,算法装,箱,当放入,J,3,时,仅看,B,2,是否能放入，因,B,1,已关闭,参见,EX,.1,但事实上，,B,1,此时是能放得下,J,3,的.,如何修正,NF,算法,先将,J,1,放入,B,1,，若 ,则,J,2,放入,B,1,否,则，,J,2,放入,B,2,;若,J,2,已放入,B,2,，对于,J,3,则依次,检查,B,1,、,B,2,若,B,1,能放得下,则,J,3,放入,B,1,否则查看,B,2,若,B,2,能放得下，则,J,3,放入,B,2,否则启用,B,3,J,3,放入,B,3,.,第八章 装箱问题,一般地，,J,1,，,J,j,已放入,B,1,，,B,i,箱子，对于,J,j,+1,则依次检查,B,1,，,B,2,，,B,i,，将,J,j,+1,放入首先找到的能,放得下的箱子，如果都放不下，则启用箱子,B,i,+1,，将,J,j,+1,放入,B,i,+1,，如此继续，直到所有物品装完为止.,计算复杂性为,O,(,nlogn,).,特点,：,1、按物品给定的顺序装箱,；,2、,对于每个物品,J,j,总是放在能容纳它的具,有最小标号的箱子.,但精度比,NF,算法更高,3 装箱问题的近似算法,Theorem,3.4,Theorem,3.5,对任意实例 I，,而且存在 任意大的实例 I，使,因而,第八章 装箱问题,Example,2,物品,J,1,J,2,J,3,J,4,J,5,J,6,w,j,6,7,4,2,8,3,I,:,C,=10,J,1,J,5,J,6,J,4,J,3,J,2,B,1,B,2,B,3,B,4,B,5,J,1,J,2,J,3,J,4,J,5,J,6,Solution,:,首先，将,J,1,放入,B,1,;,由于,J,2,在,B,1,中放不下,所,以将,J,2,放入,B,2,对于,J,3,先检查,B,1,是否能,容纳下,能.所以将,J,3,放,入,B,1,，,解为,:,其余为零，,3 装箱问题的近似算法,Example,3,物品,J,1,J,2,J,3,J,4,J,5,J,6,w,j,6,7,8,3,2,4,I,:,C,=10,J,1,J,4,J,3,J,2,Solution,:,用,NF,算法,B,1,B,2,B,3,B,4,B,5,J,1,J,2,J,6,J,5,J,3,J,4,B,1,B,2,B,3,B,4,B,5,J,1,J,2,J,6,J,5,J,3,J,4,J,6,J,5,用,FF,算法,参见,EX,.3,用,FF,算法装箱,当放入,J,4,时,B,1,能容纳,J,4,就放入,B,1,，而事实上，放入,B,2,更好.,第八章 装箱问题,三、,BF,(,Best Fit,)算法,与,FF,算法相似，按物品给定的顺序装箱，区别在,于对于每个物品,J,j,是放在一个使得,J,j,放入之后，,B,i,所,剩余长度为最小者.,即在处理,J,j,时，若,B,1,，,B,2,，,B,i,非空，而,B,i+,1,尚,未启用，设,B,1,，,B,2,，,B,i,所余的长度为,若,则将,J,j,放入,B,i,+1,内,;,否则，从 的,B,k,中，选取 一个,B,l,使得,为最小者,.,BF,算法的绝对性能比、计算复杂性与,FF,算法相同,.,Example,4,物品,J,1,J,2,J,3,J,4,J,5,J,6,w,j,6,7,8,3,2,4,I,:,C,=10,3 装箱问题的近似算法,J,1,J,4,J,3,J,2,J,6,J,5,B,1,B,2,B,3,B,4,B,5,J,1,J,2,J,6,J,5,J,3,J,4,Solution,:,用,BF,算法,解为,:,其余为零，,而 此为最优解.,第八章 装箱问题,四、,FFD,(,First Fit Decreasing,)算法,FFD,算法是先将物品按长度从大到小排序，然后用,FF,算法对物品装箱.,该算法的计算复杂性为,O,(,nlogn,).,Example,5,物品,J,1,J,2,J,3,J,4,J,5,J,6,w,j,6,7,4,2,8,3,I,:,C,=10,J,1,J,5,J,6,J,4,J,3,J,2,Solution,:,已知,：,物品,J,5,J,2,J,1,J,3,J,6,J,4,w,j,8,7,6,4,3,2,B,1,B,2,B,3,B,4,B,5,J,1,J,2,J,3,J,4,J,5,J,6,是最优的,.,NFD,算法？,BFD,算法？,3 装箱问题的近似算法,Theorem,3.6,Proof,:,显然对任意实例 I，有,记,首先证明两个结论,：,(1),FFD,算法所用的第 个箱子中每个的,长度不超过,记,w,i,是放入第 个箱子中的第一个物品,只需证,用反证法，若不然，则有 ，因此,FFD,算法中前 个箱子中,每个箱子至多有两个物品.,第八章 装箱问题,可证明存在 使前,k,个恰各含一个物品，后,个箱子各含两个物品,.,因为若不然，则存在两个箱子 使,B,p,有两,个物品,B,q,有一个物品 因物品已从大到,小排列，故 ,因此 从,而可以将,w,i,放入,B,q,中，矛盾.,3 装箱问题的近似算法,因为,FFD,未将,w,k,+1,，,w,i,放入前,k,个箱子，。