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

《一维装箱问题典型算法.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、第三章装箱问题信息处理中的组合优化CombinatorialOptimizationinInformationProcessing第三章装箱问题§1装箱问题的描述§2装箱问题的最优解值下界§3装箱问题的近似算法第三章装箱问题装箱问题（BinPacking）是一个经典的组合优化问题，有着广泛的应用，在日常生活中也屡见不鲜.§1装箱问题的描述设有许多具有同样结构和负荷的箱子B1，B2，…其数量足够供所达到目的之用.每个箱子的负荷（可为长度、重量etc.）为C,今有n个负荷为wj，0

2、题：是指寻找一种方法，使得能以最小数量的箱子数将J1，J2，…，Jn全部装入箱内.§1装箱问题的描述由于wi

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

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

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

6、箱子.Note:可能小于零是最优解的一个下界.§2装箱问题的最优解值下界问？未必！如Corollary3.1记则L2是装箱问题的最优解的一个下界，且.Proof:L2为最优解的下界是显然的.(若证明，则可得)当a=0时，是所有物品.Goback第三章装箱问题§3装箱问题的近似算法一、NF(NextFit)算法设物品J1，J2,…，Jn的长度分别为w1，w2,…，wn箱子B1，B2，…的长均为C，按物品给定的顺序装箱.先将J1放入B1,如果则将J2放入B1…如果而则B1已放入J1，J2,…，Jj，将其关闭，将Jj+1放入B2.同法进行，直到所有物品装完

7、为止.特点：1、按物品给定的顺序装箱；2、关闭原则.对当前要装的物品Ji只关心具有最大下标的已使用过的箱子Bj能否装得下？能.则Ji放入Bj；否.关闭Bj，Ji放入新箱子Bj+1.计算复杂性为O(n).§3装箱问题的近似算法Example1物品J1J2J3J4J5J6wj674283I:C=10J1J5J6J4J3J2B1B2B3B4B5J1J2J3J4J5J6Solution:首先，将J1放入B1;由于J2在B1中放不下,所以关闭B1,将J2放入B2,J3在B2中放不下(不考虑B1是否能装),所以关闭B2将J3放入B3，…解为:其余为零，第三章装箱

8、问题Theorem3.3Proof:先证再说明不可改进设I为任一实例，(要证)显然，由得反证如果,则对任意i