线材下料问题线性规划模板.docx

线材下料问题-线性规划问题陈述(下料问题)某工厂要做150套钢架,、。已知原料每根长10米,问应如何下料,可使所用原料最省?问题分析该问题是运筹学在实际运用中比较经典的“线材下料问题”,从第一部分问题陈述中能够看出,该问题的一般提法是,要做N套产品,需要用规格不同的M种线材,各种规格的长度分别为l1,l2,l3,...,lm,每一套产品需要不同规格的原料分别为m1,m2,m3,...,mm根,已知原材料的长度为一定的长度,问应该如何下料,从而使原材料的耗用最省。因此,在解决此类问题时应分两步考虑:1、确定可行的切割模式:即按照客户需要在原材料钢材上安排切割的一种组合;2、确定合理的切割模式:合理的切割模式的预料不应该大于或等于客户需要的钢材的最小尺寸。对于如上第一分部提出的线材下料问题,能够用运筹学中线性规划的方法求解,通过建立线性规划模型来具体分析。模型建立建立线性规划模型时,对于约束条件这里为切割要满足客户对钢材数量的最低要求,本题将对标准钢材的切割(、、),从而组合成一套钢架,要求为150套等因素建立约束条件。但是,对于目标函数而言,会有这样两种情况:1、求的钢材原材料总根数最少;2、求的钢材原材料余料最少。在本文的分析中,我们选择前者,即:求解使用的钢材原材料总根数最少。为了建立模型方便,我们把下料后余下的小于最短用料的钢材称为废弃钢材,,,,把10米长的原材料钢材称为原钢。因此,所用的原钢能够分解成三部分:1、成套利用的规格钢材;2、剩余的规格钢材;3、废弃钢材。通过分析计算,能够得到原钢的11种下料方式如下:表1::采取第i种下料方式的有xi根原钢,i=1,2,3,...,:,,。因此得到模型一:模型一:剩余的规格钢材当作废弃钢材的情况MinZ=0*x1+*x2+*x3+*x4+*x5+*x6+*x7+*x8+1*x9+*x10+*x11+*y1+*y2+*y3(1)4*x1+3*x2+2*x3+2*x4+x5+x6+x7-y1=+2*x5+x7+3*x8+2*x9+x10-y2=150x2+x3+2*x4+x5+3*x6+2*x7+x8+2*x9+3*x10+5*x11-y3=150xi>=0,yj>=0,且为整数i=1,2,3...11,j=1,2,3(2)(3)由(1)、(2)组成的是求废弃钢材最少的整数线性规划模型。同时,很容易联想到另一个模型,是由(2)、(3)组成的求所用原料钢材最少的整数线性规划模型。模型二:剩余的规格钢材(可同原钢一样能够再利用),不当作废弃钢材的情况MinZ=0*x1+*x2+*x3+*x4+*x5+*x6+*x7+*x8+1*x9+*x10+*x11(4)4*x1+3*x2+2*x3+2*x4+x5+x6+x7>=+2*x5+x7+3*x8+2*x9+x10>=150(5)x2+x3+2*x4+x5+3*x6+2*x7+x8+2*x9+3*x10+5*x11>=150xi>=0,i=1,2,3...11由(4)、(5)组成的是求废弃钢材最少的整数线性规划模型具有一定的实际意义,特别是当最短的规格钢材长度较长时,剩余的规格钢材就能够再次被利用。在此,我们应该注意到,由(3)、(5)组成的整数线性规划模型就是模型一。由于在建立模型一和模型二的时候,考虑了剩余规格钢材的不同处理情况,使这个问题变得清晰了,所得到的模型也比较全面,基本没有漏洞和缺陷,并且比较容易在这些基础上修改或添加一些其它的约束条件(比如:各种规格钢材下料成套时的不同比例等等),所以,我们建立的线材下料问题的模型是可行的。基于以上的分析,我们选择(3)、(5)组合而成的模型和(4)、(5)组合而成的模型进行具体求解,从而求出组合出150套圆钢所需要的最少原料钢材。求解模型:(3)4*x1+3*x2+2*x3+2*x4+x5+x6+x7>=+2*x5+x7+3*x8+2*x9+x10>=150(5)x2+x3+2*x4+x5+3*x6+2*x7+x8+2*x9+3*x10+5*x11>=150xi>=0,i=1,2,3...11此模型是设定最小使用原料钢材的条数为目标值进行求解。MinZ=0*x1+*x2+*x3+*x4+*x5+*x6+*x7+*x8+1*x9+*x10+*x11(4)4*x1+3*x2+2*x3+2*x4+x5+x6+x7>=+2*x5+x7+3*