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