首页 >
论文范文 >
自然科学论文 >
数学论文 >
运筹学论文 >
木板排样优化中整数线性规划模型的应用
摘要：目前,大多数工业生产过程中主要使用人工神经网络算法以及模拟退火等现代化算法来分割木材。而在实际排样过程中,使用单一的算法往往得不到最优方案。故本文根据不同排样问题的复杂程度,建立整数线性规划模型、木板排样优化模型,运用遗传算法,并利用Matlab、C++进行编程求解,得出不同生产条件下板材的最优分割方案和最大利用率,易与实际生产联系紧密。
加入收藏
1、概述
在实际工程技术与工业生产中，将较大的矩形板材分割为若干个不同类型矩形零件的问题，对机器设备的制造成本以及生产周期有着非常深远的影响。如何使板材的利用率最大化，是一个好的切割方案首先要解决的问题。板材优化问题就是规划原材料与每个零件的最优布局问题，使板材余料尽可能的减少，从而减少资源浪费，降低成本，提高经济效益。
2、问题分析
在解决板材分割问题时，首先要建立木板排样优化模型，寻求木板切割的最优方案，再利用整数线性规划模型做出进一步的划分，得到目标函数方程及约束条件组，运用Matlab进行编程求解，即可求解出简单的木板分割问题。为了简化计算的复杂，我们假设木板的长、宽、生产任务等均为整数。
对于更复杂的问题，如目标产品种类过多，在这种情况下，通过整数线性规划很难求出最优解，故本文引进了遗传算法来计算木板的最大利用率，并采用整数编码的方式来解决木板排样问题。另外，在解决切割多种目标产品问题时，本文引进了一个新的概念—重要度。根据每块木板上产品最多可切割的数量，得出各产品的重要度，每次进行板材切割时，按照板材的重要度依次切割，重要度靠前的板材尽可能多的切割，从而简化问题的复杂程度。
3、算法设计
在算法设计过程中，不考虑木板厚度的影响，仅以长宽作为考量标准，并忽略切割时，因技术带来的余料损失的误差。假设木板分割方式均是按照横向切割(沿木板长的方向)和纵向分割(沿木板宽的方向)，不考虑其他切割方式。如在木板A切割产品x，由数学排列组合知识可得四种切割方式，分别如下图所示。其中(1)(2)对A进行横向切割，x分别纵向和横向放置;(3)(4)对A的进行纵向切割，x分别纵向和横向放置。
四种分割方式图
四种分割方式图下载原图
确定了木板切割的四种方式后，将系统的阐述如何得到木板排样的最优方案。首先，建立木板排样优化模型。假设有相同长度和宽度的一批矩形样品P1，其面积集合为为{Ki};另外有与原木板相同长度和宽度的一批木板Si，其面积集合为{Qj}。木板的排样其实就是将这批样品P1适当地放在木板Si上。所谓的木板排样模型就是寻找最合理的放置方式从而获得木板的最大利用率。使目标函数获得最大值:
其次，建立整数线性规划模型。整数线性规划模型是指通过线性约束条件组下，求出线性目标函数最值的一种模型。对于大部分木板切割问题，需要依据实际问题得到目标函数方程和约束条件。再依据整数线性规划的方程，运用Matlab或Lingo进行编程求解，求解出木板分割的最大利润率。
当木板切割的目标产品种类繁多，并对各类产品的生产量都有明确的要求时，需要引入适应度函数。适应度函数主要用于产品分割方案的评价，同时也是优化过程中的一个重要依据。在此模型中，适应度函数可以定义为所用木板总量h的利用率与前n-1个木板的利用率之和，具体函数如下:
其中，
为h个木板S1面积之和，
选用木板面积之和，
为h-1个木板排放的产品Pi面积之和，
为前h-1个木板的面积之和。
对于更复杂的问题，需要引入本文的核心算法—遗传算法，并采用整数编码的方式来解决木板排样问题。遗传算法的核心因子是染色体，待排产品的数目n与染色体的长度相同，产品P的排列序号记为染色体的基因编码。因此，染色体的序号可以组成0～n-1的一个全排列。然后，按照编码顺序依次将产品Pi排入木板S中，这种方式也被称为基因编码。针对木板排样优化问题，首先将系统进行初始化，木板S1和产品Pi尺寸数据读入，然后对随机生成的种群赋值，再评估染色体。通过不断的循环，如果不满足循环评估条件，则重新选择染色体并进行染色体的交叉和变异，得到最优保持并回到评估染色体流程继续循环。如果满足，即可得到最优的染色体交叉情况，从而得出最优切割方案。
4、结语
本文通过建立木板排样优化模型和整数线性规划模型，引入遗传算法，并运用Matlab,C++编程，从而求出木板的最大利用率和最优分割方案，在优化排样时具有重大意义。
参考文献:
[1]刘咏.基于梯形和平行四边形的圆片下料算法设计与实现[D].2016.05.19.
[2]余鹏.生成矩形毛坯最优四块排样方式的精准算法[D].2008.04.01.
[3]司守奎,孙兆亮.数学建模算法与应用.北京:国防工业出版社,2019.1.
[4]朱银龙,吴海云,刘琦.基于线性规划的材料切割设计研究[J].技术与市场,2018(11):95.
[5]谭汉松,彭迎春.板材最优切割算法的设计与实现[J].计算机科学与应用,2003(18):95.
[6]袁哲,王永振,赵汉驰.矩形石板优化排样及切割路径规划研究[J].制造业自动化.
吴雨婷,张玉.基于整数规划下木板排样优化问题的研究[J].科技风,2020(17):111.
分享：
2020年5月28日，教育部印发《高等学校课程思政建设指导纲要》，全面推进高校课程思政建设。《纲要》指出，全面推进高校课程思政建设是深入贯彻习近平总书记关于教育的重要论述和全国教育大会精神、落实立德树人根本任务的战略举措，高校要深化教育教学改革，充分挖掘各类课程思想政治资源，发挥好每门课程的育人作用，全面提高人才培养质量。
2020-11-21
随着现代科学技术的飞速发展,运筹学相关研究日渐深入,应用范围日趋广泛,在军事领域中的作用也越来越重要。军事运筹学是应用数学和计算机等科学技术方法系统研究各类军事活动,并为决策优化提供理论和方法的军事学科,具有多学科综合交叉、注重实际应用、应用范围广、注重方案的最优性等特点。
2020-08-10
《运筹学》是一门把科学的方法应用于建立和求解数学模型，以便采取行动解决实际问题的科学。也就是运用科学的方法（如分析、试验、量化等）来决定如何最佳地运营和设计各种系统的一门学科。[1,2]运筹学也是一门综合性学科，其整合了数学、计算机及其其他相关科学内容，以期获得最优的结果做出最准确的决策。
2020-08-10
在全球能源消费日益增长的背景下，除了建造新的发电厂外，“需求响应”为缓解紧张的电力需求提供了一个经济有效的方法。在需求响应模式下，供电商在电力批发市场价格升高或系统可靠性受威胁时给电力用户发出电力价格变更信号或诱导性调整负荷通知，电力用户根据这些信号改变习惯用电模式，错峰用电，从而保障电网稳定，并抑制电价上升的短期行为。
2020-07-08
RGV是一种无人驾驶、能在固定轨道上自由运行的智能车。它根据指令来控制移动方向还有距离，具有一个机械手臂、两只机械手爪加一个物料的清洗槽，能够完成上下料及清洗物料等任务。2003年，Malmborg教授及其课题组首先提出自动小车存取系统，它主要包括轨道导引小车系统，通过RGVS小车进行货物存取。
2020-07-08
专利是知识产权的主要表达形式，在当今知识经济、科技引领的时代下，已成为企业发展和竞争的制高点。专利质量体系与企业的运营发展息息相关，企业传统的产品市场占有量发展模式逐步采用创新竞争模式。对于企业而言，专利是保护自身产品、防御对他人侵权的重要武器；是企业技术创新能力的证明；是企业规划开辟多源收入的重要手段。
2020-07-08
在工程设计中，材料不均匀、安装误差等问题的存在，往往会对结构性能造成各种影响甚至破坏。传统结构设计没有考虑施工过程中的不确定因素，而实际施工中载荷和材料性质等不断变化，这些不确定因素会使失效概率不断增大。为了确保产品的结构可靠性，有必要对不确定结构可靠度分析方法进行研究。
2020-07-08
“魔鬼在细节”。做好国际工程项目，要如履薄冰，因为往往一个细节的疏忽，就会导致项目成本大幅增加。做好一个项目，业主和承包商之间需要一种良好的合作氛围。对于承包商来说，不能过于计较一城一池的得失，该放弃的放弃，该争取的争取，最终会形成一个共赢的局面。
2020-07-08
依据《孙子兵法》对国家情报战略进行系统运筹，能够明确在国际情报对抗中的情报主体与情报客体的资源与结构，所面临的问题和所受的限制，指导国家情报工作有目的地进行“造形”与“治气”，创造情报主体的行动优势，取得情报对抗的胜利，为国家安全与发展保驾护航。
2020-07-08
自由粒子优化算法作为基于量子算法模型中的骨架模型，结构简洁，易于实现，通过对算法进行策略的改进，会使得算法的性能得到很好的提升。在自由粒子模型下的零势阱和谐振子模型下的高斯势阱的启发下，将优化问题中的目标函数进行势阱等效和泰勒近似实现量子模型下的转化，通过粒子在空间中的存在形式指导优化算法的寻优过程，实现量子模型的搜索机制。
2020-07-08
人气：3213
人气：2792
人气：2632
人气：2550
人气：1561
我要评论
期刊名称：运筹与管理
期刊人气：3024
主管单位：中国科学技术协会
主办单位：中国运筹学会
出版地方：安徽
专业分类：科学
国际刊号：1007-3221
国内刊号：34-1133/G3
邮发代号：16-191
创刊时间：1992年
发行周期：月刊
期刊开本：大16开
见刊时间：一年半以上
影响因子：0.553
影响因子：0.322
影响因子：0.352
影响因子：0.000
影响因子：0.000
科普杂志阅读、期刊信息查询、论文下载、文献查询、原创文章检测等多项服务。
服务热线
您的论文已提交，我们会尽快联系您，请耐心等待！
你的密码已发送到您的邮箱，请查看！
2020-06-30
451
上传者：管理员
