钢管切割问题.doc

钢管切割问题1、某钢管零售商从钢管厂进货,将钢管按照顾客的要求切割后售出,从钢管厂进货时所得到的钢管都是19M。(1)现有一客户需要50根4M,20根6M和15根8M的钢管,应如何下料最节省,(2)零售商如果采用不同的切割模式太多,将会导致生产过程复杂化,从而增加生产和管理成本,所以该零售商规定采用的不同的切割模式不能超过3种。此外该客户需要(1)种的三种钢管外,还需要10根5M的钢管,该如何下料最节省,问题分析对于下料问题首先要确定采用哪些切割模式。所谓切割模式,是指按照顾客要求的长度在原料钢管上安排切割的一种组合。例如,我们可以将19m的钢管切割成3根长4m的钢管,余料为7m;或者将长19m的钢管切割成长4m、6m和8m的钢管各1根,余料为1m。显然,可行的切割模式是很多的。其次,应当明确哪些切割模式是合理的。合理的切割模式通常还假设余料不应大于或等于客户需要钢管的最小尺寸。例如,将长19m的钢管切割成3根4m的钢管是可行的,但余料为7m,可进一步将7m的余料切割成4m钢管(余料为3m),或者将7m的余料切割成6m钢管(余料为1m)。经过简单的计算可知,问题1)的合理切割模式一共有7种,如表3所示:于是问题化为在满足客户需要的条件下,按照哪几种合理的模式,每种模式切割多少根原料钢管最为节省。而所谓节省,可以有两种标准,一是切割后剩余的总余料量最小,二是切割原料钢管的总根数最少。下面将对这两个目标分别讨论。模型问题1)用xi表示按照表3第i种模式(i=1,2,…,7)切割的原料钢管的根数,若以切割后剩余的总余料量最小为目标,则按照表3最后一列可得minZ1=3x1+x2+3x3+3x4+x5+x6+3x7(1)若以切割原料钢管的总根数最少为目标,则有表3钢管下料问题1)的合理切割模式模式4m钢管根数6m钢管根数8m钢管根数余料/m140032310132013412035111**********MinZ2=x1+x2+x3+x4+x5+x6+x7(2)约束条件为客户的需求,按照表3应有4x1+3x2+2x3+x4+x5?50(3)x2+2x4+x5+3x6?20(4)x3+x5+2x7?15(5)最后,切割的原料钢管的根数xi显然应当是非负整数(用Z表示整数集合,Z+表示非负整数集合):xi?Z+,i=1,2,…,7(6)于是,问题1)归结为在约束条件(3),(6)下,使目标(1)或目标(2)达到最小。显然这是线性整数规划模型。问题2)如果按照问题1)的办法处理,首先要通过枚举法确定哪些切割模式是合理的,并从中选出不超过3种模式。而由于需求的钢管规格增加到4种,所以枚举法的工作量较大。下面介绍一种带有普遍性的方法,可以同时确定切割模式和切割数量。同问题1)一样,只使用合理的切割模式,其余料不应大于3m(因为客户需要的钢管最小尺寸为4m,而本题中参数都是整数)。由于不同切割模式不能超过3种,可以用用xi表示按照第i种模式(i=1,2,3)切割的原料钢管的根数。又设使用第i种切割模式下每根原料钢管生产长4m、5m、6m和8m的钢管数量分别为r1i,r2i,r3i,r4i。仅以使用的原料总根数最少为目标,即Minx1+x2+x3(7)满足客户需求的约束条件为r11x1+r12x2+r13x3?50(8)r21x1+r22x2+r23x3?10(9)r