数学建模装箱问题PPT课件

1、第八章第八章 装箱问题装箱问题第1页/共33页 装箱问题（Bin Packing）是一个经典的组合优化问题，有着广泛的应用，在日常生活中也屡见不鲜 . 设有许多具有同样结构和负荷的箱子 B1，B2，其数量足够供所达到目的之用 . 每个箱子的负荷（可为长度、重量 etc.）为 C ,今有 n 个负荷为 wj，0 wj C j = 1，2，n 的物品 J1，J2，Jn 需要装入箱内. 是指寻找一种方法，使得能以最小数量的箱子数将J1，J2，Jn 全部装入箱内第2页/共33页1 装箱问题的描述由于 wi C，所以 BP 的最优解的箱子数不超过 n设11;0iyin箱子 Bi 被使用否则1,1.0ij

2、xi jn物品 Jj 放入箱子 Bi 中否则则装箱问题的整数线性规划模型为：1minniizy1. .1(1)njijijstw xCyin01,01,1.iijyorxori jn ()BP约束条件（1）表示：一旦箱子 Bi 被使用，放入 Bi 的物品总负荷不超过 C ；约束条件（2）表示：每个物品恰好放入一个箱子中 .11(2)nijix1jn 第3页/共33页第八章 装箱问题 上述装箱问题是这类问题最早被研究的，也是提法上最简单的问题，称为一维装箱问题但.BPNP C装箱问题的其他一些提法：1、在装箱时，不仅考虑长度，同时考虑重量或面积、 体积 etc . 即二维、三维、装箱问题；2、对

3、每个箱子的负荷限制不是常数 C ; 而是,1.iCin 最优目标可如何提？3、物品J1，J2，Jn 的负荷事先并不知道，来货是 随到随装；即 在线（On-Line）装箱问题；4、由于场地的限制，在同一时间只能允许一定数量的 箱子停留现场可供使用, etc .第4页/共33页1 装箱问题的描述BP 的应用举例：1、下料问题 轧钢厂生产的线材一般为同一长度, 而用户所需的线材则可能具有各种不同的尺寸, 如何根据用户提出的要求，用最少的线材截出所需的定货；2、 二维 BP 玻璃厂生产出长宽一定的大的平板玻璃,但用户所需玻璃的长宽可能有许多差异，如何根据用户提出的要求，用最少的平板玻璃截出所需的定货;

4、3、计算机的存贮问题 如要把大小不同的共 10 MB 的文件拷贝到磁盘中去，而每张磁盘的容量为 1. 44 MB ,已知每个文件的字节数不超过 1.44 MB , 而且一个文件不能分成几部分存贮，如何用最少的磁盘张数完成 .1.44 710.08104、生产流水线的平衡问题 给定流水节拍 C , 如何设置最少的工作站，（按一定的紧前约束）沿着流水线将任务分配到各工作站上 . 称为带附加优先约束的 BP . BP 是容量限制的工厂选址问题的特例之一.Go back第5页/共33页第八章 装箱问题由于 BP 是 NP-C 问题，所以求解考虑 一是尽可能改进简单的穷举搜索法，减少搜索工作量 . 如:

5、 分支定界法；二是启发式（近似）算法 .1minniizy1. .1(1)njijijstw xCyin01,01,1.iijyorxori jn ()BP01, 01,1.iijyxi jn()C BP 显然 是它的一个最优解 . 1,0 (),1.iiiijiwxxijyi jnC 1niioptwzC11(2)nijix1jn 第6页/共33页2 装箱问题的最优解值下界Theorem 3.1BP 最优值的一个下界为11.niiwLCa 表示不小于 a 的最小整数.Theorem 3.2 设 a 是任意满足 的整数,对 BP 的任一实例 I ,02Ca记1,jIj wCa物品2,2jCIj

6、 Caw物品3,2jCIjwa物品则32212()( )max 0,jjj Ij IwI CwL aIIC是最优解的一个下界第7页/共33页第八章 装箱问题aCC/2C-aI1I2I3Proof :仅考虑对 I1,I2,I3中物品的装箱 .中物品的长度大于C/2 ,12II每个物品需单独放入一个箱子，这就需要 个箱子 .12II又 中每个物品长度至少为 a ,3I 但可能与 I2 中的物品共用箱子，它不能与 I1 中的物品共用箱子,与 I2 中的物品如何？ 由于放 I2 中物品的 个箱子的剩余总长度为 2I22jj ICI Cw 在最好的情形下， 被 I3 中的物品全部充满，故剩下总长度 将另

