钢管下料问题

1、湖北汽车工业学院2009年大学生数学建模竞赛承诺书我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮 件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问 题。我们知道，抄袭别人的成果是违反竞赛规则的，如果引用别人的成果或其他 公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正 文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反 竞赛规则的行为，我们将受到严肃处理。参赛队员（姓名，班号，签名）：1 .冯鹏程，T773-22 .李冠华，T743-73

2、 .吴楠，T723-5日期：2010 年5 月18 日编号： 钢管下料问题的论文问题的重述某钢管零售商从钢管厂进货，将钢管按照顾客的要求切割出售从钢管厂进货得到的原材料的钢管的长度都是1850mm ，现在一顾客需要15根 290 mm，28 根 315 mm， 21 根 350 mm 和 30 根 455 mm 的钢管为了简化生产过程，规定所使用的切割模式的种类不能超过4 种， 使用频率最高的一种切割模式按照一根原料钢管价值的1/10 增加费用，使用频率次之的切割模式按照一根原料钢管价值的 2/10 增加费用，以此类推，且每种切割模式下的切割次数不能太多（一根原钢管最多生产5 根产品），此外为

3、了减少余料浪费，每种切割模式下的余料浪费不能超过100 mm,为了使总费用最小，应该如何下料？摘要该问题在于确定钢管切割模式的安排上，显然是一个优化问题。是一个在原料和成品长度等约束下求最小费用的优化模型。我们在分析题目的各种限制因素后，找到初步的目标函数，找到约束条件，建立 IP （整数优化）模型。在求解模型过程中，由于问题的规模小，我们通过分析约束条件采取枚举法分析可行域，运用MATLA豉到钢管切割模式的可行解。然后在目标函数下，进而求出最优解集合。 考虑到实际生活常识，通过对满足约束条件下的最优解来进行分析，找到符合实际的最优解。依此来确定最终的切割模式方案。在求解模型的过程中，针对不同

4、的假设背景下，可以简化模型的求解过程。我们运用LINDO/LINGO或MATLAB写程序来进行求解，同时用LINDO/LINGO软件进行初步的可行性和灵敏度分析。为了使主要结果的直观性和形象性，对获得的数据运用MATLABt理成图表。在文章的最后，我们对模型的改进和模型的应用范围进行了适当的分析，提出关于与模型的相关问题的见解。关键字切割模式优化MATLAB/LINGO灵敏度分析1 .题目提出原料钢管长度1850mm现要从这一批原料钢管中切割出15根290mm 28根 315mm 21根350mmffi 30根455mmE种特定长度的成品钢管。合理的切割模式 确定后，求使切割总费用最小的切割方

5、案。问题中的原料和成品长度都有限定， 切割费用也与切割模式有关。在阅读分析题目后，其中限制条件主要有： 1.1原料钢管长度限制，所以每根钢管的切割模式总长度不能超过1850mm1.2 一根钢管最多生产5根成品钢管，切割后的成品根数有限制 1.3切割模式的种类不能超过4种1.4 一根钢管在每种切割模式下的余料不能超过100mm1.5 费用的计算方式是和切割模式的使用频率有关2 .符号说明和模型假设2.1 符号的说明LL表示原料钢管的长度(LL = 1850mm)Qi表示第i种成品钢管的需求根数(i =1,2,3,4)L 表示第i种成品钢管的长度nj表示在第j种切割模式下切割的原料钢管的根数(j

6、= 1,2,m.m< J ) qj表示在第j种切割模式后剩下的需求成品根数qj表示在第j种切割模式下一根原料钢管切割出的第i种成品钢管根数N 表示一根原料钢管最多生产的成品根数 l j表示在第j种切割模式下每根原料钢管的余料J表示切割模式种类的限制(J=4) L 表示每根原料钢管的余料限制(AL= 100mm)N表示满足需求下需要的原料钢管的根数fj表示在第j种切割模式下的总费用F表示所有切割模式下的总费用kj 表示费用比例因子P表示原料钢管单价2.2模型的假设(1)切割过程中原料钢管不发生长度损失。(2)在切割过程中，只发生因切割而产生的费用。(3)切割费用只与切割模式使用频率有关，而

