一维下料问题的优化算法研究

摘要

一维下料问题广泛的存在于制造、建筑等行业中,如何提高材料利用率,降低成本,是相关企业关注的焦点。一维下料优化问题是指条形原材料数量若干,需要切割成多种规格的零件,每种零件数量若干,如何使得原材料的利用率高,废料少的问题。一维下料问题是一个经典的组合优化问题,属于NP难问题。因此研究一维下料问题具有重要意义。
　　本文根据原材料的类型将问题分为单一规格原材料一维下料问题和多规格原材料一维下料问题。针对原材料长度大于零件长度的情况,分别采用了不同的求解方法解决小规模下料和大规模下料问题。此外,本文还考虑了实际生产中存在的原材料长度小于零件长度的情况,并予以分析和计算。
　　针对小规模一维下料问题利用启发式算法求解。首先计算出所有可行的切割方式,然后根据约束条件搜索出有效的切割方式,并保证最后一根原材料的余料长度最长,最后组合这些有效的切割方式即为问题的解。针对大规模一维下料问题运用遗传算法求解。设计基于定长的实数编码,对不符合约束条件的个体提出一种惩罚策略,保证最后所得解的可行性,取得了较好的结果。

目录

封面

声明

中文摘要

英文摘要

目录

1 绪 论

1.1课题研究背景介绍

1.2一维下料问题的求解难点

1.3国内外研究现状

1.4 求解一维下料问题的几种常见的方法

1.4.1 线性规划的方法

1.4.2 启发式方法

1.4.3 遗传算法

1.4.4其他方法

1.5论文的主要工作和结构安排

2 一维下料问题的数学模型

2.1单一规格原材料一维下料问题的数学模型

2.2多规格原材料一维下料问题的数学模型

2.3本章小结

3.1启发式算法

3.2切割方式的计算方法

3.3实例计算与分析

3.3.1小规模一维下料问题

3.3.2大规模一维下料问题

3.4本章小结

4一维下料问题的遗传算法

4.1定长编码的遗传算法

4.2实例计算与分析

4.2.1小规模一维下料问题的遗传算法

4.2.2大规模一维下料问题的遗传算法

4.3本章小结

5 总结与展望

5.1总结

5.2展望

致谢

参考文献

附录1（攻读硕士学位期间发表论文目录）