7、外至少 个附加的箱子 .C3jjIwwCwCNote: 可能小于零w32212()( )max 0,jjj Ij IwI CwL aIIC是最优解的一个下界 .第8页/共33页2 装箱问题的最优解值下界问 ？1( )L aL未必！(,1)jwajn 如Corollary 3.1记2max( ) 0,2CLL aaa为整数则 L2 是装箱问题的最优解的一个下界，且 .21LLProof :L2 为最优解的下界是显然的 .若证明 ，则可得1(0)LL21LL32212()( )max 0,jjj Ij IwI CwL aIIC当 a = 0 时， 是所有物品 .123,III 212()(0)0m

8、ax 0,njjwI CLIC212max 0,ILI21max,IL1L21(0)LLLGo back第9页/共33页第八章 装箱问题一、NF ( Next Fit ) 算法 设物品 J1，J2,，Jn 的长度分别为 w1，w2,，wn箱子 B1，B2，的长均为 C ，按物品给定的顺序装箱 . 先将 J1 放入 B1, 如果 则将 J2 放入 B1 12wwC如果 而12121jjjwwwCwwwwC则 B1 已放入 J1，J2,，Jj，将其关闭，将 Jj+1 放入 B2 .同法进行，直到所有物品装完为止 .特点：1、按物品给定的顺序装箱；2、关闭原则 . 对当前要装的物品 Ji 只关心具有

9、最大下标的已使用过的箱子 Bj 能否装得下？能. 则 Ji 放入 Bj ；否 . 关闭 Bj ，Ji 放入新箱子 Bj+1 .计算复杂性为 O(n).第10页/共33页3 装箱问题的近似算法Example 1物品物品J1J2J3J4J5J6wj674283I : C = 10J1J5J6J4J3J2B1B2B3B4B5J1J2J3J4J5J6Solution :首先，将 J1 放入 B1由于 J2 在 B1 中放不下, 所以关闭 B1 , 将 J2 放入 B2 ,J3 在 B2 中放不下(不考虑B1 是否能装), 所以关闭 B2将 J3 放入 B3，解为:1122333445561xxxxxx

10、其余为零，( )5.NFzI 第11页/共33页第八章 装箱问题Theorem 3.32NFRProof :先证再说明不可改进2NFR设 I 为任一实例，( ).optzIk(要证 )( )2NFzIk显然，由 得1( )niioptwkzIC1niiwCk反证如果 ,( )2NFzIk则 对任意 i = 1, 2, k由于起用第 2i 个箱子是因为第 2i -1 个箱子放不下第2i个箱子中第一个物品,因此这两个箱子中物品的总长度大于 C ，所以前 2k 个箱子中物品的总长度大于 Ck .这与 矛盾 .1niiwCk( )2,2.( )NFNFoptzIRzI从而考虑实例 I : C = 1,

11、124111111,2 22 22 2Nw wwNNN( )1( )2optNFzINzIN易证( )22 ()2( )1NFNFoptzINNRzIN 得第12页/共33页3 装箱问题的近似算法二、FF ( First Fit ) 算法 设物品 J1，J2,，Jn 的长度分别为 w1，w2,，wn箱子 B1，B2，的长均为 C ，按物品给定的顺序装箱 .物品物品J1J2J3J4J5J6wj674283I : C = 10 用 NF 算法装箱, 当放入 J3 时, 仅看 B2是否能放入，因 B1 已关闭,参见 EX .1但事实上，B1 此时是能放得下 J3 的 .如何修正 NF 算法先将 J1

