文档介绍：第三章装箱问题
§1 装箱问题的描述
§2 装箱问题的最优解值下界
§3 装箱问题的近似算法
库文档分享
第三章装箱问题
装箱问题(Bin Packing)是一个经典的组合优化
问题,有着广泛的应用,在日常生活中也屡见不鲜.
§1 装箱问题的描述
设有许多具有同样结构和负荷的箱子 B1,B2,…
其数量足够供所达到目的之用. 每个箱子的负荷(可为
长度、重量 etc.)为 C ,今有 n 个负荷为 wj,0 < wj < C
j = 1,2,…,n 的物品 J1,J2,…,Jn 需要装入箱内.
装箱问题:
是指寻找一种方法,使得能以最小数量的箱子数将
J1,J2,…,Jn 全部装入箱内.
库文档分享
§1 装箱问题的描述
由于 wi < C,所以 BP 的最优解的箱子数不超过 n .
设
箱子 Bi 被使用
否则
物品 Jj 放入箱子 Bi 中
否则
则装箱问题的整数线性规划模型为:
约束条件(1)表示:一旦箱子 Bi 被使用,放入 Bi
的物品总负荷不超过 C ;
约束条件(2)表示:每个物品恰好放入一个箱子中.
库文档分享
第三章装箱问题
上述装箱问题是这类问题最早被研究的,也是提
法上最简单的问题,称为一维装箱问题. 但
装箱问题的其他一些提法:
1、在装箱时,不仅考虑长度,同时考虑重量或面积、
体积 etc . 即二维、三维、…装箱问题;
2、对每个箱子的负荷限制不是常数 C ; 而是
最优目标可如何提?
3、物品J1,J2,…,Jn 的负荷事先并不知道,来货是
随到随装;即在线(On-Line)装箱问题;
4、由于场地的限制,在同一时间只能允许一定数量的
箱子停留现场可供使用, etc .
库文档分享
§1 装箱问题的描述
BP 的应用举例:
1、下料问题轧钢厂生产的线材一般为同一长度, 而用
户所需的线材则可能具有各种不同的尺寸, 如何根据用
户提出的要求,用最少的线材截出所需的定货;
2、二维 BP 玻璃厂生产出长宽一定的大的平板玻璃,
但用户所需玻璃的长宽可能有许多差异,如何根据用
户提出的要求,用最少的平板玻璃截出所需的定货;
3、计算机的存贮问题如要把大小不同的共 10 MB 的
文件拷贝到磁盘中去,而每张磁盘的容量为 1. 44 MB ,
已知每个文件的字节数不超过 MB , 而且一个文件
不能分成几部分存贮,如何用最少的磁盘张数完成.
4、生产流水线的平衡问题给定流水节拍 C , 如何设置
最少的工作站,(按一定的紧前约束)沿着流水线将任
务分配到各工作站上. 称为带附加优先约束的 BP .
BP 是容量限制的工厂选址问题的特例之一.
Go back
库文档分享
第三章装箱问题
§2 装箱问题的最优解值下界
由于 BP 是 NP-C 问题,所以求解考虑一是尽可能
改进简单的穷举搜索法,减少搜索工作量. 如: 分支
定界法;二是启发式(近似)算法.
显然
是它的一个最优解.
库文档分享
§2 装箱问题的最优解值下界
Theorem
BP 最优值的一个下界为
表示不小于 a 的最小整数.
Theorem
设 a 是任意满足的整数,对 BP 的任一实例 I ,
记
则
是最优解的一个下界.
库文档分享
第三章装箱问题
a
C
C/2
C-a
I1
I2
I3
Proof :
仅考虑对 I1,I2,I3中物品的装箱.
中物品的长度大于C/2 ,
每个物品需单独放入一个箱子,
这就需要个箱子.
又中每个物品长度至少为 a ,
但可能与 I2 中的
物品共用箱子,
它不能与 I1 中的物品共用箱子,
与 I2 中的物品如何?
由于放 I2 中物品的个箱子的剩余
总长度为
在最好的情形下, 被 I3 中的物品全部充满,故剩
下总长度将另外至少个附加的箱子.
Note: 可能小于零
是最优解的一个下界.
库文档分享
§2 装箱问题的最优解值下界
问?
未必!
如
Corollary
记
则 L2 是装箱问题的最优解的一个下界,且.
Proof :
L2 为最优解的下界是显然的.
(若证明,则可得)
当 a = 0 时, 是所有物品.
Go back
库文档分享
第三章装箱问题
§3 装箱问题的近似算法
一、NF ( Next Fit ) 算法
设物品 J1,J2,…,Jn 的长度分别为 w1,w2,…,wn
箱子 B1,B2,…的长均为 C ,按物品给定的顺序装箱.
先将 J1 放入 B1, 如果则将 J2 放入 B1 …
如果而
则 B1 已放入 J1,J2,…,Jj,将其关闭,