搜索
钢管下料问题摘要:如何建立整数规划模型并得出整数规划模型的求解方法是本实验要点,本题建立最常见的线性整数规划,利用分支定界法和Lingo软件进行求解原料下料类问题，即生产中通过切割、剪裁、冲压等手段，将原材料加工成所需大小；按照工艺要求，确定下料方案，使所用材料最省，或利润最大。分支定界法可用于解纯整数或混合的整数规划问题，此方法灵活且便于用计算机求解，所以现在它已是解整数规划的重要方法。Lingo软件的功能是可以求解非线性规划(也可以做线性规划,整数规划等)，特点是运算速度快，允许使用集合来描述大规模的优化问题。大规模数学规划的描述分为四个部分：model:1．集合部分（如没有，可省略）SETS:集合名/元素1，元素2，…，元素n/：属性1，属性2，…ENDSETS2．目标函数与约束部分3．数据部分（如没有，可省略）4．初始化部分（如不需要初始值，可省略）end关键字：材料Lingo软件整数规划问题描述：某钢管零售商从钢管厂进货，将钢管按照顾客的要求切割后售出，从钢管厂进货时得到的原料都是19米。（1）现有一顾客需要50根4米、20根6米和15根8米的钢管。应如何下料最节省？（2）零售商如果采用的不同切割模式太多，将会导致生产过程的复杂化，从而增加生产和管理成本，所以该零售商规定采用的不同切割模式不能超过3种。此外，该客户除需要（1）中的三种钢管外，还需要10根5米的钢管。应如何下料最节省。（1）问题简化：问题1.如何下料最节省?节省的标准是什么？原料钢管:每根19米客户需求4米50根6米20根8米15根问题2.客户增加需求：由于采用不同切割模式太多，会增加生产和管理成本，规定切割模式不能超过3种。如何下料最节省？问题分析：切割模式,例如：按照客户需要在一根原料钢管上安排切割的一种组合。枚举法：合理切割模式的余料应小于客户需要钢管的最小尺寸，故而合理的切割模式如下：模式4米钢管根数6米钢管根数8米钢管根数余料（米）14003231013201341203511116030170023需求502015为满足客户需要，按照哪些种合理模式，每种模式切割多少根原料钢管，最为节省？两种标准：1.原料钢管剩余总余量最小。2.所用原料钢管总根数最少。模型构成：1.引入决策变量:xi～按第i种模式切割的原料钢管根数(i=1,2,…7)构建目标函数总余料最少MinZ1=3x1+x2+3x3+3x4+x5+x6+3x7总根数最少5米10根余料1米4米1根6米1根8米1根余料3米4米1根6米1根6米1根余料3米8米1根8米1根MinZ2=x1+x2+x3+x4+x5+x6+x72.约束条件需求约束：4x1+3x2+2x3+x4+x5=50x2+2x4+x5+3x6=20x3+x5+2x7=15xj为非负整数,j=1,2,…,73.目标函数(i)目标：总余料最少MinZ1=3x1+x2+3x3+3x4+x5+x6+3x7s.t.4x1+3x2+2x3+x4+x5=50x2+2x4+x5+3x6=20x3+x5+2x7=15xj为非负整数，j=1,2,…,7(ii)目标：总根数最少MinZ2=x1+x2+x3+x4+x5+x6+x7s.t.4x1+3x2+2x3+x4+x5=50x2+2x4+x5+3x6=20x3+x5+2x7=15xj为非负整数，j=1,2,…,7数学模型：（i）Lindo程序（总余料最小）计算结果（总余料最小）按模式2切割12根,按模式5切割15根，余料27米（ii）Lindo程序（总根数最小）计算结果（总根数最小）按模式1切割5根，按模式2切割5根，按模式5切割15根，共25根,余料35米。两个目标结果相比只下，目标2虽余料增加8米，但减少了2根，当余料没有用处时，通常以总根数最少为目标。故而目标2比较符合要求。（2）问题分析：增加一种需求：5米10根，切割模式不超过三种，则现有4种需求：4米50根，5米10根，6米20根，8米15根，用枚举法确定合理切割模式，过于复杂。更合理的处理办法:对大规模问题，用模型的约束条件界定合理模式。模型构成:1.引入决策变量xi~按第i种模式切割的原料钢管根数(i=1,2,3)；r1i,r2i,r3i,r4i~第i种切割模式下，每根原料钢管生产4米﹑5米﹑6米和8米长的钢管的数量；切割模式i数量x1x2x3需求4米r11r12r13505米r21r22r23106米r31r32r33208米r41r42r43152.目标函数（总根数最少）Z=x1+x2+x33、决策变量约束整数约束：xi,rji(i=1,2,3;j=1,2,3,4)为整数需求约束：r11x1+r12x2+r13x3=50r21x1+r22x2+r23x3=10r31x1+r32x2+r33x3=20r41x1+r42x2+r43x3=15模式合理约束：每根余料不能超过3米16=4r11+5r21+6r31+8r41=1916=4r12+5r22+6r32+8r42=1916=4r13+5r23+6r33+8r43=19总钢管数的下界：根据需求：4米50根，5米10根，6米20根，8米15根以及每根原料钢管长19米，可得(4*50+5*10+6*20+8*15)/19=26总钢管数的上界：特殊生产计划：对每根原料钢管模式1：切割成4根4米钢管，需13根；模式2：切割成1根5米和2根6米钢管，需10根；模式3：切割成2根8米钢管，需8根。共13+10+8=31总钢管数的约束：26=x1+x2+x3=31模式排列顺序可任定，因此指定x1=x2=x3数学模型：模型求解：模式1：每根原料钢管切割成2根4米、1根5米和1根6米钢管，共10根；模式2：每根原料钢管切割成3根4米和1根6米钢管，共10根；模式3：每根原料钢管切割成2根8米钢管，共8根。原料钢管总根数为28根。问题总结：（1）最少用25根，其中5根切4个4米钢管，另5根切3个4米1个6米钢管，最后15根切1个4米1个6米1个8米钢管。（2）最少用28根，其中10根切2个4米1个5米1个6米钢管，另10根切3个4米1个6米钢管，最后8根切2个8米钢管。