12、 放入 B1，若 ,12wwC则 J2 放入 B1 , 否则，J2 放入 B2 ; 若 J2 已放入 B2，对于 J3 则依次检查B1、B2 , 若 B1 能放得下, 则 J3 放入 B1 , 否则查看 B2 , 若 B2 能放得下，则 J3 放入 B2 , 否则启用 B3, J3 放入 B3.第13页/共33页第八章 装箱问题 一般地，J1,，Jj 已放入 B1,，Bi 箱子，对于 Jj+1,则依次检查 B1，B2,，Bi，将 Jj+1 放入首先找到的能放得下的箱子，如果都放不下，则启用箱子 Bi+1 ，将 Jj+1 放入 Bi+1 ，如此继续，直到所有物品装完为止 . 计算复杂性为 O(n

13、logn).特点：1、按物品给定的顺序装箱；2、对于每个物品 Jj 总是放在能容纳它的具 有最小标号的箱子 .但精度比NF 算法更高第14页/共33页3 装箱问题的近似算法Theorem 3.4( )7.( )4FFoptzIzITheorem 3.5对任意实例 I ，17( )( ) 110FFoptzIzI而且存在 任意大的实例 I ，使( )optzI17( )( ) 1)10FFoptzIzI因而17.10FFR717141020第15页/共33页第八章 装箱问题Example 2物品物品J1J2J3J4J5J6wj674283I : C = 10J1J5J6J4J3J2B1B2B3B

14、4B5J1J2J3J4J5J6Solution :首先，将 J1 放入 B1由于 J2 在 B1 中放不下, 所以将 J2 放入 B2 , 对于 J3 , 先检查 B1 是否能容纳下, 能 . 所以将 J3 放入 B1，解为:1122132435461xxxxxx其余为零，( )4.FFzI 第16页/共33页3 装箱问题的近似算法Example 3物品物品J1J2J3J4J5J6wj678324I : C = 10J1J4J3J2Solution :用 NF 算法B1B2B3B4B5J1J2J6J5J3J4B1B2B3B4B5J1J2J6J5J3J4J6J5( )4NFzI 用 FF 算法(

15、 )4FFzI 参见 EX .3 用 FF 算法装箱, 当放入 J4 时, B1 能容纳J4 就放入 B1 ，而事实上，放入 B2 更好 .第17页/共33页第八章 装箱问题三、BF ( Best Fit ) 算法 与 FF 算法相似，按物品给定的顺序装箱，区别在于对于每个物品 Jj 是放在一个使得 Jj 放入之后，Bi 所剩余长度为最小者 . 即在处理 Jj 时，若 B1，B2,，Bi 非空，而 Bi+1 尚未启用，设 B1，B2,，Bi所余的长度为12,iwww若1maxjkk iww 则将 Jj 放入 Bi+1 内;否则，从 的 Bk 中，选取 一个 Bl jkww(1)li 使得为最小

16、者min()kjljkjwwwwwwBF 算法的绝对性能比、计算复杂性与 FF 算法相同 .第18页/共33页Example 4物品物品J1J2J3J4J5J6wj678324I : C = 103 装箱问题的近似算法J1J4J3J2J6J5B1B2B3B4B5J1J2J6J5J3J4Solution :用 BF 算法解为:1122332435161xxxxxx其余为零，( )3.BFzI 611310jjwL1( ),BFzIL第19页/共33页第八章 装箱问题四、FFD ( First Fit Decreasing ) 算法FFD 算法是先将物品按长度从大到小排序，然后用FF 算法对物品装

17、箱 .该算法的计算复杂性为 O(nlogn).Example 5物品物品J1J2J3J4J5J6wj674283I : C = 10J1J5J6J4J3J2Solution :已知：( )4FFzI 物品物品J5J2J1J3J6J4wj876432B1B2B3B4B5J1J2J3J4J5J6( )3FFDzI 是最优的NFD 算法？ BFD 算法？第20页/共33页3 装箱问题的近似算法Theorem 3.63( ).2FFDRI Proof :显然对任意实例 I ，有( )( )FFDoptzIzI记*( )( )FFDoptzIlzIl首先证明两个结论：(1) FFD 算法所用的第 个箱子

