凯里学院2016年校内数学建模选拔赛.docx

凯里学院2016年校内数学建模选拔赛论文题目A参赛队员1、马吉波2、杨光福3、吴长贵学号1、20144041072、20144041183、2014410019专业班级1、14数理本2、14数理本3、14化学本联系邮箱185377860QQCOM矩形件下料问题的优化模型摘要随着科技发展，采用何种方法对矩形下料进行分割才能最节省资源已经成为人们最关注的问题，本文介绍采用线性规划的方法解决一维线性下料问题。关键词一维线性下料线性规划矩形件下料问题“下料问题（CUTTINGSTOCKPROBLEM）”是把相同形状的一些原材料分割加工成若干个不同规格大小的零件的问题，此类问题在工程技术和工业生产中有着重要和广泛的应用．某企业在生产过程中需要对矩形原材料实施下料，设其长度为L，宽度为W．生产时需要将一批相同规格的原材料分割成M种规格的零件，所有零件的厚度均与原材料一致，但长度和宽度分别为,,1WLL，其中,IL,IWW1,M．种零件的需求量分别为MN,1．下料时，零件的边必须分别和原材料的边平行．这类问题在工程上通常简称为二维下料问题（图2）．特别当所有零件的宽度均与原材料相等时，即IWWI,,，则问题称为一维下料问题（图1）．在某一块原材料上的所有零件的组合称为该原材料的下料方式．一个下料方案的优劣通常有两个评价标准，一是使用原材料数量最少，二是下料方式尽可能少．图1一维下料示意图图2二维下料示意图该企业希望设计一款软件，在输入原材料规格和各种零件规格及数量后，计算出最优下料方案，包括所需的原材料数量，每种下料方式及数量，余料长度或面积．为此，请你解决以下问题1请对单一原材料的一维下料问题建立数学模型，并给出下列问题的下料方案．原材料长度为2000MM，零件规格共10种，具体数据见表1．其中IL为需求零件的长度，IN为需求零件的数量．此外，在每个切割点处由于锯缝所产生的损耗为3MM．表1需求材料数据单位MMI12345678910IL420415414411405328313290275265IN12101630426385560462该企业另有两种长度分别为1500MM和3000MM的原材料．请针对上述问题再利用这两种原材料分别计算下料方案，并比较三种原材料之间的下料方案优劣，找出原材料长度与需求零件长度的关系．3将三种原材料混合使用，试计算上述问题的最优下料方案．一．模型的假设1、长度为2000MM的原材料，切割后的边料为无用材料。2、每一块原料皆有切割边料。3、若每一块原料切割剩下的部分小于此时所需全部需要零件中的每一块，则切割剩下的部分视为边料。二．问题的分析1、问题题目显然是要将不同规格的原材料分割成不同规格的需求材料，分割方法有多种，要求找出最能节省原材料且下料方式尽量少的一种。2、分析（1）若找到一种下料方式使得切割边料的总长L和锯缝总长L1的总和最小，则此下料方式最优。（2）因为每一块原料皆有切割边料，所以锯缝总长为定值，证明方法如下下面用数学归纳法来证明此问题假设第I个矩形原料切割成J份需求零件和一份边料，根据假设可知这个原料被分割总份数为J1，则这个原料同样包含了J个锯缝，在这里虽然I和J都不是定值，但是需求总零件的总数量却为定值315，由此可类推归纳出钜缝I1210163042638556046的总数量也为315，因此钜缝损失材料总长为31503945MM,此为定值。由于边缝损失原料为定值，因此，可把此问题简化成求切割边料最小值的问题，若切割边料达到最小，则此时的方案为最优。下列寻找如何切割使边料达到最小的方法。三．模型的建立由问题的分析可知，此类问题视为求切割边料与锯缝总长最小的问题，以此可列出线性规划求解。设LI种材料在第J种所需数量为XI,J，M每一块原料剩余边料长度为ZI,I,每一块原料的锯∈1,10且𝑚为整数，∈1,𝑛缝总长为KI,I。根据题目已知条件可列出此线性，再求出最优解即可。∈1,𝑛四．模型的求解与分析1对于问题1的求解YMIN∑𝑧𝑛{2000‒𝑋1,1∗420𝑋1,2∗415𝑋1,10∗265𝑍1𝐾12000‒𝑋2,1∗420𝑋2,2∗415𝑋2,10∗265𝑍2𝐾22000‒𝑋𝑛,1∗420𝑋𝑛,2∗415𝑋𝑛,10∗265𝑍𝑛𝐾𝑛且X,12MM，10MM，16MM，≥0且为整数∑𝑛𝑗1𝑋𝑗,1∑𝑛𝑗1𝑋𝑗,2∑𝑛𝑗1𝑋𝑗,330∑𝑛𝑗1𝑋𝑗,446MM；945MM∑𝑛𝑗1𝑋𝑗,10∑𝑛𝑖1𝑘𝑖2000N4201241510265469451037505,即得2000N1037505,解≥≥得N≥52N从52找起，分别求出所有的XMN,当所有的XMN皆为整数时，此时为最优解。为了进一步缩小范围，确定N的最大值，进而求出剩余边料总长度，以便用VB软件实现电脑操作，为此我们任意选取一种方案，求出此时需要的原料总数N1，而N下列是我选取的N1的值的一种求法≤𝑛1我们按顺续依次用原料，按第一种需求原件切割第一种原料，余下部分再以最接近而小于余下部分的需求原件切割。如先用第一块原料切割，则可切成2000/4204320，此时第七组需求原件最为接近，再割第七组按此方法求得N165此时边料总长度为652000MM1037505MM262495MM,此时的切割边料取值范围必为（0，262495）。下列我们用电脑编程，在此不妨设上述的ZIXN,11,KIXN,12,以便求出结果，用VB软件设计编程如下PRIVATESUBCOMMAND1_CLICKDIMXASSINGLE,ZASSINGLEDIMX_MINASSINGLEDIMYMINASSINGLEYMIN1FORXN,11TO12,XN,21TO10XN,101TO46FORY0TO20429IFN52Y∑52𝑖0𝑋𝑖,11X1ROUNDX1,1X2ROUNDX1,1X10ROUNDX1,10FORYMIN∑𝑧𝑛{2000‒𝑋1,1∗420𝑋1,2∗415𝑋1,10∗265𝑋1,11𝑋1,122000‒𝑋2,1∗420𝑋2,2∗415𝑋2,10∗265𝑋2,11𝑋2,122000‒𝑋𝑛,1∗420𝑋𝑛,2∗415𝑋𝑛,10∗265𝑋𝑛,11𝑋𝑛,12XI,J,12，10，16，30≥0∑𝑛𝑗1𝑋𝑗,1∑𝑛𝑗1𝑋𝑗,2∑𝑛𝑗1𝑋𝑗,3∑𝑛𝑗1𝑋𝑗,446；945∑𝑛𝑗1𝑋𝑗,10∑𝑛𝑖1𝑋𝑖,12YMAX262495,YMINY1ENDIFPRINT”𝑋1,1,𝑋1,2𝑋1,3𝑋1,12𝑋2,1,𝑋2,2𝑋2,3𝑋2,12”𝑋𝑛,1，𝑋𝑛,2𝑋𝑛,3𝑋𝑛,12ENDSUB若52不满足条件，则依次输入53、54依次反复，终在57处取得，MINY102495MM,而到到到取值都一样，而𝑋1,1𝑋57,1，𝑋1,2𝑋57,2𝑋1,12𝑋57,12，𝑋1,1,𝑋1,2，𝑋1,3𝑋1,10𝑋2,1,𝑋2,2，𝑋2,3𝑋2,10的组合却不相同。为𝑋57,