分支定界算法优化一维下料问题.pdfVIP

Vol. 8　No. 11　 June 2008 第 8卷 　第 11期 　2008年 6月 科 　学 　技 　术 　与 　工 　程 　 (2008) Science Technology and Engineering 　2008　Sci. Tech. Engng. 分支定界算法优化一维下料问题 秦平平 　刘 　文 　王兴华 (燕山大学 理学院 , 秦皇岛 066004) 摘 　要 　一维下料问题是生产实践中常见的问题 ,优化下料要求最大限度地节约原材料 ,提高原材料的利用率 。本文提出分 支定界算法优化一维下料问题 ,并用 MA TLAB 编写程序 ,通过计算机来完成这一复杂的过程 。 关键词 　一维下料问题 　　分支定界算法 　　ILp 函数 中图法分类号 　O22 14; 　　　　文献标志码 　A 　　“下料问题 ”是把相同形状的原材料分割加工 成若干不同规格大小的零件的问题 ,其中需求零件 1　一维优化下料问题的具体模型分析 的宽度相等的情况称为一维下料 问题 。此类 问题 在工程技术和工业生产中有着重要和广泛的应用 。 原材 料 长 度 为 L , 数 量 充 足 。需要 切 割 成 在很多生产部门中 , 为了提高原材料利用率 , 降低 ( ) n n ≥0 种不同规格的零件 ,根据既省材料又容易 生产成本 ,在给定长度的原材料上 ,要求消耗尽可 操作的原则 ,人们已经设计好了 n 种不同的下料方 能少的原材料数量 , 切割出不 同数量和规格 的零 式 。设第 j 种下料方式中可下得第 i种零件 aij 个 , 件 。当零件数量较少时 , 可用人工方法解决 , 当零 又已知第 i种零件得需要量为 b 个 , x 表示第 B 种 i j j 件数量较多时 ,用人工方法对原材料利用率不是很 下料方式所消耗得零件数 目, c 表示第 B 种下料方 j j 高 ,会造成资源大量浪费 , 导致生产成本上升 。因 + ( ) 式所得余料 j = 1, 2 , …, n , xj ∈Z 。 此最大限度地节约原材料 ,提