7、与其他因素无关。(4)在使总费用达到最小的所有模式中，认为余料最小是要比其他同等模式优良的切割模式3 .问题的分析和模型的建立3.1 这是一个优化问题中的IP问题，即整数优化。主要的问题是求解由一系列合理的切割模式组成的切割方案使切割过程中发生的费用最少，也就是确定由nj组成的矩阵N o3.2 目标函数的建立3.2.1 在第j种切割模式下的总费用fjf j = kj Pq(1)3.2.2 所有切割模式下的总费用F =£ fj (2)3.2.3 目标函数总费用最小MINF fj(3)3.3 约束条件,3.3.1 原料钢管长度约束二 qij Li _ LL(4)3.3.2 需求数量约束Q

8、i 21 qij(5)3.3.3 余料约束在第j种切割模式下每根原料钢管的余料% =LL 八 qij Lil j < AL(6)3.3.4 切割最多根数约束Z qij 芸 N(7)3.3.5 切割模式种类约束8)j MJ3.3.6 根数整数约束9)qj ,njN3.4 数学模型 目标函数：MINF = '、fjZ qj Li < LLQi <Z qj约束条件:Alj <AL Z qj <N 1 jJ qj ,nj w N注：当 nj = (n1 n2 n3n4箱如下关系ra n2 An3A 心，则切割费用比例向量中的元素有【kj ：'= kik2k

9、3k4 =10 1034I10 104 .数学模型的求解经过合理假设后，问题的关键就变成在约束条件下求解每种切割方式中的钢管数 量组成的行向量nj。以下我们分别采用通过编辑LINDO/LINGO呈序求解出目标 函数取得最优解时的口=1和通过遍历的方法求解（不推荐）4.1 LINDO/LINGOS 序求解4.2 MATLA取现的遍历求解由于问题简单（维数不多），我们可以通过MATLA皿行遍历求解。由于原料钢管长度是LL = 1850mm ,成品钢管的长度是 L =（290 315 350 455）,因此一根表（.）一根原料钢管切割成品的最大数量成品长度（mm290315350455最大数量6.3

10、85.875.294.07这样通过预先的原料钢管能够生产成品数量的求解，可以减小遍历时候的循环 可以简化求解过程，同时也能够对以后的求解过程进行验算。因此，在长度和余料AL=100mm限制下，我们可以通过循环进行遍历筛选出可 行解。求解的结果如下表（其中的对应切割模式的可能的使用频率最大值是根据N =（15 28 21 30 坪:取）表（4.2.1 ）可行的第一种切割模式汇总编号L1L2L3L4余料可能的使用频率最大值10004307200501004301313074022165105031110096103155771121901081202201492012107102102457113

11、002705因为费用与切割模式的使用频率有显著的关系，通过观察表（4.2.1 ）可以看到编号8的切割模式的可能的使用频率最大值为最大，并且余料也在 11种模式中也较小。因此，我们第一种切割模式采用8号切割模式，此时可以求得 5=14,1f1 = P 14 , Aq1 =Aqi1 = （1 0 21 2 卜 10可以在第二类成品钢管需求为0的情况下，进行对切割模式进行遍历，结果如下 表（.）可行的第二种切割模式汇总编号L1L2L3L4余料可能的使用频率最大值10004300200501004310315514201210053002700我们可以这样做，先采用编号3的模式，因为如果采用2号方案就

12、会造成不能解决约束条件满足的现象。因此，我们第二种切割模式采用3号切割模式，此时可 以求得 n2=1, fx=kxP1, Aq2=Gq2i=（0 0 18 1）。由于Aq2=（0 0 18 1 ）,只要再切割一根钢管即能切割完成需求。所以第三种切割模式就选择表（.）可行的第三种切割模式汇总编号L1L2L3L4余料可能的使用频率最大值10004300200501003因此，我们第三种切割模式采用表（.）2号切割模式，此时可以求得 %=1,f3 =p 1， %3 =好 =。0 1 2 综合以上的求解过程，切割方案是即每种切割模式切割的原料钢管数量是n=（14 4 1 ）,费用向量是f =（lp 1

