第八届华中地区大学生数学建模邀请赛教程.doc

-第八届华中地区大学生数学建模邀请赛承 诺 书 我们仔细阅读了第六届华中地区大学生数学建模邀请赛的竞赛细则。 我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。 我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。 我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。 我们的参赛报名号为：105141519 参赛队员 (签名) ： 队员一：罗 敏 队员二：曹 君 队员三：王 江 武汉工业与应用数学学会 第八届华中地区大学生数学建模邀请赛组委会 第八届华中地区大学生数学建模邀请赛编 号 专 用 页 选择的题号： 题A 参赛的编号： 105141519 第八届华中地区大学生数学建模邀请赛 题目： 钢构件的排料问题 【摘 要】 随着钢结构产品的广泛应用,提高原材料板材的利用效率是钢结构企业计算机辅助排样优化的目的在于提供高质,以便节约原材料,降低产品成本、提高企业经济效益和社会效益。增强企业竞争力。 本文在理论和实践中的主要研究工作如下: 针对二维不规则钢构件(异形件)排样,在综合利用计算几何、计算机图形学、优化组合的知识的基础上, 在钢构件制造产品的生产过程中，依照产品零件尺寸从板料中截取大小适当的零件过程称之为排料，也称之为下料。排料是钢构件制造的第一道工序。在这道工序中，不同的排料方案具有不同的材料利用率，而原材料的利用率直接影响产品的成本。对于一个年消耗大量钢材的生产单位，若能够提高原料利用率的1%，那么其节约的钢材成本是可观的。因此，降低废料率提高原材料利用率是钢构件生产企业追求的目标。根据实际情况，板材排料又可分为两种：一是规则形状的零件排料，一是不规则形状的零件排料。 规则形状零件是指矩形零件。其描述一般只需用矩形的长和宽。规则形状零件的排料问题的实质是研究如何组合零件摆放问题，使得在整个原料上摆放大量的不同长和宽的零件产生的废料最少、整料和余料的利用率最高。排放时，其零件间的搭接关系的处理相对容易，只需考虑长、宽两个因素（含预留的损耗量）。 不规则零件在这里是指多边形零件（一般的意义是指由直线、圆、弧、孔等的组合形），相对矩形零件排料而言，不规则零件的直接排料要复杂得多。 另外由于切割工艺的要求，切割只能实行“一刀切”的工艺（在整料或余料中，从一边的某点到另外一边某点的连线一次切割，但可以在切割下来的板料中再次切割）。板材的利用率就是所有零件面积之和与在一刀切工艺后继续切割的那部分板材面积的比值。 问题1: 对1张板料和若干规则形状零件（板料和零件参数见附件1），如何在板料中摆放零件使其板料的利用率最高。 问题2: 对1张板料和若干不规则形状零件（板料和零件参数见附件2），如何在板料中摆放零件使其板料的利用率最高。 问题3: 对2张板料和若干规则形状零件（板料和零件参数见附件3），如何在板料中摆放零件使其板料的利用率最高。 2.分析问题 2.1问题一： 需要建立二维矩形件排样问题的几何模型，之后采用启发式算法进行求解。算法采用构造性的递归结构，每完成一个排样基本单元排样后，假定将板材切割，完成零件的下料，并形成新的更小的板材。对新的更小的板材递归进行排样，直到完成所有零件的排样。为避免陷入局部最优解，为算法设置了回溯机制，当后面的零件无法完成排样时，算法返回修改之前的排样，再尝试完成后续零件的排样。当所有零件完成排样后，算法终止，记录各个零件的位置坐标，得出排样结果。 2.2问题二： 根据问题一的求解，本文对不规则的零件先进行规则化处理，如： 最小包络矩形法，通过对零件外轮廓多边形进行操作，分别求得与多边形平行或重合的最小包络矩形，找出其中的最小者即为零件最小包络矩形。为得到最小包络矩形，通过聚合矩形法，将不规则的零件，进行旋转，由文献研究可的，当两个零件的边界相差180度时，能够产生最小包络矩形。最终问题归结为规则的零件排料问题。 2.3问题三： 通过对一二两个问题的研究，本文对问题三作如问题的处理方式。问题三中，原材料数量增加了一倍，但原理与问题一类似，运用启发式算法求解问题。 3.模型假设 每个零件与板块原件的厚度都是一样的。 在满足尺寸约束的条件下，每一块矩形原件上都可以