数学建模论文--皮革下料.doc

皮件下料问题

摘要
本问题研究的是二维不规则的皮料优化排样问题。问题的优化目标为牛皮总利用率最大。容易判断出，这是一个NP完全的问题。通常的做法是寻求启发式近似算法，凭借以往的加工经验确定相关参数，从而得出牛皮原料的裁剪方式。
首先我们对给定模板的数据进行预处理，在这部分中我们统一各皮件模版的比例尺。此外，鉴于牛皮原料和皮件模板均为不规则图形，我们利用matlab，裁出两张牛皮的最大内接矩形，将牛皮原料分成“矩形部分”和“非矩形部分”。最后通过求各不规则模板的包络矩形，对不规则图形进行矩形近似。
问题要求在订单确定的情况下，以利用率最大为优化目标，提出一种对N张牛皮的排料算法。我们借鉴钢管下料模型的思想，以利用率、模板位置、完备性、可调性、均衡性为裁剪原则，人工列举了31种牛皮的裁剪方式。然后，利用LINGO，进行整数规划，以2010年1月的定单为例可求得牛皮利用率为58.23%，并且详细列举出了各张牛皮的裁剪方式。
根据上述研究，我们认为我们的模型简单易懂，可操作性强。但是，牛皮的利用率不高，且未考虑到实际的加工难度，会造成人力资源的大量消耗。
因此，在模型的改进中，我们进一步提出了不规则图形的离散化处理和批量生产两种解题思路。有效地克服了结果利用率不高和实际加工难度大的问题。

关键词：包络矩形，matlab，LINGO,整数规划

一、问题重述
在实际生产生活中裁剪是必不可少的，裁剪的好坏，利用率的高低，直接影响到生产厂家的经济利益。首先定义以下三个定义：
牛皮：整张，未裁剪的牛皮原料。经由人工检查，对不同品质的部分进行分级后，经过数码取像技术转化成CAD文件格式的二维区域。
皮板：最终产品的模板，一般由硬纸板做成，由于裁剪。产品设计完后，确定不同皮板部位的等级，经过数码取像技术转化成CAD文件格式的二维区域。
皮件：由皮革缝制成的皮套，再通过其他工艺加工成的最终产品（例如皮包，皮鞋，皮沙发等）。
根据以上定义，本问题研究的对象是数码二维区域（含等级）。
附件提供了两张牛皮模板，沙发模板和椅子模板，根据制造沙发的各个部位的皮模板可以制造一把皮沙发和一把餐椅。
在实际生产中，要求最后一张牛皮的利用率尽可能大。并且能够对牛皮和皮板进行分级运算，排料需要满足牛皮的等级大于等于皮板上的等级。
假设N张牛皮的模板都和提供的两张一样，试建立数学模型，在厂家皮件订单确定的情况下，针对N张牛皮的排料算法，要求牛皮的利用率最大化。

二、问题假设
2.1、不考虑切割时的刀口宽度问题
2.2、比例尺是像素点关于实际尺寸的比例
2.3、椅子模板的比例和沙发模板中出现次数最多的比例尺相同
三、符号说明
3.1大牛皮数目------N1；
3.2小牛皮数目------N2；
3.3第i种裁剪方式的数目------Xi；
3.4第i种裁剪方式裁剪出第j种模板的数目------Mi,j；
3.5一张沙发或一把椅子需要第j种模板的数目------numj；
3.6订单中沙发数目------m1；
3.7订单中椅子数目---------m2；

四、问题分析
此问题涉及到皮革制造业中皮料的优化排样。排样问题是典型的NP难问题。因此普通的优化排样算法是难以求解的。在工程上，通常采用遗传或者神经网络等智能优化算法，或者是启发式的近似算法。具体到这道题，所给的牛皮原料和皮件模板都是不规则的，沙发有46个模板，椅子有10个模板，在订单确定的情况下，设计以利用率最大为目标的排料算法。我们提出了以下思路：
首先裁剪出两张牛皮原料最大内接矩形，并求出各个模板的包络矩形。再借鉴钢管下料模型【1】的思想，依据利用率最大这一优化目标，设计一定的裁剪原则，从而列举两张牛皮原料可能的几种裁剪方式，将问题简化为整数规划问题。

五、模型建立与求解
5.1数据预处理
1) 比例尺
在沙发皮件模板中，有几张图的比例尺不同，我们采用其中数目最多的比例尺统一每个图的比例尺。最后将比例尺统一为98个像素点代表210mm。
2) 皮件模板的矩形包络
我们将沙发模板从1到46进行编号，椅子的模板以“椅1 椅10”编号。其中，椅子模板的面积和比例尺并未提供，我们假设98个像素点代表210mm，然后利用图像处理和MATLAB得出了各个模板的面积。
利用matlab求得各个模板的包络矩形的相关信息如下：
编号数量原面积（m^2）宽（mm）长（mm）包络矩形面积（m^2）38，3920.535949110.54136，3720.376067910.4834，3520.355766450.37221，2220.1854314910.21123，2420.1854244800.2043310.162596170.1625，2620.123004200.12627~32