Setup=4005001000300200400100: Ho1d-120.61.00.040.030.040.04; A=0580000: ENDDATA CALC: demand(1,1)=40:demand(1,3)=100: demand(1,5)=90;demand(1,6)=10; xeg(2,1)-5:reg(3,1)-7:reg(4,2)-9i eq(5,2)11 (6,3=13月 eq(7,3)=15: END 计算结果见表2（贝列出了生产产量X,空格表示不生产，即产量为0）。 表2生产计划的最后结果 周次 2 4 6 A的产量 40 100 100 B的产量 200 1000 C的产量 0s5 625 D的产量 1800 9000 E的产量 2200 11000 F的产量13715 8125 G的产量15825 9375 §2下料问题 生产中常会遇到通过切割、剪裁、冲压等手段，将原材料加工成所需大小这种工 艺过程，称为原料下料(cutting stock)间题。按照进一步的工艺要求，确定料方案 使用料最省或利润最大，是典型的优化问题。本节通过两个实例讨论用数学规划模型 决这类问题的方法 2.1钢管下料问题 例2某钢管零售商从钢管厂进货，将钢管按照顾客的要求切割后售出。从钢管厂 进货时得到的原料钢管都是19m长。 (1)现有 -客户需要50根4m长，20根6m长和15根8m长的钢管。应如何下 (2)零售商如果采用的不同切制割模式太多，将会导致生产过程的复杂化，从而增 加生产和管理成本，所以该零售商规定采用的不同切割模式不能超过3种。此外，该客 户除需要(1)中的三种钢管外，还需要10根5m长的钢管。应如何下料最节省？ 2.1.1问题(1)的求解 首先，应当确定哪些切割模式是可行的。所谓一个切割模式，是指按照客户需要
-391- Setup=400 500 1000 300 200 400 100; Hold=12 0.6 1.0 0.04 0.03 0.04 0.04; A=0 5 8 0 0 0 0; ENDDATA CALC: demand(1,1)=40;demand(1,3)=100; demand(1,5)=90;demand(1,6)=10; req(2,1)=5;req(3,1)=7;req(4,2)=9; req(5,2)=11;req(6,3)=13;req(7,3)=15; ENDCALC END 计算结果见表 2（只列出了生产产量 Xi,t ，空格表示不生产，即产量为 0）。 表 2 生产计划的最后结果 周次 1 2 3 4 5 6 A 的产量 40 100 100 B 的产量 200 1000 C 的产量 1055 625 D 的产量 1800 9000 E 的产量 2200 11000 F 的产量 13715 8125 G 的产量 15825 9375 §2 下料问题 生产中常会遇到通过切割、剪裁、冲压等手段，将原材料加工成所需大小这种工 艺过程，称为原料下料（cutting stock）问题。按照进一步的工艺要求，确定下料方案， 使用料最省或利润最大，是典型的优化问题。本节通过两个实例讨论用数学规划模型解 决这类问题的方法。 2.1 钢管下料问题 例 2 某钢管零售商从钢管厂进货，将钢管按照顾客的要求切割后售出。从钢管厂 进货时得到的原料钢管都是 19m 长。 （1）现有一客户需要 50 根 4m 长，20 根 6m 长和 15 根 8m 长的钢管。应如何下 料最节省？ （2）零售商如果采用的不同切割模式太多，将会导致生产过程的复杂化，从而增 加生产和管理成本，所以该零售商规定采用的不同切割模式不能超过 3 种。此外，该客 户除需要（1）中的三种钢管外，还需要 10 根 5m 长的钢管。应如何下料最节省？ 2.1.1 问题（1）的求解 （1）问题分析 首先，应当确定哪些切割模式是可行的。所谓一个切割模式，是指按照客户需要
在原料钢管上安排切割的一种组合。例如，我们可以将19m长的钢管切割成3根4m 长的钢管，余料为7m:或者将19m长的钢管切割成4m,6m和8m长的钢管各1根， 余料为lm。显然，可行的切制模式是很多的。 其次，应当确定哪些切割模式是合理的。通常假设一个合理的切割模式的余料不 应该大于或等于客户需要的管的最小尺寸。例如，将19m长的钢管切割成3根4m 的钢管是可行的，但余料为7m,可以进一步将7m的余料切制成4m钢管（余料为3m), 或者将7m的余料切割成6m钢管（余料为1m)。在这种合理性假设下，切割模式一共 有7种，如表3所示。 表3钢管下料的合理切制模式 4m钢管根数 6m钢管根数 8m钢管根数 余料(m) 模式1 0 0 3 模式2 0 模式S 模式6 3 模式7 0 0 3 问题化为在满足客户需要的条件下，按照哪些种合理的模式，切制多少根原料钢 管，最为节省。而所谓节省，可以有两种标准，一是切割后剩余的总余料量最小，二是 切割原料钢管的总根数最少。下面将对这两个目标分别讨论。 (2)模型建立 决策变量：用x,表示按照第i种模式(i=1,2,.,7)切制的原料钢管的根数，显 然它们应当是非负整数。 决策目标：以切割后剩余的总余料量最小为目标，则由表3可得 min=3x1+x2+3x3+3x4+x+x6+3x 6 以切制原料钢管的总根数最少为目标，则有 min=∑x 下面分别在这两种目标下求解。 约束条件：为满足客户的需求，按照表3应用 4x+3x2+2x3+x+x5250 (8) X2+x1+x3+3x5220 (9) 392
-392- 在原料钢管上安排切割的一种组合。例如，我们可以将 19m 长的钢管切割成 3 根 4m 长的钢管，余料为 7m；或者将 19m 长的钢管切割成 4m，6m 和 8m 长的钢管各 1 根， 余料为 1m。显然，可行的切割模式是很多的。 其次，应当确定哪些切割模式是合理的。通常假设一个合理的切割模式的余料不 应该大于或等于客户需要的钢管的最小尺寸。例如，将 19m 长的钢管切割成 3 根 4m 的钢管是可行的，但余料为 7m，可以进一步将 7m 的余料切割成 4m 钢管（余料为 3m）， 或者将 7m 的余料切割成 6m 钢管（余料为 1m）。在这种合理性假设下，切割模式一共 有 7 种，如表 3 所示。 表 3 钢管下料的合理切割模式 4m 钢管根数 6m 钢管根数 8m 钢管根数 余料（m） 模式 1 4 0 0 3 模式 2 3 1 0 1 模式 3 2 0 1 3 模式 4 1 2 0 3 模式 5 1 1 1 1 模式 6 0 3 0 1 模式 7 0 0 2 3 问题化为在满足客户需要的条件下，按照哪些种合理的模式，切割多少根原料钢 管，最为节省。而所谓节省，可以有两种标准，一是切割后剩余的总余料量最小，二是 切割原料钢管的总根数最少。下面将对这两个目标分别讨论。 （2）模型建立 决策变量：用 i x 表示按照第i 种模式（i = 1,2,L,7 ）切割的原料钢管的根数，显 然它们应当是非负整数。 决策目标：以切割后剩余的总余料量最小为目标，则由表 3 可得 min 1 3 1 2 3 3 3 4 5 6 3 7 z = x + x + x + x + x + x + x （6） 以切割原料钢管的总根数最少为目标，则有 ∑= = 7 1 min 2 i i z x （7） 下面分别在这两种目标下求解。 约束条件：为满足客户的需求，按照表 3 应用 4x1 + 3x2 + 2x3 + x4 + x5 ≥ 50 （8） x2 + x4 + x5 + 3x6 ≥ 20 （9）
x3+x+2x7≥15 (10) (3)横形求解 将式(6)、(8) ~(9)构成的整数线性规划模型（加上整数约束）输入LNGO model TITLE钢管下料一最小化余量： sets: co1/1.7/:c,x: xow/1.3/:b link(row,col):a; endsets data: c=3133113: b-502015 a=432】 100 0102130 0010102: enddata min=@sum (col:c*x); @for(row():0su (co1(j):a(i,)*x()>=b(i) efor(col:@gin(x)); end 求得按照模式2切割12根原料钢管，按照模式5切割15根原料钢管，共27根， 总余料量为27m。但4m长的钢管比要求多切到了1根.6m长的都管比要求多切割了 7根。显然，在总余料量最小的目标下，最优解将是使用余料尽可能小的切制方式（模 式2和模式5的余料为1m,这会号致切制原料解管的总根数较多， i)将式(7)~(10)构成的整数线性规划模型输入LNGO model: TT工E钢管下料一最小银管数： sets: co1/171:e0,e,x row/1.3/:bi link(row,col):a; endsets data: c0=3133113 c=1111111: b=502015: a=4321100 -393
-393- x3 + x5 + 2x7 ≥15 （10） （3）模型求解 i）将式（6）、（8）～（9）构成的整数线性规划模型（加上整数约束）输入 LINGO model: TITLE 钢管下料－最小化余量; sets: col/1.7/:c,x; row/1.3/:b; link(row,col):a; endsets data: c=3 1 3 3 1 1 3; b=50 20 15; a=4 3 2 1 1 0 0 0 1 0 2 1 3 0 0 0 1 0 1 0 2; enddata min=@sum(col:c*x); @for(row(i):@sum(col(j):a(i,j)*x(j))>=b(i)); @for(col:@gin(x)); end 求得按照模式 2 切割 12 根原料钢管，按照模式 5 切割 15 根原料钢管，共 27 根， 总余料量为 27m。但 4m 长的钢管比要求多切割了 1 根，6m 长的钢管比要求多切割了 7 根。显然，在总余料量最小的目标下，最优解将是使用余料尽可能小的切割方式（模 式 2 和模式 5 的余料为 1m），这会导致切割原料钢管的总根数较多。 ii）将式（7）～（10）构成的整数线性规划模型输入 LINGO model: TITLE 钢管下料－最小钢管数; sets: col/1.7/:c0,c,x; row/1.3/:b; link(row,col):a; endsets data: c0=3 1 3 3 1 1 3; c=1 1 1 1 1 1 1; b=50 20 15; a=4 3 2 1 1 0 0
0102130 0010102: enddata min=@sum(col:c*x); @for(row(i):[conlJ@sum(col(j):a(i,j)*x(j))>=b(i)) efor(co1:@gin(x)）: [remainder]y=0sum(col:c0*x); end 求得按照模式2切制15根原料钢管，按模式5切割5根，按模式7切制5根，共 25根，可算出总余料量为35m。但各长度的钢管数恰好全部满足要求， 没有多切割 与上面得到的结果比较，总余料量增加了8m,但是所用的原料钢管的总根数减少了2 根。在余料没有什么用途的情祝下，通常选择总根数最少为目标。 2.12问题(2)的求解 (1)问题分析 按照问恩()的思路。 可以通过枚举法首先确定哪些切制模式是可行的 。但击 需要的钢管规格增加到4种，所以枚举法的工作量较大。下面介绍的整数非线性规划模 型，可以同时确定切割模式和切割计划，是带有普遍性的方法。 同问题(1)类似，一个合理的切割模式的余料不应该大于或等于客户需要的银管 的最小尺寸（本题中为4m),切判计划中只使用合理的切刺模式，而由于本颗中参数都 是整数，所以合理的切割模式的余量不能大于3m。此外，这里我们仅选择总根数最少 为目标进行求解 (2)模型建立 决策变量：由于不同切割模式不能超过3种，可以用x,表示按照第种模式 (j=1,2,3)切割的原料钢管的根数，显然它们应当是非负整数。设所使用的第j种 切割模式下每根原料钢管生产4m长，5m长，6m长和8m长的钢管数量分别为 万，5,51，（非负整数).记客户需求的4种钢管的长度为，数量为b(1=1,2,3,4). 决策目标：以切割原料钢管的总根数最少为目标，即目标为 min立x (11) 约束条件：为满足客户的需求，应有 2x,26,i=l234 (12) 每一种切制模式必须可行、合理，所以每根原料钢管的成品量不能超过19，也 不能少于16m(余量不能大于3m),于是 394
-394- 0 1 0 2 1 3 0 0 0 1 0 1 0 2; enddata min=@sum(col:c*x); @for(row(i):[con1]@sum(col(j):a(i,j)*x(j))>=b(i)); @for(col:@gin(x)); [remainder]y=@sum(col:c0*x); end 求得按照模式 2 切割 15 根原料钢管，按模式 5 切割 5 根，按模式 7 切割 5 根，共 25 根，可算出总余料量为 35m。但各长度的钢管数恰好全部满足要求，没有多切割。 与上面得到的结果比较，总余料量增加了 8m，但是所用的原料钢管的总根数减少了 2 根。在余料没有什么用途的情况下，通常选择总根数最少为目标。 2.1.2 问题（2）的求解 （1）问题分析 按照问题（1）的思路，可以通过枚举法首先确定哪些切割模式是可行的。但由于 需要的钢管规格增加到 4 种，所以枚举法的工作量较大。下面介绍的整数非线性规划模 型，可以同时确定切割模式和切割计划，是带有普遍性的方法。 同问题（1）类似，一个合理的切割模式的余料不应该大于或等于客户需要的钢管 的最小尺寸（本题中为 4m），切割计划中只使用合理的切割模式，而由于本题中参数都 是整数，所以合理的切割模式的余量不能大于 3m。此外，这里我们仅选择总根数最少 为目标进行求解。 （2）模型建立 决策变量：由于不同切割模式不能超过 3 种，可以用 j x 表示按照第 j 种模式 （ j =1,2,3）切割的原料钢管的根数，显然它们应当是非负整数。设所使用的第 j 种 切割模式下每根原料钢管生产 4m 长，5m 长，6m 长和 8m 长的钢管数量分别为 j j j j r r r r 1 2 3 4 , , , （非负整数）。记客户需求的 4 种钢管的长度为 i l ，数量为b（i i =1,2,3,4 ）。 决策目标：以切割原料钢管的总根数最少为目标，即目标为 ∑= 3 1 min j j x （11） 约束条件：为满足客户的需求，应有 j i j ∑rij x ≥ b = 3 1 ，i = 1,2,3,4 （12） 每一种切割模式必须可行、合理，所以每根原料钢管的成品量不能超过 19m，也 不能少于 16m（余量不能大于 3m），于是
16s214,519,j=12,3 (13) (3)模型求解 式(11)~(13)构成这个问题的优化模型。由于在式(11)~(13)中出现了决 策变量的乘积，所以这是一个整数非线性规划模型，虽然用LNGO软件可以直接求解， 但我们发现有时LNGO软件运行很长时间也难以得到最优解。为了减少运行时间，可 以增加一些显然的约束条件，从而缩小可行解的搜索范围。 例如，由于3种切制模型的排列顺序是无关紧要的，所以不妨增加以下约束 X1≥X32x3 (14) 又如，我们注意到所需原料钢管的总根数有者明显的上界和下界。首先，无论如何，原 料钢管的总根数不可能少于[(4×50+5×10+6×20+8×15)/19]=26（根）。其次， 考虑一种非常特殊的生产计划：第一种切割模式下只生 4m钢管，1根原料钢管切制 成4根4m钢管，为满足50根4m钢管的需求，需要13根原料钢管：第二种切制模式 下只生产5m、6m钢管，一根原料钢管切割成1根5m钢管和2根6m钢管，为满足10 根5m钢管和20根6m钢管的需求，需要10根原料钢管：第三种切割模式下只生产8m 钢管，1根原料钢管切制成2根8m钢管，为满足15根8m钢管的需求，需要8根原料 钢管。 于是满 足要求的这种生 计划 需13+10+8=31根原料钢管 这就得到了最 优解的一个上界。所以可增加以下约束： 26≤2≤31 (15) 将式(I)一(I5)构成的模型输入LING0如下： mode l Tite钢管下料·最小化钢管根数的LINGO模型： SETS: NEEDS/1.4/:LENGTH,b; CUTS/1.3/:X; ENDSETS DATA: LENGTH=4 5 6 8: b=50102015: CAPACITY-19: ENDDATA min=@SUM(CUTS (I)X(I)) @FOR(NEEDS (I):@SUM(CUTS (J):x(J)*R(I,J))>b(I)) -395
-395- 16 19 4 1 ≤ ∑ ≤ i= i ij l r ， j = 1,2,3 （13） （3）模型求解 式（11）～（13）构成这个问题的优化模型。由于在式（11）～（13）中出现了决 策变量的乘积，所以这是一个整数非线性规划模型，虽然用 LINGO 软件可以直接求解， 但我们发现有时 LINGO 软件运行很长时间也难以得到最优解。为了减少运行时间，可 以增加一些显然的约束条件，从而缩小可行解的搜索范围。 例如，由于 3 种切割模型的排列顺序是无关紧要的，所以不妨增加以下约束： 1 2 3 x ≥ x ≥ x （14） 又如，我们注意到所需原料钢管的总根数有着明显的上界和下界。首先，无论如何，原 料钢管的总根数不可能少于[(4×50 + 5×10 + 6× 20 + 8×15)/19] = 26 （根）。其次， 考虑一种非常特殊的生产计划：第一种切割模式下只生产 4m 钢管，1 根原料钢管切割 成 4 根 4m 钢管，为满足 50 根 4m 钢管的需求，需要 13 根原料钢管；第二种切割模式 下只生产 5m、6m 钢管，一根原料钢管切割成 1 根 5m 钢管和 2 根 6m 钢管，为满足 10 根 5m 钢管和 20 根 6m 钢管的需求，需要 10 根原料钢管；第三种切割模式下只生产 8m 钢管，1 根原料钢管切割成 2 根 8m 钢管，为满足 15 根 8m 钢管的需求，需要 8 根原料 钢管。于是满足要求的这种生产计划共需13 +10 + 8 = 31根原料钢管，这就得到了最 优解的一个上界。所以可增加以下约束： 26 31 3 1 ≤ ∑ ≤ i= i x （15） 将式（11）～（15）构成的模型输入 LINGO 如下： model: Title 钢管下料 - 最小化钢管根数的LINGO模型; SETS: NEEDS/1.4/:LENGTH,b; CUTS/1.3/:X; PATTERNS(NEEDS,CUTS):R; ENDSETS DATA: LENGTH=4 5 6 8; b=50 10 20 15; CAPACITY=19; ENDDATA min=@SUM(CUTS(I): X(I) ); @FOR(NEEDS(I):@SUM(CUTS(J):X(J)*R(I,J))>b(I) );