一维多线材下料问题的算法研究与实验

论文摘要

现今,切割下料问题广泛地存在于国民的经济生产中。一维多线材下料问题指一种以上不同尺寸的原材料和所需毛坯的维数都是一维时,在已知供应条件的情况下,考虑如何切割下料,不仅能满足毛坯的需求,而且能最大限度的提高材料利用率。在钢材、合金型金属线材等工业生产领域中,优化的下料方案将为企业降低生产成本,提高效益。随着科学技术的快速发展和计算机技术的日益普及,越来越多的成熟的研究技术和方法被应用到解决切割下料问题的过程中。因此,对该问题求解方法的研究不管是在理论上还是在实际应用中都具有非常重要的意义。本篇论文针对现有线性规划方法的不足,对顺序法,差值法和比值法等联合解法应用于线性规划方法进行了研究,讨论了各方法的实现步骤,并通过实验,对多种实施策略进行了比较,为实际应用开发提供实验依据。特别是通过差值法和比值法的应用,使得改进后的一维多线材切割系统中,能够有效的提高计算效率,缩短计算时间。实验研究结果表明,与目前常用的传统算法相比较,差值法和比值法有计算速度快的优点。本文主要的研究方法如下：首先,针对所研究的问题建立求解一维多线材下料问题的数学模型。在此基础之上,介绍所使用算法的基本思想以及实现原理。本文所讨论的是基于线性规划的一维多线材优化切割联合算法。该算法是在线性规划算法的基础之上改进而来的。基本思想是使用单纯形法前,对排样方式进行选择。其次,基于最优排样方式的数学模型,来求解背包问题,生成不同长度的线材上各自价值最大的排样方式。顺序法,差值法和比值法根据各自不同的策略,选择较好的排样方式作为换入基。其中,比值法的方法是用排样方式的价值除以所使用的线材的长度,取比值最大值,并将对应的排样方式作为换入基,带入单纯形法进行迭代。这样就保证了最有意义的排样方式最先被换入,从而减少了总的换入次数,在保证取到最优解的同时缩短了计算时间。最后,针对实际的需要,确定下料系统的基本功能模块,开发出基于线性规划算法的一维多线材优化下料系统,并对其界面进行整合、规划,使其更加美观和人性化。在系统上实现各联合解法的基础之上,通过大量的实验数据的测试,将各个测试的结果进行相互对比和分析,结果表明,在材料利用率都达到最优时,比值法的运行时间较其他算法有较大幅度的减少,是一种有效的求解一维下料问题的算法。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 引言
• 1.2 研究的目的和意义
• 1.3 国内外研究的现状
• 1.4 本文的主要工作
• 1.5 论文的结构安排
• 第二章 一维下料问题的数学模型
• 2.1 下料问题的类型
• 2.2 下料方案及排样方式
• 2.3 一维下料问题的数学描述
• 2.4 常规线性规划求解方法
• 2.4.1 常规线性规划模型
• 2.4.2 延迟列生成方法
• 2.5 启发式算法
• 2.5.1 启发式多级序列线性优化算法
• 2.6 基于遗传算法的求解方法
• 2.6.1 遗传算法的原理和求解过程
• 2.6.2 遗传算法的优点和缺点
• 第三章 基于线性规划的联合解法
• 3.1 多线材下料问题的数学模型及其求解方法
• 3.2 分离式的延迟列生成法
• 3.3 综合式的延迟列生成法
• 3.3.1 顺序法
• 3.3.2 差值法
• 3.3.3 比值法
• 3.4 联合解法的求解方法
• 3.5 算法的实施
• 3.5.1 算法结束的准则
• 3.5.2 对线性规划解的取整的策略
• 3.5.3 算法的内容与流程图
• 第四章 一维优化下料系统的研制与实验计算
• 4.1 一维多线材下料系统的研制
• 4.2 一维多线材下料系统的实现
• 4.2.1 数据输入模块
• 4.2.2 优化计算模块
• 4.2.3 图形输出模块
• 4.3 实验计算
• 4.3.1 第一组算例
• 4.3.2 第二组算例
• 4.3.3 第三组算例
• 4.3.4 第四组算例
• 4.4 实验结果分析
• 第五章 总结与展望
• 参考文献
• 攻读全日制工程硕士学位期间发表的论文
• 附录1 常用符号说明
• 附录2 实验数据
• 致谢