文档介绍：该【数学建模 - 装箱问题公开课一等奖课件赛课获奖课件 】是由【书犹药也】上传分享，文档一共【33】页，该文档可以免费在线阅读，需要了解更多关于【数学建模 - 装箱问题公开课一等奖课件赛课获奖课件 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。第八章 装箱问题
组合优化理论
Combinatorial
Optimization Theory
第八章 装箱问题
§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