下料问题

nullnull下料问 生产中常会遇到通过切割、剪裁、冲压等手段，将原加工成所需大小这种过程，称为原料下料（cutting stock）问题。按照进一步的工艺要求，确定下料方案，使用料最省，或利润最大null钢管下料问题 某钢管零售商从钢管厂进货，将钢管按照顾客的要求切割后售出。从钢管厂进货时得到的原料钢管都是19米长。 1) 现有一客户需要50根4米长、20根6米长和15根8米长的钢管。应如何下料最节省？ 2) 零售商如果采用的不同切割模式太多，将会导致生产过程的复杂化，从而增加生产和管理成本，所以该零售商规定采用的不同切割模式不能超过3种。此外，该客户除需要1）中的三种钢管外，还需要10根5米长的钢管。应如何下料最节省？null问题1）的求解 问题分析 首先，应当确定哪些切割模式是可行的。所谓一个切割模式，是指按照客户需要在原料钢管上安排切割的一种组合。例如，我们可以将19米长的钢管切割成3根4米长的钢管，余料为7米显然，可行的切割模式是很多的。其次，应当确定哪些切割模式是合理的。通常假设一个合理的切割模式的余料不应该大于或等于客户需要的钢管的最小尺寸。在这种合理性假设下，切割模式一共有7种，如表5-3所示。null表5-3 钢管下料的合理切割模式 null问题化为在满足客户需要的条件下，按照哪些种合理的模式，切割多少根原料钢管，最为节省。而所谓节省，可以有两种，一是切割后剩余的总余料量最小，二是切割原料钢管的总根数最少。下面将对这两个目标分别讨论。null模型建立 决策变量 用xi 表示按照第i种模式（i=1, 2, …, 7）切割的原料钢管的根数，显然它们应当是非负整数。 决策目标 以切割后剩余的总余料量最小为目标，则由表1可得 (32)以切割原料钢管的总根数最少为目标，则有 (33)下面分别在这两种目标下求解。null约束条件 为满足客户的需求，按照表1应有 null模型求解 1. 将（32），（34）~（36）构成的整数线性规划模型（加上整数约束）输入LINDO如下： Title 钢管下料 - 最小化余量Min 3x1 + x2 + 3x3 + 3x4 + x5 + x6 + 3x7 s.t. 4x1 + 3x2 + 2x3 + x4 + x5 >= 50 x2 + 2x4 + x5 + 3x6 >= 20 x3 + x5 + 2x7 >= 15 end gin 7 nullMin= 3*x1 + x2 + 3*x3 + 3*x4 + x5 + x6 + 3*x7 ; 4*x1 + 3*x2 + 2*x3 + x4 + x5 >= 50; x2 + 2*x4 + x5 + 3*x6 >= 20; x3 + x5 + 2*x7 >= 15; @gin(x1); @gin(x2); @gin(x3);@gin(x4); @gin(x5); @gin(x6); @gin(x7); null求解可以得到最优解如下： OBJECTIVE FUNCTION VALUE 1) 27.00000 VARIABLE VALUE REDUCED COST X1 0.000000 3.000000 X2 12.000000 1.000000 X3 0.000000 3.000000 X4 0.000000 3.000000 X5 15.000000 1.000000 X6 0.000000 1.000000 X7 0.000000 3.000000 null 即按照模式2切割12根原料钢管，按照模式5切割15根原料钢管，共27根，总余料量为27米。显然，在总余料量最小的目标下，最优解将是使用余料尽可能小的切割模式（模式2和5的余料为1米），这会导致切割原料钢管的总根数较多。null2. 将（33）~（36）构成的整数线性规划模型（加上整数约束）输入LINDO：Title 钢管下料 - 最小化钢管根数 Min x1 + x2 + x3 + x4 + x5 + x6 + x7 s.t. 4x1 + 3x2 + 2x3 + x4 + x5 >= 50 x2 + 2x4 + x5 + 3x6 >= 20 x3 + x5 + 2x7 >= 15 end gin 7null求解，可以得到最优解如下：OBJECTIVE FUNCTION VALUE 1) 25.00000 VARIABLE VALUE REDUCED COST X1 0.000000 1.000000 X2 15.000000 1.000000 X3 0.000000 1.000000 X4 0.000000 1.000000 X5 5.000000 1.000000 X6 0.000000 1.000000 X7 5.000000 1.000000null 即按照模式2切割15根原料钢管，按模式5切割5根，按模式7切割5根，共27根，可算出总余料量为35米。与上面得到的结果相比，总余料量增加了8米，但是所用的原料钢管的总根数减少了2根。在余料没有什么用途的情况下，通常选择总根数最少为目标。null问题2）的求解 问题分析 按照解问题1）的思路，可以通过枚举法首先确定哪些切割模式是可行的。但由于需求的钢管规格增加到4种，所以枚举法的工作量较大。下面介绍的整数非线性规划模型，可以同时确定切割模式和切割计划，是带有普遍性的。 同1）类似，一个合理的切割模式的余料不应该大于或等于客户需要的钢管的最小尺寸（本题中为4米），切割计划中只使用合理的切割模式，而由于本题中参数都是整数，所以合理的切割模式的余量不能大于3米。此外，这里我们仅选择总根数最少为目标进行求解。 null模型建立决策变量 由于不同切割模式不能超过3种，可以用xi 表示按照第i种模式（i=1, 2, 3）切割的原料钢管的根数，显然它们应当是非负整数。设所使用的第i种切割模式下每根原料钢管生产4米长、5米长、6米长和8米长的钢管数量分别为r1i, r2i, r3i, r4i（非负整数）。 决策目标 以切割原料钢管的总根数最少为目标，即目标为（37）null约束条件 为满足客户的需求，应有(38)(39)(40)(41)null 每一种切割模式必须可行、合理，所以每根原料钢管的成品量不能超过19米，也不能少于16米（余量不能大于3米），于是(42)(43)(44)null模型求解 （37）~（44）构成这个问题的优化模型。由于在（38）~（41）式中出现了决策变量的乘积，所以这是一个整数非线性规划模型，虽然用LINGO软件可以直接求解，但我们发现在较低版本的LINGO软件中需要运行很长时间也难以得到最优解。为了减少运行时间，可以增加一些显然的约束条件，从而缩小可行解的搜索范围。例如，由于3种切割模式的排列顺序是无关紧要的，所以不妨增加以下约束：（45）null又例如，我们注意到所需原料钢管的总根数有着明显的上界和下界。首先，无论如何，原料钢管的总根数不可能少于 （根）其次，考虑一种非常特殊的生产计划：第一种切割模式下只生产4米钢管，一根原料钢管切割成4根4米钢管，为满足50根4米钢管的需求，需要13根原料钢管；第二种切割模式下只生产5米、6米钢管，一根原料钢管切割成1根5米钢管和2根6米钢管，为满足10根5米和20根6米钢管的需求，需要10根原料钢管；null第三种切割模式下只生产8米钢管，一根原料钢管切割成2根8米钢管，为满足15根8米钢管的需求，需要8根原料钢管。于是满足要求的这种生产计划共需13+10+8=31根原料钢管，这就得到了最优解的一个上界。所以可增加以下约束：(46)将（37）~（46）构成的模型输入LINGO如下：null将（37）~（46）构成的模型输入LINGO如下：model: Title 钢管下料 - 最小化钢管根数的LINGO模型; min=x1+x2+x3; x1*r11+x2*r12+x3*r13 >=50; x1*r21+x2*r22+x3*r23 >=10; x1*r31+x2*r32+x3*r33 >=20; x1*r41+x2*r42+x3*r43 >=15; 4*r11+5*r21+6*r31+8*r41 <=19; 4*r12+5*r22+6*r32+8*r42 <=19; 4*r13+5*r23+6*r33+8*r43 <=19; 4*r11+5*r21+6*r31+8*r41 >=16; 4*r12+5*r22+6*r32+8*r42 >=16; 4*r13+5*r23+6*r33+8*r43 >=16;x1+x2+x3 >= 26; x1+x2+x3 <= 31; x1>=x2; x2>=x3; @gin(x1); @gin(x2); @gin(x3); @gin(r11);@gin(r12);@gin(r13); @gin(r21);@gin(r22);@gin(r23); @gin(r31);@gin(r32);@gin(r33); @gin(r41);@gin(r42);@gin(r43); end null 经过LINGO求解，得到输出如下： Local optimal solution found. Objective value: 28.00000 Extended solver steps: 72 Total solver iterations: 3404 Model Title: 钢管下料-最小化钢管根数的LINGO模型null Variable Value Reduced Cost X1 10.00000 0.000000 X2 10.00000 0.000000 X3 8.000000 0.000000 R11 2.000000 0.000000 R12 3.000000 0.000000 R13 0.000000 0.000000 R21 1.000000 0.000000 R22 0.000000 0.000000 R23 0.000000 0.000000 R31 1.000000 0.000000 R32 1.000000 0.000000 R33 0.000000 0.000000 R41 0.000000 0.000000 R42 0.000000 0.000000 R43 2.000000 0.000000null 即按照模式1、2、3分别切割10、10、8根原料钢管，使用原料钢管总根数为28根。第一种切割模式下一根原料钢管切割成3根4米钢管和1根6米钢管；第二种切割模式下一根原料钢管切割成2根4米钢管、1根5米钢管和1根6米钢管；第三种切割模式下一根原料钢管切割成2根8米钢管。 如果充分利用LINGO建模语言的能力，使用集合和属性的概念，可以编写以下LINGO程序，这种方法更具有一般的通用性，并有利于输入更大规模的下料问题的优化模型：nullmodel: Title 钢管下料 - 最小化钢管根数的LINGO模型; SETS: NEEDS/1..4/:LENGTH,NUM; ! 定义基本集合NEEDS及其属性LENGTH,NUM; CUTS/1..3/:X; ! 定义基本集合CUTS及其属性X; PATTERNS(NEEDS,CUTS):R; ! 定义派生集合PATTERNS（这是一个稠密集合）及其属性R; ENDSETS DATA: LENGTH=4 5 6 8; NUM=50 10 20 15; CAPACITY=19; ENDDATA min=@SUM(CUTS(I): X(I) ); null!目标函数; @FOR(NEEDS(I): @SUM(CUTS(J): X(J)*R(I,J) ) >NUM(I) ); !满足需求约束; @FOR(CUTS(J): @SUM(NEEDS(I): LENGTH(I)*R(I,J) ) CAPACITY -@MIN(NEEDS(I):LENGTH(I)) ); !合理切割模式约束; @SUM(CUTS(I): X(I) ) >26; @SUM(CUTS(I): X(I) ) <31; !人为增加约束; @FOR(CUTS(I)|I#LT#@SIZE(CUTS):X(I)>X(I+1) ); !人为增加约束; @FOR(CUTS(J): @GIN(X(J)) ) ; @FOR(PATTERNS(I,J): @GIN(R(I,J)) ); end 求解这个模型，得到的结果与前面的结果完全相同。