优化模型-下料问题课件

下料问题下料问题 生产中常会遇到通过切割、剪裁、冲压等手段，将原材料加工成所需大小这种工艺过程，称为原料下料（cuttingstock）问题。按照进一步的工艺要求，确定下料方案，使用料最省，或利润最大，是典型的优化问题。本节通过两个实例讨论用数学规划模型解决这类问题的方法。§5.3.1钢管下料问题例5.3某钢管零售商从钢管厂进货，将钢管按照顾客的要求切割后售出。从钢管厂进货时得到的原料钢管都是19米长。1) 现有一客户需要50根4米长、20根6米长和15根8米长的钢管。应如何下料最节省？2) 零售商如果采用的不同切割模式太多，将会导致生产过程的复杂化，从而增加生产和管理成本，所以该零售商规定采用的不同切割模式不能超过3种。此外，该客户除需要1）中的三种钢管外，还需要10根5米长的钢管。应如何下料最节省？问题1）的求解

问题分析首先，应当确定哪些切割模式是可行的。所谓一个切割模式，是指按照客户需要在原料钢管上安排切割的一种组合。例如，我们可以将19米长的钢管切割成3根4米长的钢管，余料为7米显然，可行的切割模式是很多的。其次，应当确定哪些切割模式是合理的。通常假设一个合理的切割模式的余料不应该大于或等于客户需要的钢管的最小尺寸。在这种合理性假设下，切割模式一共有7种，如表5-3所示。表5-3钢管下料的合理切割模式4米钢管根数6米钢管根数8米钢管根数余料（米）模式14003模式23101模式32013模式41203模式51111模式60301模式70023问题化为在满足客户需要的条件下，按照哪些种合理的模式，切割多少根原料钢管，最为节省。而所谓节省，可以有两种标准，一是切割后剩余的总余料量最小，二是切割原料钢管的总根数最少。下面将对这两个目标分别讨论。模型建立

决策变量用xi表示按照第i种模式（i=1,2,…,7）切割的原料钢管的根数，显然它们应当是非负整数。

决策目标以切割后剩余的总余料量最小为目标，则由表1可得(32)以切割原料钢管的总根数最少为目标，则有

(33)下面分别在这两种目标下求解。约束条件为满足客户的需求，按照表1应有模型求解1.将（32），（34）~（36）构成的整数线性规划模型（加上整数约束）输入LINDO如下：

Title钢管下料-最小化余量Min3x1+x2+3x3+3x4+x5+x6+3x7s.t.4x1+3x2+2x3+x4+x5>=50x2+2x4+x5+3x6>=20 x3+x5+2x7>=15endgin7 求解可以得到最优解如下：OBJECTIVEFUNCTIONVALUE1)27.00000VARIABLEVALUEREDUCEDCOSTX10.0000003.000000X212.0000001.000000X30.0000003.000000X40.0000003.000000X515.0000001.000000X60.0000001.000000X70.0000003.000000

即按照模式2切割12根原料钢管，按照模式5切割15根原料钢管，共27根，总余料量为27米。显然，在总余料量最小的目标下，最优解将是使用余料尽可能小的切割模式（模式2和5的余料为1米），这会导致切割原料钢管的总根数较多。2.将（33）~（36）构成的整数线性规划模型（加上整数约束）输入LINDO：Title钢管下料-最小化钢管根数Minx1+x2+x3+x4+x5+x6+x7s.t.4x1+3x2+2x3+x4+x5>=50 x2+2x4+x5+3x6>=20 x3+x5+2x7>=15endgin7求解，可以得到最优解如下：OBJECTIVEFUNCTIONVALUE1)25.00000 VARIABLEVALUEREDUCEDCOSTX10.0000001.000000X215.0000001.000000X30.0000001.000000X40.0000001.000000X55.0000001.000000X60.0000001.000000X75.0000001.000000 即按照模式2切割15根原料钢管，按模式5切割5根，按模式7切割5根，共27根，可算出总余料量为35米。与上面得到的结果相比，总余料量增加了8米，但是所用的原料钢管的总根数减少了2根。在余料没有什么用途的情况下，通常选择总根数最少为目标。问题2）的求解 问题分析按照解问题1）的思路，可以通过枚举法首先确定哪些切割模式是可行的。但由于需求的钢管规格增加到4种，所以枚举法的工作量较大。下面介绍的整数非线性规划模型，可以同时确定切割模式和切割计划，是带有普遍性的方法。 同1）类似，一个合理的切割模式的余料不应该大于或等于客户需要的钢管的最小尺寸（本题中为4米），切割计划中只使用合理的切割模式，而由于本题中参数都是整数，所以合理的切割模式的余量不能大于3米。此外，这里我们仅选择总根数最少为目标进行求解。模型建立决策变量由于不同切割模式不能超过3种，可以用xi表示按照第i种模式（i=1,2,3）切割的原料钢管的根数，显然它们应当是非负整数。设所使用的第i种切割模式下每根原料钢管生产4米长、5米长、6米长和8米长的钢管数量分别为r1i,r2i,r3i,r4i（非负整数）。

