文档介绍：皮件下料问题20103892范良昊20103917潘兰蓉20103908陈艳伟摘要本问题研究的是二维不规则的皮料优化排样问题。问题的优化目标为牛皮总利用率最大。容易判断出,这是一个NP完全的问题。通常的做法是寻求启发式近似算法,凭借以往的加工经验确定相关参数,从而得出牛皮原料的裁剪方式。首先我们对给定模板的数据进行预处理,在这部分中我们统一各皮件模版的比例尺。此外,鉴于牛皮原料和皮件模板均为不规则图形,我们利用matlab,裁出两张牛皮的最大内接矩形,将牛皮原料分成“矩形部分”和“非矩形部分”。最后通过求各不规则模板的包络矩形,对不规则图形进行矩形近似。问题要求在订单确定的情况下,以利用率最大为优化目标,提出一种对N张牛皮的排料算法。我们借鉴钢管下料模型的思想,以利用率、模板位置、完备性、可调性、均衡性为裁剪原则,人工列举了31种牛皮的裁剪方式。然后,利用LINGO,进行整数规划,%,并且详细列举出了各张牛皮的裁剪方式。根据上述研究,我们认为我们的模型简单易懂,可操作性强。但是,牛皮的利用率不高,且未考虑到实际的加工难度,会造***力资源的大量消耗。因此,在模型的改进中,我们进一步提出了不规则图形的离散化处理和批量生产两种解题思路。有效地克服了结果利用率不高和实际加工难度大的问题。关键词:包络矩形,matlab,LINGO,整数规划一、问题重述在实际生产生活中裁剪是必不可少的,裁剪的好坏,利用率的高低,直接影响到生产厂家的经济利益。首先定义以下三个定义:牛皮:整张,未裁剪的牛皮原料。经由人工检查,对不同品质的部分进行分级后,经过数码取像技术转化成CAD文件格式的二维区域。皮板:最终产品的模板,一般由硬纸板做成,由于裁剪。产品设计完后,确定不同皮板部位的等级,经过数码取像技术转化成CAD文件格式的二维区域。皮件:由皮革缝制成的皮套,再通过其他工艺加工成的最终产品(例如皮包,皮鞋,皮沙发等)。根据以上定义,本问题研究的对象是数码二维区域(含等级)。附件提供了两张牛皮模板,沙发模板和椅子模板,根据制造沙发的各个部位的皮模板可以制造一把皮沙发和一把餐椅。在实际生产中,要求最后一张牛皮的利用率尽可能大。并且能够对牛皮和皮板进行分级运算,排料需要满足牛皮的等级大于等于皮板上的等级。假设N张牛皮的模板都和提供的两张一样,试建立数学模型,在厂家皮件订单确定的情况下,针对N张牛皮的排料算法,要求牛皮的利用率最大化。二、、、、椅子模板的比例和沙发模板中出现次数最多的比例尺相同三、------N1;------N2;------Xi;------Mi,j;------numj;------m1;---------m2;四、问题分析此问题涉及到皮革制造业中皮料的优化排样。排样问题是典型的NP难问题。因此普通的优化排样算法是难以求解的。在工程上,通常采用遗传或者神经网络等智能优化算法,或者是启发式的近似算法。具体到这道题,所给的牛皮原料和皮件模板都是不规