文档介绍：第三章第三章装箱问题装箱问题信息处理中的组合优化第三章装箱问题§§1 1 装箱问题的描述装箱问题的描述§§2 2 装箱问题的最优解值下界装箱问题的最优解值下界§§3 3 装箱问题的近似算法装箱问题的近似算法第三章第三章装箱问题装箱问题装箱问题(Bin Packing)是一个经典的组合优化问题,有着广泛的应用,在日常生活中也屡见不鲜.§§1 1 装箱问题的描述装箱问题的描述设有许多具有同样结构和负荷的箱子B1,B2,…其数量足够供所达到目的之用. 每个箱子的负荷(可为长度、重量etc.)为C ,今有n个负荷为wj,0 < wj < C j = 1,2,…,n 的物品J1,J2,…,:装箱问题:是指寻找一种方法,使得能以最小数量的箱子数将J1,J2,…,Jn全部装入箱内..§1 装箱问题的描述由于wi < C,所以BP的最优解的箱子数不超过n . .设11 ;0iy i n?? ???箱子Bi被使用否则1, 1 .0ijx i j n?? ???物品Jj放入箱子Bi中否则则装箱问题的整数线性规划模型为:1minniiz y???1. . 1 (1)nj ij ijs t w x Cy i n?? ??0 1, 0 1 , 1 .i ijy or x or i j n? ? ?( )BP约束条件(1)表示:一旦箱子Bi 被使用,放入Bi的物品总负荷不超过C ;约束条件(2)表示: (2)nijix???1j n?第三章装箱问题上述装箱问题是这类问题最早被研究的,也是提法上最简单的问题,称为一维装箱问题. . NP C? ?装箱问题的其他一些提法:1、在装箱时,不仅考虑长度,同时考虑重量或面积、体积etc . 即二维、三维、…装箱问题;2、对每个箱子的负荷限制不是常数C ; 而是, 1 .iC i n?最优目标可如何提?3、物品J1,J2,…,Jn的负荷事先并不知道,来货是随到随装;即在线(On-Line)装箱问题;4、由于场地的限制,在同一时间只能允许一定数量的箱子停留现场可供使用, etc .§1 装箱问题的描述BP的应用举例:1、下料问题轧钢厂生产的线材一般为同一长度, 而用户所需的线材则可能具有各种不同的尺寸, 如何根据用户提出的要求,用最少的线材截出所需的定货;2、二维BP玻璃厂生产出长宽一定的大的平板玻璃,但用户所需玻璃的长宽可能有许多差异,如何根据用户提出的要求,用最少的平板玻璃截出所需的定货;3、计算机的存贮问题如要把大小不同的共10 MB 的文件拷贝到磁盘中去,而每张磁盘的容量为1. 44 MB , MB , 而且一个文件不能分成几部分存贮, 7 10? ? ?4、生产流水线的平衡问题给定流水节拍C , 如何设置最少的工作站,(按一定的紧前约束)沿着流水线将任务分配到各工作站上. 称为带附加优先约束的BP . back第三章装箱问题§§2 2 装箱问题的最优解值下界装箱问题的最优解值下界由于BP是NP-C 问题,所以求解考虑一是尽可能改进简单的穷举搜索法,减少搜索工作量. 如: 分支定界法;二是启发式(近似) y???1. . 1 (1)nj ij ijs t w x Cy i n?? ??0 1, 0 1 , 1 .i ijy or x or i j n? ? ?( )BP0 1, 0 1 , 1 .i ijy x i j n? ????( )C BP显然是它的一个最优解. 1, 0 ( ), , , 1 .iii ij iwx x i j y i j nC? ????1niioptwzC???11 (2)nijix?