决策目标以切割原料钢管的总根数最少为目标，即目标为（37）约束条件为满足客户的需求，应有(38)(39)(40)(41) 每一种切割模式必须可行、合理，所以每根原料钢管的成品量不能超过19米，也不能少于16米（余量不能大于3米），于是(42)(43)(44)模型求解 （37）~（44）构成这个问题的优化模型。由于在（38）~（41）式中出现了决策变量的乘积，所以这是一个整数非线性规划模型，虽然用LINGO软件可以直接求解，但我们发现在较低版本的LINGO软件中需要运行很长时间也难以得到最优解。为了减少运行时间，可以增加一些显然的约束条件，从而缩小可行解的搜索范围。例如，由于3种切割模式的排列顺序是无关紧要的，所以不妨增加以下约束：（45）又例如，我们注意到所需原料钢管的总根数有着明显的上界和下界。首先，无论如何，原料钢管的总根数不可能少于

（根）其次，考虑一种非常特殊的生产计划：第一种切割模式下只生产4米钢管，一根原料钢管切割成4根4米钢管，为满足50根4米钢管的需求，需要13根原料钢管；第二种切割模式下只生产5米、6米钢管，一根原料钢管切割成1根5米钢管和2根6米钢管，为满足10根5米和20根6米钢管的需求，需要10根原料钢管；第三种切割模式下只生产8米钢管，一根原料钢管切割成2根8米钢管，为满足15根8米钢管的需求，需要8根原料钢管。于是满足要求的这种生产计划共需13+10+8=31根原料钢管，这就得到了最优解的一个上界。所以可增加以下约束：(46)将（37）~（46）构成的模型输入LINGO如下：将（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

经过LINGO求解，得到输出如下：Localoptimalsolutionfound.Objectivevalue:28.00000Extendedsolversteps:72Totalsolveriterations:3404ModelTitle:钢管下料-最小化钢管根数的LINGO模型

VariableValueReducedCostX110.000001.000000X210.000001.000000X38.0000001.000000R112.0000000.000000R123.0000000.000000R130.0000000.000000R211.0000000.000000R220.0000000.000000R230.0000000.000000R311.0000000.000000R321.0000000.000000R330.0000000.000000R410.0000000.000000R420.0000000.000000R432.0000000.000000 即按照模式1、2、3分别切割10、10、8根原料钢管，使用原料钢管总根数为28根。第一种切割模式下一根原料钢管切割成3根4米钢管和1根6米钢管；第二种切割模式下一根原料钢管切割成2根4米钢管、1根5米钢管和1根6米钢管；第三种切割模式下一根原料钢管切割成2根8米钢管。如果充分利用LINGO建模语言的能力，使用集合和属性的概念，可以编写以下LINGO程序，这种方法更具有一般的通用性，并有利于输入更大规模的下料问题的优化模型：model:Title钢管下料-最小化钢管根数的LINGO模型;SETS:NEEDS/1..4/:LENGTH,NUM; !定义基本集合NEEDS及其属性LENGTH,NUM;CUTS/1..3/:X; !定义基本集合CUTS及其属性X;PATTERNS(NEEDS,CUTS):R;!定义派生集合PATTERNS（这是一个稠密集合）及其属性R;ENDSETSDATA: LENGTH=4568; NUM=50102015; CAPACITY=19;ENDDATAmin=SUM(CUTS(I):X(I)); !目标函数;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);!合理切割模式约束;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