13、4 P 4 3 P 1 j,切割方式组成的矩 101010,1202、一-5阵是 q = 0050,最优解是MINF=£fj =Pj21012,j模型求解结果如下表（.）钢管下料方案编号L1L2L3L4余料使用频率切割费用1120220141.4P2005010040.8P3101230010.3P小计15282130980192.5P源程序见附件（2.1）,运行结果见附件（2.2）5 .数学模型的评价和进一步讨论5.1 数学模型的优点这是一个经济生活中常见的确定生产方案问题，是运筹学中很典型的问题。并且在合理的将约束条件简化条件下，能够和实际结果符合的较好。5.1.1 模型思路明朗

14、清晰，结构简单，有一定的适用范围能够较为简便的解决生 产方案安排问题。5.1.2 模型可以很容易的推广到在 M种原料下，生产N种成品的情形，方案制定 并进行优化（非遍历解法）。6.1.3 模型（一）能够根据不考虑运输费用的假设条件下进行合理的简化大幅度 的减少了工作量。而且模型（三）也能继承模型（一）的一些有关的思路。6.1.4 很重要的一点是问题（二）对模型（一）进行了灵敏度的分析和影子价格 的讨论，这有很重要的意义，明确的给出了模型的适用范围和在有关量发生变化时对模型中目标函数最优解的影响。这是很有现实意义的，因为有关量往往是依靠大量观测值得到的一个统计估计值。这些估计值有一个置信区间，即

15、不是一个准确的真值，自然会有误差，而模型（一）对销售价格的灵敏度分析就能够证明模型在相关量的一个变动范围内有效。显然这是很有实际意义的。5.2 数学模型需要改进的地方由于这是在实际基础上经过理想化假设后抽象出来的数学模型，因此这个数学模型也存在着一些缺陷5.2.1 必须是建立在静态假设条件下的，即要求在运输过程中相关价格量、供给量、需求量等不能发生变动，5.2.2 模型的解是整数，即离散的，原因是经济中商品量的变动很多都是单位变动，即离散的，所以模型就不能很好的处理量变化是连续性的商品运输问题，6.2.3 对运输费用的假设是与里程，即吨*公里成正比的，实际上运输价格并不一定都是这种关系，影响运

16、输费用的因素还有很多，需要考虑的地方还有很多。 并且商品的运输过程中发生损失是很难避免的，尤其是水果等鲜货，这些都会造成模型的解偏离真实值6.2.4 对运输线路的假设是直线，而现实中的航线是曲线，主要原因是我们没有获得航线里程准确的数据，这也会影响模型解的真实性。不过以上的缺陷可以在这个模型的基础上进行改进，同时如果能够获得一些准确的原始数据，就能够较为客观的反映现实，所以也不能否认这个模型的意义。6.2.5 数学模型的适用领域和范围由于这是一般化的问题，因此能够对其进行推广，应用广泛，可以作为必须满足需求要求的运输方案制定的初步参考，同时也可以作为采购运输销售经营模式的初步参考。可以看到这个

17、数学模型在经济运筹学领域的应用很广。参考文献1 薛毅，耿美英. 运筹学与实验，北京：电子工业出版社，2008.9.2 张杰，周硕，郭丽杰. 运筹学模型与实验，北京：中国电力出版社，2007.3谢金星，薛毅.优化建模与LINDO/LINGO软件.北京：清华大学出版社，2005.附件附件（1.1 ）附件（1.2）附件（2.1 ）建模比赛MATLAB 遍历程序1 clcclearl0=1850;l=290 315 350 455;m=15 28 21 30;for i=0:1:6for j=0:1:5for k=0:1:5for h=0:1:4 n=i,j,k,h;if (i+j+k+h)<=5)&(l0-n*l')<=100)&(l0-n*l')>=0)n=i,j,k,hendendendend end建模比赛MATLAB 遍历程序2clcclearl0=1850;l=290 315 350 455;m=15 28 21 30;for i=0:1:6for k=0:1:5