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; 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(只列出了生产产量X,,空格表示不生产,即产量为0) 表2生产计划的最后结果 周次 A的产量 100 B的产量 1000 C的产量1055 D的产量 9000 E的产量 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)问题分析 首先,应当确定哪些切割模式是可行的。所谓一个切割模式,是指按照客户需要 391
-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根 余料为1m。显然,可行的切割模式是很多的 其次,应当确定哪些切割模式是合理的。通常假设一个合理的切割模式的余料不 应该大于或等于客户需要的钢管的最小尺寸。例如,将19m长的钢管切割成3根4m 的钢管是可行的,但余料为7m,可以进一步将7m的余料切割成4m钢管(余料为3m) 或者将7m的余料切割成6m钢管(余料为1m)。在这种合理性假设下,切割模式一共 有7种,如表3所示。 表3钢管下料的合理切割模式 4m钢管根数 6m钢管根数 8m钢管根数 余料(m) 模式2 模式3 0102 3133 模式4 模式5 模式6 0 模式7 2 问题化为在满足客户需要的条件下,按照哪些种合理的模式,切割多少根原料钢 管,最为节省。而所谓节省,可以有两种标准,一是切割后剩余的总余料量最小,二是 切割原料钢管的总根数最少。下面将对这两个目标分别讨论 (2)模型建立 决策变量:用x表示按照第i种模式(=1,2,…,7)切割的原料钢管的根数,显 然它们应当是非负整数。 决策目标:以切割后剩余的总余料量最小为目标,则由表3可得 min1=3x1+x2+3x3+3x4+x5+x6+3x7 (6) 以切割原料钢管的总根数最少为目标,则有 下面分别在这两种目标下求解 约束条件:为满足客户的需求,按照表3应用 x1+3x2+2x3+x4+x5 x2+x4+x5+3x6≥ (9)
-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）
x2+x4+2x≥15 (10) (3)模型求解 i)将式(6)、(8)~(9)构成的整数线性规划模型(加上整数约束)输入LⅠNG nodel TITLE钢管下料一最小化余量 w/1..3/:b link(row, col) endsets data 3133113 b=502015 a=4321100 0102130 0010102 enddata min=@sum(col: c*x)i @for (row(i): @sum(col(3):a(i,3)*x(3))>=b(1))i @for(col: @gin(x)) 求得按照模式2切割12根原料钢管,按照模式5切割15根原料钢管,共27根, 总余料量为27m。但4m长的钢管比要求多切割了1根,6m长的钢管比要求多切割了 7根。显然,在总余料量最小的目标下,最优解将是使用余料尽可能小的切割方式(模 式2和模式5的余料为lm),这会导致切割原料钢管的总根数较多。 i)将式(7)~(10)构成的整数线性规划模型输入LING model TITLE钢管下料一最小钢管数; co1/1..7/:c0,C,x; row/1..3/:b link(row, col): a endsets data c0=3133113; C=1111111 b=502015 a=4321100
-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 @for(row(i): [conl]esum(col(j):a(1,3)*x(3))>=b(i)); @for (col: egin(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种,可以用x,表示按照第j种模式 (j=1,2,3)切割的原料钢管的根数,显然它们应当是非负整数。设所使用的第j种 切割模式下每根原料钢管生产4m长,5m长,6m长和8m长的钢管数量分别为 F,y,3y4,(非负整数)。记客户需求的4种钢管的长度为1,数量为b(i=1,2,34)。 决策目标:以切割原料钢管的总根数最少为目标,即目标为 mn∑x (11) 约束条件:为满足客户的需求,应有 ∑冖x≥b,i= 每一种切割模式必须可行、合理,所以每根原料钢管的成品量不能超过19m,也 不能少于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），于是
j=1,2,3 (3)模型求解 式(11)~(13)构成这个问题的优化模型。由于在式(11)~(13)中出现了决 策变量的乘积,所以这是一个整数非线性规划模型,虽然用 LINGO软件可以直接求解, 但我们发现有时 LINGO软件运行很长时间也难以得到最优解。为了减少运行时间,可 以增加一些显然的约束条件,从而缩小可行解的搜索范围 例如,由于3种切割模型的排列顺序是无关紧要的,所以不妨增加以下约束: (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根原料钢管;第三种切割模式下只生产8 钢管,1根原料钢管切割成2根8m钢管,为满足15根8m钢管的需求,需要8根原料 钢管。于是满足要求的这种生产计划共需13+10+8=31根原料钢管,这就得到了最 优解的一个上界。所以可增加以下约束: 26 x≤31 (15) 将式(11)~(15)构成的模型输入 LINGO如下 model Title钢管下料-最小化钢管根数的 LINGO模型; NEEDS/1. 4/: LENGTH, b; PATTERNS(NEEDS, CUTS): R ENDSETS LENGTH=4 5 8: b=50102015 CAPACITY=19 ENDDATA min=@SUM (CUTS (I): x(I)) @FOR(NEEDS(I): eSUM (CUTS(J): x(J)*R(I,J))>b(I))i
-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) );