18、中每个的长度不超过*1,2,.,lll;3C记 wi 是放入第 个箱子中的第一个物品,只需证*1l 3iCw 用反证法，若不然，则有 ，因此 FFD11,.,3iCww算法中前 个箱子中, 每个箱子至多有两个物品 .*l第21页/共33页C3C23C第八章 装箱问题 可证明存在 使前 k 个恰各含一个物品，后 个箱子各含两个物品0k *lk 因为若不然，则存在两个箱子 使 Bp有两个物品 , Bq 有一个物品 因物品已从大到小排列，故 , 因此 从而可以将wi 放入 Bq 中，矛盾.,pqBBpq1221,()ttw wtt3tw132,tttiwwww123.tttiCwwww第22页/共3

19、3页3 装箱问题的近似算法 因为 FFD 未将 wk+1,，wi 放入前 k 个箱子，说明其中任一个箱子已放不下, 故在最优解中也至少有 k 个箱子不含 wk+1,，wi中任一个物品 . 假设就是前 k 个箱子，因此在最优解中， wk+1,，wi-1也会两两放入第个箱子中，且因为这些物品长度大于 , 所以*1,.,kl3C每个箱子中只有两个物品，且 已放不下 . 但最优解中 wi 必须放入前 个箱子中，矛盾. 故3iCw *l.3iCw (2) FFD 算法放入第 个箱子中物品数不超过*1,.,ll*1l *1,niiwl C而如果至少有 个物品放入第*l*1,.,ll个箱子中，记前 个物品的

20、长度为 .*1,.,laa*l第23页/共33页第八章 装箱问题记 FFD 算法中前 个箱子中每个箱子物品总长为 *l*,1jbjl 显然，对任意*1,jjjlbaC否则长为 的物品可放入第 j 个箱子中，因此ja*1111()nllljjjjjjjjjwbabal C矛盾 .所以 (2) 结论成立 . 由(1)、(2) 知FFD 算法比最优算法多用的箱子是用来放至多 个物品，而每个物品长不超过 ，因此*1l 3C第24页/共33页3 装箱问题的近似算法( ) 1( )( ) 13( )411( )( )3( )33( )optoptoptFFDoptoptoptoptzIzIzIzIzIzI

21、zIzI 因此因为 如果 ，则 ，故不妨设 ( )1optzI ( )1FFDzI ( )2optzI ( )413( )362FFDoptzIzI考虑实例 I ：物品集长度为 , C 为箱长. ,233344C C C C C C( )2,( )3optFFDzIzI说明 是不可改进的 .32第25页/共33页第八章 装箱问题 比较 NF 算法、FF ( BF ) 算法、FFD 算法，它们的近似程度一个比一个好，但这并不是说 NF、FF(BF)就失去了使用价值 .1、FF(BF)、FFD 算法都要将所有物品全部装好后 , 所有箱子才能一起运走，而 NF 算法无此限制，很适合装箱场地小的情形；

22、FFD 算法要求所有物品全部到达后才开始装箱, 而 NF、FF(BF) 算法在给某一物品装箱时，可以不知道下一个物品的长度如何，适合在线装箱第26页/共33页存储罐注液问题第八章 装箱问题 某化工厂有 9 个不同大小的存储罐，有一些已经装某液体 . 现新到一批液体化工原料需要存储，这些液体不能混合存储，它们分别是 1200 m3 苯，700 m3 丁醇，1000 m3 丙醇，450 m3 苯乙醇和1200 m3 四氢呋喃 . 下表列出每个存储罐的属性(单位: m3), 问应如何将新到的液体原料装罐, 才能使保留未用的存储罐个数最多?存储罐编号存储罐编号123456789容容 量量5004004

23、00600600900800800800当前内容当前内容-苯苯-四氢呋喃四氢呋喃-体体 积积100300第27页/共33页第八章 装箱问题Solution :存储罐编号存储罐编号123456789容容 量量500400400600600900800800800当前内容当前内容-苯苯-四氢呋喃四氢呋喃-体体 积积100300 分别记苯、丁醇、丙醇、苯乙醇、四氢呋喃为第1，2，3，4，5种液体 . 显然，新到液体应尽可能装入已存有此种液体的罐中 . 所以余下液体为：900 m3 苯，700 m3 丁醇，1000 m3 丙醇，450 m3 乙醇和700 m3 四氢呋喃 . 剩余空罐为1，3，4，5，6，8，9 . 由于不允许混合，每种液体至少需要1个空罐 .令10ijx第 i 种液体装入第 j 个存储罐否则记第 j 个空罐的容量