求解这个模型，得到的结果与前面的结果完全相同。§5.3.2易拉罐下料问题 例5.4某公司采用一套冲压设备生产一种罐装饮料的易拉罐，这种易拉罐是用镀锡板冲压制成的（参见图5-3）。易拉罐为圆柱形，包括罐身、上盖和下底，罐身高10厘米，上盖和下底的直径均为5厘米。该公司使用两种不同规格的镀锡板原料，规格1的镀锡板为正方形，边长24厘米；规格2的镀锡板为长方形，长、宽分别为32和28厘米。由于生产设备和生产工艺的限制，对于规格1的镀镀锡板原料，只可以按照图2中的模式1、2或3进行冲压；对于规格2的镀锡板原料只能按照模式4进行冲压。使用模式1、2、3、4进行每次冲压所需要的时间分别为1.5、2、1、3（秒）。模式1模式2模式3模式4上盖下底罐身图5-3易拉罐下料模式 该工厂每周工作40小时，每周可供使用的规格1、2的镀锡板原料分别为5万张和2万张。目前每只易拉罐的利润为0.10元，原料余料损失为0.001元/厘米2（如果周末有罐身、上盖或下底不能配套组装成易拉罐出售，也看作是原料余料损失）。工厂应如何安排每周的生产？已知上盖和下底的直径d=5厘米，可得其面积为

19.6厘米2表5-44种冲压模式的特征罐身个数底、盖个数余料损失（厘米2）冲压时间（秒）模式1110222.61.5模式224183.32模式3016261.81模式445169.53问题的目标显然应是易拉罐的利润扣除原料余料损失后的净利润最大，约束条件除每周工作时间和原料数量外，还要考虑罐身和底、盖的配套组装。模型建立 决策变量用xi表示按照第i种模式的冲压次数（i=1,2,3,4），y1表示一周生产的易拉罐个数。为计算不能配套组装的罐身和底、盖造成的原料损失，用y2表示不配套的罐身个数，y3表示不配套的底、盖个数。虽然实际上xi和y1，y2，y3应该是整数。但是由于生产量相当大，可以把它们看成是实数，从而用线性规划模型处理。 决策目标假设每周生产的易拉罐能够全部售出，公司每周的销售利润是0.1y1。原料余料损失包括两部分：4种冲压模式下的余料损失，和不配套的罐身和底、盖造成的原料损失。按照前面的计算及表2的结果，总损失为0.001(222.6x1+183.3x2+261.8x3+169.5x4+157.1y2+19.6y3)。于是，决策目标为(47)约束条件时间约束：每周工作时间不超过40小时=144000（秒），由表2最后一列得(48)原料约束：每周可供使用的规格1、2的镀锡板原料分别为50000张和20000张，即(49)(50)

配套约束：由表2一周生产的罐身个数为x1+2x2+4x4,一周生产的底、盖个数为10x1+4x2+16x3+5x4，因为应尽可能将它们配套组装成易拉罐销售。所以y1满足

(51)这时不配套的罐身个数y2，和不配套的底、盖个数y3应为

(52)

(53)（47）~（53）就是我们得到的模型，其中（51）是一个非线性关系，不易直接处理，但是它可以等价为以下两个线性不等式：

(54)

(55)模型求解 将模型（47）~（50）和（52）~（55）直接输入LINDO（输入LINGO也可以），求解时LINDO发出警告信息（程序和警告信息参见图5-4）。图中错误编号“66”的含义（参见第4章的错误代码表）是：模型中数据不平衡，所以发出警告信息（注意，只是警告信息，所以仍然可以继续求解）。求解结果是： OBJECTIVEFUNCTIONVALUE1)4298.337VARIABLEVALUEREDUCEDCOSTY1160250.0000000.000000X10.0000000.000050X240125.0000000.000000X33750.0000000.000000X420000.0000000.000000Y20.0000000.223331Y30.0000000.036484图5-4模型中数据不平衡的警告信息 这个结果可靠吗？由于LINDO警告模型中数据之间的数量级差别太大，所以我们可以进行预处理，缩小数据之间的差别。实际上，约束（48）~（50）中右端项的数值过大（与左端的系数相比较），LINDO在计算中容易产生比较大的误差，所以出现此警告信息。 为了解决这一问题，可以将所有决策变量扩大10000倍（相当