文档介绍：binatorialOptimizationinInformationProcessing渭增臣襟仙苍妓柿附哉俐忆街龟伴古汗均欧印尧闭帮勒育脐将髓敛蒲仓摇第三章_装箱问题第三章_装箱问题第三章装箱问题§1装箱问题的描述§2装箱问题的最优解值下界§3装箱问题的近似算法隐特顷谚萄蹦狞透谆烛慨黔血骗盟啼刁扼爹踪谚协礼嗓沮啊阵零恐拖广换第三章_装箱问题第三章_装箱问题第三章装箱问题装箱问题(BinPacking)是一个经典的组合优化问题,有着广泛的应用,在日常生活中也屡见不鲜.§1装箱问题的描述设有许多具有同样结构和负荷的箱子B1,B2,…(可为长度、重量etc.)为C,今有n个负荷为wj,0<wj<Cj=1,2,…,n的物品J1,J2,…,:是指寻找一种方法,使得能以最小数量的箱子数将J1,J2,…,§1装箱问题的描述由于wi<C,:约束条件(1)表示:一旦箱子Bi被使用,放入Bi的物品总负荷不超过C;约束条件(2)表示:,也是提法上最简单的问题,:1、在装箱时,不仅考虑长度,同时考虑重量或面积、、三维、…装箱问题;2、对每个箱子的负荷限制不是常数C;而是最优目标可如何提?3、物品J1,J2,…,Jn的负荷事先并不知道,来货是随到随装;即在线(On-Line)装箱问题;4、由于场地的限制,在同一时间只能允许一定数量的箱子停留现场可供使用,§1装箱问题的描述BP的应用举例:1、下料问题轧钢厂生产的线材一般为同一长度,而用户所需的线材则可能具有各种不同的尺寸,如何根据用户提出的要求,用最少的线材截出所需的定货;2、二维BP玻璃厂生产出长宽一定的大的平板玻璃,但用户所需玻璃的长宽可能有许多差异,如何根据用户提出的要求,用最少的平板玻璃截出所需的定货;3、计算机的存贮问题如要把大小不同的共10MB的文件拷贝到磁盘中去,,,而且一个文件不能分成几部分存贮,、生产流水线的平衡问题给定流水节拍C,如何设置最少的工作站,(按一定的紧前约束)§2装箱问题的最优解值下界由于BP是NP-C问题,所以求解考虑一是尽可能改进简单的穷举搜索法,:分支定界法;二是启发式(近似)§,对BP的任一实例I,记则是最优解的一个下界./2C-aI1I2I3Proof:仅考虑对I1,I2,,每个物品需单独放入一个箱子,,但可能与I2中的物品共用箱子,它不能与I1中的物品共用箱子,与I2中的物品如何?由于放I2中物品的个箱子的剩余总长度为在最好的情形下,被I3中的物品全部充满,:§2装箱问题的最优解值下界问?未必!,:L2为最优解的下界是显然的.(若证明,则可得)当a=0时,